【Python讲优化】S06E06 最优化的基本概念和存在条件

1.最优化问题的由来和概述

在实际应用中,最优化问题是我们绕不开的话题,最优化问题由两部分组成:
$$minimize \,f(x)$$$$subject\,to\,x\in \Omega$$

他要解决的实际问题就是针对我们上面所写的实值函数$f$,去寻找一个合适的$x$,使得函数$f$的取值达到最小,需要注意的是,如果函数$f$是一个一元函数,那么$x$就是一个使得函数取得最小值的数值,而对于一个$n$元函数$f$而言,自然的,$x$就是一个$n$维向量:$\begin{bmatrix} x_1&x_2&x_3&...&x_n \end{bmatrix}^T$。

如果你对上面的表述比较陌生,没关系,我们对应回忆一下二元函数$f(x,y)$的情形,实际上我们就是在这里把自变量$x$和$y$统一表述成向量$\begin{bmatrix} x_1&x_2\end{bmatrix}^T$。

我们知道所有的$n$维向量会构成一个$R^n$空间,而所谓的集合$\Omega$是自变量$x$的约束集,在空间中,也是$R^n$空间中的一个子集,一般我们将约束集表示成:$\Omega=\{ x:h(x)=0,g(x)\le 0\}$。

换句话说,我们所讨论的有约束条件的优化问题,就是指自变量$x$必须取自于约束集$\Omega$范围中的值,在这个范围内寻找使得函数$f$取得极小值的$x$的取值。

当然,如果我们的约束集定义为$\Omega=R^n$,实际上就对应了另一种情况,也就是无约束的优化问题。

在实际问题中,我们可能还会想到要求取目标函数$f$的极大值,我们对其取负号$-f$,就将其统一到求极小值的框架中来了。

2.关于极小值的一些概念

关于极小值点的概念,我们这里要展开说一下:

对于在约束域$\Omega$内的点$x'$,如果在约束域内他的邻域$|x-x'|<\epsilon$当中,对于其余所有的自变量$x$,都有$f(x)\ge f(x')$,那么我们就说$x'$是函数约束域中的一个局部极小值点,那么如果在整个约束域$\Omega$中的自变量$x$都满足$f(x)\ge f(x')$,那么此时的$x'$就由局部极小值点升格成了全局极小值点。

我们以一个最简单的一元函数$y=f(x)$的图像为例,这个概念就非常清晰了。

图1.局部极小值点与全局极小值点

图1.局部极小值点与全局极小值点

在这个例子中,图像上所展示的是函数$f(x)$在约束域内的图像,很显然$x=x_1$以及$x=x_2$都是极小值点,而进一步的,$x_1$是全局极小值点,$x_2$是局部极小值点。

而实际操作中,请大家注意:我们一般会觉得,严格说来只有找到了全局极小值点,才算是最终解决了问题,而在实际的应用当中,全局极小值点是非常难找到的,通常找到局部极小值点一般也就可以了。

3.剖析最优化分析的工具

在讲解寻找极小值的具体方法前,大家请务必牢记这几个工具:

我们以二元函数$f(x_1,x_2)=x_1^2+3x_2^2+2x_1x_2+4x_1+5x_2$为例。

函数$f$的一阶导数$D_f$是一个向量,他和梯度向量一致,即:$D_f=\begin{bmatrix} \frac{\partial f}{\partial x_1}& \frac{\partial f}{\partial x_2}&...& \frac{\partial f}{\partial x_n} \end{bmatrix}$。

这上面的实际例子中,$D_f=\begin{bmatrix}2x_1+2x_2+4&2x_1+6x_2+5 \end{bmatrix}$。

而函数的二阶导数$D^2f$将组成一个矩阵,这就是非常重要的黑塞$(Hessian)$矩阵。

$$D^2f=\begin{bmatrix}\frac{\partial^2f}{\partial x_1^2}&\frac{\partial^2f}{\partial x_1 \partial x_2}&...&\frac{\partial^2f}{\partial x_1 \partial x_n}\ \\...&...&...&...\\\frac{\partial^2f}{\partial x_n \partial x_1}&\frac{\partial^2f}{\partial x_n \partial x_2}&...&\frac{\partial^2f}{\partial x_n^2 }\end{bmatrix}$$

进一步对应的,上面的二元函数$f(x_1,x_2)$的黑塞矩阵为$\begin{bmatrix}2&2\\2&6 \end{bmatrix}$。

4.探索极小值存在的条件

4.1.一阶必要条件

首先我们来看满足极小值存在的一阶条件:

我们来看下面这个简单的例子:$f(x_1,x_2)=x_1^2+x_2^2$,我们观察他在极小值点$(0,0)$处的图像:
图2.极小值点处的图像

图2.极小值点处的图像

很显然,函数$f$在极小值点$x'$邻域附近的点$x$的取值需要满足$f(x)\ge f(x')$,也就是说在取值点$x'$处沿着各个方向向量$u$的导数都应该大于等于$0$:

$$lim_{h\rightarrow 0}\frac{f(p+hu)-f(p)}{h}=\nabla f(p)\cdot u \ge 0$$

这里运用一个小技巧,由于我们的方向导数在任意方向上都满足大于等于$0$,因此沿着$-u$方向,这个不等关系依然成立,也就是说我们需要同时满足以下两个不等式:
$$\nabla f(p)\cdot u \ge 0$$$$\nabla f(p)\cdot (-u) \ge 0 \Rightarrow \nabla f(p)\cdot u \le 0$$

top Created with Sketch.