乘子何时代表局部变化率?
最优化模型常有一个指定的资源水平 。若已经解出某个水平下的问题,当 稍微改变时,是否必须从头计算?乘子可以预测最优值的一阶变化,但我们必须先说清楚正在追踪哪个最优解,以及为什么它会平滑移动。我们会对正则的严格局部极小值证明这点;后面的例子则说明全局最优值未必有同一个导数。
设 及 在 附近二阶连续可微,考虑
右端项是参数。采用拉格朗日(Lagrange)函数 。在 ,假设 的驻点乘子为 ,即 。记 及 。注意 包含约束的曲率,不只是 的 Hessian。
定理 2.3.1
(严格局部极小值的平滑分支)
假设 行满秩,而且对每个满足 的非零 都有 。那么,对靠近 的 ,在 附近存在唯一驻点对 ,并且它连续可微地依赖 。每个 都是严格局部极小点。分支值 满足
这是所选局部分支的结论,并不断言该分支为全局最优。
证明
(由带边系统得到隐函数)
驻点及可行性方程 、 对 的导数在基点为
若 ,则 且 。把第二式与 取内积,得 。在 上的正定性迫使 ;接着 ,行满秩便迫使 。因此方阵 非奇异,隐函数定理给出 附近唯一的 驻点分支 。由连续性, 的行满秩,以及 在 上的正定性,在足够小的邻域内仍然成立,因此等式约束的二阶充分条件保证每个分支点均为严格局部极小点。
对 微分得 。利用链式法则及驻点方程,
证明透视
每个假设在哪里用上
行满秩用了两次:一次是把 从 的核中排除,另一次是通过 把驻点方程转化为值的导数。二阶正定性只需在 上成立;唯一不显然的一步是与 取内积:由于 ,乘子项 消失,只剩下切向曲率。值的公式之后无需任何最优性论证便可完成,因为沿分支有 。证明从未把分支与远处的可行点比较,所以既没有用到、也没有得到全局最优性;若 不再满秩,如下面最后一个例题,第一步便已失效。
对小改变 ,结果写成 。按照这里的符号惯例,预测的边际成本是乘子的负值。
常见错误
(未说明惯例便解读乘子的正负)
“乘子为正,说明值随 增加”这种说法,在写出约束形式之前并无意义。采用 时,值的导数是 ;采用 时,乘子反号,导数变成 。解读符号前先核对惯例。
计算解如何变化
沿方向 微分驻点及可行性方程。在基点,导数 及 满足
这里目标函数和约束函数除了上述右端项外,并不直接依赖 。如果参数还出现在其他地方,微分相应方程时便会产生额外项。由 ,局部值的 Hessian 为 。
当 在整个空间正定时,带边系统可以用消元法解出。
命题 2.3.2
( 时的响应矩阵)
在定理的假设下,再设 在 上成立。则 正定,并且
证明
(消去原变量的响应)
对 ,行满秩给出 ,故 ;所以 正定且可逆。响应方程组的第一个块行给出 。代入 得 ,于是 ,且 。由于 任意,这些就是所述导数;再由 得最后一式。
这个公式计算方便,但 比定理的假设更强:即使 在切空间之外奇异或不定,带边系统仍可能非奇异。
常见错误
(用目标函数的 Hessian 代替拉格朗日函数的 Hessian)
曲率条件针对的是 ,而不是 。若目标函数是线性的而约束是弯曲的,如下面的圆周例题,便有 ,二阶检验看似失败;其实全部曲率都来自约束项。
例题
例题 2.3.3
(分配指定总量)
最小化 ,约束为 。驻点方程给出 和 ,因此 、、。所以 ,而 。这里 、,故 ,。Hessian 正定,因此这个可行驻点对每个 都是唯一全局极小值。
例题 2.3.4
(由约束提供的曲率)
在 时,最小化 ,约束为 。驻点方程给出 和 ,故 ;可行性给出 。两个驻点为 ,对应 。
在 ,,且 ,故定理适用。分支值为 ,而
在 ,、,故 ,命题预测 ;直接计算 也得到同一数值。另一个驻点有 及 ,切向曲率为负,它是极大点,而不是极小值分支。
以下两项说明定理不涵盖的情形。
反例模式
平滑局部分支可以交换全局最优地位
最小化 ,约束为 。当 , 与 都是严格局部极小点,值均为零;等式梯度行满秩,切向曲率亦为正。因此每个点都有平滑局部分支。然而全局值 在零不可微。事实上 ,而可行点 与 显示 。若 在零有导数,右侧差商会迫使导数至多为 ,左侧差商则迫使它至少为 。矛盾反映两个局部分支互相竞争;切换点的全局值不能由任何一个局部乘子单独微分。
在更一般的参数化下,另一种失败是正则性消失。
例题 2.3.5
(约束梯度消失时)
最小化 ,约束为 。可行集为 ,故全局值是 ,它在 不可微。在 ,唯一可行点是 ,该处 :行满秩失效。更进一步,驻点方程 在 无解,所以根本不存在乘子。不能只因为最优值有限,就套用乘子公式。
练习与解答
快速检查
(最小化 ,约束 。求解、乘子、值及值的导数。)
采用 的惯例。
解答 · 答案
驻点方程给出 、,可行性给出 ,故 。所以 ,,且 。严格凸的目标函数保证唯一全局极小值。
快速检查
(最小化 ,约束 。尽管目标 Hessian 不定,验证定理在 的假设,并求分支值。)
只在 上检验曲率。
解答 · 答案
这里 、。在 上,对 二次型为 。可行问题中 ,在 取得最小值,故 ,而 ,。负曲率不违反定理,因为定理只要求沿切方向正定;含 的命题则不适用,因为 。
快速检查
(最小化 ,约束 。把约束写成 ,求其乘子,并与值的导数比较。)
写出 。
解答 · 答案
对 的驻点方程为 ,故 。值为 ,其导数为 。若使用原本的 惯例,乘子则为 ,导数为 。
快速检查
(在第一个例题中,用 的导数估计 增加 时值的变化,再与精确变化比较。)
回想 。
解答 · 答案
,故一阶估计为 。精确地,。差额 是二次项,并非一阶公式失效。