二阶充分条件

当问题$(P)$中约束规范
(1) $f(x),g_i(x),i=1,2,\dots ,m$均为凸函数
(2) $h_i(x)，i=1,\dots ,I$为线性函数
满足KKT条件的点是$(P)$的最优解.
考虑如果$(1)$或者$(2)$无法满足时，最优解的条件，需要使用二阶信息.
设$x^{\ast }$满足KKT条件
$$\{\begin{array}{rl}& \nabla f(x^{\ast })+\sum {\lambda }_i\nabla g_i(x^{\ast })+\sum {\mu }_i\nabla h_i(x^{\ast })=0\\ & {\lambda }_i\ge 0\\ & {\lambda }_i{g}_i(x^{\ast })=0\end{array}$$
建立拉格朗日函数$L(x)$, 令
$$L(x)=f(x)+\sum _i{\lambda }_i{g}_i(x)+\sum _i{\mu }_i{h}_i(x)$$
可以得到
$$\begin{array}{rl}& \nabla L(x^{\ast })=\nabla f(x^{\ast })+\sum {\lambda }_i\nabla g_i(x^{\ast })+\sum {\mu }_i\nabla h_i(x^{\ast })=0\\ & L(x^{\ast })=f(x^{\ast })+\sum {\lambda }_i{g}_i(x^{\ast })+\sum {\mu }_i{h}_i(x^{\ast })=f(x^{\ast })\\ & \forall x\in S,L(x)=f(x)+\sum \underset{\le 0}{\underbrace{{\lambda }_i{g}_i(x)}}+\sum \underset{=0}{\underbrace{{\mu }_i{h}_i(x)}}\Rightarrow L(x)\le f(x)\end{array}$$
可以知道，如果$x^{\ast }$是$L(x)$的最优解，则$x^{\ast }$是$(P)$的最优解.

1.设$x^{\ast }$是KKT点，$\lambda ,\mu ,L(x)，\nabla L(x^{\ast })=0$
(1). 如果${\nabla }^{2}L(x)⪰0,\forall x\in S$，则$x^{\ast }$是$L(x)$的全局最优解，也是$(P)$的全局最优解.
(2). 如果${\nabla }^{2}L(x)⪰0,\forall x\in S\cap N_s(x^{\ast })$，则$x^{\ast }$是局部最优解.
(3). 如果${\nabla }^{2}L(x)\succ 0$, 则$x^{\ast }$是$(P)$问题的严格局部最优解，$d^T{\nabla }^{2}L(x^{\ast })d>0，\forall d\ne 0$ 任何一个方向都会使函数值上升.
设$d^T{\nabla }^{2}L(x^{\ast })d>0,\forall d\in F_1(x^{\ast })$
$$F_1(x^{\ast })=\left\{d|\{\begin{array}{l}\nabla g_i(x^{\ast }{)}^{T}d\le 0,i\in I\\ \nabla h_i(x^{\ast }{)}^{T}d=0,i=1,2,\dots ,l\end{array}\right\}$$
$F_1(x^{\ast })$中目标函数值会上升的方向需要去除，考虑${\lambda }_i$，根据敏感系数${\lambda }_i$的定义，在${\lambda }_i>0$的情况下，$g_i(x)\le 0,g_i(x^{\ast })=0$，所以在$x^{\ast }\to x$方向上有
$$\nabla g_i(x^{\ast }{)}^{T}d<0$$
令
I + = { i ∣ λ i > 0 , i ∈ I } I 0 = { i ∣ λ i = 0 , i ∈ I } \begin{aligned} I^+=\{i\mid \lambda_i>0, i\in I\}\\ I^0=\{i\mid \lambda_i=0, i\in I\} \end{aligned} I+={i∣λi​>0,i∈I}I0={i∣λi​=0,i∈I}​
子集合$F_2(x)$
$$F_2(x^{\ast })=\left\{d|\begin{array}{rl}& \nabla g_i(x^{\ast })\le 0,i\in I^0\\ & g_i(x^{\ast }{)}^{T}d=0,i\in I^{+}\\ & \nabla h_i(x^{\ast }{)}^{T}d=0,i=1,2\dots ,l\end{array}\right\}\subset F_1(x^{\ast })$$

定理

假设$x^{\ast }$满足KKT条件，$\lambda ,\mu ,L(x)=f(x)+\sum {\lambda }_i{g}_i(x)+{\mu }_i{h}_i(x)$可以知道$\nabla L(x^{\ast })=0$, 已知$d^T{\nabla }^{2}L(x^{\ast })d>0,\forall d\in F_2(x^{\ast })$.
则$x^{\ast }$是$(P)$问题的严格局部最优解.
证明：
使用反证法，设$x^{\ast }$不是严格局部最优解，则存在点列$x_k\to x^{\ast }，x_k\in S，f(x_k)\le f(x^{\ast })$，如果可以找打方向$d\in F_2$，但是$d^T{\nabla }^{2}L(x^{\ast })d\le 0$则定理不成立.
记
$$\begin{gathered} d_k=\frac{x_k-x^{\ast }}{\Vert x_k-x^{\ast }\Vert } \\ {\alpha }_k=\Vert x_k-x^{\ast }\Vert \end{gathered}$$
显然， { α k } → 0 \{\alpha_k\}\to 0 {αk​}→0且 { d k } \{d_k\} {dk​}有界，$x_k=x^{\ast }+{\alpha }_k{d}_k$
计算
$$\begin{array}{rl}& f(x_k)-f(x^{\ast })={\alpha }_k\nabla f(x^{\ast }{)}^T{d}_k+\frac{{\alpha }_k^2}{2}{d}_k^T{\nabla }^{2}f(x^{\ast })d_k+o({\alpha }_k^2)\le 0(1)\\ & g_i(x_k)-g_i(x^{\ast })={\alpha }_k\nabla g_i(x^{\ast }{)}^T{d}_k+\frac{{\alpha }_k^2}{2}{d}_k^T{\nabla }^2{g}_i(x^{\ast })d_k+o({\alpha }_k^2)\le 0,i\in I(2)\\ & h_i(x_k)-h_i(x^{\ast })={\alpha }_k\nabla h_i(x^{\ast })d_k+\frac{{\alpha }_k^2}{2}{d}_k^T{\nabla }^2{h}_i(x^{\ast })d_k+o({\alpha }_k^2)=0,i=1,2\dots ,l(3)\end{array}$$
对方程(1)，除以${\alpha }_k$，令$k\to \infty$，得到
$$\nabla f(x^{\ast }{)}^T{d}_k\le 0$$
对方程(2)，除以${\alpha }_k$，令$k\to \infty$，得到
$$\nabla g_i(x^{\ast }{)}^T{d}_k\le 0$$
对方程(3)，除以${\alpha }_k$，令$k\to \infty$，得到
$$\nabla h_i(x^{\ast }{)}^T{d}_k=0$$
由KKT条件（两边同时乘以$d$）可以得到
$$\underset{\le 0}{\underbrace{\nabla f(x^{\ast }{)}^{T}d}}+\sum \underset{\le 0}{\underbrace{{\lambda }_i\nabla g_i(x^{\ast }{)}^{T}d}}+\sum \underset{=0}{\underbrace{{\mu }_i\nabla h_i(x^{\ast }{)}^{T}d}}=0$$
所以可以得到
$$\begin{gathered} \nabla f(x^{\ast }{)}^{T}d=0 \\ \text{\hspace{1em}(3)} \end{gathered}$$
$$\sum {\lambda }_i\nabla g_i(x^{\ast }{)}^{T}d=0\text{\hspace{1em}(4)}$$
由方程$(4)$可以得到
$$\begin{array}{rl}& \nabla g_i(x^{\ast }{)}^{T}d=0,i\in I^{+}\\ & \nabla g_i(x^{\ast }{)}^{T}d\le 0,i\in I^0\\ & \nabla h_i(x^{\ast }{)}^{T}d=0\end{array}$$
即$d\in F_2(x^{\ast })$
计算$(1)+\sum {\lambda }_i\ast (2)+\sum {\mu }_i\ast (3)$
$$\begin{array}{rl}& {\alpha }_k\nabla f(x^{\ast }{)}^T{d}_k+\sum {\lambda }_i\nabla g_i(x^{\ast }{)}^T{d}_k+\sum {\mu }_i\nabla h_i(x^{\ast }{)}^T{d}_k+\\ & \frac{{\alpha }_k^2}{2}(d_k^T{\nabla }^{2}f(x_k^{\ast })d_k+\sum {\lambda }_i{d}_k^T{\nabla }^2{g}_i(x^{\ast })d_k+\sum {\mu }_i{d}_k^T{\nabla }^2{h}_i(x^{\ast })d_k)+o({\alpha }_k^2)\le 0\end{array}$$
整理可得
$$\begin{array}{rl}& \underset{=0}{\underbrace{{\alpha }_k(\nabla f(x^{\ast })+\sum {\lambda }_i\nabla g_i(x^{\ast })+\sum {\mu }_i\nabla h_i(x^{\ast }){)}^T{d}_k}}+\\ & \frac{{\alpha }_k^2}{2}{d}_k^T{\nabla }^{2}L(x^{\ast })d_k+o({\alpha }_k^2)\le 0\end{array}$$
即
$$\frac{1}{2}{d}_k^T{\nabla }^{2}L(x^{\ast })d_k+\frac{o({\alpha }_k^2)}{{\alpha }_k^2}\le 0$$
令$k\to \infty$，可知$\exists d\in F_2(x^{\ast })$，使$d^T{\nabla }^{2}L(x^{\ast })d\le 0$.与已知条件矛盾.
综上，$x^{\ast }$是$(P)$的严格局部最优解.

参考资料

约束优化理论 lecture 9. 崔雪婷