返回学习路线

约束数值优化：同一问题的六条求解路线 ​

任务与验收目标 ​

一个二维设计变量 $z=(x,y)$ 希望靠近目标 $(2,1)$，但总资源最多为二，两个变量都不能为负：

$$minf(z)=\frac{1}{2}[(x-2{)}^2+(y-1{)}^2],Az\le b,A=\left(\begin{array}{cc}-1& 0\\ 0& -1\\ 1& 1\end{array}\right),b=\left(\begin{array}{c}0\\ 0\\ 2\end{array}\right).$$

请分别执行活跃集、二次罚、精确 ℓ1 罚、增广乘子、对数障碍和原始—对偶内点路线。所有方法都对照同一个最优点、同一组约束符号，并说明自己的有限轮输出有什么证书。最后，把线性资源边界替换成圆约束，检验一次 SQP；再用一个非凸四次目标检查信赖域的拒绝规则及截断 CG 的边界。

完成任务的标准是：能列出真正求解的子问题，复算每个候选与参数，分别核验原始可行性、驻点、乘子符号和互补量。目标值较小却不可行的点不算成功；内层方程解得很准也不能替代原问题证书。

先建立所有路线共用的最优答案 ​

取

$$z_{\ast }=(3/2,1/2),{\lambda }_{\ast }=(0,0,1/2),f_{\ast }=1/4.$$

松弛为 $s_{\ast }=b-A{z}_{\ast }=(3/2,1/2,0)$，故可行；${\lambda }_{\ast }\ge 0$ 且 $s_{\ast }^T{\lambda }_{\ast }=0$。同时

$$\mathrm{\nabla }f(z_{\ast })=(-1/2,-1/2{)}^T,A^T{\lambda }_{\ast }=(1/2,1/2{)}^T.$$

驻点成立，严格凸性使它成为唯一全局解。还可以完全展开：对任意可行 $z$，

$$f(z)-f_{\ast }=\frac{1}{2}\Vert z-z_{\ast }{\Vert }^2+\frac{1}{2}(2-x-y)\ge 0.$$

这个恒等式是无需任何求解器的独立证书。它也说明答案在斜边内部，枚举三个顶点不能解决这项二次规划。

路线一：活跃集在可行域里找正确的面 ​

沿活跃集法公理库二次规划的活跃集法Active-set quadratic programming · Working-set method从可行点出发，在工作约束确定的面内求二次下降方向，再用阻挡步长和乘子符号增删约束。，从 $(0,0)$ 和工作集 $W=\{1,2\}$ 开始。工作方向由 $p+\mathrm{\nabla }f+A_W^T\nu =0,A_{W}p=0$ 决定。

当前点	工作集	方向或乘子	本轮动作
$(0,0)$	$\{1,2\}$	$p=0,\nu =(-2,-1)$	删除约束一
$(0,0)$	$\{2\}$	$p=(2,0)$	比值一，到 $(2,0)$ 并加入约束三
$(2,0)$	$\{2,3\}$	$p=0,{\nu }_2=-1,{\nu }_3=0$	删除约束二
$(2,0)$	$\{3\}$	$p=(-1/2,1/2)$	完整步到 $(3/2,1/2)$
$(3/2,1/2)$	$\{3\}$	$p=0,{\nu }_3=1/2$	KKT 终止

移动时目标依次是 $5/2,1/2,1/4$，始终原始可行。两次删除只改变工作假设，不改变点的位置。最终乘子非负才允许终止，不能在第一个零方向就退出。

路线二：二次罚从不可行侧逼近 ​

对全部三条约束加入正部平方罚：

$$Q_{\mu }(z)=f(z)+\frac{\mu }{2}[max(-x,0{)}^2+max(-y,0{)}^2+max(x+y-2,0{)}^2].$$

候选将落在 $x,y>0,x+y>2$ 区域，所以只需考虑最后一项。令 $r=x+y-2$，驻点给出 $x=2-\mu r,y=1-\mu r$，于是

$$r_{\mu }=\frac{1}{1+2\mu },{\ell }_{\mu }=\mu r_{\mu },z_{\mu }=(2-{\ell }_{\mu },1-{\ell }_{\mu }).$$

解出的点确实满足假设的三个符号，所以也是整个严格凸罚目标的唯一最小点。罚乘子估计为 $(0,0,{\ell }_{\mu })$，原驻点残差精确为零；原始违约却为 $r_{\mu }$。局部 Hessian 特征值是一与 $1+2\mu$。

$\mu$	$z_{\mu }$	最大违约	Hessian 条件数
$1$	$(5/3,2/3)$	$1/3$	$3$
$10$	$(32/21,11/21)$	$1/21$	$21$
$100$	$(302/201,101/201)$	$1/201$	$201$

这里 $f(z_{\mu })={\ell }_{\mu }^2<1/4$。目标比最优值还低并不矛盾，因为点在可行域之外。二次罚公理库二次罚函数法与病态性Quadratic penalty method将等式违背的平方加入目标，通过增大罚参数逼近可行解，并量化有限罚参数的偏差与内层 Hessian 的病态性。的验收要看违约与驻点两项，不能按原目标大小排出“比最优还好”的结果。

路线三：有限 ℓ1 罚率就得到原解 ​

令

$$P_{\rho }(z)=f(z)+\rho [max(-x,0)+max(-y,0)+max(x+y-2,0)].$$

最优乘子的最大分量是 $1/2$。由精确罚定理公理库精确 ℓ1 罚函数Exact l1 penalty以约束违背的绝对值和正部构造有限参数即可精确的罚函数，并说明乘子阈值、非光滑最优性与局部全局边界。，任取 $\rho >1/2$，例如一，罚目标的唯一最小点就是 $z_{\ast }$。

也能直接核验尖角。$z_{\ast }$ 的前两条约束严格松弛，罚次梯度为零；第三条在零处允许取 $\theta (1,1)$、$0\le \theta \le 1$。选 $\theta =1/2$，恰好抵消 $(-1/2,-1/2)$，故零在罚目标次微分中。严格凸性保证唯一性。

作为边界对照，取 $\rho =1/4$，不可行区域的唯一驻点是 $(7/4,3/4)$，违约为 $1/2$，仍未恢复原解。有限精确罚率不意味着粗糙的内层近似也会恰好可行；它描述的是精确最小点。

路线四：乘子保存历史，罚率保持一 ​

不等式可写成 $g_i(z)+u_i=0,u_i\ge 0$。对这些等式使用增广乘子法公理库增广 Lagrange 乘子法Augmented Lagrangian method · Method of multipliers联合最小化增广目标后累加约束违背，借对偶近端机制在固定罚参数下改善可行性，并分别检查内层与外层误差。，再把 $u_i$ 精确消去，就得到不等式增广函数

$${\mathcal{L}}_{\rho }(z,\lambda )=f(z)+\frac{1}{2\rho }\sum _i[max(0,{\lambda }_i+\rho g_i(z){)}^2-{\lambda }_i^2],$$

以及投影乘子更新 ${\lambda }_i^{+}=max(0,{\lambda }_i+\rho g_i(z^{+}))$。消元来自在 $u_i\ge 0$ 上最小化一个关于 $g_i+u_i+{\lambda }_i/\rho$ 的平方；因此不等式乘子自然保持非负。

取 $\rho =1,{\lambda }^0=0$。本例每个联合最小点都满足 $x,y>0$，前两条罚项与乘子为零。只需保存第三个乘子 ${\ell }_k$：

$${\ell }_{k+1}=\frac{{\ell }_k+1}{3},z^{k+1}=(2-{\ell }_{k+1},1-{\ell }_{k+1}),{\ell }_k=\frac{1}{2}(1-3^{-k}).$$

$k$	$z^k$	${\ell }_k$	$x^k+y^k-2$
$1$	$(5/3,2/3)$	$1/3$	$1/3$
$2$	$(14/9,5/9)$	$4/9$	$1/9$
$3$	$(41/27,14/27)$	$13/27$	$1/27$
$4$	$(122/81,41/81)$	$40/81$	$1/81$

内层 Hessian 始终具有特征值一和三。与路线二相比，减少违约靠的是乘子变化，计算矩阵的曲率比没有不断上升。有限轮点仍不可行，虽然每轮新乘子下的驻点残差已为零。

路线五：障碍点始终留在三角形内部 ​

取

$$\underset{z}{min}tf(z)-\log x-\log y-\log (2-x-y).$$

给每个 $t$ 用阻尼 Newton 求中心点，初值 $(1/2,1/2)$，先保三项松弛严格正，再作 Armijo 回溯。若 $s=b-Az$，梯度和 Hessian 分别为

$$G=t(z-(2,1))+A^T{s}^{-1},B=tI+A^T\mathrm{diag}(s^{-2})A.$$

逆与幂在这里逐分量计算。脚本从原式组装它们，独立于下一节的原始—对偶求解。

$t$	中心点 $(x,y)$	原目标	精确中心的间隙 $3/t$
$1$	$(0.941987,0.586226)$	$0.645301$	$3$
$4$	$(1.229778,0.513420)$	$0.415001$	$0.75$
$16$	$(1.409449,0.492110)$	$0.303352$	$0.1875$
$64$	$(1.474956,0.495873)$	$0.264908$	$0.046875$

定义 ${\lambda }_i=1/(t{s}_i)$，在中心点就有 $z-(2,1)+A^T\lambda =0$。本 QP 的对偶函数可直接配方求出：

$$d(\lambda )={\lambda }^T(A(2,1{)}^T-b)-\frac{1}{2}\Vert A^T\lambda {\Vert }^2,\lambda \ge 0.$$

于是 $f(z)-d(\lambda )=s^T\lambda =3/t$。表中的浮点中心另行检查驻点残差，最大约 $6.3\times {10}^{-13}$，并重算真实目标差，不能只把理论 $3/t$ 填入验收栏。中心路径公理库对数障碍函数与中心路径Logarithmic barrier · Central path在严格可行域中加入对数障碍，构造扰动互补条件，并由中心点的对偶证书得到可计算的目标误差界。给的是原始上界与对偶下界，它和不可行罚点拥有不同的证书。

路线六：原始—对偶内点直接同时修正三组条件 ​

本节仍解同一个 QP，采用 $g(z)=Az-b$、$s=b-Az$。从

$$z^0=(1/2,1/2),s^0=(1/2,1/2,1),{\lambda }^0=(1/2,3/2,2)$$

出发，已经满足 $Az+s=b$ 与 $z-(2,1)+A^T\lambda =0$，且松弛和乘子均严格正。间隙为三，平均互补量 $\mu =1$。

令 $\sigma =1/5$，每轮解

$$\left(\begin{array}{ccc}I& 0& A^T\\ A& I& 0\\ 0& \mathrm{\Lambda }& S\end{array}\right)\left(\begin{array}{c}\mathrm{\Delta }z\\ \mathrm{\Delta }s\\ \mathrm{\Delta }\lambda \end{array}\right)=-\left(\begin{array}{c}{r}_d\\ r_p\\ S\lambda -\sigma \mu \mathbf{1}\end{array}\right),$$

其中 $r_d=z-(2,1)+A^T\lambda ,r_p=Az+s-b$。第一轮得到

$$\mathrm{\Delta }z=(11/25,-3/100),\mathrm{\Delta }s=(11/25,-3/100,-41/100),\mathrm{\Delta }\lambda =(-27/50,-101/100,-49/50).$$

乘子第一项最先触零，边界比值为 $25/27$。取边界比值的 $9/10$，即 $\alpha =5/6$，新点为

$$z^1=(13/15,19/40),s^1=(13/15,19/40,79/120),{\lambda }^1=(1/20,79/120,71/60).$$

原始等式与驻点仍精确成立，所有需要保正的分量均正。实际间隙不是预设的 $3\sigma$，而是

$$(s^1{)}^T{\lambda }^1=\frac{3269}{2880}\approx 1.135069.$$

脚本继续使用同一中心化与保正规则，并在必要时回溯到实际间隙满足 ${\mathrm{gap}}^{+}\le (1-0.1\alpha )\mathrm{gap}$。本例得到：

轮数	$(x,y)$	原始目标	对偶下界	实际间隙
$0$	$(0.5,0.5)$	$1.25$	$-1.75$	$3$
$1$	$(0.866667,0.475000)$	$0.780035$	$-0.355035$	$1.135069$
$2$	$(1.238733,0.437626)$	$0.447895$	$-0.009754$	$0.457650$
$4$	$(1.467899,0.483627)$	$0.274886$	$0.226207$	$0.048679$
$8$	$(1.499820,0.499960)$	$0.250110$	$0.249790$	$0.000320$
$18$	$(1.499999999474,0.499999999895)$	$0.250000000316$	$0.249999999368$	$9.47\times {10}^{-10}$

每一轮都重算两组等式残差、正性和 $f-d=s^T\lambda$，故最后一行确实认证原目标误差小于 ${10}^{-9}$。这与不可行初值的 LP 算例公理库原始—对偶内点法Primal-dual interior-point method · Primal-dual path following对原始可行性、对偶可行性与扰动互补条件联合取 Newton 步，以保正步长推进，并区分互补量与真正的可行对偶间隙。不同：若原始或驻点等式不满足，互补量就不能直接代替上下界之差。

曲线约束加试：SQP 的线性化误差 ​

改求 $F(x,y)=(x-2{)}^2+y^2$，约束 $c=x^2+y^2-1=0$。在 $z_0=(3/5,4/5),{\lambda }_0=1/5$，Lagrangian Hessian 为 $(12/5)I$，QP 给出

$$p=(16/15,-4/5),J_{c}p=0.$$

由单位圆的展开，$c(z_0+\alpha p)=16{\alpha }^2/9$。完整步虽然使 $F$ 降到 $1/9$，在 $\mathrm{\Phi }=F+2|c|$ 下却从 $13/5$ 升到 $11/3$。半步给出 $(17/15,2/5)$，真实违约为 $4/9$，$\mathrm{\Phi }=9/5$，通过系数 $0.1$ 的 Armijo 条件。

验收时应同时写出“QP 线性化误差为零”和“真实约束误差为 $4/9$”。前者不能覆盖后者。SQP公理库序列二次规划Sequential quadratic programming · SQP将非线性约束线性化，以 Lagrangian 的曲率构造局部 QP，并通过乘子更新和罚函数验收控制真实约束误差。下一轮重新线性化，正是为了继续处理这份曲率造成的偏离。

非凸加试：信赖域与截断 CG 各自负责什么 ​

取 $h(x)=x^4-2x^2+x$，在零点使用模型 $m(p)=p-2p^2$。半径二时最优候选 $p=-2$ 的预测下降是十，真实下降却为负六，因此拒绝并缩半径；半径一时 $p=-1$ 的预测下降三、实际下降二，故比值为 $2/3$，可以接受。外层公理库信赖域法的接受与半径更新Trust-region method用实际下降与预测下降的比值接受或拒绝模型步，并调整信赖半径，使局部二次模型服务于真实目标下降。检验的是真实函数，不是模型自己是否解得漂亮。

对内层不定模型 $H=\mathrm{diag}(-2,1),g=(0,1),\mathrm{\Delta }=1$，完整子问题公理库信赖域二次子问题Trust-region subproblem在有限半径内最小化可能不定的二次模型，以半正定移位和互补关系认证全局解，并处理奇异的困难情形。的解为 $(\pm \sqrt{8}/3,-1/3)$，模型值 $-7/6$。零启动截断 CG公理库Steihaug 截断共轭梯度Steihaug–Toint truncated CG · Truncated conjugate gradient trust-region method只用对称矩阵的向量积沿 CG 路径降低二次模型，并在负曲率、信赖边界或小模型残差处给出不同退出状态。只探索第二坐标轴，返回 $(0,-1)$、值 $-1/2$。它有 Cauchy 下降，却没有发现未被梯度激发的负曲率方向。

因此三份结论要各自验收：内层是否达到所需下降，外层是否真的降低目标，最终是否达到要求的一阶或二阶条件。一个局部数值方法返回的驻点，不能靠“全局化”三个字变成非凸全局最优解。

复现与逐项验收 ​

下载 Python 核验脚本，需要 Python 3 与 NumPy。运行后生成逐项结果 JSON；查看本次核验结果。脚本既执行活跃集和内点迭代，也独立核对闭式罚解、乘子递推、SQP 有理数和信赖域证书。

• 活跃集：五次状态检查后到达 $(3/2,1/2)$，全过程可行，终止乘子非负
• 二次罚：有限参数有残差 $1/(1+2\mu )$，同时报告条件数 $1+2\mu$
• 精确罚：给出乘子阈值、尖角次梯度和低于阈值的不可行对照
• 增广乘子：固定罚率一，残差按 $3^{-k}$ 减少，明确有限轮仍有违约
• 障碍：所有松弛正，中心残差小，使用实际对偶值复核 $3/t$
• 原始—对偶：三组条件分别检查，最后实际间隙小于 ${10}^{-9}$
• SQP 与信赖域：验收基于真实函数与真实约束，区分模型解、允许步及最终证书

进一步阅读 ​

• Jorge J. Moré and D. C. Sorensen, Computing a Trust Region Step，§§2–4
• Dimitri P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods，Chs. 2–4
• Stephen Boyd and Lieven Vandenberghe, Convex Optimization，Ch. 11