动机
下界只有在知道它为何有效及是否能达到真实最小值时,才能完成最优性证明。凸几何提供这个理由:超平面能把点与凸集分离;次梯度则是凸函数的支撑斜率。把分离应用到可实现的约束违反量与目标值集合,支撑超平面便成为拉格朗日(Lagrange)乘子。本节在明确的有限维假设下推导这个关系,并检查假设失败时可能发生的事。
非光滑函数同样需要几何。绝对值在零没有普通导数,却有支撑斜率和清楚的最小点。次梯度记录这些斜率。把乘子解释为最优值的导数,则另外需要价值函数可微;一般只能得到不等式。
定义
定义 5.1.1
(凸集、次梯度与次微分)
非空集合 若包含任意两点间整条线段便是凸集。设有限凸函数 定义于开凸集 。若
则 是 的次梯度;全体次梯度记为 。因此 当且仅当 在 上最小化 。若 在 可微,则 :导数给出支撑斜率,并沿正反方向测试可证其他次梯度相同。例如 在零的次微分为 。
定义 5.1.2
(欧氏投影)
对闭非空凸集 及点 ,欧氏投影 是距离 最近的唯一 中点。将最小化序列限制在有界球内并取收敛子列,得到存在;距离平方的严格凸性给出唯一性。沿 至任意 的线段微分距离平方,得投影不等式 。
定理/命题
定理 5.1.3
(与闭凸集严格分离)
若 非空、闭且凸,,则存在非零向量 及标量 ,使对所有 均有 。
对偶证明会用到两个关于开凸集的辅助事实。
引理 5.1.4
(开凸集与其闭包)
非空开凸集 满足 。
命题 5.1.5
(与开凸集的弱分离)
若非空开凸集 不含 ,则存在非零 ,使所有 满足 。
有了这些工具,就可以陈述主要的对偶定理。
定理 5.1.6
(Slater 强对偶及乘子取得)
设 为开凸集, 在 可微且凸, 仿射。假设存在 满足 及所有 ,而有限的原问题最小值 在 取得。则存在 和 ,使 满足 KKT,且对偶最大值等于 。
这是严格不等式版本的充分条件;更一般的相对内部版本可放宽部分仿射不等式。结论既包括零间隙,也包括对偶乘子取得最大值。单有凸性或原问题最小点,并不能推得这两项。
证明思路
由投影得到分离
证明
(由投影得到分离向量)
取 和 。因 ,。投影不等式给出每个 的 ;但 ,取 即得结论。支撑平面垂直于由 到 的最短线段,严格间隙就是距离的平方。闭性不可省:、 时,没有线性函数能在 和集合之间留出严格间隙。
概念视角分析
分离向量是距离函数的次梯度
设 ,这是一个凸函数,恰好在 上为零。对 及 ,向量 是 在 处的次梯度:记 ,投影不等式给出 ,因此 。当 时左边为零,整理后即得 。因此严格分离正是 的次梯度不等式在其零集上的表现。
证明
(从内部逼近单纯形)
先证一个基本引理:非空开凸集 等于 。包含关系 显然。反过来,若 在闭包内部,可选一个包含 于其内部、且足够小而位于该内部的单纯形。以 中点充分近似各顶点,令 仍在所得新单纯形内部。凸性使整个新单纯形属于 ,所以 。此引理的证明没有使用分离定理。
证明
(用极限得到弱分离)
还需使用开凸集分离推论:若非空开凸集 不含 ,存在非零 使所有 满足 。若 ,可对闭包使用投影证明;若 ,取不属于闭包且趋于 的点列,逐一分离,将法向量归一化并取单位球面上的收敛子列,再令点列趋近 ,便得到弱分离。引理保证 时 ,所以这两种情况已涵盖所有可能。
扰动集合的支撑平面
证明
(分离严格上集)
先限制在仿射切片 ,定义严格上集
非空且开:对已给的见证点,稍微改变 后严格不等式仍成立。两个见证点的凸组合仍在 ,各函数的凸性保留严格上界,故 凸。 不属于 ,否则存在原问题可行点的值小于最小值。
将此点与 分离。 沿每个坐标向上封闭,故分离法向量 满足 、,以及
对任意 ,从上方趋近 ,得到 。若 ,严格可行点对任何非零 都有 ,矛盾。所以 ;除以它并重用 记号,得到
在 ,可行性给出相反不等式,故取等号,并且每个 。凸可微函数 在仿射切片上由 最小化。由 开放,沿 的每个方向可作足够小的正反移动,所以 与 正交,属于 。选 令 。
完整拉格朗日函数在 凸且于 驻定,其下确界因此等于该处值 。构造出的乘子取得对偶值 ;弱对偶又限制任何对偶值不超过它。这同时证明零间隙和对偶取得,并无预先假设后者。
扰动证明中的符号为何固定
证明透视
严格上集的作用
论证依靠 的三个特点。第一, 向上封闭,这迫使符号确定:若法向量在某坐标的系数为负,在 内把该坐标推向 ,就使 趋于 ,违反其下界。所以 、,而分离定理保证 。第二,严格可行性只在一步使用,就是排除 :由 ,任何非零 都给出 。一旦 ,把它归一化为一,其余坐标就成为乘子;若只有边界可行点,则可能出现 的异常法向量,如下面对偶不取得的例子。第三,严格不等式使 直接成为开凸集,无须假设价值函数的上境图闭合,而这一点可能不成立:非紧致定义域上的下确界未必取得,闭凸集的投影也未必闭。从上方趋近 ,就把弱分离转化为 上的不等式。等式乘子在此之后才由仿射切片的梯度条件加入,所以对偶取得是结论而不是假设。
价值函数与敏感度
对不等式右端 ,令 ,不可行时取 ;对 定义 。
命题 5.1.7
(乘子是价值函数的次梯度)
假设 有限,而某对 (其中 )满足 ,例如上述 Slater 假设下就成立。则
所以 是广义实值凸函数 在零的次梯度。若 在零可微,则 。
证明
(扰动问题的弱对偶)
若 不可行,则 ,无需证明。否则设 满足 及 。由于 ,
对这些 取下确界即得不等式。若 在零可微,把 分别除以小的 及小的 ,得到对每个 都有 。
对不可行的扰动,这个不等式仍有意义;不可微时可以有多个支撑斜率。价值函数的凸性可由两个扰动的近似最优可行点取凸组合,再令目标误差趋于零得到。
尖角处的支撑斜率
即使定义简单,价值函数也可能不可微。考虑 。在零,每个 都满足对所有 的 ,所以 。左右斜率分别为零及一,普通导数不存在。一个次梯度仍提供有效的全局下界,但只描述其中一条支撑线,不是唯一的边际变化率;可微时所有支撑斜率才必须相同。
次梯度可直接相加。若同一凸定义域上 、,相加两个定义不等式得到 。反向的完整求和公式需要另外的正则性假设,本节只需这个包含关系。例如 :加上仿射项将 的每条支撑斜率加二;反过来减去仿射项可证没有其他斜率。
例题详解
例题 5.1.8
(投影产生分离直线)
设 、。投影 ,。每个点 满足 ,但 。直线 支撑 并严格分离 。
例题 5.1.9
(非光滑次微分)
对 ,不等式 对所有 成立,当且仅当 :分别测试正负 得两个界,且两界亦充分。所以 证明零点最小,即使普通导数不存在。正点的次微分是 ,负点是 。
例题 5.1.10
(一个有尖角的价值函数)
在 和 下最小化 ,其值是 。 时两个约束均活跃。将它们写成 和 ,驻点条件为 ,且乘子非负。每个和为一的乘子对均最优。第二个约束的扰动支撑斜率是 ,恰好是 在零的次微分。这个线性凸问题说明,乘子不唯一和价值函数不可微可以同时出现;两者都不表示存在对偶间隙。
支撑不等式对所有扰动成立,即使所选乘子不唯一。离开基准点后,它通常比真实价值函数弱。尖角例子中,斜率零给出 ,斜率一给出 。在此例取这两个仿射下界的最大值恰好恢复 ;一般最优化问题并不自动如此。
常见错误
以下是处理分离与乘子时容易犯的错误。
常见错误
(期望与开集严格分离)
若 位于开凸集 的闭包内但不属于 ,就只能得到弱分离。对开单位圆盘及 ,法向量 在圆盘上给出 ;但不存在 使所有 都满足 ,因为圆盘中的点可以任意接近 。
常见错误
(一个乘子不代表价值函数可微)
在尖角处,次微分可以包含许多斜率。上面的尖角例子中,每个 都是最优乘子,而 在零没有导数。选定一个乘子只证明一条支撑不等式,并不是唯一的边际效应。
常见错误
(Slater 条件是充分而非必要)
没有严格可行点时,问题仍可以零间隙且对偶取得。在 及 下最小化 ,唯一可行点为 ,Slater 条件不成立;但 在 时为 ,否则为 ,而 取得原问题的值 。
零间隙与对偶取得是两个不同的结论,定理同时断言两者。
反例模式
值相等不保证对偶有最大点
由 就断定某个乘子取得上确界,是很自然却错误的推论。在 下最小化 。唯一可行点是零,所以 。对 ,:该函数在零的导数为一,稍向左移就降低拉格朗日函数值。但当 时 :对 ,由 得 ,而 。因此值上强对偶成立,却没有有限乘子取得对偶值。缺少的假设是严格可行性:没有点满足 。若有严格可行点,分离论证就会给出取得对偶值的乘子。
总结
投影给出闭凸集的严格分离;对凸扰动集合用开集分离得到乘子,严格可行性迫使目标系数非零。仿射切片的梯度条件补上等式乘子,从而证明对偶取得。次梯度表达支撑不等式,导数则需要更多光滑性。
练习
快速检查
(求 到 的投影,并写出严格分离不等式。)
沿竖直方向投影到直线 。
解答 · 答案
投影是 ;取 ,在半空间上有 。
快速检查
(求 在零的值,并求 的最小值或说明不存在。)
使用次梯度之前,先看负的 。
解答 · 答案
。当 ,,所以没有最小值。该和在零的次微分为 ,不含零。
快速检查
(在 下最小化 。求最优乘子及零附近扰动约束 的价值函数。)
从扰动约束解出 的范围。
解答 · 答案
写 ,最小点 ,驻点条件给 。当 ,可行集为 ,故 、; 时公式改变。
快速检查
(对上述不取得的对偶例子,证每个有限 有 ,并找一个趋向一的下界。)
利用 。
解答
在零的导数为一,稍向左移使值小于一。对 , 给出 。又 ,所以上确界为一但不取得。