最优化抄书笔记：约束优化的最优性条件

七彩极

Reference：
[1] 李董辉，童小娇，万中，数值最优化算法与理论.
[2] 马昌凤，最优化方法及其 Matlab 程序设计.

只看例子可直接跳到5，给出了手算约束优化问题的简单过程。

一、约束优化问题的提法


从今天开始要加快进度了，从这篇笔记开始我们来学习约束优化问题。
约束优化问题的一般提法为
\begin{array}{l} \min f\left( x \right)  \\ s.t.\begin{cases}         g_i\left( x \right) \ge 0,i\in I:=\left\{ 1,\cdots ,m_1 \right\}\\         h_j\left( x \right) =0,j\in J:=\left\{ m_1+1,\cdots ,m \right\}\\ \end{cases} \end{array}\quad\color{violet}{\cdots(1)}
其中 g_i 称为不等式约束， h_j 称为等式约束。
容易看出 \color{violet}{(1)} 的可行域 D=\{x:g_i(x)\ge 0,\ h_j(x) = 0\} 是一个闭集。

二、可行方向


Definition 1  可行方向
我们称 d\in\mathbb R^n 是 x\in D 的一个可行方向，如果存在 \alpha_0>0 ，对任意的 \alpha\in(0,\alpha_0] 成立
x+\alpha d\in D
x 处可行方向的全体记作 FD(x,D) 。可行的下降方向称为可行下降方向。
Remark  容易知道，可行下降方向的定义为 d\in FD(x,D) 且 \nabla f(x)^Td<0 。

Definition 2  序列可行方向
d\in\mathbb R^n 称为 x\in D 的一个序列可行方向，如果存在数列 \{\delta_k\} 和向量序列 \{d_k\} 使得
x+\delta_kd_k\in D,\ \forall k
并且 \delta_k\to 0,d_k\to d 。 x 处序列可行方向的全体记作 SFD(x,D) 。
Remark  换言之，序列可行方向是可行方向的极限。如果可行方向理解为从“边界”向“内部”的箭头，那么序列可行方向就是这些箭头再加上一些“切线”。



Theorem 1
设 x^* 是 \color{violet}{(1)} 的局部最优解，则对任意的 d\in SFD(x^*,D) ，成立
\nabla f(x^*)^Td\ge 0
换言之，最优点处任何的序列可行方向不是下降方向。
Proof
取定 d\in SFD(x^*,D) ，则存在 d_k\to d,\delta_k\to0 使得 x+\delta_kd_k\in D 。因为 x^* 是局部最优解，故当 k 充分大时有
f(x^*)\le f(x^*+\delta_kd_k)=f(x^*)+\delta_k\nabla f(x^*)^Td_k+o(\delta_k)
即
\nabla f(x^*)^Td_k+o(1)\ge 0
令 k\to\infty 即得 \nabla f(x^*)^Td\ge 0 。□

Theorem 2
设 x^*\in D 满足
\nabla f(x^*)^Td>0,\forall d\in SFD(x^*,D)\backslash\{0\}
则 x^* 是 \color{violet}{(1)} 的严格局部最优解。
Proof
反证，假设定理不对，则存在 x_k\to x^* ， x_k\ne x^* 满足 f(x_k)\le f(x^*) 。令 d_k=\frac{x_k-x^*}{\left\|x_k-x^*\right\|} ，则 \{d_k\} 有界，从而必有收敛子列，不妨就设 \{d_k\} 收敛到 d\ne 0 。令 \delta_k=\left\|x_k-x^*\right\| ，则 \delta_k\to 0 。则按定义可知， d\in SFD(x^*,D) 是非零的序列可行方向，但
f\left( x^* \right) \ge f\left( x_k \right) =f\left( x^*+\delta _kd_k \right) =f\left( x^* \right) +\delta _k\nabla f\left( x^* \right) ^Td_k+o\left( \delta _k \right)   
取极限得 \nabla f(x^*)^Td\le 0 ，矛盾。□

Definition 3  有效约束
记 I(x):=\{i:g_i(x)=0\} ，我们称 A(x)=I(x)\cup J 为 x 处的有效集或积极集。若 i\in A(x) ，则对应的 i 称为有效约束，其他约束称为非有效约束。
Remark 1  有效约束的意义是： x 位于可行域的边界 g_i(x)=0 上。
Remark 2  显然等式约束都是有效约束。
Remark 3  一般来说，不同的可行点有不同的有效约束。

Definition 4  线性化可行方向
我们称 d\in\mathbb R^n 是 x\in D 的线性化可行方向，如果
d^T\nabla g_i(x)\ge 0,\ \forall i\in \color{red}{I(x)},\ \ d^T\nabla h_j(x)=0,\ \forall j\in J
x 处线性化可行方向的全体记作 LFD(x,D) 。

Theorem 3
FD(x,D)\subset SFD(x,D)\subset LFD(x,D)
Proof
只需证明第二个包含关系。设 d\in SFD(x,D) ，则存在 d_k\to d,\delta_k\to 0 使得 x+\delta_kd_k\in D ，从而
0\le g_i\left( x+\delta _kd_k \right) =\delta _k\nabla g_i\left( x \right) d_k+o\left( \delta _k \right) ,\forall i\in I\left( x \right)   
0=h_j\left( x+\delta _kd_k \right) =\delta _k\nabla h_j\left( x \right) d_k+o\left( \delta _k \right) ,\forall j\in J
取极限即得到结论。□

我们给出以下两个引理，在这两种情形下有 SFD(x,D)=LFD(x,D) 。

Lemma 1
若 g_i,h_j 都是线性函数，则 FD(x,D)=SFD(x,D)=LFD(x,D) 。

Definition 5  线性无关约束品性
若在 x 处，向量组 \{\nabla g_i(x),\nabla h_j(x)\}_{i\in I,j\in J} 线性无关，则称 x 处LICQ(Linear independence constraint qualification，线性无关约束品性)成立。

Lemma 2
若在 x\in D 处LICQ成立，则 SFD(x,D)=LFD(x,D) 。

三、Kuhn-Tucker最优性条件


Theorem 4
\nabla f(x)^Td\ge 0 对所有 d\in LFD(x,D) 成立的充分必要条件是：存在 \lambda_i,\mu_j,i\in I(x),j\in J ，使得
\nabla f(x)-\sum\limits_{i\in I(x)}\lambda_ig_i(x)-\sum\limits_{j\in J}\mu_j \nabla h_j(x)=0,\quad \lambda_i\ge 0
Proof
充分性：对任意的 d\in LFD(x,D) ，左乘 d^T ，得：
\nabla f(x)^Td-\sum_{i\in I(x)}{\lambda _i}d^T\nabla g_i(x)-\sum_{j\in J}{\mu _j}d^T\nabla h_j(x)=\nabla f(x)^Td-\sum_{i\in I(x)}{\lambda _i}d^T\nabla g_i(x)=0  
从而
\nabla f(x)^Td=\sum_{i\in I(x)}{\lambda _i}d^T\nabla g_i(x)\ge 0  
必要性：记
S=\left\{ \sum_{i\in I\left( x \right)}{\lambda _i\nabla g_i\left( x \right)}+\sum_{j\in J}{\mu _j\nabla h_j\left( x \right)}:\lambda _i,\mu _j\in \mathbb{R} ,\lambda _i\ge 0 \right\}   
我们只要证 \color{red}{\nabla f(x)\in S} 。若不然，我们来找 d\in LFD(x,D) 使得 \nabla f(x)^Td<0 。考虑函数
\psi(s)=\left\|\nabla f(x)-s\right\|^2
则 \psi 是一致凸函数。又 S 是一个闭凸锥(即 tS\subset S,\ \forall t\ge 0 )，故 \psi 在 S 中存在唯一的极小点 \hat s 。再考虑函数
\phi(t)=\left\|t\hat s-\nabla f(x)\right\|^2
可知 t=1 是 \min_{t\ge 0}\phi(t) 的解。这表明 \phi'(1)=0 ，即
\hat s^T(\hat s-\nabla f(x))=0
另一方面，任取 s\in S ，由于 S 是凸集，故 s-\hat s 是 \hat s 处的可行方向，根据Theorem 1有
\nabla \psi \left( \hat{s} \right) ^T\left( s-\hat{s} \right) \ge 0  
也就是
2\left( \hat{s}-\nabla f\left( x \right) \right) ^T\left( s-\hat{s} \right) =2s^T\left( \hat{s}-\nabla f\left( x \right) \right) \ge 0 \quad\color{blue}{\cdots(*)}
令 \color{orange}{d=\hat s-\nabla f(x)} ，则根据 \color{blue}{(*)} ，可知 d\in LFD(x,D) (注意 \nabla g_i(x),\nabla h_j(x)\in S )，并且由于 \nabla f(x)\notin S 可知 d 非零。但
\nabla f\left( x \right) ^Td=\left( \hat{s}-d \right) ^Td=\hat{s}^Td-\left\| d \right\| ^2=\hat{s}^T\left( \hat{s}-\nabla f\left( x \right) \right) -\left\| d \right\| ^2=-\left\| d \right\| ^2<0  
和已知条件矛盾。□

有了这个结果，我们就可以推导出Kuhn-Tucker条件了。首先给出以下的一些定义：

Definition 6  Lagrange函数和Lagrange乘子
我们称 L:\mathbb R^{n+m}\to\mathbb R ，
L(x,\lambda,\mu):=f(x)-\lambda^Tg_I(x)-\mu^Th_J(x)=f(x)-\sum\limits_{i\in I}\lambda_ig_i(x)-\sum\limits_{j\in J}\mu_jg_j(x)
为 \color{violet}{(1)} 的Lagrange函数， \lambda\in\mathbb R^{m_1} 和 \mu\in \mathbb R^{m-m_1} 称为Lagrange乘子。
Remark  对于 x\in D ，显然 L(x,\lambda,\mu)\le f(x) 。

Definition 7   Kuhn-Tucker条件
设 \hat x\in D ，若存在Lagrange乘子 \lambda,\mu 使得
\begin{cases}         \nabla _xL\left( \hat{x},\lambda ,\mu \right) =0\\ \\         h_j\left( \hat{x} \right) =0,\forall j\in J\\ \\         \lambda _i\ge 0,g_i\left( \hat{x} \right) \ge 0,\lambda _ig_i\left( \hat{x} \right) =0,\forall i\in I\\ \end{cases}  
则称 \hat x 满足KT条件，或称 \hat x 是 \color{violet}{(1)} 的KT点。
Remark 1  KT条件也可写成紧凑形势
H\left( \hat{x},\lambda ,\mu \right) :=\left( \begin{array}{c}         \nabla _xL\left( \hat{x},\lambda ,\mu \right)\\         h_J\left( x \right)\\         \min \left\{ \lambda _I,g_I\left( x \right) \right\}\\ \end{array} \right) =0  
Remark 2  有些书上也叫KKT条件。
Remark 3  若 x^* 是KT点，则 L(x^*,\lambda^*,\mu^*)=f(x^*) 。

Theorem 5  一阶必要条件
设 x^* 是 \color{violet}{(1)} 的局部最优解，且 SFD(x^*,D)=LFD(x^*,D) ，则 x^* 是KT点。
Proof
根据Theorem 1知，对任意的 d\in LFD(x^*,D) 有 \nabla f(x^*)^Td\ge 0 。根据Theorem 4，存在 \lambda_i,i\in I(x^*) 和 \mu_j,j\in J 使得
\nabla f(x^*)-\sum\limits_{i\in I(x)}\lambda_i^*\nabla g_i(x^*)-\sum\limits_{j\in J}\mu_j^* \nabla h_j(x^*)=0,\quad \lambda_i^*\ge 0
再对于那些 i\in I\backslash I(x^*) ，令 \lambda_i^*=0 ，则上式就成为
\nabla f(x^*)-\sum\limits_{i\in I}\lambda_i^*\nabla g_i(x^*)-\sum\limits_{j\in J}\mu_j^* \nabla h_j(x^*)=0,\quad \lambda_i^*\ge 0
这就是KT条件的第一个条件。显然，第二个条件也满足。最后，若 i\in I(x^*) ，则 g_i(x^*)=0 ，否则我们定义了 \lambda_i^*=0 ，这就是第三个条件。□
Remark  特别地，如果诸 g_i,h_j 都是线性的，或者极小点处LICQ成立，则极小点是KT点。

最后指出，对于凸优化问题，KT条件也是充分条件。

Theorem 6  凸优化的充要条件
设 \color{violet}{(1)} 中 f 是凸函数， g_i 是凹函数， h_i 是线性函数， x^*\in D 满足KT条件，则 x^* 是 \color{violet}{(1)} 的全局极小点。
Proof
由 f 的凸性和 g_i 的凹性可得：
f(x)\ge f(x^*)+\nabla f(x^*)^T(x-x^*),\ g_i(x)\le g(x^*)+\nabla g(x^*)^T(x-x^*),\ \forall i\in I
特别地，对于 i\in I(x^*) 有
0\le g_i(x)\le g_i(x^*)+\nabla g_i(x^*)^T(x-x^*)=\nabla g_i(x^*)^T(x-x^*)
由于 h_j 是线性的，故可设 h_j(x)={a_j}^Tx+b_j ，我们有 \nabla h_j(x)=a_j ，故
\nabla h_j(x^*)(x-x^*)={a_j}^T(x-x^*)=({a_j}^Tx-b_j)-({a_j}^Tx^*-b_j)=0
综合上述，任取 x\in D ，由KT条件即得
\begin{array}{l} f\left( x \right) \ge f\left( x^* \right) +\nabla f\left( x^* \right) ^T\left( x-x^* \right)  \\  \\\displaystyle =f\left( x^* \right) +\sum_{i\in I\left( x^* \right)}{\lambda _{i}^{*}\nabla g_i\left( x \right) ^T\left( x-x^* \right)}+\sum_{j\in J}{\mu _{j}^{*}\nabla h_j\left( x \right) ^T\left( x-x^* \right)} \\  \\ \ge f\left( x^* \right)  \end{array}
□

四、二阶最优性条件


这部分介绍约束问题的二阶最优性条件。首先引入下面的记号：

Notation
设 x^* 是 \color{violet}{(1)} 的局部最优解且 SFD(x^*,D)=LFD(x^*,D) ，则 x^* 是KT点，对应的Lagrange乘子记作 \lambda^*,\mu^* 。记 z^*=(x^*,\lambda^*,\mu^*) ， S(z^*) 是满足下面条件的 d\in\mathbb R^n 的全体：
\begin{cases}         d^T\nabla h_j\left( x \right) =0,\forall j\in J\\         d^T\nabla g_i\left( x \right) =0,\forall i\in I(x^*)\\         d^T\nabla g_i\left( x \right) \ge 0,\forall i\in I\backslash I(x^*)\\ \end{cases}  
(易知： S(z^*)\subset LFD(x^*,D) )

Lemma 3  二阶必要条件
设 f,g_i,h_j 都二阶连续可微， x^* 是 \color{violet}{(1)} 的局部最优解且在该点处LICQ成立， z^* 的定义同上，则
w^T\nabla _{x}^{2}L\left( z^* \right) w\ge 0,\  \forall w\in S\left( z^* \right)   
Remark  一个简单的推论：若  \nabla _{x}^{2}L\left( z^* \right)   负定，则 x^* 不是极小点。

Theorem 7  二阶充分条件
设 x^*\in D,\lambda^*\in\mathbb R^{m_1},\mu^*\in\mathbb R^{m-m_1} 满足KT条件。若
w^T\nabla_x^2 L(z^*)w>0,\ \forall w\in S(z^*)
则 x^* 是 \color{violet}{(1)} 的严格局部极小点。
Proof
反证，假设定理的结论不对，我们来找 d\in S(z^*) 使得 d^T\nabla_x^2 L(z^*)d\le 0 。
首先，因为 x^* 不是严格的极小点，可知存在 x_k\to x^* 且 x_k\ne x^* 使得 f(x_k)\le f(x^*) 。类似于Theorem 2中的讨论，令 d_k=\frac{x_k-x^*}{\left\|x_k-x^*\right\|} ，不妨设 d_k\to d ，则 d 非零， d\in SFD(x^*,D)\subset LFD(x^*,D) ，并且 \nabla f(x^*)^Td\le 0 (这不是平凡的，但是和Theorem 2中的讨论完全一致)。于是由KT条件得
0\ge \nabla f\left( x^* \right) ^Td=\sum_{i\in I}{\lambda _id^T\nabla g_i\left( x^* \right)}+\sum_{j\in J}{\mu _jd^T\nabla h_j\left( x^* \right)}=\sum_{i\in I\left( x^* \right)}{\lambda _id^T\nabla g_i\left( x^* \right)}\ge 0  
因为 d\in LFD(x^*,D) ，故 d^T\nabla g_i(x)\ge 0 对任意 i\in I 成立，从而 d^Tg_i(x)=0,\ \forall i\in I(x^*) ，这说明了 \color{red}{d\in S(z^*)} 。但
\begin{array}{l}\displaystyle 0\ge f\left( x_k \right) -f\left( x^* \right) \ge L\left( x_k,\lambda ^*,\mu ^* \right) -f\left( x^* \right)  \\  \\\displaystyle =L\left(z^* \right) +\left( x_k-x^* \right) \nabla _xL\left( z^* \right) +\frac{1}{2}\left( x_k-x^* \right) ^T\nabla _{x}^{2}L\left( z^* \right) \left( x_k-x^* \right) -f\left( x^* \right) +o\left( \left\| x_k-x \right\| ^2 \right)   \\  \\\displaystyle  =\frac{1}{2}\left( x_k-x^* \right) ^T\nabla _{x}^{2}L\left( z^* \right) \left( x_k-x^* \right) +o\left( \left\| x_k-x \right\| ^2 \right)   \end{array}
故
\frac{1}{2}\left( \frac{x_k-x^*}{\left\| x_k-x \right\|} \right) ^T\nabla _{x}^{2}L\left( z^* \right) \left( \frac{x_k-x^*}{\left\| x_k-x \right\|} \right) +o\left( 1 \right) =\frac{1}{2}{d_k}^T\nabla _{x}^{2}L\left( z^* \right) d_k+o\left( 1 \right) \le 0  
令 k\to\infty 即得 d^T\nabla_x^2 L(z^*)d\le 0 ，与已知矛盾。□

五、一个例子


Example 1
设 x=(x_1,x_2)^T ，考虑如下的约束优化问题：
\begin{array}{l} \min f\left( x \right) =x_1 \\ s.t.\begin{cases}         g\left( x \right) =16-\left( x_1-4 \right) ^2-x_{2}^{2}\ge 0\\         h\left( x \right) =x_{1}^{2}+\left( x_2-2 \right) ^2-4=0\\ \end{cases} \end{array}\quad\color{cyan}{\cdots(\star)}
这个问题的几何意义很明显： h 是以 (0,2) 为圆心， 2 为半径的圆周；而 g 是以 (4,0) 为圆心， 4 为半径的圆的内部(包含边界)，即图中红色的这一段是可行域：


在这里面要找让 x_1 最小的那个 x ，那么精确解显然是 (0,0)^T 。

当然，这是我们肉眼看出来的，接下来我们利用KT条件和二阶条件来进行严格的分析。
首先写出 \color{cyan}{(\star)} 的Lagrange函数为
L\left( x,\lambda ,\mu \right) =x_1-\lambda \left[ 16-\left( x_1-4 \right) ^2-x_{2}^{2} \right] -\mu \left[ x_{1}^{2}+\left( x_2-2 \right) ^2-4 \right]   
对它求导得到
\nabla _xL\left( x,\lambda ,\mu \right) =\left( \begin{array}{c}         1+2\left( x_1-4 \right) \lambda -2x_1\mu\\         2x_2\lambda -2\left( x_2-2 \right) \mu\\ \end{array} \right) =0 \quad \color{green}{\cdots(\rm I)}
补上KT条件的另外两个条件：
\min \left\{ \lambda ,16-\left( x_1-4 \right) ^2-x_{2}^{2} \right\} =0 \quad\color{blue}{\cdots(\rm II)}
x_{1}^{2}+\left( x_2-2 \right) ^2-4=0\quad\color{red}{\cdots(\rm III)}  
接下来我们需要解这个System。可以从 \color{blue}{(\rm II)} 这个条件入手，分情况讨论：
Case 1： \lambda=0 ，这时 \color{green}{(\rm I)} 的第二个方程为 2(x_2-2)\mu=0 。显然不能是 \mu=0 ，否则 \color{green}{(\rm I)} 的第二个等式就成为 1=0 ，从而 x_2=2 。再由 \color{red}{(\rm III)} 得到 x_1=\pm 2 ，但由 \color{blue}{(\rm II)} 可知，只能是 x_1=2 ，否则 g(x)<0 。再解 \color{green}{(\rm I)} 的第一个方程 1-2x_1\mu=0 得到 \mu=\frac{1}{4} 。至此我们得到第一个KT点：
\color{magenta}{(x^1,\lambda^1,\mu^1)=((2,2)^T,0,\frac{1}{4})}
Case 2：  16-\left( x_1-4 \right) ^2-x_{2}^{2}=0  ，这时可设
x_1=4+4\cos \theta ,x_2=4\sin \theta \text{，}\theta \in \left[ 0,2\pi \right)   
代入 \color{red}{(\rm III)} 得
16+32\cos \theta +16\cos ^2\theta +16\sin ^2\theta +4-16\sin \theta -4=0  
化简得
\sin \theta -2\cos \theta =2  
利用辅助角公式(提一个 \sqrt 5 出来)，得
\sin \left( \theta -\mathrm{arc}\tan 2 \right) =\sin \left( \mathrm{arc}\tan 2 \right)   
于是  \theta =\pi   或 \theta =2\mathrm{arc}\tan 2 。
Case 2.1： \theta=\pi ，此时易知 x=(0,0)^T ，此时 \color{green}{(\rm I)} 成为
1-8\lambda=0,\ \mu=0
至此得到第二个KT点
\color{magenta}{(x^2,\lambda^2,\mu^2)=((0,0)^T,\frac{1}{8},0)}
Case 2.2： \theta=2\arctan 2 ，此时计算得 \tan\theta=-\frac{4}{3} ，即它的补角所在的三角形是“345”，其中“ 5 ”是圆的半径 4 ，那么“ 4 ”就是 3.2 ，“ 3 ”就是 2.4 。于是 x_1=4-2.4=\frac{8}{5} ， x_2=3.2=\frac{16}{5} 。再代入 \color{green}{(\rm I)} ，解一个比较痛苦的线性方程组可得 \lambda=\frac{3}{40},\mu=\frac{1}{5} (我自己没算)。至此，我们得到第三个KT点
\color{magenta}{(x^3,\lambda^3,\mu^3)=((\frac{8}{5},\frac{16}{5})^T,\frac{3}{40},\frac{1}{5})}
再来看二阶条件，我们对 L 求二阶导，得到：
\nabla _{x}^{2}L\left( x,\lambda ,\mu \right) =\nabla _x\left( \begin{array}{c}         1+2\left( x_1-4 \right) \lambda -2x_1\mu\\         2x_2\lambda -2\left( x_2-2 \right) \mu\\ \end{array} \right) =\left( \begin{matrix}         2\lambda -2\mu&                0\\         0&                2\lambda -2\mu\\ \end{matrix} \right) =2\left( \lambda -\mu \right) I_2  
对于三个KT点 \color{magenta}{x^i} ，我们发现，在 \color{magenta}{x^1,x^3} 处， \lambda-\mu<0 ，此时Lagrange函数的Hesse阵是负定的，从而它们一定不是极小点；而 \color{\magenta}{x^2} 处， \lambda-\mu=\frac{1}{8}>0 ，此时L函数的Hesse阵正定，从而 \color{magenta}{x^2} 是极小点。
综合上述， \color{magenta}{x^2} 是 \color{cyan}{(\star)} 的唯一全局极小点。

从这个问题当中也可以看出来，人工求解这种约束优化问题是非常麻烦的，因此从下一篇笔记开始我们将介绍用于求解约束优化问题的各种算法。