二次罚函数法与病态性

等式约束是一条零厚度的线或曲面。二次罚把它换成一个谷：离约束越远，费用按距离指标的平方增长。加大参数会把谷压窄，却没有把谷底所在的点硬性钉在约束上。

靠近可行集，平方罚的斜率会趋于零。若目标函数仍有把点拉向不可行侧的力量，就必须留下少量违约，才能产生足够大的反向罚梯度。因此二次罚常从约束外逼近答案；这和精确 ℓ1 罚公理库精确 ℓ1 罚函数Exact l1 penalty以约束违背的绝对值和正部构造有限参数即可精确的罚函数，并说明乘子阈值、非光滑最优性与局部全局边界。的尖角机制不同。对不等式，对数障碍公理库对数障碍函数与中心路径Logarithmic barrier · Central path在严格可行域中加入对数障碍，构造扰动互补条件，并由中心点的对偶证书得到可计算的目标误差界。则让迭代点留在严格可行侧。

把误差和条件数放在同一张账本上 ​

考虑

约束最优点是 $(3/2,-1/2)$，目标值为 $1/4$，采用 $L=f+\lambda c$ 时最优乘子为 $1/2$。罚子问题的一阶条件为

两式相减得到 $x-y=2$。令 $r=x+y-1$，再相加得 $(1+2\mu )r=1$，所以

乘子估计 ${\lambda }_{\mu }=\mu /(1+2\mu )\to 1/2$。点误差恰为 $\Vert (x_{\mu },y_{\mu })-(3/2,-1/2)\Vert =r_{\mu }/\sqrt{2}$。

罚 Hessian 为

沿切方向 $(1,-1)$ 的特征值是一，沿约束法向 $(1,1)$ 的特征值是 $1+2\mu$，所以二范数条件数公理库线性方程组的条件数与扰动Conditioning of linear systems · Matrix condition number把一般问题条件性具体化为可逆线性系统的右端、系数矩阵与联合扰动界。为 $1+2\mu$。

若要求违约不超过 ${10}^{-4}$，精确解也需要 $\mu \ge 4999.5$，对应条件数至少一万。内层若只解到粗精度，还会叠加另一份误差；增大参数本身没有完成求解。

原问题有解，罚子问题仍可能无下界 ​

取 $f(x)=-x^4$、约束 $x=0$。原问题只有一个可行点，最优值为零；但任何有限 $\mu$ 都有

因此不存在全局罚子问题最小点。另一个风险是只求局部驻点：对 $f(x)=x^2,c(x)=x^2-1$，$x=0$ 对所有 $\mu$ 都满足 $\mathrm{\nabla }{Q}_{\mu }=0$，违约却始终为 $-1$。内层驻性不能替代内层最小化，更不能替代外层可行性。

极限定理的证明机制 ​

任取原问题可行点 $z$。全局罚最小性给出

沿一个收敛子列 $x_{k_j}\to \overline{x}$，连续性使 $f(x_{k_j})$ 有界，故

于是 $c(\overline{x})=0$。同时 $f(x_k)\le f(z)$，取极限得 $f(\overline{x})\le f(z)$。由于 $z$ 是任意可行点，$\overline{x}$ 全局最优。关键是与任意可行点比较整个罚目标，而不是只观察梯度。

对仿射约束 $c(x)=Ax-b$，Hessian 中最后的非线性项消失，罚曲率直接增加 $\mu A^{T}A$。约束的零空间方向不受这项影响，法向方向则变硬，所以病态性来自不同方向被不均匀地拉伸。改变约束的单位也会改变罚项尺度；若将某个等式乘上一千，其平方罚权重会放大一百万。

一个可执行的外层停止方式 ​

可以令 ${\mu }_{k+1}=10{\mu }_k$，为每轮指定内层梯度容差 ${\epsilon }_k\downarrow 0$，并记录三项：内层 $\Vert \mathrm{\nabla }{Q}_{{\mu }_k}(x_k)\Vert$、原约束 $\Vert c(x_k)\Vert$、原 Lagrangian 驻性 $\Vert \mathrm{\nabla }f(x_k)+J_c(x_k{)}^T{\lambda }_k\Vert$，其中 ${\lambda }_k={\mu }_{k}c(x_k)$。第三项在精确算术下等于第一项，却必须连同约束残差解释；一项小而另一项大时不能停止为“约束最优”。

对不等式 $g_i(x)\le 0$，可加入 $\mu \sum _{i}max(g_i(x),0{)}^2/2$。该项通常一阶连续，切换位置却未必二阶连续，因此内层算法的光滑性假设要相应调整。增广 Lagrange 法公理库增广 Lagrange 乘子法Augmented Lagrangian method · Method of multipliers联合最小化增广目标后累加约束违背，借对偶近端机制在固定罚参数下改善可行性，并分别检查内层与外层误差。进一步保存并更新乘子，使固定或适度的罚参数也能持续消除违约。

稠密 Newton 内层每步通常需要 $O(n^3)$ 的分解，梯度和 Hessian 组装成本另计。罚参数增加多少轮并不能代表总工作，因为每轮线性系统会变得更难解；应一并报告约束误差、线性系统残差、条件数估计和实际内层次数。