动机
处理约束可以直接拒绝不可行点,但这不是唯一方法。罚函数对违反约束收取代价,允许无约束求解器探索不可行点。二次罚函数的参数越大,违反的代价越高,但有限参数仍可能留下非零残差。非光滑的精确罚函数则可在有限参数下重现受约束解,只要罚系数大于某个最优乘子的大小。
增广拉格朗日(Lagrange)函数结合乘子和二次罚项。乘子更新并非任意修正:在凸等式约束问题中,它是对偶目标的近端步。本节推导此恒等式,并在子问题精确求解且取得最小值的假设下证明收敛。实际计算常用近似解,但以下证明不会暗中涵盖未指定的误差或停止容差。
定义
考虑等式约束问题
p ∗ = inf { f ( x ) : x ∈ R n , A x = b } , p_* = \inf\{f(x):x\in\mathbb R^n,\ Ax=b\}, p ∗ = inf { f ( x ) : x ∈ R n , A x = b } ,
其中 f : R n → R f:\mathbb R^n\to\mathbb R f : R n → R 凸且连续可微,A ∈ R m × n A\in\mathbb R^{m\times n} A ∈ R m × n 。记 r ( x ) = A x − b r(x)=Ax-b r ( x ) = A x − b ,拉格朗日对偶函数为
q ( λ ) = inf x [ f ( x ) + λ T r ( x ) ] , λ ∈ R m . q(\lambda)=\inf_x[f(x)+\lambda^Tr(x)],\qquad \lambda\in\mathbb R^m. q ( λ ) = x inf [ f ( x ) + λ T r ( x )] , λ ∈ R m .
主要结果均假设存在原问题最小点 x ∗ x_* x ∗ 和对偶最大点 λ ∗ \lambda_* λ ∗ ,它们有共同的有限值 p ∗ = q ( λ ∗ ) p_*=q(\lambda_*) p ∗ = q ( λ ∗ ) ,因此对偶间隙为零。弱对偶 q ( λ ) ≤ p ∗ q(\lambda)\le p_* q ( λ ) ≤ p ∗ 总是成立。这些都是明确的假设;单有凸性不能保证取得最优值。
定义 11.1.1
(增广拉格朗日函数、精确罚函数与乘子法)
对 c > 0 c\gt0 c > 0 及 ρ > 0 \rho\gt0 ρ > 0 ,定义增广拉格朗日函数及精确罚目标
L c ( x , λ ) = f ( x ) + λ T r ( x ) + c 2 ∥ r ( x ) ∥ 2 2 , P ρ ( x ) = f ( x ) + ρ ∥ r ( x ) ∥ 1 . L_c(x,\lambda)=f(x)+\lambda^Tr(x)+\frac c2\|r(x)\|_2^2,
\qquad P_\rho(x)=f(x)+\rho\|r(x)\|_1. L c ( x , λ ) = f ( x ) + λ T r ( x ) + 2 c ∥ r ( x ) ∥ 2 2 , P ρ ( x ) = f ( x ) + ρ ∥ r ( x ) ∥ 1 . 给定 λ k \lambda_k λ k ,精确乘子法 选取 L c ( ⋅ , λ k ) L_c(\cdot,\lambda_k) L c ( ⋅ , λ k ) 的全局最小点 x k + 1 x_{k+1} x k + 1 ,再令
λ k + 1 = λ k + c r ( x k + 1 ) . \lambda_{k+1}=\lambda_k+c\,r(x_{k+1}). λ k + 1 = λ k + c r ( x k + 1 ) .
记 r k + 1 : = r ( x k + 1 ) r_{k+1}:=r(x_{k+1}) r k + 1 := r ( x k + 1 ) 。我们假设每个这样的子问题都取得最小值,不要求最小点唯一。公式使用所选最小点的残差及固定的 c c c ,不要求 c → ∞ c\to\infty c → ∞ 。次序很重要:先用旧乘子最小化,再计算残差并更新乘子。若颠倒次序或使用不同的残差,便得到不同的迭代,必须重新建立下文的驻点恒等式。
定理/命题
在上述原问题与对偶问题均取得最优值及零间隙的假设下,若 ρ > ∥ λ ∗ ∥ ∞ \rho\gt\|\lambda_*\|_\infty ρ > ∥ λ ∗ ∥ ∞ ,则 P ρ P_\rho P ρ 的每个全局最小点都是原问题的可行最优点;每个原问题最小点也最小化 P ρ P_\rho P ρ 。当两个常数相等时,可能出现不可行的罚函数最小点。
在相同假设下,若每个增广子问题都精确求解并取得最小点,则乘子法满足 λ k → λ ˉ \lambda_k\to\bar\lambda λ k → λ ˉ ,其中 λ ˉ \bar\lambda λ ˉ 是某个对偶最优点;r ( x k ) → 0 r(x_k)\to0 r ( x k ) → 0 且 f ( x k ) → p ∗ f(x_k)\to p_* f ( x k ) → p ∗ 。原变量序列的每个聚点都可行且是原问题最优点。当最小点不唯一时,定理不断言原变量序列有界或收敛。
证明思路
绝对值罚项为何可以精确
对偶最优性表示每个 x x x 都满足 f ( x ) + λ ∗ T r ( x ) ≥ q ( λ ∗ ) = p ∗ f(x)+\lambda_*^Tr(x)\ge q(\lambda_*)=p_* f ( x ) + λ ∗ T r ( x ) ≥ q ( λ ∗ ) = p ∗ 。由 Hölder 不等式,
P ρ ( x ) ≥ p ∗ + ρ ∥ r ( x ) ∥ 1 − λ ∗ T r ( x ) ≥ p ∗ + ( ρ − ∥ λ ∗ ∥ ∞ ) ∥ r ( x ) ∥ 1 . P_\rho(x)\ge p_*+\rho\|r(x)\|_1-\lambda_*^Tr(x)
\ge p_*+(\rho-\|\lambda_*\|_\infty)\|r(x)\|_1. P ρ ( x ) ≥ p ∗ + ρ ∥ r ( x ) ∥ 1 − λ ∗ T r ( x ) ≥ p ∗ + ( ρ − ∥ λ ∗ ∥ ∞ ) ∥ r ( x ) ∥ 1 . 原问题最小点的残差为零,且 P ρ = p ∗ P_\rho=p_* P ρ = p ∗ 。若系数严格为正,每个不可行点的罚值严格大于 p ∗ p_* p ∗ ,所以罚函数最小点都可行且最优。已假设存在的原问题最小点本身也证明罚函数最小点存在。这是关于精确目标的全局结论;罚函数的局部最小点可能需要另行分析,近似的数值最小点也是如此。
至于增广拉格朗日定理,证明先确定乘子更新的含义,然后只研究乘子。
乘子更新是对偶近端步
在精确子问题最小点,可微性与凸性给出
0 = ∇ f ( x k + 1 ) + A T [ λ k + c r ( x k + 1 ) ] = ∇ f ( x k + 1 ) + A T λ k + 1 . 0=\nabla f(x_{k+1})+A^T[\lambda_k+c r(x_{k+1})]
=\nabla f(x_{k+1})+A^T\lambda_{k+1}. 0 = ∇ f ( x k + 1 ) + A T [ λ k + cr ( x k + 1 )] = ∇ f ( x k + 1 ) + A T λ k + 1 . 所以 x k + 1 x_{k+1} x k + 1 全局最小化乘子 λ k + 1 \lambda_{k+1} λ k + 1 下的普通拉格朗日函数,且 q ( λ k + 1 ) = f ( x k + 1 ) + λ k + 1 T r k + 1 q(\lambda_{k+1})=f(x_{k+1})+\lambda_{k+1}^Tr_{k+1} q ( λ k + 1 ) = f ( x k + 1 ) + λ k + 1 T r k + 1 。对任意 μ \mu μ ,在同一点估计下确界,得超梯度不等式
q ( μ ) ≤ q ( λ k + 1 ) + ( μ − λ k + 1 ) T r k + 1 . q(\mu)\le q(\lambda_{k+1})+(\mu-\lambda_{k+1})^Tr_{k+1}. q ( μ ) ≤ q ( λ k + 1 ) + ( μ − λ k + 1 ) T r k + 1 . 由 r k + 1 = ( λ k + 1 − λ k ) / c r_{k+1}=(\lambda_{k+1}-\lambda_k)/c r k + 1 = ( λ k + 1 − λ k ) / c ,配方可见 λ k + 1 \lambda_{k+1} λ k + 1 唯一地最大化
q ( μ ) − 1 2 c ∥ μ − λ k ∥ 2 . q(\mu)-\frac1{2c}\|\mu-\lambda_k\|^2. q ( μ ) − 2 c 1 ∥ μ − λ k ∥ 2 . 具体地说,超梯度不等式把任意 μ \mu μ 处的值与 λ k + 1 \lambda_{k+1} λ k + 1 处的值之差控制在 − ∥ μ − λ k + 1 ∥ 2 / ( 2 c ) -\|\mu-\lambda_{k+1}\|^2/(2c) − ∥ μ − λ k + 1 ∥ 2 / ( 2 c ) 以下。为看清抵消,令 d = μ − λ k + 1 d=\mu-\lambda_{k+1} d = μ − λ k + 1 、v = λ k + 1 − λ k v=\lambda_{k+1}-\lambda_k v = λ k + 1 − λ k 。超梯度项贡献 d T v / c d^Tv/c d T v / c ,而展开二次罚项贡献 − [ 2 d T v + ∥ d ∥ 2 ] / ( 2 c ) -[2d^Tv+\|d\|^2]/(2c) − [ 2 d T v + ∥ d ∥ 2 ] / ( 2 c ) ,交叉项相消。这直接证明了近端解释;即使原子问题有多个最小点,下一个乘子仍唯一。
Fejér 不等式及收敛
在超梯度不等式中取 μ = λ ∗ \mu=\lambda_* μ = λ ∗ ,并使用 q ( λ ∗ ) = p ∗ q(\lambda_*)=p_* q ( λ ∗ ) = p ∗ 。展开距离平方得
∥ λ k − λ ∗ ∥ 2 − ∥ λ k + 1 − λ ∗ ∥ 2 ≥ ∥ λ k + 1 − λ k ∥ 2 + 2 c [ p ∗ − q ( λ k + 1 ) ] . \|\lambda_k-\lambda_*\|^2-\|\lambda_{k+1}-\lambda_*\|^2
\ge\|\lambda_{k+1}-\lambda_k\|^2
+2c[p_*-q(\lambda_{k+1})]. ∥ λ k − λ ∗ ∥ 2 − ∥ λ k + 1 − λ ∗ ∥ 2 ≥ ∥ λ k + 1 − λ k ∥ 2 + 2 c [ p ∗ − q ( λ k + 1 )] . 由弱对偶,右边两项非负。求和表明乘子序列有界、乘子增量的平方和有限,而且非负对偶间隙之和有限。因此 λ k + 1 − λ k → 0 \lambda_{k+1}-\lambda_k\to0 λ k + 1 − λ k → 0 ,从而 r k + 1 → 0 r_{k+1}\to0 r k + 1 → 0 ,并有 q ( λ k + 1 ) → p ∗ q(\lambda_{k+1})\to p_* q ( λ k + 1 ) → p ∗ 。
在有限维中,有界序列存在收敛子列。对偶函数是关于 λ \lambda λ 的连续仿射函数族的下确界,故上半连续。子列极限因而是对偶最优点:其值至少是上极限 p ∗ p_* p ∗ ,而弱对偶又给出至多 p ∗ p_* p ∗ 。对这个极限再次使用距离不等式,距离单调不增,而某个子列的距离趋于零,所以整个序列都收敛至该对偶最优点。
最后,f ( x k + 1 ) = q ( λ k + 1 ) − λ k + 1 T r k + 1 → p ∗ f(x_{k+1})=q(\lambda_{k+1})-\lambda_{k+1}^Tr_{k+1}\to p_* f ( x k + 1 ) = q ( λ k + 1 ) − λ k + 1 T r k + 1 → p ∗ ,因为乘子有界而残差趋于零。若原变量有收敛子列,由 r r r 及 f f f 的连续性,其极限可行且值为 p ∗ p_* p ∗ 。此证明不保证原变量存在聚点;没有有界性或强制性假设时可能没有聚点。
证明透视
一个恒等式,之后只看乘子 证明的关键是一个恒等式。内层问题在旧乘子 λ k \lambda_k λ k 处的精确驻点条件,被改写为普通拉格朗日函数在新乘子 λ k + 1 \lambda_{k+1} λ k + 1 处的驻点条件;精确性及“先最小化、后更新”的次序正是在这里用到。凸性只用一次:把该驻点提升为全局最小点,从而得到以 r k + 1 r_{k+1} r k + 1 为超梯度的超梯度不等式。更新规则把 r k + 1 r_{k+1} r k + 1 转化为增量 ( λ k + 1 − λ k ) / c (\lambda_{k+1}-\lambda_k)/c ( λ k + 1 − λ k ) / c ,代入 λ ∗ \lambda_* λ ∗ 便得 Fejér 单调性;零间隙假设 q ( λ ∗ ) = p ∗ q(\lambda_*)=p_* q ( λ ∗ ) = p ∗ 使间隙项非负。此后论证只涉及乘子:有界性、增量可求和从而残差趋于零,以及用紧致性和上半连续性确定极限。原变量的信息只在最后经 f ( x k + 1 ) = q ( λ k + 1 ) − λ k + 1 T r k + 1 f(x_{k+1})=q(\lambda_{k+1})-\lambda_{k+1}^Tr_{k+1} f ( x k + 1 ) = q ( λ k + 1 ) − λ k + 1 T r k + 1 回到论证中。没有任何一步给出原变量的界,所以定理不断言它们收敛。
近似解会改变什么
精确驻点方程是通往超梯度与近端恒等式的桥梁。若子问题只求解到固定的目标容差,未必满足该方程,证明不能直接忽略误差。可以在指定的可求和误差及合适的残差条件下分析近似近端步,但正确的条件取决于如何度量精度。本节只证明精确方法,不断言固定或未指定的内层容差也能继承其收敛性。
乘子如何改变二次罚法
概念视角 结构
乘子的作用 由 q q q 的定义及零间隙假设 q ( λ ∗ ) = p ∗ q(\lambda_*)=p_* q ( λ ∗ ) = p ∗ ,每个 x x x 都满足以下关于增广目标的不等式:
L c ( x , λ ∗ ) ≥ p ∗ + c 2 ∥ r ( x ) ∥ 2 . L_c(x,\lambda_*)\ge p_*+\frac c2\|r(x)\|^2. L c ( x , λ ∗ ) ≥ p ∗ + 2 c ∥ r ( x ) ∥ 2 . 原问题最优点使等号成立。因此即使固定有限的 c > 0 c\gt0 c > 0 ,L c ( ⋅ , λ ∗ ) L_c(\cdot,\lambda_*) L c ( ⋅ , λ ∗ ) 的每个最小点都可行且是原问题最优点。此结论假设已经知道正确的乘子;迭代的目的则是在不知道它时趋近对偶最优点,上面的证明明确说明了沿途能得到什么结论。
标量例子使这一区别更清楚。乘子为零时,内层解是不可行的纯罚点 1 / ( 1 + c ) 1/(1+c) 1/ ( 1 + c ) ;乘子为一时,相同固定 c c c 的子问题在零处取得最小值。改变来自线性乘子项抵消了目标函数违反等式的一阶倾向,而不是有限的二次项本身突然变得精确。
增大罚系数与数值条件数
增大 c c c 可减少纯罚法的违反量,但也可能使内层最小化在不同方向上的曲率差距加大。考虑 f ( x 1 , x 2 ) = 1 2 ( x 1 2 + x 2 2 ) f(x_1,x_2)=\tfrac12(x_1^2+x_2^2) f ( x 1 , x 2 ) = 2 1 ( x 1 2 + x 2 2 ) ,约束 x 1 = 1 x_1=1 x 1 = 1 。其二次罚函数的 Hessian 为 diag ( 1 + c , 1 ) \operatorname{diag}(1+c,1) diag ( 1 + c , 1 ) ,谱条件数为 1 + c 1+c 1 + c 。对条件数敏感的求解器在 c c c 增大时可能需要更多工作量。乘子法提供另一种权衡:可固定 c c c 并更新线性项,但仍需按所用收敛定理的要求求解每个子问题。
约束的缩放会改变表面上的数值参数。以可逆矩阵 D D D 把 A x − b = 0 Ax-b=0 A x − b = 0 换成 D ( A x − b ) = 0 D(Ax-b)=0 D ( A x − b ) = 0 ,可行集不变,但欧氏二次罚项变成 ∥ D ( A x − b ) ∥ 2 \|D(Ax-b)\|^2 ∥ D ( A x − b ) ∥ 2 ,对不同残差方向赋予不同权重。乘子也相应变换:若 λ ~ \widetilde\lambda λ 乘以缩放后的残差,原乘子为 D T λ ~ D^T\widetilde\lambda D T λ 。因此应结合约束的规范化方式来解读罚阈值与条件数。
可计算的检查及其限制
更新式给出 ∥ r ( x k + 1 ) ∥ = ∥ λ k + 1 − λ k ∥ / c \|r(x_{k+1})\|=\|\lambda_{k+1}-\lambda_k\|/c ∥ r ( x k + 1 ) ∥ = ∥ λ k + 1 − λ k ∥/ c ,所以乘子的改变直接度量等式违反量。仅有小残差却不能证明近似最优:可行点的目标值可以任意大。精确内层驻点方程提供第二个检查:∇ f ( x k + 1 ) + A T λ k + 1 = 0 \nabla f(x_{k+1})+A^T\lambda_{k+1}=0 ∇ f ( x k + 1 ) + A T λ k + 1 = 0 。在定理的假设下,这些性质伴随目标值收敛;对近似实现,两类误差的大小及累积效果仍需另行分析。
距离不等式提供的定量信息
Fejér 不等式也给出有限次迭代的界。令 D = ∥ λ 0 − λ ∗ ∥ D=\|\lambda_0-\lambda_*\| D = ∥ λ 0 − λ ∗ ∥ ,把前 T T T 个不等式相加并舍去最后的非负距离平方,得到
∑ k = 0 T − 1 ∥ λ k + 1 − λ k ∥ 2 ≤ D 2 , ∑ k = 0 T − 1 [ p ∗ − q ( λ k + 1 ) ] ≤ D 2 2 c . \sum_{k=0}^{T-1}\|\lambda_{k+1}-\lambda_k\|^2\le D^2,
\qquad
\sum_{k=0}^{T-1}[p_*-q(\lambda_{k+1})]\le\frac{D^2}{2c}. k = 0 ∑ T − 1 ∥ λ k + 1 − λ k ∥ 2 ≤ D 2 , k = 0 ∑ T − 1 [ p ∗ − q ( λ k + 1 )] ≤ 2 c D 2 .
所以前 T T T 个残差中至少有一个的范数平方不超过 D 2 / ( c 2 T ) D^2/(c^2T) D 2 / ( c 2 T ) ,也至少有一个对偶间隙不超过 D 2 / ( 2 c T ) D^2/(2cT) D 2 / ( 2 c T ) ;两者未必出现在同一步。这些计算给出各列中最佳迭代的界,并未建立最后一次迭代的速率。定理中较强的极限结论由上文的可求和性和有限维紧致性得到。
近端推导也解释了为何下一个乘子不依赖所选的精确原问题最小点:每个选择给出的候选乘子都满足近端目标的同一个全局二次上界。两个不同的候选都必须是其唯一最大点,矛盾。原变量却仍可沿零空间方向不同,下面关于精确子问题极小点的练习展示了这一点。
例题详解
在 x = 0 x=0 x = 0 下最小化 f ( x ) = − x f(x)=-x f ( x ) = − x 。唯一的可行点的值为零,λ ∗ = 1 \lambda_*=1 λ ∗ = 1 时 q ( λ ∗ ) = 0 q(\lambda_*)=0 q ( λ ∗ ) = 0 ,其他乘子时为 − ∞ -\infty − ∞ 。若 ρ > 1 \rho\gt1 ρ > 1 ,− x + ρ ∣ x ∣ -x+\rho|x| − x + ρ ∣ x ∣ 在每个非零点都为正,唯一最小点是零。若 ρ = 1 \rho=1 ρ = 1 ,每个 x ≥ 0 x\ge0 x ≥ 0 的目标值都是零,故有不可行最小点。定理中的严格不等式不可省略。
在 x = 0 x=0 x = 0 下最小化 f ( x ) = 1 2 ( x − 1 ) 2 f(x)=\tfrac12(x-1)^2 f ( x ) = 2 1 ( x − 1 ) 2 。二次罚函数 1 2 ( x − 1 ) 2 + c 2 x 2 \tfrac12(x-1)^2+\tfrac c2x^2 2 1 ( x − 1 ) 2 + 2 c x 2 的最小点为 x = 1 / ( 1 + c ) x=1/(1+c) x = 1/ ( 1 + c ) ,对每个有限的 c > 0 c\gt0 c > 0 都非零。增大 c c c 会缩小违反量,却不会在有限参数下达到精确可行;原问题的乘子为 λ ∗ = 1 \lambda_*=1 λ ∗ = 1 。
对相同的 f f f 及 x = 0 x=0 x = 0 ,最小化 L c ( x , λ k ) L_c(x,\lambda_k) L c ( x , λ k ) 得 x k + 1 = ( 1 − λ k ) / ( 1 + c ) x_{k+1}=(1-\lambda_k)/(1+c) x k + 1 = ( 1 − λ k ) / ( 1 + c ) 、λ k + 1 = ( λ k + c ) / ( 1 + c ) \lambda_{k+1}=(\lambda_k+c)/(1+c) λ k + 1 = ( λ k + c ) / ( 1 + c ) 。所以 λ k + 1 − 1 = ( λ k − 1 ) / ( 1 + c ) \lambda_{k+1}-1=(\lambda_k-1)/(1+c) λ k + 1 − 1 = ( λ k − 1 ) / ( 1 + c ) 。对每个 c > 0 c\gt0 c > 0 ,乘子以几何速率收敛至一,残差趋于零。与纯二次罚法不同,固定 c c c 的乘子迭代能趋向精确可行。
常见错误
最优乘子给出罚系数的充分阈值;任意乘子不能套用相同的证明,而阈值取等号时可能有不可行最小点,第一个例题已说明这一点。
反例模式
由乘子估计定出的罚阈值 断言:乘子法一旦给出估计 λ k \lambda_k λ k ,任何 ρ > ∥ λ k ∥ ∞ \rho\gt\|\lambda_k\|_\infty ρ > ∥ λ k ∥ ∞ 都使 ℓ 1 \ell_1 ℓ 1 罚函数精确。取标量问题 f ( x ) = 1 2 ( x − 1 ) 2 f(x)=\tfrac12(x-1)^2 f ( x ) = 2 1 ( x − 1 ) 2 、x = 0 x=0 x = 0 ,并取 c = 2 c=2 c = 2 、λ 0 = 0 \lambda_0=0 λ 0 = 0 ,于是 λ 1 = 2 / 3 \lambda_1=2/3 λ 1 = 2/3 ;再取 ρ = 0.8 > λ 1 \rho=0.8\gt\lambda_1 ρ = 0.8 > λ 1 。对 x > 0 x\gt0 x > 0 ,罚函数 P ρ ( x ) = 1 2 ( x − 1 ) 2 + 0.8 ∣ x ∣ P_\rho(x)=\tfrac12(x-1)^2+0.8|x| P ρ ( x ) = 2 1 ( x − 1 ) 2 + 0.8∣ x ∣ 的导数为 x − 0.2 x-0.2 x − 0.2 ,在 x = 0.2 x=0.2 x = 0.2 为零,此处 P ρ = 0.32 + 0.16 = 0.48 < 0.5 = P ρ ( 0 ) P_\rho=0.32+0.16=0.48\lt0.5=P_\rho(0) P ρ = 0.32 + 0.16 = 0.48 < 0.5 = P ρ ( 0 ) 。所以罚函数最小点不可行。修正后的表述使用最优乘子:此处 λ ∗ = 1 \lambda_*=1 λ ∗ = 1 ;当 ρ > 1 \rho\gt1 ρ > 1 时,在 x > 0 x\gt0 x > 0 上斜率 x − 1 + ρ > 0 x-1+\rho\gt0 x − 1 + ρ > 0 ,在 x < 0 x\lt0 x < 0 上斜率 x − 1 − ρ < 0 x-1-\rho\lt0 x − 1 − ρ < 0 ,故零是唯一最小点。
另外两个错误涉及收敛定理,而非罚函数。
所述更新要求增广子问题取得最小值,收敛证明使用精确最小化,而不仅仅是“残差足够小”。可行点的目标值可以任意大;把残差与最优性联系起来的是第二个检查 ∇ f ( x k + 1 ) + A T λ k + 1 = 0 \nabla f(x_{k+1})+A^T\lambda_{k+1}=0 ∇ f ( x k + 1 ) + A T λ k + 1 = 0 。
对偶收敛及可行性本身不保证不唯一或无界的原变量序列收敛。若 A A A 有非平凡零空间,而 f f f 在其上不变,精确内层最小点就可以沿它漂移,下面关于精确子问题极小点的练习正说明了这一点。
总结
弱对偶把最优乘子转化为精确 ℓ 1 \ell_1 ℓ 1 罚函数的界;单独的二次罚项一般不精确。在凸等式情形,精确增广拉格朗日最小化产生对偶近端步;距离不等式给出乘子收敛、可行性和目标值收敛。假设包括原问题与对偶问题取得最优值、零间隙,以及内层精确求解且取得最小值。
练习
快速检查
(对 f ( x ) = − x f(x)=-x f ( x ) = − x 及约束 x = 0 x=0 x = 0 ,分别描述 ρ = 1 \rho=1 ρ = 1 和 ρ > 1 \rho\gt1 ρ > 1 时 P ρ P_\rho P ρ 的所有最小点。)
比较 − x + ρ ∣ x ∣ -x+\rho|x| − x + ρ ∣ x ∣ 在零两侧的斜率。
解答 · 答案 ρ = 1 \rho=1 ρ = 1 时,− x + ∣ x ∣ -x+|x| − x + ∣ x ∣ 在 [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) 上为零,在 x < 0 x\lt0 x < 0 时为正,所以所有 x ≥ 0 x\ge0 x ≥ 0 都是最小点。ρ > 1 \rho\gt1 ρ > 1 时,离开零的两侧目标值都为正,故零是唯一最小点。
快速检查
(对 f ( x ) = 1 2 ( x − 1 ) 2 f(x)=\tfrac12(x-1)^2 f ( x ) = 2 1 ( x − 1 ) 2 、x = 0 x=0 x = 0 、c = 2 c=2 c = 2 ,由 λ 0 = 0 \lambda_0=0 λ 0 = 0 出发,求 x 1 , λ 1 , x 2 , λ 2 x_1,\lambda_1,x_2,\lambda_2 x 1 , λ 1 , x 2 , λ 2 。)
解答 · 答案 由递推得 x 1 = 1 / 3 x_1=1/3 x 1 = 1/3 、λ 1 = 2 / 3 \lambda_1=2/3 λ 1 = 2/3 、x 2 = 1 / 9 x_2=1/9 x 2 = 1/9 、λ 2 = 8 / 9 \lambda_2=8/9 λ 2 = 8/9 。每次先用当前乘子作内层最小化,再加上 2 x k + 1 2x_{k+1} 2 x k + 1 更新乘子。
快速检查
(为何在此算法中,∥ λ k + 1 − λ k ∥ 2 \|\lambda_{k+1}-\lambda_k\|^2 ∥ λ k + 1 − λ k ∥ 2 可求和能推出可行性,却未必推出原变量收敛?)
解答 更新式给出 r ( x k + 1 ) = ( λ k + 1 − λ k ) / c r(x_{k+1})=(\lambda_{k+1}-\lambda_k)/c r ( x k + 1 ) = ( λ k + 1 − λ k ) / c ,故增量趋于零使残差趋于零。但它只控制 A x − b Ax-b A x − b ,不控制在 A A A 的零空间中的移动;不唯一的内层最小点可以沿该空间移动。
快速检查
(设 f ( x 1 , x 2 ) = 1 2 x 1 2 f(x_1,x_2)=\tfrac12x_1^2 f ( x 1 , x 2 ) = 2 1 x 1 2 ,约束 x 1 = 0 x_1=0 x 1 = 0 。解释为何即使残差及目标值收敛,仍可选取无界的精确子问题最小点序列。)
解答 增广目标只依赖 x 1 x_1 x 1 ,故可选任何使其最小的第一坐标,并令 x 2 , k = k x_{2,k}=k x 2 , k = k 。若 λ 0 = 0 \lambda_0=0 λ 0 = 0 ,精确最小化的第一坐标、所有残差及目标值都为零,但原变量序列无界。