【最优化】非线性优化及KKT条件

无约束极值问题的极值条件

最优性条件就是最优化问题的目标函数与约束函数在最优点所满足的充分条件和必要条件

考虑非线性规划问题

$\min\;f(\boldsymbol x),\quad\boldsymbol x\in\Bbb R^n$

其中， $f(\boldsymbol x)$ 是定义在 $\Bbb R^n$ 上的实函数。该问题就是求 $f(\boldsymbol x)$ 在 $n$ 维欧氏空间中的极小点，称为无约束极值问题。

下降方向

定理：设函数 $f(\boldsymbol x)$ 在点 $\bar{\boldsymbol x}$ 处可微，若存在方向 $\boldsymbol d$ 使得 $\nabla f(\bar{\boldsymbol x})^\top\boldsymbol d\lt0$ ，则存在 $\delta\gt0$ 使得 $\forall \lambda\in(0,\delta)$ 有：

$f(\overline{\boldsymbol x}+\lambda\boldsymbol d)\lt f(\overline{\boldsymbol x})$

事实上， $\nabla f(\bar{\boldsymbol x})^\top\boldsymbol d$ 就是函数 $f(\boldsymbol x)$ 在点 $\bar{\boldsymbol x}$ 处的方向导数 $\text{D}f(\bar{\boldsymbol x};\boldsymbol d)$ 。而满足上述条件的方向称为下降方向。

该定理的可以通过对函数 $f(\overline{\boldsymbol x}+\lambda\boldsymbol d)$ 在 $\bar{\boldsymbol x}$ 处的 Taylor 展开式推导得到。

必要条件

一阶必要条件：设函数 $f(\boldsymbol x)$ 在点 $\bar{\boldsymbol x}$ 处可微，若 $\bar{\boldsymbol x}$ 是局部极小点，则此处的梯度 $\nabla f(\bar{\boldsymbol x})=\bf0$ .

证明：反证法. 若 $\nabla f(\bar{\boldsymbol x})\neq\bf0$ ，令方向 $\boldsymbol d=-\nabla f(\bar{\boldsymbol x})$ ，则方向导数

$\nabla f(\bar{\boldsymbol x})^\top\boldsymbol d=-\nabla f(\bar{\boldsymbol x})^\top\nabla f(\bar{\boldsymbol x})=-\Vert\nabla f(\bar{\boldsymbol x})\Vert^2\lt0$

满足前述定理的条件，所以应该有 $f(\overline{\boldsymbol x}+\lambda\boldsymbol d)\lt f(\overline{\boldsymbol x})$ ，这与 $\bar{\boldsymbol x}$ 是局部极小点的前提矛盾（因为邻域内还有函数值比它小的点）。

注意，该条件为必要条件。所以 $\nabla f(\bar{\boldsymbol x})=\bf0$ 不能反过来说明 $\bar{\boldsymbol x}$ 是局部极小点。梯度为0的点可能是极小点、极大点或是鞍点，它们都统称为驻点。

二阶必要条件：设函数 $f(\boldsymbol x)$ 在点 $\bar{\boldsymbol x}$ 处二次可微，若 $\bar{\boldsymbol x}$ 是局部极小点，则此处的梯度 $\nabla f(\bar{\boldsymbol x})=\bf0$ ，且 Hesse 矩阵 $\nabla^2f(\bar{\boldsymbol x})$ 半正定。

证明：根据一阶必要条件，接下来只需证明海森矩阵半正定即可。
将函数 $f(\overline{\boldsymbol x}+\lambda\boldsymbol d)$ 在 $\bar{\boldsymbol x}$ 处的 Taylor 展开到二阶：

$f(\overline{\boldsymbol x}+\lambda\boldsymbol d)=f(\overline{\boldsymbol x})+\frac12\lambda^2\boldsymbol d^\top\nabla^2f(\overline{\boldsymbol x})\boldsymbol d+o\left(\Vert\lambda\boldsymbol d\Vert^2\right)$

移项，然后两边同时除以 $\lambda^2$ ，得：

$\frac{f(\overline{\boldsymbol x}+\lambda\boldsymbol d)-f(\overline{\boldsymbol x})}{\lambda^2}=\frac12\boldsymbol d^\top\nabla^2f(\overline{\boldsymbol x})\boldsymbol d+\frac{o\left(\Vert\lambda\boldsymbol d\Vert^2\right)}{\lambda^2}$

自然，当 $\vert\lambda\vert$ 充分小时，由于 $\bar{\boldsymbol x}$ 是局部极小点所以 $f(\overline{\boldsymbol x}+\lambda\boldsymbol d)\geq f(\overline{\boldsymbol x})$ ，从而得到：

$\boldsymbol d^\top\nabla^2f(\overline{\boldsymbol x})\boldsymbol d\geq0$

即Hesse 矩阵 $\nabla^2f(\bar{\boldsymbol x})$ 半正定。证毕。

充分条件

二阶充分条件：设函数 $f(\boldsymbol x)$ 在点 $\bar{\boldsymbol x}$ 处二次可微，若此处的梯度 $\nabla f(\bar{\boldsymbol x})=\bf0$ ，且 Hesse 矩阵 $\nabla^2f(\bar{\boldsymbol x})$ 正定（不是半正定），则 $\bar{\boldsymbol x}$ 是局部极小点。

证明：已知 $\nabla f(\bar{\boldsymbol x})=\bf0$ ，现将函数 $f(\boldsymbol x)$ 在 $\bar{\boldsymbol x}$ 处的 Taylor 展开到二阶：

$f(\boldsymbol x)=f(\overline{\boldsymbol x})+\frac12(\boldsymbol{x-\overline{x}})^\top\nabla^2f(\overline{\boldsymbol x})(\boldsymbol{x-\overline{x}})+o\left(\Vert(\boldsymbol{x-\overline{x}})\Vert^2\right)$

设 Hesee 矩阵的最小特征值为 $\lambda_{\min}$ ，则中间项：

$(\boldsymbol{x-\overline{x}})^\top\nabla^2f(\overline{\boldsymbol x})(\boldsymbol{x-\overline{x}})\geq\lambda_{\min}\Vert(\boldsymbol{x-\overline{x}})\Vert^2$

从而有：

f(\boldsymbol x)\geq f(\overline{\boldsymbol x})+\left(\frac12\lambda_\min +\frac{o\left(\Vert(\boldsymbol{x-\overline{x}})\Vert^2\right)}{\Vert(\boldsymbol{x-\overline{x}})\Vert^2}\right)\Vert(\boldsymbol{x-\overline{x}})\Vert^2

所以，当 $\boldsymbol{x\to\overline{x}}$ 时， $\exists\epsilon\gt0,\;\boldsymbol x\in N(\bar{\boldsymbol x},\epsilon),\; f(\boldsymbol x)\geq f(\overline{\boldsymbol x})$ .

即 $\bar{\boldsymbol x}$ 是局部极小点。证毕。

充要条件

考虑凸性函数时，可以得出全局极小点的充分必要条件。

无约束凸函数极值条件：设 $f(\boldsymbol x)$ 是定义在 $\Bbb R^n$ 上的可微凸函数， $\bar{\boldsymbol x}\in\Bbb R^n$ ，则 $\bar{\boldsymbol x}$ 是全局极小点的充分必要条件是此处的梯度 $\nabla f(\bar{\boldsymbol x})=\bf0$ 。

另：若 $f(\boldsymbol x)$ 是严格凸函数，则全局极小点唯一。

约束极值问题的最优性条件

有约束的极值问题一般表示如下：

$\begin{aligned} \min \quad&f(\boldsymbol x)\\ \text{s. t. }\quad&g_i(\boldsymbol x)\geq0,\quad i=1,...,m\\ &h_j(\boldsymbol x)=0,\quad j=1,...,l \end{aligned}$

可行方向

规定：

可行域：满足约束条件（包括不等式约束和等式约束）的点的集合，记为 $S$ ；
下降方向集：由所有下降方向组成的集合，根据其定义可记为 $F_0=\{\boldsymbol d\mid\nabla f(\bar{\boldsymbol x})^\top\boldsymbol d\lt0\}$ ；

类比无约束问题，我们要考察局部极小点，我们就需要衡量是否点 $\bar{\boldsymbol x}$ 在其邻域内沿着可能的所有方向移动后函数值不会再减小。由于有着约束条件的制约，我们还需要考虑这些方向是不是可以让 $\bar{\boldsymbol x}$ 移动后仍然在可行域内。由此我们还需引入可行方向的概念。

定义：设集合 $S\subset\Bbb R^n$ ， $\bar{\boldsymbol x}\in\text{cl}\;S$ （i.e. $\bar{\boldsymbol x}$ 在 $S$ 的闭包内）， $\boldsymbol {d\neq0}$ ，若 $\exists \delta\gt0,\;\forall\lambda\in(0,\delta)$ 使得

$\boldsymbol{\bar{x}}+\lambda\boldsymbol d\in S$

则称这样的方向为 $S$ 在 $\bar{\boldsymbol x}$ 的可行方向。可行方向锥就是所有可行方向组成的集合，记为 $D$ 。

显然，若 $\bar{\boldsymbol x}$ 是局部极小点，那么它的可行方向就一定不是下降方向。换言之，有 $F_0\cap D=\varnothing$ .

不等式约束问题

经过前面的描述，我们已经初步有了应对带约束的问题时如何判断局部最优解的方法： $F_0\cap D=\varnothing$ . 现在为了用代数的方法来表示，我们先分析只带有不等式约束的问题，并且引入起作用约束的概念。

$\begin{aligned} \min \quad&f(\boldsymbol x)\\ \text{s. t. }\quad&g_i(\boldsymbol x)\geq0,\quad i=1,...,m \end{aligned}$

该问题的约束条件在某个点 $\bar{\boldsymbol x}\in S$ 时存在两种情况：

$\begin{aligned} g_i(\overline{\boldsymbol x})=0,\quad i\in I\\ g_i(\overline{\boldsymbol x})\gt0,\quad i\not\in I \end{aligned}$

使得等式成立的这些约束我们称为起作用约束，它们的下标集用 $I$ 表示。对应地，剩下的约束就是不起作用约束。

事实上， $\bar{\boldsymbol x}$ 坐落在起作用约束的边界上，此时如果 $\bar{\boldsymbol x}$ 往某些方向 $\boldsymbol d$ 移动，无论步长 $\lambda$ 有多小，它都会离开限定的约束而成为不可行点。这也是这种约束被称为起作用约束的原因。对于不起作用约束，因为 $\bar{\boldsymbol x}$ 暂时坐落在内部，所以它在一定步长下往任意方向都可以移动。

所以考察可行方向，我们可以只考虑当前的起作用约束。称这种可行方向的集合为局部约束方向锥或内方向锥： $G_0=\{\boldsymbol d\mid\nabla g_i(\bar{\boldsymbol x})^\top\boldsymbol d\gt0,\;i\in I\}$ . （让 $\bar{\boldsymbol x}$ 往 $g_i$ 的值会变大的方向移动，离开边界）