增广拉格朗日法

增广拉格朗日法（augmented Lagrangian method）把约束乘子与约束残差的二次罚项合在一起，通过交替求解变量子问题和更新乘子来处理约束优化。它与只把罚参数不断增大的二次罚函数法有不同的纠偏机制。下面先讨论等式约束，乘子允许为任意实数。

固定罚参数也能逐步满足约束

考虑 $min\frac{1}{2}{x}^2$，要求 $x=1$。原问题只有一个可行点，最优值为 $1/2$。给定乘子 $\lambda$ 和罚参数 $\rho >0$，增广拉格朗日函数为 $$L_{\rho }(x,\lambda )=\frac{1}{2}{x}^2+\lambda (x-1)+\frac{\rho }{2}(x-1{)}^2.$$ 固定乘子求最小点，导数条件给出 $(1+\rho )x+\lambda -\rho =0$。随后把约束偏差反馈给乘子： $$x_{k+1}=\frac{\rho -{\lambda }_k}{1+\rho },{\lambda }_{k+1}={\lambda }_k+\rho (x_{k+1}-1).$$ 取 $\rho =1,{\lambda }_0=0$，依次得到 $(x_1,{\lambda }_1)=(1/2,-1/2)$、$(x_2,{\lambda }_2)=(3/4,-3/4)$、$(x_3,{\lambda }_3)=(7/8,-7/8)$。乘子越来越负，使下一次子问题对偏小的 $x$ 施加更强的纠偏。

ρ 固定为一，乘子趋于 −1，变量趋于一；零时刻的变量仅作起始示意。

把两步合并，得到 ${\lambda }_{k+1}=({\lambda }_k-\rho )/(1+\rho )$。最优乘子为 ${\lambda }^{\ast }=-1$，因此 $${\lambda }_{k+1}+1=\frac{{\lambda }_k+1}{1+\rho },x_{k+1}-1=-\frac{{\lambda }_k+1}{1+\rho }.$$ 这完整证明了本例以收缩因子 $1/(1+\rho )$ 趋向可行最优点，罚参数无须趋于无穷。

一般仿射等式与驻点关系

设 $x\in {ℝ}^n$，$A\in {ℝ}^{p\times n}$、$b\in {ℝ}^p$，目标 $f$ 可微。定义 $$L_{\rho }(x,\lambda )=f(x)+{\lambda }^{𝖳}(Ax-b)+\frac{\rho }{2}\Vert Ax-b{\Vert }^2.$$ 乘子法先取全局子问题解 $x_{k+1}\in \arg \underset{x}{min}{L}_{\rho }(x,{\lambda }_k)$，再更新 ${\lambda }_{k+1}={\lambda }_k+\rho (A{x}_{k+1}-b)$。假设子问题有解，其一阶条件直接化成 $$0=\mathrm{\nabla }f(x_{k+1})+A^{𝖳}{\lambda }_k+\rho A^{𝖳}(A{x}_{k+1}-b)=\mathrm{\nabla }f(x_{k+1})+A^{𝖳}{\lambda }_{k+1}.$$ 更新乘子后，拉格朗日驻点关系恰好满足；尚未消除的是可行性残差 $A{x}_{k+1}-b$。若 $f$ 凸，且残差为零，上式与凸函数一阶不等式一起证明当前点全局最优：对任意可行 $z$，有 $f(z)\ge f(x)-{\lambda }^{𝖳}A(z-x)=f(x)$。

精确子问题可被近似求解代替，但此时驻点式也出现内层误差；其容限和外层残差需共同控制。一般非凸模型中的局部子问题解，不能自动提供上述凸全局结论。

纯罚函数每次返回同一偏差，乘子反馈则逐轮缩半。

罚函数比较、变式与求解成本

若只用 $\frac{1}{2}{x}^2+\rho (x-1{)}^2/2$，固定 $\rho$ 时总会得到 $x=\rho /(1+\rho )<1$，重复求同一子问题并不会进一步缩小偏差。要让其误差趋零，需要让 $\rho \to \mathrm{\infty }$；增广法则保留并更新了线性项。

变式把目标改为 $c{x}^2/2$，要求 $x=a$，其中 $c>0$。此时 $x_{k+1}=(\rho a-{\lambda }_k)/(c+\rho )$，最优乘子 $-ca$，乘子误差每步乘以 $c/(c+\rho )$。例如 $c=2,a=3,\rho =2$、初乘子零，第一点为 $1.5$，新乘子为 $-3$，第二点为 $2.25$，最终趋于三。这与主例共用同一个推导。

增广项并不无条件使任意目标有界。例如二维目标 $f(x,y)=-y^2$、约束 $x=0$，只给 $x$ 加二次罚项无法限制 $y$，子问题仍无下界。对非线性等式 $h(x)=0$，可将残差换为 $h(x)$，但罚项可能非凸，内层求解和收敛条件必须重新分析。

下例只用标准库，输入正曲率、目标约束值、正罚参数、初乘子及步数，返回变量、乘子、可行性残差和驻点残差，不改写输入。每步时间与工作空间为常数，历史占 $O(K)$。一般二次目标的子问题要处理 $Q+\rho A^{𝖳}A$，稠密分解成本约为 $O(n^3)$，固定罚参数时可复用分解；过大参数也可能使数值条件变差。

Python 3

def augmented_scalar(c=1.0, a=1.0, rho=1.0, multiplier=0.0, count=3):
    if c <= 0 or rho <= 0 or count < 0:
        raise ValueError("positive curvature and penalty required")
    lam, trace = float(multiplier), []
    for k in range(1,count+1):
        x = (rho*a-lam)/(c+rho)
        residual = x-a
        lam += rho*residual
        trace.append((k,x,lam,residual,c*x+lam))
    return trace

for row in augmented_scalar():
    print(row)
print("variant", augmented_scalar(c=2,a=3,rho=2,count=2))
assert all(abs(row[-1]) < 1e-12 for row in augmented_scalar())

主例输出可行性残差为 -0.5,-0.25,-0.125，驻点残差均为零。前几步的原目标低于 $1/2$，因为它们尚不可行，这些数值不能当作原问题已取得的可行上界。