无约束时,可以向任意方向移动;有约束时,有些能让目标下降的方向已经被挡住。因此最优点可能还带着非零梯度。
这一讲要学会用KKT条件检查最优点。先从一维和二维例子认识四组条件,再用弹簧接触理解它们,最后把等式约束、非负变量和交通均衡接起来。
学习顺序是:先把约束写成统一形式,算梯度,列KKT,按互补松弛分情况,最后检查全部条件。
共 33 页。按原课件顺序,左侧看原页,右侧读讲解。
对这里的可微凸问题,找到满足KKT的 ,就能确定 是全局最优点。反过来,从最优点推出一定存在乘子,还需要约束资格条件;常见的Slater条件是存在一点让所有凸不等式严格成立。
先理解为什么KKT能证明最优。固定这组 ,拉格朗日函数 是凸的。驻点条件给出 ,所以x*让L达到最小。
对任意可行x,由 与 ,有 。而互补松弛让 。连起来:
因此所有可行x的目标都不会比x*小。做本讲例题时,列完条件还必须检查可行性和乘子非负,单独解出驻点方程不够。
最小化 ,约束 。唯一可行点就是0,所以它必然最优。但在0处 、,驻点式变成 ,任何乘子都无法满足。这个约束没有严格可行点,恰好说明为什么课件在“当且仅当”前注明了附加条件。
图中 分别是左墙、两物块之间、右墙的接触力大小。接触只能推,因此这些值非负。取向右为正,两物块的受力平衡分别为
中间的弹簧对左块向右拉,对右块向左拉。两块接触时,接触力则把它们推开,所以 在左块式中为负、在右块式中为正。把两式乘以−1,正好得到上一页的驻点式。
怎么求位置? 取 。先试三处都无接触,令乘子全为0。驻点式给 、,解得 。但两块中心距只有2,小于 ,所以排除。
再试只有两块接触。设 、,驻点式化成 和 。两式相加得 ,与中心距联立得到 。回代得到 。两墙间隙均为0.5,墙的乘子为0,两块间隙为0且乘子为正,满足全部KKT。
用三根弹簧的长度 ,以及长度下界 。三段长度相加等于 ,每段都要满足 。把第16页的两条驻点式移项,得到三个量相等:
若 ,互补松弛给 ,所以 。若 ,由 得 ,也就是 。合并两种情况:
因此只需求一个 。若 ,各段只能取下界。若 ,左边从最低值 上升,超过最低值后严格递增,可以分段求解。得到 后,恢复 、,接触力是 。
上面的数值例子中,。令中间段取下界,两边段均为 ,故 、。它大于两边的下界1.25且小于中间的下界2.5,分支成立,中央接触力为 。
希望 。因为每条路成本只依赖自己的流量,利用微积分基本定理,可构造:
其中v是积分里的临时变量。现在解:
取等式 ,梯度是 。采用第26页的减号约定,拉格朗日函数为 。驻点给 。消去μ后正是:
用 算第29页的分流。积分得到 。再按两条路的流量分情况:
若成本函数连续且不减,积分目标是凸的,KKT就能刻画这种均衡。这个目标叫势函数,它通常不等于总出行时间 ;这里构造它,是为了让梯度恰好等于个人面对的路线成本。