增广 Lagrange 乘子法

二次罚公理库二次罚函数法与病态性Quadratic penalty method将等式违背的平方加入目标，通过增大罚参数逼近可行解，并量化有限罚参数的偏差与内层 Hessian 的病态性。只根据本轮违约收取费用。乘子法还保留一个历史账本：若约束反复向同一侧偏离，乘子就持续增加该方向的压力。原来必须靠更大罚系数维持的法向力，可以逐渐由乘子承担。

配方得到

所以每次更新乘子，都移动了二次项的中心。固定 $\rho$ 不意味着每轮解决同一个罚问题；变化的线性项让内层最优点持续移动。

同一个等式问题，固定罚率一 ​

取

内层的两个方程为

更新后 ${\lambda }^{k+1}={\lambda }^k+c$，因此

解这个标量递推可得

所有内层 Hessian 都是 $\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$，条件数一直为三。固定二次罚而不更新乘子会永久停在第一行；乘子法却趋于 $(3/2,-1/2)$，而不必把这组特征值拉得越来越开。

每一行都有 $\mathrm{\nabla }f(x^k,y^k)+(1,1{)}^T{\lambda }^k=0$，但有限轮约束残差仍非零。只检查驻点方程，会在第一轮错误地认为原问题已经解完。

联合最小化和交替最小化不相同 ​

若 $f(x,z)=f_1(x)+f_2(z)$ 且约束为 $x-z=0$，本页要求一次联合求出 $L_{\rho }(x,z,{\lambda }^k)$ 的最小点。ADMM公理库交替方向乘子法（ADMM）Alternating direction method of multipliers · ADMM将凸目标拆成两个近端子问题，用乘子累积一致性误差，并以原始与对偶残差检查最优性的算法。则先固定 $z$ 更新 $x$，再固定新的 $x$ 更新 $z$，最后更新乘子。一次交替扫掠一般没有完成联合最小化，所以不能直接套用本页的对偶近端等式；ADMM 有自己的残差和收敛证明。

非凸等式也可以定义同样的增广函数，但此时内层局部最小点不必最小化普通 Lagrangian，对偶近端证明就失去关键一步。局部收敛需要正则约束、二阶充分条件、足够好的乘子初值及相应罚率条件，不能由更新公式单独推出。

乘子更新为什么是对偶隐式步 ​

精确内层的一阶条件为

由于 $f$ 凸，$x^{k+1}$ 同时全局最小化普通 $L(x,{\lambda }^{k+1})$。记 $r^{k+1}=A{x}^{k+1}-b$。对任意 $\lambda$，

所以 $r^{k+1}$ 是凹对偶函数在新乘子处的超梯度。又因为 ${\lambda }^{k+1}-{\lambda }^k=\rho r^{k+1}$，它恰好抵消近端二次项在新点的梯度，这就证明了前面的近端最大化等式。与显式对偶梯度上升不同，方向由新点的超梯度确定。

约束误差为什么趋零 ​

固定一个对偶最优乘子 ${\lambda }_{\ast }$。上面的超梯度不等式给出

展开 ${\lambda }^k={\lambda }^{k+1}-\rho r^{k+1}$ 的平方，得到

乘子到任意对偶解的距离不增，并且相邻乘子差的平方可求和。因此 $r^{k+1}=({\lambda }^{k+1}-{\lambda }^k)/\rho \to 0$。同一个超梯度不等式还给出

乘子有界；对偶函数上半连续，使其聚点都是对偶解。再以任一这样的聚点作上面距离不等式的参照，得到整个乘子序列收敛。若原变量也有聚点，由 $r^k\to 0$ 及精确驻点式取极限，该聚点满足原问题的 KKT。强凸 $f$ 时原解唯一，驻点式还可把乘子收敛传到原变量。一般凸情形不能仅由乘子收敛保证所有原变量有界。

不等式怎样进入乘子更新 ​

对凸目标与仿射不等式 $g(x)=Ax-b\le 0$，引入非负松弛 $u\ge 0$，把约束写成 $g(x)+u=0$。固定 $\lambda$、$\rho >0$ 后，关于松弛的内层最小化可逐坐标完成：

代回 $f(x)+{\lambda }^T(g(x)+u)+(\rho /2)\Vert g(x)+u{\Vert }^2$，得到

若在 $x$ 上的精确最小值能取到，先求 $x^{+}\in \mathrm{argmin}{\tilde{L}}_{\rho }(x,\lambda )$，再代回最优松弛，乘子更新就是

这里的非负投影由松弛最小化导出，不是把等式更新中的负乘子随意删掉。关于 $u$ 的内层含非负约束：在边界应检查单侧最优性，不能对它直接套用前面无约束内层的零梯度式。上述计算给出了不等式版本的具体一步；若要引用其收敛结论，还须匹配约束内层的可解性、鞍点与误差条件。

不精确内层与线性代数复用 ​

对前面的等式版本，若内层只解到 $e^{k+1}={\mathrm{\nabla }}_x{L}_{\rho }(x^{k+1},{\lambda }^k)$，更新乘子后仍有精确恒等式

因此停止至少要同时控制 $\Vert r^{k+1}\Vert$ 和 $\Vert e^{k+1}\Vert$。固定一个很粗的内层容差，不能直接保留精确版本的收敛结论；常见理论使用逐步收紧、可求和误差或相对误差条件。

若 $f(x)=x^{T}Hx/2+c^{T}x$ 且 $H\succ 0$，内层是

固定 $\rho$ 时可以预先分解这个线性系统公理库线性方程组System of linear equations可写为矩阵方程 Ax=b 的有限个一次方程系统。：稠密设置成本 $O(n^3)$，每轮三角求解 $O(n^2)$，约束残差和乘子更新另需矩阵向量积。对偶近端观点也把它与Moreau 包络公理库Moreau 包络Moreau envelope · Moreau-Yosida regularization以二次 infimal convolution 将闭凸函数平滑化并保留其极小点的函数。联系起来，但算子解释不会免除内层求解成本。