约束可能阻止目标函数下降的方向,因此单看目标函数的驻点并不足够。拉格朗日(Lagrange)乘子描述这种阻碍;对偶性则用合适的乘子为所有可行值提供下界。当某个可行值等于下界时,最优性便得到证明。
拉格朗日函数与弱对偶
在 、()及 ()下最小化 。
定义 2.1.1
(拉格朗日函数、对偶函数与对偶问题)
拉格朗日函数为
对偶函数是 ,它可以等于 。对偶问题在 、 不受符号限制下最大化 ,其最优值记作 ;原问题的下确界记作 。
定理 2.1.2
(弱对偶)
对任意原问题可行点 、 及任意 ,都有 。因此 ;在有定义时允许取广义实数值。
证明
(可行性使每个附加项非正)
对可行的 ,等式项为零,且因 、 而有 ,所以 。对可行 取下确界,再对对偶可行乘子取上确界,便得 。
若某可行 和对偶可行 的值相等,两者都是最优的;这一证明不需要凸性。此结果比较上下界,并不断言两边都取得最优值。强对偶表示最优值相等,不表示任意试算值相等。对偶迭代点即使可行,也可能只给出很弱的下界;反过来,不可行点即使目标值很好,也不是原问题的上界。若同时有原问题可行值和对偶值,两者之差称为非负的对偶间隙。当有限最优值位于两者之间时,小间隙便限制了各值与最优值的距离。
符号约定不可忽视。若改为最大化,或把不等式写成 ,乘子的符号也须相应一致地改变。乘子并非任意的罚项:在本约定中若选负乘子,上面的下界推理就可能失效。
KKT 条件
定义 2.1.3
(Karush–Kuhn–Tucker 条件)
在开定义域上,对可微函数,点 及乘子 的 KKT 条件为:
- 原始可行性: ,。
- 对偶可行性: 。
- 互补松弛: 每个 满足 。
- 驻点条件: 。
严格不活跃的不等式约束必有零乘子;活跃约束的乘子却也可以是零。互补松弛并不表示每个活跃约束都有正乘子。KKT 条件并不自动是所有受约束最优点的必要条件,还需要约束规范条件。
定理 2.1.4
(凸问题的 KKT 充分性)
在开凸定义域上,若 和所有 可微且凸,所有 为仿射函数,则任何满足驻点条件、乘子非负、互补松弛的可行点及乘子,都是原问题和对偶问题的最优解。
证明
(一个不等式、一次最小化、一个等式)
由于 、各 凸、各 仿射, 在开定义域上凸且可微。驻点条件表示它在 处梯度为零,故由凸性的一阶刻画, 最小化该函数,并有 。互补松弛与可行性给出 。因此每个可行 都满足
所以 是原问题最优点。对任何对偶可行 ,弱对偶给出 ,所以这组乘子是对偶最优的。
证明透视
链中每一环用了什么
上式的不等式链使证书一目了然。第一个不等式只用到 的可行性和符号 ,即单点处的弱对偶。中间的不等式用到凸性与可微性:它们把驻点方程提升为拉格朗日函数的全局最小性;对非凸问题,驻点可能是极大点或鞍点。最后的等式用到互补松弛及 ;若缺少它,链只给出较弱的 。整个证明没有出现约束规范条件:约束规范关乎乘子是否存在,而这个证明一开始就已经有了乘子。
此定理不要求 Slater 条件。Slater 条件是保证最小点存在乘子的一种途径;一旦找到 KKT 证书,充分性证明只需上述凸性和可微性假设。分清两个方向,就不会误以为严格可行性不成立会使一个已验证的证书失效。
反方向则需要假设;以下是 Slater 条件的一个具体的充分形式。
定理 2.1.5
(Slater 条件给出 KKT 乘子)
设 为开凸集, 与每个 在 上可微且凸,各 为仿射函数。假设 内有一点满足所有等式并严格满足每个不等式,且原问题的最小值有限并在 内取得。则强对偶成立,最优乘子存在,且每个原问题最小点都有 KKT 乘子。
其分离证明见分离、次梯度与强对偶单元。严格可行性必须检查,不能只因最优点存在就推断它成立。更精细的版本可放宽仿射不等式的严格性并使用相对内部;本节采用刚才较强的条件。
例子:对偶证书
例题 2.1.6
(KKT 点及其对偶函数)
最小化 ,约束为 。拉格朗日函数为 。驻点条件给出 、;若约束活跃,,所以 ,。该点可行,乘子非负,互补松弛成立;凸性使 KKT 条件足以证明最优。
同一结论也可直接从对偶读出。代入 的最小点得
最大值 等于原问题的值。 严格可行,所以 Slater 条件也成立。
当最优值函数可微时,乘子与右端项微小放宽带来的最优值变化率有关,按此符号约定相差一个负号;没有可微性等额外条件时,不可直接断言它就是导数。
约束规范为何重要
即使是凸问题,也不能直接删去 Slater 假设。
反例模式
最小点没有乘子的凸问题
断言:可微凸问题的每个最小点都有 KKT 乘子。在 下最小化 ;两个函数都是凸的。唯一可行点为零,故它是最优的;然而驻点条件在零处要求 ,即 ,任何乘子都不可能满足。此处没有严格可行点,而且约束梯度在最优点处为零。修正后的表述正是上面的 Slater 定理,而其严格可行假设在此不成立。这不是 KKT 充分性的反例,而是必要性需要假设的例子。
等式约束及乘子
等式与不等式不同:等式乘子不受符号限制。原因可从弱对偶的证明看出:在可行点处 ,故不论 的符号如何, 都为零。代数上可用两个反向不等式代替等式,但这可能引入多余的乘子,使解释不那么直接。
例题 2.1.7
(等式约束下的投影)
在 下最小化 。令 ,驻点条件为 、,故 ;可行性给出 、。等式乘子可以为负。目标函数是凸的且约束是仿射的,所以 KKT 条件证明全局最小值为 。另一证法是 ;两种方法得到同一个下界。
例题 2.1.8
(活跃约束的乘子可以为零)
在 下最小化 。唯一最优点是 ,约束在此活跃。驻点条件 给出 ,所有 KKT 条件成立。因此约束活跃本身不保证乘子为正。虽然可行集阻止向右移动,无约束最优点已在边界上,故放宽约束没有一阶改进。
例题 2.1.9
(对偶函数可以无下界)
在 下最小化 。对 ,。在整个实数轴上取下确界,除非 ,否则结果为 ; 时结果为 。因此对偶最大值为 ,在 处取得;原问题可行点 的值也是 ,构成相等的证书。此计算说明必须在整个定义域上最小化 ,不能只代入原问题的可行点。
灵敏度及符号检查
概念视角分析
乘子作为最优值的导数
设约束 写成 。固定某个最优乘子并改变 ,拉格朗日函数改变 。在最优值函数 可微且包络公式适用的条件下,。因此乘子也是一个变化率:约束每放宽一个单位时最优值的边际下降量。负号符合直觉:增大 会扩大可行集,最小值不可能上升。即使不可微,单调性仍成立,但具体的导数公式未必成立。
上面的二次例子若把右端的 改成 ,当 时,活跃的解为 ,最优值为 ,乘子为 。求导得 。当 时,无约束最小点可行,最优值和乘子都为零。这个计算同时显示了乘子的局部含义以及活跃约束集的变化。
选择及检查候选点
对小问题,可列出可能的活跃约束集,联立驻点条件及活跃的等式,再检查所有不等式和乘子符号。不满足任一条件的代数解不是 KKT 点。不活跃约束的乘子必为零,但反过来不一定。最后应以凸性证明充分性,或为非凸问题另给论证。非凸问题的 KKT 驻点可以是极大点或鞍点,因此解出乘子方程并非证明的终点。
不靠猜测建立对偶问题
计算次序很重要。先写清原问题的定义域,并按选定的约定整理不等式方向;再用非负的不等式乘子和不受符号限制的等式乘子建立 。固定乘子后,在整个定义域上对 取下确界,允许结果为 ;最后才在乘子的可行范围内最大化对偶函数。即使 的最小点不存在,下确界仍定义了 ;不能无理由地代入一个驻点并称之为对偶值。
例如在 下最小化 。对 ,配方得 ,所以 。最大化得乘子 、;原问题可行点 的值也是 ,构成全局证书。 是 的全局最小点,理由是平方项系数为正,而不只是导数为零。
即使原问题不是凸的,对偶函数仍是凹的。令两组乘子为 ,。由于拉格朗日函数关于乘子是仿射的,
因为下确界内的每一项都不小于各自的下确界,便得到这个不等式。故在凸的乘子可行域上最大化对偶函数是凹函数的最大化问题。但凹性本身不保证有限最优值或零对偶间隙;这些是另外的问题。
会:没有凸性时,即使是单变量问题,对偶最优值也可以严格低于原问题最优值。
自然的下一个问题
最好的对偶界会不会严格低于最优值?
会:没有凸性时,即使是单变量问题,对偶最优值也可以严格低于原问题最优值。
在非凸定义域 上,在 之下最小化 。唯一可行点是 ,因此 。对 ,
其最大值为 。对偶间隙 为正,因此没有乘子能证明最优性。凸性加上 Slater 条件是排除这种间隙的一种充分条件。
常见错误
必须一并检查候选点和乘子。弱对偶总给出下界,但原问题与对偶问题的最优值相等是另一个命题;对非凸问题,单有 KKT 条件不能证明驻点全局最优。
常见错误
(以为每个活跃约束都有正乘子)
活跃的约束不一定有正乘子:在 下最小化 ,约束活跃而 。另一方面,在本节的最小化约定中, 的负乘子是不可行的。
常见错误
(只在可行点上最小化拉格朗日函数)
对偶函数是在整个定义域上取下确界,而不是在原问题的可行集上取。对 下最小化 的问题,若在 时只考虑可行的 ,会得到 ,而正确的值是 。
常见错误
(混用符号约定)
改变符号约定不改变原问题,但会改变证书的公式。例如把 写成 ,就用非负乘子乘以 。若改写为 ,却仍在同一拉格朗日函数中保留同样的乘子符号,该项在可行点处会给出上界方向的贡献。解释乘子之前,应先核对弱对偶不等式。
总结
拉格朗日函数把约束转化为候选下界。若原问题可行点和对偶可行乘子的值相同,即证明了全局最优。在可微凸问题中 KKT 条件产生这种证书;在前述假设下,严格可行性保证已取得的最优点有证书。这些工具足以处理本节例题,但并未涵盖所有对偶理论及约束规范条件。
练习
快速检查
(在 下最小化 ,给出 KKT 证书。)
无约束最小点不可行,故试设约束活跃。
解答 · 答案
最小点为 ,由 处的 得 ;可行性、非负性和互补松弛都成立,由凸性得最优。
快速检查
(在 下最小化 ;约束是否活跃,乘子是多少?)
比较无约束最小点与上界。
解答 · 答案
最小点为零,该处不等式严格成立,故约束不活跃,互补松弛给出乘子为零。
快速检查
(求在 下最小化 的对偶函数 (),并验证两边最优值相等。)
对所有实数 最小化 。
解答 · 答案
对 最小化 得 ,所以 。在 上最大值是 ,等于原问题的值 。