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

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

考虑非线性规划问题

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

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

下降方向

定理:设函数f(x)f(\boldsymbol x) 在点xˉ\bar{\boldsymbol x}可微,若存在方向d\boldsymbol d 使得f(xˉ)d<0\nabla f(\bar{\boldsymbol x})^\top\boldsymbol d\lt0,则存在δ>0\delta\gt0 使得λ(0,δ)\forall \lambda\in(0,\delta) 有:

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

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

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

必要条件

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

证明:反证法. 若f(xˉ)0\nabla f(\bar{\boldsymbol x})\neq\bf0,令方向d=f(xˉ)\boldsymbol d=-\nabla f(\bar{\boldsymbol x}),则方向导数

f(xˉ)d=f(xˉ)f(xˉ)=f(xˉ)2<0\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(x+λd)<f(x)f(\overline{\boldsymbol x}+\lambda\boldsymbol d)\lt f(\overline{\boldsymbol x}),这与xˉ\bar{\boldsymbol x} 是局部极小点的前提矛盾(因为邻域内还有函数值比它小的点)。

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


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

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

f(x+λd)=f(x)+12λ2d2f(x)d+o(λd2)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)

移项,然后两边同时除以λ2\lambda^2,得:

f(x+λd)f(x)λ2=12d2f(x)d+o(λd2)λ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 充分小时,由于xˉ\bar{\boldsymbol x}局部极小点所以f(x+λd)f(x)f(\overline{\boldsymbol x}+\lambda\boldsymbol d)\geq f(\overline{\boldsymbol x}),从而得到:

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

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

充分条件

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

证明:已知f(xˉ)=0\nabla f(\bar{\boldsymbol x})=\bf0,现将函数f(x)f(\boldsymbol x)xˉ\bar{\boldsymbol x} 处的 Taylor 展开到二阶:

f(x)=f(x)+12(xx)2f(x)(xx)+o((xx)2)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 矩阵的最小特征值为λmin\lambda_{\min},则中间项:

(xx)2f(x)(xx)λmin(xx)2(\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

所以,当xx\boldsymbol{x\to\overline{x}} 时,ϵ>0,  xN(xˉ,ϵ),  f(x)f(x)\exists\epsilon\gt0,\;\boldsymbol x\in N(\bar{\boldsymbol x},\epsilon),\; f(\boldsymbol x)\geq f(\overline{\boldsymbol x}).

xˉ\bar{\boldsymbol x}局部极小点。证毕。

充要条件

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

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

另:若f(x)f(\boldsymbol x)严格凸函数,则全局极小点唯一

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

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

minf(x)s. t. gi(x)0,i=1,...,mhj(x)=0,j=1,...,l\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}

可行方向

规定:

  • 可行域:满足约束条件(包括不等式约束和等式约束)的点的集合,记为SS
  • 下降方向集:由所有下降方向组成的集合,根据其定义可记为F0={df(xˉ)d<0}F_0=\{\boldsymbol d\mid\nabla f(\bar{\boldsymbol x})^\top\boldsymbol d\lt0\}

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

定义:设集合SRnS\subset\Bbb R^nxˉcl  S\bar{\boldsymbol x}\in\text{cl}\;Si.e.xˉ\bar{\boldsymbol x}SS闭包内),d0\boldsymbol {d\neq0},若δ>0,  λ(0,δ)\exists \delta\gt0,\;\forall\lambda\in(0,\delta) 使得

xˉ+λdS\boldsymbol{\bar{x}}+\lambda\boldsymbol d\in S

则称这样的方向为SSxˉ\bar{\boldsymbol x} 的可行方向。可行方向锥就是所有可行方向组成的集合,记为DD

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

不等式约束问题

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

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

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

gi(x)=0,iIgi(x)>0,i∉I\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}

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

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

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

我们可以自然地得出不等式约束问题下的一个必要条件就是:F0G0=F_0\cap G_0=\varnothing

证明

Fritz John 条件

待更

Karush-Kuhn-Tucker 条件

待更

一般约束问题

最优化:拉格朗日乘子法 - LeeLIn。 - 博客园 (cnblogs.com)

FJ&KKT

Lagrange

二阶条件

对偶及鞍点问题

参考

  1. 陈宝林 编著. 《最优化理论与算法》. 清华大学出版社. IISBN : 978-7-320-11376-8
  2. 凸优化高质量开源课程 - 美国卡内基梅隆大学
  3. 【非线性优化】线性约束问题的KKT条件 - 知乎
  4. 拉格朗日乘子法 - KKT条件 - 对偶问题 - massquantity - 博客园