---

[toc]

介绍

因为等式约束二次规划问题的Lagrange函数是二次函数，求Lagrange函数的稳定点就是求KKT方程组，而一般等式约束的最优化问题的Lagrange函数一般事非线性函数，就需要用迭代的方法求稳定点

求解一般等式约束问题的每一步迭代都要求解一个二次规划问题，该方法称为序列二次规划（Sequential Quadratic Programming）方法

Lagrange-Newton的方法

对等式约束最优化问题

$$\begin{aligned} min\ &f(x)\\ s.t.\ &g(x)=0 \end{aligned}$$

它的Lagrange函数为$L(x,\lambda)=f(x)-\lambda{g(x)}$

且满足KKT条件

$$\nabla L(x,\lambda)= \begin{bmatrix}\nabla_xL(x,\lambda)\\\nabla_\lambda L(x,\lambda)\end{bmatrix}= \begin{bmatrix}\nabla f(x) - \lambda\nabla g(x)\\-g(x)\end{bmatrix}=0 \quad$$

假设当前迭代点为$(x_k,\lambda_k)$，该点的增量为$(d_x,d_\lambda)$

则$\nabla{L(x_k+d_x,\lambda_k+d_\lambda)}在(x_k,\lambda_k)$的Taylor展开为

$$\nabla{L(x_k+d_x,\lambda_k+d_\lambda)}\approx \nabla{L(x_k,\lambda_k)}+ \nabla^2L(x_k,\lambda_k) \begin{bmatrix}d_k\\d_\lambda\end{bmatrix}=0$$

即要$\nabla^2L(x_k,\lambda_k)\begin{bmatrix}d_k\\d_\lambda\end{bmatrix}=-\nabla{L(x_k,\lambda_k)}$,其中

$$\nabla^2L(x_k,\lambda_k)= \begin{bmatrix}\nabla^2f(x_k)-\lambda_k\nabla^2g(x_k) & -\nabla{g(x_k)}\\-\nabla{g(x_k)}^T & 0\end{bmatrix}$$

所以

$$\begin{bmatrix}\nabla^2f(x_k)-\lambda_k\nabla^2g(x_k) & -\nabla{g(x_k)}\\-\nabla{g(x_k)}^T & 0\end{bmatrix} \begin{bmatrix}d_x \\ d_\lambda \end{bmatrix}= \begin{bmatrix} -\nabla{f(x_k)}+\lambda_k\nabla{g(x_k)}\\g(x_k) \end{bmatrix}$$

该方程的系数矩阵为KKT矩阵，若记$\lambda_{k+1}=\lambda_k+d_\lambda,d_k=d_x$,带入得到方程组为

$$\begin{bmatrix}\nabla^2f(x_k)-\lambda_k\nabla^2g(x_k) & -\nabla{g(x_k)}\\-\nabla{g(x_k)}^T & 0\end{bmatrix} \begin{bmatrix}d_k\\\lambda_{k+1}\end{bmatrix}= \begin{bmatrix}-\nabla{f(x_k)}\\g(x_k)\\\end{bmatrix}$$

解出$d_k,\lambda_{k+1}$，从而$x_{k+1}=x_k+d_k$

Lagrange-Newton方法的等价形式

令$W_k=\nabla^2f(x_k)-\lambda_k\nabla^2g(x_k)$

考虑下面的二次规划问题：

$$\begin{aligned} &min\ q_k(d)=\frac{1}{2}d^TW_kd+\nabla{f(x_k)}^Td+f(x_k)\\ &s.t.\ g(x_k)+\nabla{g(x_k)}^Td=0 \end{aligned}$$

当$\nabla{g(x_k)}$列满秩且$d^TW_kd>0,\nabla{g(x_k)}^Td=0且d\neq0$时，有唯一解$d_k,\lambda_{k+1}$，且满足KKT方程组

$$\left\{ \begin{aligned} & W_kd+\nabla{f(x_k)}-\lambda\nabla{g(x_k)}=0\\ & \nabla{g(x_k)}^Td+g(x_k)=0 \end{aligned} \right.$$

即是

$$\begin{bmatrix}W_k & -\nabla{g(x_k)}\\-\nabla{g(x_k)}^T & 0\end{bmatrix} \begin{bmatrix}d\\\lambda\end{bmatrix}= \begin{bmatrix}-\nabla{f(x_k)}\\g(x_k)\end{bmatrix}$$

当求解上式的$d=d_k,\lambda=\lambda_{k+1}$时，刚好是Lagrange-Newton的KKT方程组的形式。所以上述是Lagrange-Newton方法的等价形式

解一般约束最优化问题的序列二次规划方法

考虑一般约束最优化问题

$$\begin{aligned} min\ &f(x)\\ s.t.\ &g_i(x)=0,i\in J\\ &g_i(x)\ge0,i\in I \end{aligned}$$

则由上面可知，为求解上式，在$x_k$处，我们需要求解下面的子问题

$$\begin{aligned} min\ &\frac{1}{2}d^TW_kd+\nabla{f(x_k)}^Td+f(x_k)\\ s.t.\ &g(x_k)+\nabla{g(x_k)}^Td=0,i\in J\\ &g(x_k)+\nabla{g(x_k)}^Td\ge0,i\in I \end{aligned}$$

对上式求解得到$d_k,\lambda_{k+1}$；这是一个二次规划问题，可以用我们二次规划的方法求解得到。对一般约束最优化问题，每一次迭代都要解一个二次规划的子问题，所以称该方法为序列二次规划（SQP）方法