不等式为何需要不同的罚项
等式残差应趋近零;不等式残差则只需变成非正:严格负值代表容许的松弛量。把整个残差平方,会把松弛也当成误差,因而可能改变最优化问题。在 gi(x)≤0 的约定下,不等式乘子也必须保持非负。若照搬等式更新而不维持符号限制,便可能破坏对偶问题作为下界的意义。
正部增广拉格朗日(Lagrange)函数尊重这两个区别。其乘子更新是到非负象限的 Euclidean 投影。我们会推导公式,证明精确最小化实现了受约束对偶问题上的近端步,并在有限维、光滑凸模型中建立收敛。定理包括取到及约束规范假设,并非对任意非凸问题或近似内层求解法的断言。
模型与基本假设
考虑
p∗=min{f(x):x∈Rn, gi(x)≤0, i=1,…,m},q(z)=xinf{f(x)+zTg(x)},z∈R+m.
假设 f,g1,…,gm 都是 Rn 上有限值、连续可微的凸函数;有限的原问题最小值取到;且存在严格可行点 xs,使所有 gi(xs)<0。分离、次梯度与强对偶单元中已证的 Slater 定理于是提供至少一个取到的对偶最大点 z∗,满足 q(z∗)=p∗。等价地,下述收敛证明也可直接从原问题与对偶问题均取到且零间隙开始;严格可行性只是保证这些事实的一条充分途径。它不用来断言内层最小点存在。
固定 c>0,取 λ0≥0,并额外假设下文每个实际使用的内层问题都取到最小值。例如,若 f 是强制的,这便自动成立:增广目标不小于 f(x)−∥λk∥2/(2c),且连续,所以其下水平集有界,最小值也取到。只有在讨论原问题点的聚点及到解集的距离时,才另外假设所选原问题最小点构成有界序列。
定义 11.2.1
(正部增广拉格朗日函数与精确外层迭代)
对向量 v,以 [v]+ 表示逐分量的 max(vi,0)。对 c>0 及 λ≥0,定义
Φc(u,λ)=2c∥[λ+cu]+∥2−∥λ∥2,Lc(x,λ)=f(x)+Φc(g(x),λ).一次精确外层迭代任选
xk+1∈xargminLc(x,λk),λk+1=[λk+cg(xk+1)]+.
定理不要求固定参数 c 增至无穷。但每次迭代仍须有精确且取到的最小点;计算方便不能替代这个假设。
从最大化推导正部公式
固定 u,λ,对 z 配方:
zTu−2c1∥z−λ∥2=−2c1∥z−(λ+cu)∥2+λTu+2c∥u∥2.
在 z≥0 上,唯一最大点是 z=[λ+cu]+,即 λ+cu 到非负象限的投影。逐坐标代入可得
Φc(u,λ)=z≥0max{zTu−2c1∥z−λ∥2}.
确切地说,若 λi+cui>0,该坐标的贡献是 λiui+cui2/2;否则最大值是 −λi2/(2c)。两个值及其一阶导数在 λi+cui=0 处吻合。因此 Φc 关于 u 连续可微,梯度为 [λ+cu]+;它也是凸函数,且对 u 的每个坐标单调不减。另一种看法是,上述最大化把 Lc(⋅,λ) 写成凸函数 f+zTg 减去常数后的逐点上确界。因此 Lc 为凸,其梯度是
∇xLc(x,λ)=∇f(x)+i=1∑m[λi+cgi(x)]+∇gi(x).
在精确内层最小点,此梯度为零。以投影更新定义 z=λ+,便使 x 成为普通凸拉格朗日函数 f+zTg 的驻点,所以它也是该函数的全局最小点。特别地,
q(z)=f(x)+zTg(x)>−∞.
这是由原问题最小化通往对偶函数的桥梁。只计算投影而没有最小化内层目标,并不能建立这个等式。
概念视角结构
投影就是符号约束的最优性条件
对 z=[λ+cg(x)]+ 和任何 w≥0,Euclidean 投影给出
(λ+cg(x)−z)T(w−z)≤0,g(x)T(w−z)≤c1(z−λ)T(w−z).这个不等式取代了精确罚函数与增广拉格朗日单元中等式约束方法的残差恒等式。若 zi>0,更新满足 zi−λi=cgi(x)。若 zi=0,约束可以严格松弛,上述等式未必成立。但投影不等式在两种情形下都成立,并提供收敛证明所需的符号。
精确的近端对偶恒等式
定理 11.2.2
(精确内层求解给出唯一近端对偶步)
在上述凸且可微的假设下,设 x 最小化 Lc(⋅,λ),其中 c>0、λ≥0。则 z=[λ+cg(x)]+ 是
q(w)−2c1∥w−λ∥2在 w≥0 上的唯一最大点。因此,无论选哪个精确原问题最小点,都产生同一个下一乘子,即使其原问题坐标可以不同。
对任何 w≥0,q 的定义及精确驻点条件给出
q(w)≤f(x)+wTg(x)=q(z)+g(x)T(w−z)≤q(z)+c1(z−λ)T(w−z).减去 ∥w−λ∥2/(2c) 并展开平方,得到更强的上界
q(w)−2c∥w−λ∥2≤q(z)−2c∥z−λ∥2−2c∥w−z∥2.所以 z 最大化近端式,其他点除非等于 z,否则值必严格较小。若 q(w)=−∞,不等式直接成立。这里没有未经证明地交换下确界与最大值;证明是构造一对原问题点与对偶点,然后直接验证其全局不等式。
精确收敛及适用范围
定理 11.2.3
(固定参数的不等式增广拉格朗日法收敛)
在基本假设及精确、取到的内层最小化下,λk 收敛至一个对偶最大点,[g(xk+1)]+→0,且 f(xk+1)→p∗。对每个 i 也有 λk+1,igi(xk+1)→0。所选原问题点序列的每个聚点都是原问题最优点。若此序列有界,便有聚点,且它到原问题解集的距离趋近零。若解集只有一点,则有界的原问题点序列收敛至该点。
证明分两部分:先处理乘子,再由乘子读出原问题的结论。
对偶迭代点的距离不等式
令 z=λk+1、λ=λk、d=z−λ。在配方前的不等式中取 w=z∗,并用 q(z∗)=p∗,便得
c[p∗−q(z)]≤dT(z∗−z).平方距离恒等式于是给出
∥z−z∗∥2≤∥λ−z∗∥2−∥d∥2−2c[p∗−q(z)].增量的范数平方非负,对偶间隙则由弱对偶保证非负。到任何对偶最优点的距离单调不增,故乘子有界。从 k=0 至 T−1 求和,得到
k=0∑T−1∥λk+1−λk∥2≤∥λ0−z∗∥2,k=0∑T−1[p∗−q(λk+1)]≤2c∥λ0−z∗∥2.因此 d→0,对偶间隙也趋近零。在有限维中,有界乘子序列有收敛子序列。对偶函数是连续仿射函数族的下确界,故上半连续。因此它在该子序列极限处的值至少为 p∗;再由弱对偶,该极限为对偶最优点。把这个特定极限取作 z∗,同一距离不等式仍成立。这些距离单调不增,且有子序列趋近零,故整个乘子序列收敛至该极限。
恢复可行性、互补性与目标值
整个向量 g(x) 未必趋近零。相反,若 gi(x)>0,当前非负乘子使 zi=λi+cgi(x)>0,所以
0≤[gi(x)]+≤∣di∣/c.这就证明了正部违约量趋于零。此外,当 zi>0 时,cgi(x)=di;当 zi=0 时,下列两个乘积均为零。因此每个坐标都满足精确恒等式
zigi(x)=zidi/c.由乘子有界和 d→0,得到逐分量的渐近互补性及 zTg(x)→0。再由 f(x)=q(z)−zTg(x),便得目标收敛。这个证明不需要设法控制负的松弛量 gi(x) 本身。
若某原问题子序列收敛至 xˉ,连续性给出 g(xˉ)≤0 和 f(xˉ)=p∗。在有界假设下,若到闭解集的距离不趋近零,便有一个子序列与解集保持至少某个 ε>0 的距离;但它有进一步的子序列收敛至最优点,矛盾。唯一性于是迫使原问题点收敛。若没有有界性,这些紧致性步骤并不能凭空产生聚点。
证明透视
精确性、符号约束与紧致性分别用在哪里
精确内层驻点条件把 q(λk+1) 识别为所选原问题点的拉格朗日值,从而建立近端及距离不等式。符号约束只通过投影不等式进入;它是不等式而非等式约束情形中的等式,但方向仍然正确,给出 c[p∗−q(z)]≤dT(z∗−z)。其后对偶部分全靠距离不等式:距离单调使乘子有界,裂项求和迫使 d→0 及对偶间隙趋近零。所有原问题结论都经由两个坐标恒等式 [gi]+≤∣di∣/c 及 zigi=zidi/c 从 d→0 读出,所以从不需要控制负的松弛量。有限维紧致性先用于有界乘子,以取得最优极限;只有原问题点也有界时,才另外用于这些点。目标有极限、违约量趋于零,不能控制沿着不改变两者的方向任意移动。
透视的最后一句并非技术细节,一个带平坦方向的例子就能说明。
令 f(x,y)=x2/2、g(x,y)=−1。处处严格可行,原问题解是所有 (0,y)。从 λ0=0 开始。乘子为零时 [λ0+cg]+=0,所以增广目标是 x2/2,与 y 无关,每个 (0,y) 都是精确内层最小点。第 k 步选 (0,k)。投影乘子保持 [0−c]+=0,目标等于最优值 0,也没有违约,但原问题点序列无界,没有聚点。这符合定理,因为其原问题结论以有界性为条件;它也说明为何须另外列出这个条件。
算例与失效检查
最小化 f(x)=(x−1)2/2,受 g(x)=x≤0 约束。解为 x∗=0、p∗=1/2,最优乘子为一。内层驻点条件是 x−1+z=0,而 z=[λ+cx]+。对 λ≥0、c>0,相容分支为
x+=1+c1−λ,λ+=z=1+cλ+c>0.所以 λ+−1=(λ−1)/(1+c)。当 c=2、λ0=0,前两对是 (x1,λ1)=(1/3,2/3) 及 (x2,λ2)=(1/9,8/9)。早期内层解不可行,但违约量趋近零,目标趋近 1/2。因乘子会变动,有限且固定的 c 已足够。
最小化 (x+1)2/2,受 x≤0 约束,取 c=1、λ0=3。内层驻点式是 x+1+[λ+x]+=0。第一步在正分支给出 x1=−2、λ1=1;因 3−2=1>0,分支相容。第二步给出 x2=−1、λ2=0,恰在分支交界。其后保持 (x,λ)=(−1,0)。残差 g(x)=−1 保持严格为负,这正是应有的情形:约束在最优点不活跃。由于其乘子为零,互补性成立。
反例模式
把松弛平方会解成另一个问题
在不活跃约束的例子中,若在 λ=0、c=1 改用等式形式的二次罚函数,就是在 x=−1/2 处最小化 (x+1)2/2+x2/2,而得不到原问题最优点 −1。若还采用无符号限制的等式乘子更新,便有 x+=−(1+λ)/2、λ+=(λ−1)/2。从零开始会得到 λk→−1,是不合法的不等式乘子;同时 xk→0,是目标值为 1/2 的等式约束解。原不等式问题的最优值却为零。正部公式及投影同时修复这两个错误。
不能直接删去严格可行性,却仍保留定理中对偶取到的前提。考虑最小化 x,受 x2≤0 约束。原问题值零取到,但当 z>0 时 q(z)=xinf(x+zx2)=−1/(4z),而 q(0)=−∞。对偶上确界为零,却不在任何有限乘子处取到。距离论证没有可作基准的 z∗。这是其假设不成立,而非与定理矛盾。
诚实的内层停止准则
对拟定的内层点 x,计算 z=[λ+cg(x)]+。可计算的驻点残差是
e=∇f(x)+i∑zi∇gi(x)=∇xLc(x,λ).
精确证明使用了 e=0。两个诱人的停止规则都不能提供它。
单靠原问题违约量及乘子变化不能推出 e=0。在不活跃约束的标量例子中,取 λ=0,反复选 x=0,便永远有零违约量及零乘子变化,但目标为 1/2 而非零,且 e=1。
即使固定的小正梯度容许值,也不保证渐近精确最优化。对任何 0<ε<1,反复选 x=−1+ε/2 且 λ=0。该点严格可行,投影后的下一乘子为零;内层梯度为 ε/2,低于容许值 ε。但固定的目标差仍为 ε2/8>0。由这个停止规则宣称精确收敛是错误的。
若有额外信息,可得到有效的内层误差证书。若已知 Lc(⋅,λ) 是 μ-强凸的,μ>0,其精确最小点为 xc,则支撑二次不等式给出
Lc(x,λ)−Lc(xc,λ)≤2μ∥e∥2.
证法是用 Lc(x,λ)+eT(y−x)+μ∥y−x∥2/2 从下方控制 Lc(y,λ),再对 y 最小化右边。这是内层目标误差证书,并不证明带任意误差的外层方法收敛。完整的非精确定理必须指定误差怎样下降或累积,以及它怎样扰动对偶不等式;这不在此处所证精确方法的范围内。
练习
快速检查
(对 c=2、λ=(1,3)T、u=(−1,1)T,直接及利用最大化公式计算 z=[λ+cu]+ 和 Φc(u,λ)。)
解答
λ+cu=(−1,5)T,所以 z=(0,5)T。正部公式给出 (25−10)/4=15/4。最大化式中,zTu=5,且 ∥z−λ∥2=(0−1)2+(5−3)2=5,故值为 5−5/4=15/4;逐坐标投影证明这就是最大值。
快速检查
(在活跃约束的标量例子中,取 c=1、λ0=2。求 x1,λ1,x2,λ2,并检查可行的内层点也可以有正乘子。)
解答
x1=−1/2、λ1=3/2,再有 x2=−1/4、λ2=5/4。两个原问题点都严格满足不等式,乘子却为正。互补松弛性是极限最优点的条件,不是每个中间内层解都要满足的要求。实际上,λ1x1=−3/4=λ1(λ1−λ0)/c。
快速检查
(若 D=∥λ0−z∗∥,利用距离不等式给出前 T 个原问题点中最小的正部违约量平方的上界。这是否为末次迭代速率?)
把增量平方和与 [gi]+≤∣di∣/c 结合。
解答
可求和性给出 k=0∑T−1∥λk+1−λk∥2≤D2。由 ∥[g(xk+1)]+∥2≤∥λk+1−λk∥2/c2,最小的违约量平方至多为 D2/(c2T)。这是最佳迭代上界。证明已建立整个违约量序列收敛,但这个平均论证不建立 1/T 的末次迭代上界。
快速检查
(若一个 2-强凸的内层目标的梯度残差范数至多为 0.01,可得什么目标误差上界?固定这个上界是否证明外层精确收敛?)
解答
误差至多为 0.012/(2⋅2)=0.000025。这给出一次内层求解的目标误差上界。标量反例表明,反复使用固定容许值不能建立外层精确收敛;非精确外层定理需要明确的额外误差条件。
快速检查
(在不活跃约束的标量例子中取 c=1,由 λ0=1/2 出发。求 x1 及 λ1。)
解答
内层驻点式为 x+1+[21+x]+=0。正分支给出 x=−3/4,但此时 21+x=−1/4<0,分支不相容。零分支给出 x+1=0,故 x1=−1,且确有 21−1<0;因此 λ1=[21−1]+=0。一步精确迭代就到达最优对 (−1,0):只要 λ0−1≤0,零分支就相容,所以在这个不活跃的约束上,任何 λ0≤1 的起始乘子都会在一步内被舍去。