序列二次规划

序列二次规划（sequential quadratic programming，SQP）用一系列局部二次目标、线性化约束的子问题求解光滑非线性约束优化。目标的二次曲率通常来自拉格朗日函数，而不只是原目标；线性化约束满足也不代表新点已经满足原来的曲约束。

一条抛物线约束上的局部步骤

考虑 $min f (x, y) = \frac{1}{2} [(x - 1)^{2} + y^{2}]$ ，约束 $h (x, y) = x^{2} - y = 0$ 。定义 $L = f + λ h$ ，其变量 Hessian 为 $diag (1 + 2 λ, 1)$ 。取当前点 $(1 / 2, 1 / 4)$ 、乘子估计 $λ = 1 / 4$ ，则梯度 $g = (- 1 / 2, 1 / 4)$ ，约束 Jacobian 为 $J = (1, - 1)$ 。SQP 子问题是 $min_{d} - \frac{1}{2} d_{x} + \frac{1}{4} d_{y} + \frac{1}{2} (\frac{3}{2} d_{x}^{2} + d_{y}^{2}), d_{x} - d_{y} = 0.$ 代入 $d_{y} = d_{x}$ ，一阶条件为 $- 1 / 4 + (5 / 2) d_{x} = 0$ ，故 $d = (0.1, 0.1)$ ，新点为 $(0.6, 0.35)$ 。QP 的乘子为 $0.35$ 。原约束残差却为 $0. 6^{2} - 0.35 = 0.01$ ，因为线性化省略了 $d_{x}^{2}$ 。

抛物线约束及当前点处的切线 — 候选点满足切线等式，却位于原曲线下方，误差等于 dₓ²。

与牛顿求解最优性方程的关系

一般先看等式约束 $h : ℝ^{n} \to ℝ^{p}$ ，目标和约束二阶连续可微，乘子为 $λ \in ℝ^{p}$ 。KKT 方程是 $\nabla_{x} L (x, λ) = 0, h (x) = 0$ 。对这组方程作牛顿线性化，记 $H = \nabla_{x x}^{2} L$ 、 $J = D h$ ，得到 $(\begin{matrix} H & J^{𝖳} \\ J & 0 \end{matrix}) (\binom{d}{Δ λ}) = - (\binom{\nabla f + J^{𝖳} λ}{h}) .$ 把第一行中的旧乘子项移到左侧，并定义 $λ^{+} = λ + Δ λ$ ，便成为 $H d + \nabla f + J^{𝖳} λ^{+} = 0, J d + h = 0.$ 它正是二次子问题 $min \nabla f^{𝖳} d + d^{𝖳} H d / 2$ 、 $J d + h = 0$ 的驻点条件。因此精确 Hessian 的等式 SQP 步与 KKT 牛顿步一致。若 $J$ 行满秩、 $H$ 在 $\ker J$ 上正定，则子问题在可行仿射空间有唯一最小点，KKT 系统可逆。这里需要的是约束切空间上的曲率，不一定是整个空间的正定性。^[1]

有不等式 $c_{i} (x) \leq 0$ 时，子问题加入 $c_{i} (x) + \nabla c_{i} (x)^{𝖳} d \leq 0$ ，由 QP 判断哪些边界活跃。不能未经判断把全部不等式都写成等式。

消去约束后的一维目标及唯一最小点 — 原例可用 y=x² 消元，导数严格递增提供独立的全局校验。

原例的最优点与完整复算

原约束可消去 $y = x^{2}$ ，变为 $ϕ (x) = \frac{1}{2} [(x - 1)^{2} + x^{4}]$ ，导数为 $2 x^{3} + x - 1$ ，二阶导数 $6 x^{2} + 1 > 0$ 。导数在零处为负、一处为正，且严格递增，所以有唯一根。该根约为 $x^{*} = 0.589755$ ，相应 $y^{*} \approx 0.347810$ 、 $λ^{*} = y^{*}$ 。这是利用本例特殊消元结构证明的全局最优，不是一般 SQP 的全局保证。

从第一步之后继续更新，代码中的约束残差迅速缩小。其算式来自两条 KKT 行：令 $j = 2 x, a = 1 + 2 λ$ ，则 $d_{y} = j d_{x} + h$ ， $λ^{+} = y + d_{y}$ ，最终 $d_{x} = - \frac{(x - 1) + j (y + h)}{a + j^{2}} .$ 分母为正时本例沿线性化可行方向的二次曲率为正，这使子问题确有唯一解。

线性化的边界与变式

变式从 $(0, 0), λ = 0$ 出发，线性化只要求 $d_{y} = 0$ ，QP 会选 $d_{x} = 1$ 。候选点 $(1, 0)$ 的原目标降到零，但原约束残差升到一。这说明只接受原目标下降无法处理约束。实际 SQP 通常结合罚函数、过滤器或信赖域法，同时衡量目标和可行性。

退化约束也会破坏线性系统。对 $h (x) = x^{2} - 1$ ，在 $x = 0$ 处有 $h = - 1, h^{'} = 0$ ，线性化要求 $- 1 = 0$ ，子问题不可行。原问题明明有两个可行点，局部线性化却可能没有。全步的局部二次收敛需要足够接近正则解及相应光滑、非退化和二阶条件，不能从任意初值无条件宣称。

标准库演示

函数专用于上述抛物线模型，输入点和乘子，返回每次 QP 全步后的状态及残差，不改写输入。它不包含通用全局化策略，因此例中的成功只是所示初值的结果。每步为常数成本，历史为 $O (K)$ ；一般稠密等式 KKT 系统的直接求解成本约为 $O ((n + p)^{3})$ ，稀疏结构可显著改变成本。

Python 3

def sqp_parabola(start=(0.5,0.25,0.25), count=4):
    if len(start) != 3 or count < 0:
        raise ValueError("point, multiplier and nonnegative count required")
    x,y,lam = map(float,start)
    trace = [(x,y,lam,x*x-y)]
    for _ in range(count):
        h,j,a = x*x-y,2*x,1+2*lam
        denominator = a+j*j
        if denominator <= 0:
            raise ArithmeticError("nonpositive reduced curvature")
        dx = -((x-1)+j*(y+h))/denominator
        dy = j*dx+h
        lam = y+dy
        x,y = x+dx,y+dy
        trace.append((x,y,lam,x*x-y))
    return trace

for row in sqp_parabola():
    print(tuple(round(v,9) for v in row))
print("variant",sqp_parabola((0,0,0),1)[-1])
assert abs(sqp_parabola(count=8)[-1][-1]) < 1e-12

参考文献

↑ NEOS Guide, Sequential Quadratic Programming，局部二次模型、线性化约束及拉格朗日 Hessian。

[1] NEOS Guide, Sequential Quadratic Programming，局部二次模型、线性化约束及拉格朗日 Hessian。

[1]