DASE 7113 · 课程精讲

约束最优条件

共 33 页。按原课件顺序,左侧看原页,右侧读讲解。

逐页目录 · 共 33 页
  1. 有了限制以后,怎样判断一个点已经最好
  2. 先回顾:无约束凸函数让梯度等于零
  3. 把所有不等式写成gi(x)≤0
  4. 互补松弛:有余量的约束,其乘子为零
  5. KKT四组条件:可行、非负、互补、驻点
  6. KKT什么时候能用来确定最优解
  7. 所有约束都松时,KKT退回梯度为零
  8. 例题一:最小化x²,约束x≥−1
  9. 例题二:约束改为x≥1,最优点被挡在边界
  10. 二维例题:先把每个梯度都写出来
  11. 解出(0.5,0.5),并用等值线理解
  12. 把x1下界提高到0.8,重列KKT
  13. 解出(0.8,0.2):两条边界同时起作用
  14. 两物块三弹簧:用能量代替逐种受力分类
  15. 势能与几何约束逐项从图里读出来
  16. 给三处可能的接触分别配一个乘子
  17. 乘子就是接触力,互补就是“有间隙便没有力”
  18. 等式约束拆成两条方向相反的不等式
  19. 先按两条不等式机械列出KKT
  20. 两个非负数之差,可以表示任意实数
  21. 等式约束的简洁条件:驻点与可行
  22. 等式之外,再加每个变量都非负
  23. 标准基向量ej为什么出现在驻点式里
  24. 把一长串乘子整理成一个向量
  25. 消去μ,得到最常用的紧凑形式
  26. 等式乘子换个符号,条件仍然等价
  27. 交通分流:每条路的时间取决于自己的流量
  28. A路2、B路3:为什么这个分配不稳定
  29. 两条都有人走时,均衡成本应相同
  30. 没人走的路可以更贵,仍然是均衡
  31. 把均衡规则压缩成两句话
  32. 用一个最低成本λ写出互补条件
  33. 对成本积分,构造恰好产生均衡条件的目标
原第 1 页

有了限制以后,怎样判断一个点已经最好

原课件第1页
点击原页可打开 PDF。

无约束时,可以向任意方向移动;有约束时,有些能让目标下降的方向已经被挡住。因此最优点可能还带着非零梯度。

这一讲要学会用KKT条件检查最优点。先从一维和二维例子认识四组条件,再用弹簧接触理解它们,最后把等式约束、非负变量和交通均衡接起来。

学习顺序是:先把约束写成统一形式,算梯度,列KKT,按互补松弛分情况,最后检查全部条件。

原第 2 页

先回顾:无约束凸函数让梯度等于零

原课件第2页
点击原页可打开 PDF。

对可微凸函数 f:Rn→R,无约束最小化的条件是:

x* 是最优点⟺∇f(x*)=0.

x* 的星号表示待求的最优点。梯度 ∇f 是所有一阶偏导组成的向量;等于0表示每个方向的一阶变化都为0。凸性进一步保证这个驻点是全局最小点。

例如 f(x)=x2,令 f′(x)=2x=0,得到 x*=0。但若增加 x≥1,0已经不可行,最优点变成1,而 f′(1)=2≠0。这说明约束问题需要新的条件。

对应课堂录音Week08 Part01 01:29:38–01:34:55
原第 3 页

把所有不等式写成gi(x)≤0

原课件第3页
点击原页可打开 PDF。

本节研究的标准形式是:

minxf(x),gi(x)≤0(i=1,…,m),

其中 f 和每个 gi 都是可微凸函数。m 是不等式条数,n 是决策变量个数,它们不一定相同。

例如 x≥1 应移项写成 1−x≤0,所以约束函数是 g(x)=1−x,导数是−1。不要只看原不等号就套公式,先统一成“某个函数≤0”,后面的乘子符号才能保持一致。

KKT是Karush–Kuhn–Tucker的缩写。它给每条不等式配一个乘子,再用这些乘子把目标梯度与约束梯度联系起来。

对应课堂录音Week08 Part01 01:29:38–01:34:55
原第 4 页

互补松弛:有余量的约束,其乘子为零

原课件第4页
点击原页可打开 PDF。

每条约束 gi(x)≤0 配一个乘子 λi≥0,并要求:

gi(x*)≤0,λi≥0,λigi(x*)=0.

最后一条叫互补松弛。两个数的乘积为0,至少有一个因子为0:

  1. 若 gi(x*)<0,约束还有余量,那么只能是 λi=0。
  2. 若 λi>0,就必须 gi(x*)=0,约束恰好卡在边界。
  3. 也允许两者同时为0。因此“约束取等号”不一定意味着乘子严格大于0。

例如 g(x)=1−x。在 x=2 时,g=−1,所以乘子只能取0。在 x=1 时,g=0,任意非负乘子都使乘积为0,实际取值还要由驻点式决定。

自测:边界取等号时,乘子能等于0吗?

考虑 minx2,约束 x≥0。最优点 x=0 就在边界。取 g(x)=−x,驻点式为 2x−λ=0,所以 λ=0。可行性和互补松弛也都成立。

对应课堂录音Week08 Part01 01:34:55–01:40:08
原第 5 页

KKT四组条件:可行、非负、互补、驻点

原课件第5页
点击原页可打开 PDF。

把前面的条件与梯度条件合起来:

gi(x*)≤0原始可行性,(1)λi≥0对偶可行性,(2)λigi(x*)=0互补松弛,(3)∇f(x*)+∑i=1mλi∇gi(x*)=0驻点条件.(4)

前三组对每个 i 分别成立,最后一组是向量等式,也就是n条分量方程。要找到同一个x和同一组乘子,同时满足它们。

把 L(x,λ)=f(x)+∑iλigi(x) 称为拉格朗日函数,驻点式就是 ∇xL=0。这里求导只对x进行,乘子先当作常数。

几何上,驻点式表示 −∇f 可以写成边界约束梯度的非负加权和。−∇f 指向目标降得最快的方向,边界约束的梯度指向各自约束值增大的方向。第11和13页会用等值线展示两者如何相抵。

对应课堂录音Week08 Part01 01:34:55–01:40:08
原第 6 页

KKT什么时候能用来确定最优解

原课件第6页
点击原页可打开 PDF。

对这里的可微凸问题,找到满足KKT的 (x*,λ),就能确定 x* 是全局最优点。反过来,从最优点推出一定存在乘子,还需要约束资格条件;常见的Slater条件是存在一点让所有凸不等式严格成立。

先理解为什么KKT能证明最优。固定这组 λ≥0,拉格朗日函数 L(x,λ)=f(x)+∑iλigi(x) 是凸的。驻点条件给出 ∇xL(x*,λ)=0,所以x*让L达到最小。

对任意可行x,由 gi(x)≤0 与 λi≥0,有 L(x,λ)≤f(x)。而互补松弛让 L(x*,λ)=f(x*)。连起来:

f(x)≥L(x,λ)≥L(x*,λ)=f(x*).

因此所有可行x的目标都不会比x*小。做本讲例题时,列完条件还必须检查可行性和乘子非负,单独解出驻点方程不够。

为什么从最优点反推乘子,要检查约束资格?

最小化 f(x)=x,约束 g(x)=x2≤0。唯一可行点就是0,所以它必然最优。但在0处 f′(0)=1、g′(0)=0,驻点式变成 1+λ·0=0,任何乘子都无法满足。这个约束没有严格可行点,恰好说明为什么课件在“当且仅当”前注明了附加条件。

对应课堂录音Week08 Part01 01:34:55–01:40:08
原第 7 页

所有约束都松时,KKT退回梯度为零

原课件第7页
点击原页可打开 PDF。

假设一个最优点严格满足每条约束,即 gi(x*)<0 对所有i都成立。互补松弛逐条要求:

λigi(x*)=0⟹λi=0.

把所有零乘子代入驻点式:

∇f(x*)+∑i0·∇gi(x*)=0⟹∇f(x*)=0.

因此可以先解 ∇f=0,再把结果代回每条约束。只要所有约束都满足,取全部乘子为0就得到一组KKT解。只要有一条约束不满足,就要继续查边界分支。

对应课堂录音Week08 Part01 01:40:14–01:41:21Week08 Part01 01:43:44–01:47:43
原第 8 页

例题一:最小化x²,约束x≥−1

原课件第8页
点击原页可打开 PDF。
  1. 统一约束:g(x)=−x−1≤0。
  2. 求导:f′(x)=2x,g′(x)=−1。
  3. 写出四组KKT:
2x−λ=0,−x−1≤0,λ≥0,λ(−x−1)=0.

按乘积式分情况:

  1. 若约束取等号,−x−1=0,则 x=−1。驻点式变成 −2−λ=0,所以 λ=−2,违反非负要求,排除。
  2. 若 λ=0,驻点式给 2x=0,所以 x=0。约束值 −0−1=−1≤0,其余条件也都满足。

因此 x*=0、λ*=0,最小目标值为0。这里 x=−1 虽然可行,也满足驻点方程和互补式,却无法通过乘子非负的检查。

对应课堂录音Week08 Part01 01:43:44–01:47:43Week08 Part01 01:49:45–01:54:36Week08 Part02 00:00:00–00:00:44
原第 9 页

例题二:约束改为x≥1,最优点被挡在边界

原课件第9页
点击原页可打开 PDF。

目标仍为 x2,约束改成 g(x)=1−x≤0。KKT为:

2x−λ=0,1−x≤0,λ≥0,λ(1−x)=0.
  1. 先试 λ=0。驻点式给 x=0,但约束要求 x≥1,所以不可行。
  2. 只能令另一个因子 1−x=0,得到 x=1。
  3. 代回驻点式 2−λ=0,得到 λ=2。
  4. 检查:1−x=0,λ=2≥0,乘积为0,所有条件成立。

最优解 x*=1,最小值1。对比上一页:约束松时乘子0;这一页约束阻止目标继续向0下降,乘子为正。此时目标导数2并不为0,由约束导数乘以2后抵消。

动手试 · 移动约束边界,观察乘子

把本页的 x≥1 改成 x≥b。试 b=−1、0、1,观察最优点和乘子何时改变。

对应课堂录音Week08 Part02 00:00:00–00:00:44Week08 Part02 00:03:28–00:08:10
原第 10 页

二维例题:先把每个梯度都写出来

原课件第10页
点击原页可打开 PDF。

最小化 f(x)=x12+x22,要求 x1+x2≥1、x1≥0。改写:

g1=1−x1−x2≤0,g2=−x1≤0.

三个梯度分别为:

∇f=(2x12x2),∇g1=(−1−1),∇g2=(−10).

给两条约束配 λ1,λ2。g1 同时含两个变量,所以 λ1 会进入驻点式的两行。g2 只含 x1,所以 λ2 只出现在第一行。完整条件为

2x1−λ1−λ2=0,2x2−λ1=0,(1)1−x1−x2≤0,−x1≤0,(2)λ1,λ2≥0,(3)λ1(1−x1−x2)=0,λ2(−x1)=0.(4)

每条约束都有自己的可行性、乘子和互补式。课件右下可行性行的常数−1是笔误,应为+1,与原题和乘积式一致。

对应课堂录音Week08 Part02 00:03:28–00:08:10Week08 Part02 00:11:40–00:14:49
原第 11 页

解出(0.5,0.5),并用等值线理解

原课件第11页
点击原页可打开 PDF。

两组互补式各有两个因子,所以可以检查四种组合:

  1. λ1=λ2=0:驻点式给 x1=x2=0,违反和至少1。
  2. g1=0,λ2=0:驻点两行化为 2x1=λ1=2x2。结合 x1+x2=1,得到 x1=x2=0.5、λ1=1。此时 g1=0、g2=−0.5≤0,两乘子非负,两条乘积也都为0。
  3. λ1=0,g2=0:x1=0,第二行给 x2=0,仍违反和至少1。
  4. g1=g2=0:得 x=(0,1)。第二行给 λ1=2,第一行给 λ2=−2,违反非负,排除。

因此最优点为 (0.5,0.5),目标值 0.52+0.52=0.5,乘子 (1,0)。

图中的圆是 x12+x22 的等值线,表示到原点距离平方相同。把圆从原点向外放大,首次接触可行域的点就是斜线上的垂足 (0.5,0.5)。此处 x1>0,第二条约束松,所以 λ2=0。目标梯度 (1,1) 与 λ1∇g1=(−1,−1) 相加为0。

对应课堂录音Week08 Part02 00:14:51–00:19:06
原第 12 页

把x1下界提高到0.8,重列KKT

原课件第12页
点击原页可打开 PDF。

目标和第一条约束不变,只把 x1≥0 改为 x1≥0.8。标准形式为:

g1=1−x1−x2≤0,g2=0.8−x1≤0.

第二条只改了常数,梯度仍为 (−1,0)T。所以驻点式不变,改变的是可行性与互补式:

2x1−λ1−λ2=0,2x2−λ1=0,(1)1−x1−x2≤0,0.8−x1≤0,(2)λ1,λ2≥0,(3)λ1(1−x1−x2)=0,λ2(0.8−x1)=0.(4)

原来的 (0.5,0.5) 已被新下界排除。课件右下第一条可行性式常数仍误写为−1,按原题 x1+x2≥1 移项应得 1−x1−x2≤0。

对应课堂录音Week08 Part02 00:14:51–00:19:06Week08 Part02 00:19:06–00:19:39Week08 Part02 00:28:05–00:29:34
原第 13 页

解出(0.8,0.2):两条边界同时起作用

原课件第13页
点击原页可打开 PDF。

继续完整检查四种组合:

  1. 两乘子都0:驻点给 (0,0),不可行。
  2. g1=0,λ2=0:仍得到 (0.5,0.5),违反 x1≥0.8。
  3. λ1=0,g2=0:边界给 x1=0.8,第二行驻点式 2x2=λ1=0 给 x2=0。两者之和为0.8,违反第一条约束。
  4. 两约束都取等号:由 x1=0.8 与 x1+x2=1,得到 x2=0.2。

把最后一组点代入驻点式:

0.4−λ1=0⟹λ1=0.4,1.6−0.4−λ2=0⟹λ2=1.2.

两乘子都非负,所有约束和互补式成立。最优值是 0.82+0.22=0.68。三支加权梯度为:

(1.6,0.4)+0.4(−1,−1)+1.2(−1,0)=(0,0).

图中最优点处,斜边和竖边共同阻挡继续靠近原点,两条约束都参与梯度平衡。图例中保留的(0.5,0.5)文字是旧标注,正确最优点是(0.8,0.2)。

对应课堂录音Week08 Part02 00:28:05–00:29:34Week08 Part02 00:31:18–00:35:39
原第 14 页

两物块三弹簧:用能量代替逐种受力分类

原课件第14页
点击原页可打开 PDF。

左右两面墙相距 l,两个物块宽度都是 w,中心位置分别是 x1,x2。三根弹簧刚度为 k1,k2,k3,原长都设为0,地面无摩擦。

要求平衡位置,可以对每块列合力为0。但物块可能碰墙,也可能彼此接触,每一种接触状态对应不同受力情况。

另一个办法是最小化总势能,同时加上物体不能穿墙、不能互相穿透的几何约束。能量写“系统想怎样运动”,约束写“哪些位置不能去”。接触力随后从KKT乘子里出现。

对应课堂录音Week08 Part02 00:31:18–00:35:39Week09 Part01 00:04:26–00:07:46Week09 Part01 00:17:21–00:22:12
原第 15 页

势能与几何约束逐项从图里读出来

原课件第15页
点击原页可打开 PDF。

图中把弹簧连接到物块中心。三根弹簧长度分别是 x1、x2−x1、l−x2。原长0时,弹簧能量为 12k×长度2,所以:

U(x1,x2)=12k1x12+12k2(x2−x1)2+12k3(l−x2)2.

物块有宽度,需要三条几何限制:

  1. 左物块左边缘 x1−w/2 不能越过左墙,因此 x1≥w/2。
  2. 左块右边缘不能超过右块左边缘:x1+w/2≤x2−w/2,即 x2−x1≥w。
  3. 右物块右边缘不能越过右墙:x2+w/2≤l,即 l−x2≥w/2。

能容纳两个物块需要 l≥2w。在这些位置限制内,找使U最小的 (x1,x2)。

对应课堂录音Week08 Part02 00:35:40–00:37:04Week08 Part02 00:37:09–00:39:47Week09 Part01 00:04:26–00:07:46
原第 16 页

给三处可能的接触分别配一个乘子

原课件第16页
点击原页可打开 PDF。

把几何限制改成标准形式:

g1=−x1+w/2≤0,g2=x1−x2+w≤0,g3=x2+w/2−l≤0.

先对能量求偏导。中间弹簧对x1求导时,x2−x1 的导数为−1;对x2求导时为+1:

∂U∂x1=k1x1−k2(x2−x1),∂U∂x2=k2(x2−x1)−k3(l−x2).

约束梯度依次为 (−1,0)T,(1,−1)T,(0,1)T。代入驻点式:

k1x1−k2(x2−x1)−λ1+λ2=0,(1)k2(x2−x1)−k3(l−x2)−λ2+λ3=0.(2)

再加上 gi≤0、λi≥0、λigi=0 对 i=1,2,3 成立,就得到完整KKT。要看找到的平衡位置是否唯一,可以检查 U 的Hessian。把偏导再求一遍,得到

H=(k1+k2−k2−k2k2+k3),vTHv=k1v12+k2(v2−v1)2+k3v22.

当三刚度为正,任何非零 v 都使这个二次型为正。因此 U 严格凸,可行时平衡位置唯一。

对应课堂录音Week08 Part02 00:37:09–00:39:47Week09 Part01 00:04:26–00:07:46
原第 17 页

乘子就是接触力,互补就是“有间隙便没有力”

原课件第17页
点击原页可打开 PDF。

图中 λ1,λ2,λ3 分别是左墙、两物块之间、右墙的接触力大小。接触只能推,因此这些值非负。取向右为正,两物块的受力平衡分别为

−k1x1+k2(x2−x1)+λ1−λ2=0,(1)−k2(x2−x1)+k3(l−x2)+λ2−λ3=0.(2)

中间的弹簧对左块向右拉,对右块向左拉。两块接触时,接触力则把它们推开,所以 λ2 在左块式中为负、在右块式中为正。把两式乘以−1,正好得到上一页的驻点式。

怎么求位置? 取 k1=k2=k3=1,l=6,w=2.5。先试三处都无接触,令乘子全为0。驻点式给 2x1−x2=0、2x2−x1=6,解得 (2,4)。但两块中心距只有2,小于 w=2.5,所以排除。

再试只有两块接触。设 x2−x1=2.5、λ1=λ3=0,驻点式化成 x1+λ2=2.5 和 x2−λ2=3.5。两式相加得 x1+x2=6,与中心距联立得到 x1=1.75,x2=4.25。回代得到 λ2=0.75。两墙间隙均为0.5,墙的乘子为0,两块间隙为0且乘子为正,满足全部KKT。

展开通用解法:刚度不相等时怎样求?

用三根弹簧的长度 s=(x1,x2−x1,l−x2),以及长度下界 b=(w/2,w,w/2)。三段长度相加等于 l,每段都要满足 si≥bi。把第16页的两条驻点式移项,得到三个量相等:

k1s1−λ1=k2s2−λ2=k3s3−λ3=q.

若 si>bi,互补松弛给 λi=0,所以 si=q/ki。若 si=bi,由 λi≥0 得 q≤kibi,也就是 q/ki≤bi。合并两种情况:

si=max(bi,q/ki),∑i=13max(bi,q/ki)=l.

因此只需求一个 q。若 l=2w,各段只能取下界。若 l>2w,左边从最低值 2w 上升,超过最低值后严格递增,可以分段求解。得到 s 后,恢复 x1=s1、x2=s1+s2,接触力是 λi=kisi−q。

上面的数值例子中,b=(1.25,2.5,1.25)。令中间段取下界,两边段均为 q,故 2q+2.5=6、q=1.75。它大于两边的下界1.25且小于中间的下界2.5,分支成立,中央接触力为 2.5−1.75=0.75。

对应课堂录音Week08 Part02 00:43:28–00:46:24Week09 Part01 00:04:26–00:07:46Week09 Part01 00:12:35–00:17:19Week09 Part01 00:17:21–00:22:12
原第 18 页

等式约束拆成两条方向相反的不等式

原课件第18页
点击原页可打开 PDF。

现在考虑凸目标与仿射等式约束:

minxf(x),hi(x)=0(i=1,…,p).

仿射表示 hi(x)=aiTx−bi。等式能拆成:

hi(x)≤0,−hi(x)≤0.

一条说不大于0,另一条说不小于0,两条同时成立只能等于0。例如 x1+x2=1,写成 x1+x2−1≤0 和 1−x1−x2≤0。

给第一条配非负乘子 λi+,给第二条配 λi−。上下标的+、−在这里标记哪一条约束,两者本身都非负。

对应课堂录音Week09 Part01 00:17:21–00:22:12Week09 Part01 00:25:29–00:26:01Week09 Part01 00:30:36–00:35:48
原第 19 页

先按两条不等式机械列出KKT

原课件第19页
点击原页可打开 PDF。

对 hi≤0 与 −hi≤0,梯度分别是 ∇hi 和 −∇hi。因此驻点式为:

∇f(x*)+∑i=1pλi+∇hi(x*)−∑i=1pλi−∇hi(x*)=0.

每个i还配有:

hi(x*)≤0,−hi(x*)≤0,λi+,λi−≥0,λi+hi(x*)=0,λi−[−hi(x*)]=0.

两条可行性已经强制 hi(x*)=0,于是两条乘积式自动为0。需要保留的信息集中在等式本身,以及驻点式中的“两个乘子之差”。

对应课堂录音Week09 Part01 00:28:13–00:28:27Week09 Part01 00:30:36–00:35:48
原第 20 页

两个非负数之差,可以表示任意实数

原课件第20页
点击原页可打开 PDF。

驻点式中同一个梯度出现两次,可以合并:

λi+∇hi−λi−∇hi=(λi+−λi−)∇hi.

定义新乘子 νi=λi+−λi−。虽然原来两个数都非负,它们的差却可以是任意实数。例如 3=3−0、−3=0−3、0=2−2。

反过来,给定任意 νi,总能取 λi+=max(νi,0)、λi−=max(−νi,0)。因此合并没有丢失取值可能。

等式乘子之所以不要求非负,就是由这个差得到的。课件继续用 λi 表示新乘子;这里先写 νi,帮助区分它与前面非负的不等式乘子。

对应课堂录音Week09 Part01 00:30:36–00:35:48
原第 21 页

等式约束的简洁条件:驻点与可行

原课件第21页
点击原页可打开 PDF。

合并以后,只需:

∇f(x*)+∑i=1pνi∇hi(x*)=0,hi(x*)=0,νi∈R.

没有乘子非负条件,也不需要额外写互补式,因为等式在可行点本来就为0。

算一个例子:最小化 x12+x22,满足 x1+x2=1。取 h=x1+x2−1,条件为:

2x1+ν=0,2x2+ν=0,x1+x2=1.

前两式相减给 x1=x2,代入第三式得 x1=x2=0.5,再回代得 ν=−1。等式乘子可取任意实数,因此这组值满足条件。

为什么这就证明了最优?固定 ν=−1 后,L=f+νh 仍是凸函数,因为 h 是仿射函数。驻点让 L 取全局最小值,而且每个可行点都满足 h=0,所以可行点上的 L 就等于 f。

对应课堂录音Week09 Part01 00:30:36–00:35:48
原第 22 页

等式之外,再加每个变量都非负

原课件第22页
点击原页可打开 PDF。

接下来处理经常出现的形式:

minxf(x),hi(x)=0 (i=1,…,p),x≥0.

向量 x≥0 的意思是每个分量 xj≥0,不是把整个向量当一个数比较。若有n个变量,就增加了n条不等式。

列KKT时,把它们统一写成 −xj≤0,每条配一个 μj≥0。等式乘子 νi 仍可正可负。这里i数等式,j数变量,不要把两套下标混在一起。

对应课堂录音Week09 Part01 00:30:36–00:35:48
原第 23 页

标准基向量ej为什么出现在驻点式里

原课件第23页
点击原页可打开 PDF。

ej 是第j个标准基向量:第j个分量为1,其余为0。例如三维中 e2=(0,1,0)T。因为 ∇xj=ej,所以 ∇(−xj)=−ej。

加上非负约束后,完整KKT为:

∇f(x*)+∑i=1pνi∇hi(x*)−∑j=1nμjej=0,(1)hi(x*)=0(i=1,…,p),(2)xj*≥0,μj≥0,μjxj*=0(j=1,…,n).(3)

最后的互补式本来是 μj(−xj*)=0,两边乘−1,就得到 μjxj*=0。非负约束梯度前的负号,则必须留在驻点式里。

对应课堂录音Week09 Part01 00:42:46–00:43:22Week09 Part01 00:45:24–00:50:32
原第 24 页

把一长串乘子整理成一个向量

原课件第24页
点击原页可打开 PDF。

定义 μ=(μ1,…,μn)T。由于e1只把数放到第1位、e2只放到第2位,因此:

∑j=1nμjej=μ.

驻点式压缩成 ∇f(x*)+∑iνi∇hi(x*)−μ=0。其他非负与互补条件也能写成:

x*≥0,μ≥0,μTx*=0.

为什么一个内积为0就能替代n条乘积式?展开内积是 ∑jμjxj*。每项都非负,非负数之和等于0,只能每一项都等于0。例如 x=(2,0)、μ=(0,3),两分量各自乘积都是0,内积也是0。

对应课堂录音Week09 Part01 00:45:24–00:50:32
原第 25 页

消去μ,得到最常用的紧凑形式

原课件第25页
点击原页可打开 PDF。

从驻点式解出:

μ=∇f(x*)+∑i=1pνi∇hi(x*)=:F.

冒号等号表示把右边这一整段命名为F。再把它代入 μ≥0、μTx*=0,得到:

hi(x*)=0,x*≥0,F≥0,FTx*=0.

逐分量读:xj*≥0、Fj≥0、xj*Fj=0。所以若 xj*>0,必须 Fj=0;若 Fj>0,必须 xj*=0。这与前面“间隙和接触力不能同时为正”是同一种互补结构。

对应课堂录音Week09 Part01 00:45:24–00:50:32Week09 Part01 01:31:00–01:31:57
原第 26 页

等式乘子换个符号,条件仍然等价

原课件第26页
点击原页可打开 PDF。

上一页定义 F=∇f+∑iνi∇hi。本页改为:

F=∇f−∑iλi∇hi.

两者相同,只需把 λi=−νi。等式乘子能取任意实数,整体取相反数不会限制它们的范围。因此也可以写:

hi(x*)=0,x*≥0,∇f(x*)−∑iλi∇hi(x*)≥0, ⟨x*,∇f(x*)−∑iλi∇hi(x*)⟩=0.

尖括号是内积,等于向量转置相乘。关键是两处同时使用同一套加减号:不等式里的F和互补式里的F必须一致。不能只改一处。

对应课堂录音Week09 Part01 00:45:24–00:50:32
原第 27 页

交通分流:每条路的时间取决于自己的流量

原课件第27页
点击原页可打开 PDF。

一个小镇有总出行需求d,人们从Home去Work,可选A、B两条路。x1 是A路流量,x2 是B路流量,必须满足:

x1+x2=d,x1,x2≥0.

c1(x1)、c2(x2) 分别是两路的出行时间。c是cost(成本)的记号,这里用时间作为成本;每条路的时间随它的流量变化。

要找的是稳定分配:每个出行者都已在自己的最佳路线上,没有人能仅靠换路降低时间。本讲采用连续流量模型,把个人相对总流量看得足够小,比较当前路线成本。

对应课堂录音Week09 Part01 00:57:06–01:03:32Week09 Part01 01:07:10–01:08:34
原第 28 页

A路2、B路3:为什么这个分配不稳定

原课件第28页
点击原页可打开 PDF。

图中总需求为3,分配 x1=1,x2=2,对应成本 c1(x1)=2、c2(x2)=3。两个x是流量,两个c是时间,不要把这两种数字混读。

正在走B路的人花3,而A路只需2,因此他希望改走A。这表示当前分配存在改进个人出行时间的动机,不是稳定均衡。

流量转移后,两路时间也可能变化,不能把2和3当作永远固定的常数。本页判断的只是眼前这组分配是否稳定。

对应课堂录音Week09 Part01 01:07:10–01:08:34Week09 Part01 01:14:20–01:17:53
原第 29 页

两条都有人走时,均衡成本应相同

原课件第29页
点击原页可打开 PDF。

现在 x1=x2=1.5,两路成本都是2.5。总流量仍为 1.5+1.5=3。

走A的人改走B,当前成本还是2.5;走B的人改走A也是一样。没有人能通过换路获得更低时间,因此这种分配符合本模型的均衡规则。

这里“两路成本相同”与“两路都有人使用”一起出现。下一页会说明:若某条路根本没人走,均衡并不要求它也具有相同成本。

对应课堂录音Week09 Part01 01:14:20–01:17:53
原第 30 页

没人走的路可以更贵,仍然是均衡

原课件第30页
点击原页可打开 PDF。

图中 x1=0,x2=3,A路成本3,B路成本2。全部人都在便宜的B路,且总流量仍为3。

B路的人若换去A,时间由2变3,更差,所以没人愿意换。A路虽与B路成本不同,却没人使用;这仍然稳定。

因此不能把均衡一律写成 c1=c2。准确说法是:所有被使用的路线都达到最低成本;未使用的路线可以等于或高于最低成本。

对应课堂录音Week09 Part01 01:14:20–01:17:53
原第 31 页

把均衡规则压缩成两句话

原课件第31页
点击原页可打开 PDF。

前面三个例子可以统一成:

  1. 如果一条路不是最低成本路线,就不能有人使用它。
  2. 如果一条路有人使用,它就必须是最低成本路线。

第一句的逆否命题就是第二句。两句都禁止同一种情况,即一条路成本高于最低成本,流量却大于0。

也允许一条最低成本路线暂时流量为0。均衡只禁止“有人在更贵的路上,同时还有更便宜的选择”,不要求每条同价路线都一定有正流量。

对应课堂录音Week09 Part01 01:14:20–01:17:53Week09 Part01 01:21:44–01:27:17
原第 32 页

用一个最低成本λ写出互补条件

原课件第32页
点击原页可打开 PDF。

引入 λ 表示均衡时的最低路线成本。它和流量一起求。所有路线的成本差 ci(xi*)−λ 非负,乘积式则禁止正流量与正成本差同时出现。

xi*≥0,ci(xi*)−λ≥0,xi*[ci(xi*)−λ]=0(i=1,2),

再加需求守恒 x1*+x2*=d。若流量为正,乘积式强制成本等于λ;若成本大于λ,乘积式强制流量0。

验证前两种稳定例:两路都有人且成本2.5,取λ=2.5,两个成本差均0;只有B有人且成本2、A成本3,取λ=2,A的乘积为 0×1=0,B为 3×0=0。

这正好长得像“变量非负+F非负+内积为0”的KKT结构。于是可以倒过来寻找一个优化目标,使它的梯度等于路线成本。

对应课堂录音Week09 Part01 01:21:44–01:27:17Week09 Part01 01:31:00–01:31:57
原第 33 页

对成本积分,构造恰好产生均衡条件的目标

原课件第33页
点击原页可打开 PDF。

希望 ∇f(x)=c(x)。因为每条路成本只依赖自己的流量,利用微积分基本定理,可构造:

f(x)=∫0x1c1(v)dv+∫0x2c2(v)dv,∂f∂xi=ci(xi).

其中v是积分里的临时变量。现在解:

minxf(x),x1+x2=d,x≥0.

取等式 h=x1+x2−d=0,梯度是 (1,1)T。采用第26页的减号约定,拉格朗日函数为 L=f−λ(x1+x2−d)−μTx。驻点给 ci(xi)−λ−μi=0。消去μ后正是:

xi≥0,ci(xi)−λ≥0,xi[ci(xi)−λ]=0.

用 c1(x1)=1+x1,c2(x2)=1+x2,d=3 算第29页的分流。积分得到 f=x1+x12/2+x2+x22/2。再按两条路的流量分情况:

  1. 若只走一条路,该路流量3,成本4,另一条路流量0,成本1。选用路线的成本要求 λ=4,另一条路的成本差 1−4<0,所以两个单路方案都排除。
  2. 若两条路都使用,两个成本差都是0,故 1+x1=1+x2=λ。再用 x1+x2=3,得 x1=x2=1.5、λ=2.5。两流量为正、总量为3,两个成本差都是0,满足全部条件。

若成本函数连续且不减,积分目标是凸的,KKT就能刻画这种均衡。这个目标叫势函数,它通常不等于总出行时间 ∑ixici(xi);这里构造它,是为了让梯度恰好等于个人面对的路线成本。

对应课堂录音Week09 Part01 01:21:44–01:27:17Week09 Part01 01:31:00–01:31:57Week09 Part01 01:32:01–01:35:56