用斜率构造下界
可微凸函数的切线位于图像下方。若函数不可微,或我们想找指定斜率下最好的仿射下界,该怎样做?对 ,定义它的共轭函数为
扩充值 可用来表示约束:非空集合 的指示函数 在 上为零,在集合外为 。若 在某点有限且从不取 ,称它为真函数;下文除另有说明外均假设它是真函数。即使如此, 仍可能为无穷大:这表示指定斜率下没有有限截距的仿射下界。由于 是一族关于 的仿射函数的上确界,它总是凸函数,即使 本身不是凸的。
对任何 的 和任何 ,定义立即给出 Fenchel 不等式:
两边将不同变量分开,因此它能产生对偶下界。等号亦有明确的几何意义。回想 表示对每个 都有 ;这个定义对真函数均有意义,不要求可微。
定理 5.4.1
(Fenchel 不等式的等号)
设 为真函数且 。则 当且仅当 。特别地,等号成立时 有限。
证明
(上确界与支撑平面表达同一条件)
等号表示 是所有 的上确界,也就是对每个 ,
移项便得到次梯度不等式 。反过来,次梯度不等式使上确界不超过 ;取 又使它不小于该值,故等号成立。由于 有限, 也有限。这个等价性不需要可微、凸性或另一个最大值存在定理。
三个手算共轭函数
例题 5.4.2
(二次函数的共轭)
对 上的 ,配方得 ,所以 ,上确界在 取得。(1) 的等号恰好在 时成立,与定理对可微函数的预测一致。
例题 5.4.3
(绝对值的共轭)
对 ,若 ,则 ,而 达到零;若 ,令 沿 的符号方向趋向无穷,则 无界。因此 。在 ,(1) 的等号为 ,给出熟悉的 ;当 ,等号迫使 且 ,所以 。
例题 5.4.4
(指示函数的共轭:支撑函数)
对非空集合 ,,因为 以外的点贡献 。这称为 的支撑函数。若 ,它在 时为 ,在 时为 。这里上确界是在真正的可行集合上取的,而不是自动取遍整个 。对无界集合 ,同样的计算给出: 时 , 时为 ;共轭在整条半直线上取值 。
下例由两个不同函数得到同一个共轭,于是自然要问:共轭究竟记住了什么?
反例模式
共轭不保留任意非凸细节
令 ,其他点取 ,则 。区间 的指示函数也有同一共轭,但在 处前者为 ,后者为零。因此不能不加条件地说取两次共轭便能还原任意函数;还原定理需要闭凸等假设。
等式约束的对偶下界
设 为 实矩阵,考虑
每个乘子都给出一个下界。
命题 5.4.5
(等式约束的弱对偶)
对每个 及每个可行 ,
因此即使两个最优值都没有取得,仍有 。
证明
(以 为斜率的 Fenchel 不等式)
若 ,无需证明。否则把 代入 (1):,再由可行性 ,右边就是 。若 ,则 ,不等式自然成立。对可行 取下确界,再对 取上确界,便得最后一个结论。
转置前的负号来自拉格朗日(Lagrange)函数 ;采用相反符号也可以,但必须前后一致。
定理 5.4.6
(原问题与对偶问题的解构成最优证书)
若 可行、,且 ,则 在约束 下最小化 、 最大化 ,而且 。
证明
(使两个界相等)
由等号定理及可行性,,所以 。弱对偶说任何对偶值都不超过任何可行目标值,因此对所有 及所有可行 都有 ,两者均为最优。
这是充分证书;没有额外假设时,不能断言这样的乘子必定存在。
常见错误
(把证书定理倒过来读)
定理并没有说每个约束问题都有满足 的乘子。没有进一步假设时,对偶下界可以严格小于原问题的值。对 上的 及约束 ,原问题的值为 ,而 给出 ,故 。
例题 5.4.7
(线性等式下的最小范数)
最小化 ,条件为 。这里 ,逐坐标配方得 。因此 ,在 取得最大值 。可行点 的目标值也是 ,且 。两个界相等,便严格证明了全局最优性。
概念视角几何
证书需要上下两个界
可行点给出原问题最优值的上界,乘子给出下界,两界相等便封闭了间隙。单有驻点方程而点不可行,或单有可行点,都不足以证明最优。
练习与解答
快速检查
(求 的共轭及上确界取得的位置。)
配方前先平移变量。
解答 · 答案
令 ,则 。配方得 ,在 ,即 取得。
快速检查
(求 的共轭及次微分 。)
在区间上最大化一个线性函数。
解答 · 答案
在 上最大化 : 时得到 , 时得到 。在 ,不等式 对所有 成立,恰好当 。因此 。区间外左边为 ,不构成额外限制。
快速检查
(最小化 ,条件为 。利用 求对偶最大点。)
对偶函数只在 时有限。
解答 · 答案
唯一可行点为 ,目标值为 。当 时对偶值为 ,否则为 ,故在 取得最大值 。也可验证 。原问题与对偶问题的值相等。
快速检查
(对无约束函数 ,求 ,并解释为何这个精确下界不给出最小点。)
考虑 (1) 的等号能否成立。
解答 · 答案
,所以 (1) 给出精确下确界 。但每个有限 都满足 ,故等号从不成立,下确界不被取得。精确的下界未必能达到。