约束最优化方法 (一) 最优性条件

本文首发于公众微信号-AI研究订阅号，来源东北大学模式识别研究生课程《最优化》个人学习笔记。之前讨论的是无约束最优化方法，这一节主要介绍的是带有约束的非线性规划问题，所谓的非线性规划，就是约束项里面不仅有等式约束，还有不等式约束。解这类问题有两种方法，一个是容许方向法、它是一种直接处理约束的方法；另一个是罚函数法，它是将约束问题转变成一系列无约束问题，用无约束的极小点去逐渐逼近约束问题的...

小小何先生

11094人浏览 · 2019-12-02 21:09:29

小小何先生 · 2019-12-02 21:09:29 发布

之前讨论的是无约束最优化方法，这一节主要介绍的是带有约束的非线性规划问题，所谓的非线性规划，就是约束项含有平方这种。解这类问题有两种方法，一个是容许方向法、它是一种直接处理约束的方法；另一个是罚函数法，它是将约束问题转变成一系列无约束问题，用无约束的极小点去逐渐逼近约束问题的极小点。但是在介绍这两种方法之前，要先介绍一些概念。

最优性条件

最优性条件：
最优性条件，就是最优化问题的目标函数与约束函数在最优点所满足的充分条件和必要条件。
最优性必要条件：
最优性必要条件是指，最优点应该满足的条件。也就是已知其为最优点，能够推断出来的条件。
最优性充分条件：
最优性充分条件是指，可使得某个容许点成为最优点的条件。也就是知道一些条件，能够推出其为最优点。

本节主要讨论一般约束问题的最优性条件。我们将先从仅含等式约束或不等式约束的问题入手，然后自然过渡到一般约束问题。所以这一节主要介绍各种约束下的最优性条件，也就是各种约束下，什么样的条件能够推出这个点是最优点、另外一种，已知各种约束下的最优点，能够推出什么条件。整体目录结构如下：

等式约束问题的最优性条件
不等式约束问题的最优性条件
- 几何最优性条件
- Fritz John条件
- Kuhn-Tucker条件
一般约束问题的最优性条件

等式约束问题的最优性条件

考虑仅含等式约束的问题1：
$\begin{array}{l}{\min f(x)} \\ {\text {s.t. } h_{j}(x)=0, \quad j=1,2, \cdots, l .}\end{array}$

这个问题的最优性条件与求解方法在微积分中已从理论上得到了解决，这就是Lagrange定理和Lagrange乘子法。

定理1：假设

i) ： $x^{*}$ 是上述约束问题的局部最优点；
ii) : $f$ , $h_{1}$ , $h_{2}$ , $\cdot\cdot\cdot$ , $h_{l}$ ： $R^{n}\rightarrow R^{1}$ 在 $x^{*}$ 附近连续可微（有一阶连续偏导数）。
iii) : $\bigtriangledown h_{1}(x^{*})$ ， $\bigtriangledown h_{2}(x^{*})$ ， $\cdot\cdot\cdot$ ， $\bigtriangledown h_{l}(x^{*})$ 线性无关，则存在实数 $\lambda_{1}^{*}$ ， $\lambda_{2}^{*}$ ， $\cdot\cdot\cdot$ ， $\lambda_{l}^{*}$ 使得：
$\nabla f\left(x^{*}\right)=\sum_{j=1}^{l} \lambda_{j}^{*} \nabla h_{j}\left(x^{*}\right)$

这个定理的意义还在于，它把对等式约束问题的求解转化为对无约束问题的求解。

上式是最优性一阶必要条件。

定理2：在约束问题1中，假设：

i) ： $f$ , $h_{1}$ , $h_{2}$ , $\cdot\cdot\cdot$ , $h_{l}$ ： $R^{n} \rightarrow R^{1}$ 是二次连续可微函数；
ii) : 存在 $x^{*} \in R^{n}$ 与 $\lambda^{*} \in R^{l}$ ，使得Lagrange函数的梯度为零，即：
$\bigtriangledown L(x^{*},\lambda^{*})=0$
iii) : 对于满足条件：

$v^{T} \bigtriangledown h_{j}(x^{*})=0，j=1,2,···，l$

的任意非零向量 $\in R^{n}$ ，都有：
$v^{T} \bigtriangledown_{x}^{2}L(x^{*}，\lambda^{*})v > 0$

这个定理的几何意义是，在Lagrange函数的驻点 $[x^{*} \ \ \lambda^{*}]$ 处，如果Lagrange函数关于 $x$ 的Hesse矩阵在 $l$ 个约束(超)曲面的切平面的交集上正定(注意，并不需要在原来的空间中正定)，那么 $x^{*}$ 就是严格局部极小点。

这里就是直接给出两个定理，没办法，理解记忆吧。第一个定理相对来说比较重要一点。

不等式约束问题的最优性条件

几何最优性条件

下面将给出约束问题2：
$\begin{array}{l}{\min f(x)} \\ {\text {s.t. } s_{i}(x) \geqslant 0, \quad i=1,2, \cdots, m .}\end{array}$
的最优性条件。

定义1 ：对于约束问题，设 $\overline{x} \in D$ ， $D=\{x|s_{i}(x)\geq 0 , i =1,2, \cdots, m \}$ 若 $\overline{x}$ 使得某个不等式约束有 $s_{i}(\overline{x})=0$ ，则该不等式约束 $s_{i}(x) \geq 0$ 称为是关于容许点 $\overline{x}$ 的起作用约束；否者，若 $s_{i}(\overline{x}) > 0$ ，则该不等式约束称为是关于容许点的不起作用约束。

定义2 ：设 $C$ 是 $R$ 中的非空集，且 $\in C$ 。对于 $\forall p \in R^{n}$ ，若当 $\in C$ 时，对于 $\forall t \geq 0$ ，必有 $\in C$ ，则集合 $C$ 称为以 $x$ 为顶点的锥。若锥 $C$ 是凸集，则称为凸锥。

定义3 ：设 $D$ 是 $R^{n}$ 中的非空集，且 $\in D$ 。对于非零向量 $\in R^{n}$ ，若存在 $\delta > 0$ ，当 $\in (0, \delta)$ 时，必有 $\in D$ ，则 $p$ 称为点 $x$ 的容许方向向量，其方向称为点 $x$ 的容许方向。由点 $x$ 的全部容许方向向量构成的集合称为点 $x$ 的容许方向集，或者说容许方向锥。
如图所示
引理：设 $\overline{x} \in D = \{x|s_{i}(x) \geq 0, i =1,2, \cdots , m\}$ ， $I=\{i|s_{i}(\overline{x})=0,i=1,2, \cdots, m\}$ ；并设当 $\in I$ 时， $s_{i}(x)$ 在点 $\widetilde{x}$ 处可微，当 $\overline{i \in I}$ 时， $s_{i}(x)$ 在点 $\widetilde{x}$ 处连续。若对于所有的 $\in I$ ，向量 $p$ 都使得 $\bigtriangledown_{s_{i}}(\widetilde{x})^{T}p >0$ ，则 $p$ 是点 $\widetilde{x}$ 的一个容许方向。

约束曲面 $s_{i}(x)=0$ 把整个空间分成两部分，梯度 $\bigtriangledown_{s_{i}}(\widetilde{x})$ 总是指向包含容许集的那一侧。

把由点 $x$ 的所有下降方向向量构成的集合称为点 $x$ 的下降方向锥。

定理：设 $f:R^{n} \rightarrow R^{1}$ 在点 $x$ 可微，则点 $x$ 处的下降方向向量 $p$ 必满足：
$\bigtriangledown f(x)^{T}p < 0$

记 $S(x)=\{p|\bigtriangledown f(x)^{T}p < 0 \}$ ，则 $S (x)$ 是点 $x$ 处的下降方向集。显然 $S (x)$ 是 $R^{n}$ 中的半空间。

接下来就是几何最优性条件的定义：(因为这个条件是仅借助点集的概念给出的，所以称为几何最优性条件)：

定理： 在约束问题2中，若 $x^{*}$ 是局部最优点，则点 $x^{*}$ 处的容许方向锥和下降方向锥的交集是空集。

上面这个定理仅仅是必要的，而不是充分的。也就是说知道这个点是最优点能够推断出容许方向锥和下降方向锥的交集是空集，但由容许方向锥和下降方向锥的交集是空集并不能推断出其是最优点。

Fritz John条件

这里要介绍：引理(Farkas)、引理(Gordan)、定理：Fritz John

引理(Farkas)：设 $a_{1}$ ， $a_{2}$ ， $\cdots$ ， $a_{m}$ 和 $b$ 是 $n$ 维向量，则满足：
$a_{i}^{T}p \geq 0, \ i=1,2,\cdots , m$
的向量 $p$ 也满足
$b^{T}p \geq 0$
的充要条件是，存在非负数 $\gamma_{1}$ ， $\gamma_{2}$ ， $\cdots$ ， $\gamma_{n}$ ，使得：
$b=\sum_{i=1}^{m}\gamma_{i}a_{i}$

这个依旧不需要证明，相信它就完事了，因为直观上感觉就是非常正确的。可以看课本图4-6。或者下面这张图理解( $b$ 理解为 $f(x^{*})$ )：

引理(Gordan)：设 $a_{1}$ ， $a_{2}$ ， $\cdots$ ， $a_{m}$ 是 $n$ 维向量，则不存在向量 $p$ 使得：
$a_{i}^{T}p<0, \ \ i=1,2, \cdots,m$
成立的充要条件是，存在不全为零的非负数 $\gamma_{1}$ ， $\gamma_{2}$ ， $\cdots$ ， $\gamma_{n}$ ，使得：
$\sum_{i=1}^{m}\gamma_{i}a_{i}=0$
这个怎么理解呢？不存在向量 $p$ 使得 $a_{i}^{T}p<0, \ \ i=1,2, \cdots,m$ ，所表示的几何意义就是 $a_{1}$ ， $a_{2}$ ， $\cdots$ ， $a_{m}$ 不会在超平面的一侧，因为要是在一侧的话，就会存在这样一个向量 $p$ 满足要求。既然不会在一侧，那么就一定会有一个非零的线性组合，使其最终结果为0。

定理：Fritz John： 在问题2中，设 $x^{*}$ 是局部最优解， $f (x)$ ， $s_{1}(x)$ ， $s_{2}(x)$ ， $\cdots$ ， $s_{m}(x)$ 在点 $x^{*}$ 处可微，那么，存在不全为零的实数 $\mu_{0}$ ， $\mu_{1}$ ， $\cdots$ ， $\mu_{m}$ 使得：
$\left.\begin{array}{rl}{\mu_{0} \nabla f\left(x^{*}\right)-\sum_{i=1}^{m} \mu_{i} \nabla s_{i}\left(x^{*}\right)} {=0} \\ {\mu_{i} s_{i}\left(x^{*}\right)=0,} {\ \ \ i=1,2, \cdots, m} \\ {\mu_{i} \geq 0,} {\ \ \ i=0,1, \cdots, m}\end{array}\right\}$

上面这个式子我们来理解一下，因为这个 $x^{*}$ 是最优点，所以这个容许集和下降方向集是空集。所以不存在向量 $p$ ，使得：
$\nabla f\left(x^{*}\right)^{T} p<0, \\ \left(-\nabla s_{i}\left(x^{*}\right)\right)^{T} p<0, i \in I\left(x^{*}\right)$

$\mu_{i}s_{i}(x^{*})=0\ (i=1,2,\cdots ,m)$ 称为互补松弛条件。它表明：若 $s_{i}(x^{*})>0$ ，即 $\overline{\in} I$ ，则必有 $\mu_{i}=0$ ；若 $\mu_{i}>0$ ，则必有 $s_{i}(x^{*})=0$ ，即 $\in I$ 。

这个定理给你了问题2的一个最优性必要条件。上式称为Fritz John条件，满足Fritz-John条件的点称为Fritz-John点。 $\mu_{1}$ ， $\mu_{2}$ ， $\cdots$ ， $\mu_{m}$ 也称为Lagrange乘子。

Fritz-John条件仅是判别某一容许点是否为最优点的必要条件，而不是充分条件。

Kuhn-Tucker条件

如果Fritz-John条件中 $\mu_{0}=0$ 时，Fritz-John条件失去实用价值。为了使得其大于0，就有了Kuhn-Tucker条件。

定理：Kuhn-Tucker：

在问题2中，假设
i） $x^{*}$ 是局部最优点；
ii) $f(x),s_{1}(x),s_{2}(x),···，s_{m}(x)$ 在点 $x^{*}$ 处可微；
iii) 点 $x^{*}$ 处的全部起作用约束的梯度线性无关。那么存在实数 $\mu_{1}、\mu_{2}，···，\mu_{m}$ 使得：
$\begin{aligned} \nabla f\left(x^{*}\right)-\sum_{i=1}^{m} \mu_{i} \nabla s_{i}\left(x^{*}\right) =&0 \\ \mu_{i} S_{i}\left(x^{*}\right)=0, i=1,2, \cdots, &m, \\ \mu_{i} \geq 0, i=1, \cdots, &m \end{aligned}$

Kuhn-Tucker条件是Fritz John条件的特殊情况。

Kuhn-Tucker条件有明显的几何意义。在Kuhn-Tucker定理的公式中，删去不起作用约束项（注意，它们的系数是 $\mu_{i}=0$ ，当 $\overline{\in}I$ ，Kuhn-Tucker条件可简写成：存在 $\mu_{i} \geq 0$ （ $\in I$ ）使得：
$\nabla f(x^{*})=\sum_{i \in I}\mu_{i}\nabla_{s_{i}}(x^{*})$

此式在几何上表示：若 $x^{*}$ 是问题地最优解，根据Farkas引理可知，在此点处地目标函数地梯度必处在由起作用约束函数地梯度张成地凸锥之中。

一般约束问题的最优性条件

之前是不等式约束，现在考虑一般约束问题地最优性条件，既有等式约束还有不等式约束的情况。我们这节就介绍一般约束问题下的Fritz-John定理和Kuhn-Tucker定理：

Fritz-John定理：

考虑问题：

$\left.\begin{array}{ll}{\min } & {f(x)} \\ {\text {s.t.}} & {s(x) \geq 0} \\ {} & {h(x)=0}\end{array}\right\}$

在上述问题中设 $x^{*}$ 是局部最优点 $f (x)$ ， $s_{1}(x), \cdots ,s_{m}(x), h(x), \cdots ,h_{l}(x)$ 在点 $x^{*}$ 处可微。那么，存在不全为零的实数 $\mu_{0},\mu_{1},\cdots .\mu_{m}, \lambda_{1},\lambda_{2},\cdots \lambda_{l}$ ，使得：
$\begin{aligned} \mu_{0} \nabla f\left(x^{*}\right) &-\sum_{i=1}^{m} \mu_{i} \nabla s_{i}\left(x^{*}\right)-\sum_{j=1}^{l} \lambda_{j} \nabla h_{j}\left(x^{*}\right)=0 \\ \mu_{i} S_{i}\left(x^{*}\right) &=0, \quad i=1,2, \cdots, m \\ \mu_{i} & \geq 0, \quad i=0,1, \cdots, m \end{aligned}$

这个定理可以看成是Lagrange定理的结论与Fritz-John定理的结论的合并。相当于多了 $l$ 个等式约束。

Kuhn-Tucker定理：

考虑问题：

$\left.\begin{array}{ll}{\min } & {f(x)} \\ {\text {s.t.}} & {s(x) \geq 0} \\ {} & {h(x)=0}\end{array}\right\}$

假设：
i) $x^{*}$ 是局部最优解；
ii） $f(x)，s_{1}(x)，\cdots , s_{m}(x)，h_{1}(x)，\cdots ，h_{l}(x)$ 在点 $x^{*}$ 处可微；
iii）点 $x^{*}$ 处的全部起作用约束的梯度线性无关。

那么存在实数 $\mu_{0},\mu_{1},\cdots .\mu_{m}, \lambda_{1},\lambda_{2},\cdots \lambda_{l}$ 使得：

$\begin{aligned} \nabla f\left(x^{*}\right)-\sum_{i=1}^{m} \mu_{i} \nabla s_{i}\left(x^{*}\right)-\sum_{j=1}^{l} \lambda_{j} \nabla h_{j}\left(x^{*}\right)=0 \\ \mu_{i} S_{i}\left(x^{*}\right)=0, \quad i=1,2, \cdots, m \\ \mu_{i} \geq 0, i=1, \cdots, m& \end{aligned}$

定理：
在以下凸规划问题中：
$\left.\begin{array}{ll}{\min } & {f(x)} \\ {\text {s.t.}} & {s(x) \geq 0} \\ {} & {h(x)=0}\end{array}\right\}$
假设 $f$ 是可微凸函数， $s_{1}，\cdots ,s_{m}$ 是可微凹函数， $h_{1}，\cdots ,h_{l}$ 是线性函数。若 $x^{*}$ 是上述问题的Kuhn-Tucker点，则 $x^{*}$ 就是上述问题的全局最优点。(用Hesson矩阵即可证明是不是凸优化问题)。