【算法工程师的数学基础】系列将会从线性代数、微积分、数值优化、概率论、信息论五个方面进行介绍,感兴趣的欢迎关注【搜索与推荐Wiki】公众号,获得最新文章。

《算法工程师的数学基础》已更新:


这里数学优化部分的内容记录在一篇文章中,内容比较多,建议先收藏再认真看。

数学优化

数学优化(Mathemattical Optimization)问题,也叫最优化问题,是指在一定约束条件下,求解一个目标函数的最大值(或最小值)问题。

数学优化的类型

离散优化和连续优化

根据输入变量$x$的值域是否为实数域, 数学优化问题可以分为离散优化问题和连续优化问题。

离散优化问题

离散优化(Discrete Optimization)问题是目标函数的输入变量为离散变量,比如为整数或有限集合中的元素。离散优化问题主要有两个分支:

  • 1、组合优化(Combinational Optimization):其目标是从一个有限集合中找出使得目标函数最优的元素。在一般的组合优化问题中,集合中的元素之间存在一定的关联,可以表示为图结构。典型的组合优化问题有旅行商问题、最小生成树问题、图着色问题等。很多机器学习问题都是组合优化问题,比如特征选择、聚类问题、超参数优化问题以及结构化学习(Structuced Learning)中标签预测问题等。
  • 2、整数规划(Integer Programming):输入变量$x \in Z^d$为整数。一般常见的整数规划问题为整数线性规划(Integer Linear Programming, ILP)。整数线性规划的一种最直接的求解方法是:

    • 1)去掉输入为整数的限制,得到一个就称为一个一般的线性规划问题,这个线性规划问题为原整数线性规划问题的松弛问题;
    • 2)求得相应松弛问题的解;
    • 3)把松弛问题的解四舍五入到最接近的整数。但是这种方法得到的解一般都不是最优的,因此原问题的最优解不一定在松弛问题最优解的附近

      另外,这种方法得到的解也不一样定满足约束条件。

连续优化问题

连续优化(Continuous Optimization)问题是目标函数的输入变量为连续变量$x \in R^d$,即目标函数为实体函数。

无约束优化和约束优化

在连续优化问题中,根据是否有变量的约束条件,可以将优化问题分为无约束优化问题和约束优化问题。

无约束优化问题(Unconstrained Optimization)的可行域为整个实数域$D = R^d$,可以写为:

其中$x \in R^d$为输入变量,$f: R^d \rightarrow R$为目标函数。

约束优化问题(Constrained Optimization)中变量$x$需要满足一些等式或不等式的约束条件。约束优化问题通常使用拉格朗日乘数法来进行求解。

线性优化和非线性优化

如果在公式$\underset{x}{ min } \, f(x)$中,目标函数和所有的约束函数都为线性函数,则该问题为线性规划问题(Linear Programming)。相反,如果目标函数或任何一个约束函数为非线性函数,则该问题为非线性规划问题(Nonlinear Programming)。

在非线性优化问题中,有一类比较特殊的问题是凸优化问题(Conver Programming)。在凸优化问题中,变量$x$的可行域为凸集,即对于集合中任意两点,他们的连线全部位于在集合内部。目标函数$f$也必须为凸函数,即满足:

凸优化问题是一种特殊的约束化问题,需满足目标函数为凸函数,并且等式约束函数为线性函数,不等式约束函数为凹函数。

优化算法

优化问题一般都是通过迭代的方法来求解:通过猜测一个初始的估计$x_0$,然后不断迭代优化产生新的估计$x_1, x_2, … ,x_t$,希望$x_t$最终收敛的最优解$x^$。一个好的优化算法应该是在一定的时间或者空间复杂度下能够快速准确地找到最优解。同时,好的优化算法受初始猜测点的影响较小,通过迭代能稳定地找到最优解$x^$的邻域,然后迅速收敛于$x^*$。

优化算法中常用的迭代方法有:线性搜索置信域方法等。线性搜索的策略是寻找方向和步长,具体算法有梯度下降法牛顿法共轭梯度法等。

全局最优和局部最优

对于很多非线性优化问题,会存在若干个局部的极小值。局部最小值,或局部最优解$x^$定义为:存在一个$\delta > 0$,对于所有的满足$||x-x^|| \leq \delta$的$x$,公式$f(x^) \leq f(x)$成立。也就是说,在$x^$的附近区域内,所有的函数值都大于或者等于$f(x^*)$。

对于所有的$x \in A$,都有$f(x^) \leq f(x)$成立,则$x^$为全局最小值,或全局最优解。

一般的,求局部最优解是容易的,但很难保证其为全局最优解。对于线性规划或凸优化问题,局部最优解就是全局最优解。

要确认一个点$x^$是否为局部最优解,通过比较它的邻域内有没有更小数值是不现实的。如果函数$f(x)$是二次连续可微的,我们可以通过检查目标函数在点$x^$的梯度$\bigtriangledown f(x^)$和Hessian矩阵$\bigtriangledown^2 f(x^)$来判断。

定理:局部最小值的一阶必要条件:如果$x^$为局部最优解并且函数$f$在$x^$的邻域内一阶可微,则在$\bigtriangledown f(x^*) = 0$

证明:如果函数$f(x)$是连续可微的,根据泰勒公式(Taylor’s Formula),函数$f(x)$的一阶展开可以近似为:

梯度下降法

梯度下降法(Gradient Descent Method)也叫最速下降法,经常用来求解无约束优化的极小值问题。

对于函数$f(x)$,如果$f(x)$在点$x_t$附近是连续可微的,那么$f(x)$下降最快的方向是$f(x)$在$x_t$点的梯度方向的反方向。

根据泰勒一阶展开公式:

要使得$f(x_{t+1}) < f(x_t)$,就得使$\Delta x^T \bigtriangledown f(x_t) <0$。取$\delta x="-" \alpha="" f(x_t)$,如果$\alpha="">0$为一个够小数值时,那么$f(x_{t+1}) < f(x_t)$成立。

这样我们就可以从一个初始值$x_0$出发,通过迭代公式:

生成序列$x_0, x_1,x_2, …$使得:

如果顺利的话,序列$(x_n)$收敛到局部最优解$x^*$。注意每次迭代步长$\alpha$可以改变,但其取值必须合适,如果过大就不会收敛,如果过小则收敛速度太慢。

梯度下降法的过程如下图所示。曲线是等高线(水平集),即函数$f$为不同常数的集合构成的曲线。红色的箭头指向该点梯度的反方向(梯度方向与通过该点的等高线垂直)。沿着梯度下降方向,将最终到达函数$f$值的局部最优解。

梯度下降法

梯度下降法为一阶收敛算法,当靠近极小值时梯度变小,收敛速度会变慢,并且可能以“之字形”的方式下降。如果目标函数为二阶连续可微,我们可以采用牛顿法。牛顿法为二阶收敛算法,收敛速度更快,但是每次迭代需要计算Hessian矩阵的逆矩阵,复杂度较高。

相反,如果要求解一个最大值问题,就需要向梯度正方形迭代进行搜索,逐渐接近函数的局部极大值点,这个过程则被称为梯度上升法(Gradient ascent)。

拉格朗日乘数法与KKT条件

在求解最优化问题的时候,拉格朗日乘数法 (Lagrange Multiplier) 和 KKT条件是两种最常见的方法。

最优化一般分为三种情况:

1、无约束条件

解决办法通常是对原函数求导,令导函数等于0的点可能是极值点,例如上边说的梯度下降法

  1. 等式约束条件

    设目标函数是$f(x)$,等式约束函数是$g(x)$,即在$g(x)$满足的情况下求解$f(x)$的极值。常用的解决办法就是拉格朗日乘数法

  2. 不等式约束条件

    设目标函数是$f(x)$,不等式约束函数是$g(x)$,即在$g(x)$满足的情况下求解$f(x)$的极值。常用的解决办法就是KKT(Karush Kuhn Tucker)条件

约束优化问题可以表示为:

其中$h_i(x)$为等式约束条件,$g_j(x)$为不等式约束条件。

等式约束优化问题

如果上述公式中只有等式约束$h_i(x)=0$,可以构造一个拉格朗日函数$L(x, \lambda)$

其中$\lambda$为拉格朗日乘数,可以是正数或者负数。如果$f(x^)$是原始约束优化问题的局部最优解,那么存在一个$\lambda^$使得$(x^, \lambda^)$为拉格朗日函数$L(x,\lambda)$的驻点。因此只需要令$\frac{\partial L(x, \lambda)}{ \partial x} = 0$,$\frac{\partial L(x, \lambda)}{ \partial \lambda} = 0$,得到:

上述方程式的解即为原始问题的可能解,在实际应用中,需根据问题来验证是否为极值点。

驻点:函数的一阶导数为0地点(驻点也称为稳定点,临界点)。对于多元函数,驻点是所有一阶偏导数都为零的点。驻点不一定是极值点,但极值点一定是驻点。

拉格朗日乘数法是将一个有$d$个变量和$m$个等式约束条件的最优化问题转换为一个有$d+m$个变量的函数求平稳点的问题。拉格朗日乘数法所得的平稳点会包含原问题的所有极值点,但并不保证每个平稳点都是原问题的极值点。

不等式约束优化问题

如果上述公式定义的是一般约束化的问题,其拉格朗日乘数为:

其中:

  • $a = [a_i, …, a_m]^T$为等式约束的拉格朗日乘数
  • $b = [b_i, …, b_n]^T$为不等式约束的拉格朗日乘数

当约束条件不满足时,有$max_{a,b} L(x,a,b) = \infty$;当约束条件满足时并且$b \geq 0$时,$max_{a,b} L(x,a,b) = f(x)$。因此原始约束优化问题等价于:

这是一个min-max优化问题称为主问题(primal problem)。

对偶问题 主问题的优化一般比较困难,我们可以通过交换,min-max的顺序来简化。定义拉格朗日对偶函数为:

$\Gamma(a,b)$是一个凹函数,即使$f(x)$是非凸的。

当$b \geq 0$时,对于任意的$\tilde{x} \in D$,有

令$p^*$是原问题的最优解,则有

即拉格朗日对偶函数$\Gamma(a,b)$为原问题最优解的下界。

优化拉格朗日对偶函数$\Gamma(a,b)$并得到原问题的最优下界,称为拉格朗日对偶函数问题(Lagrange dual problem)

拉格朗日对偶函数为凹函数,因此拉格朗日对偶问题为凸优化问题。

令$d^$是拉格朗日对偶问题的最优解,则有$d^ \leq p^$,这个性质称为弱对偶性,如果$d^ = p^*$,这个性质称为强对偶性质。

当强对偶性质成立时,令$x^$和$a^, b^*$分别是原问题和对偶问题的最优解,那么他们满足以下条件:

称为不定式约束优化问题的KKT条件(Karush-Kuhn-Tucher conditions)。KKT条件是拉格朗日乘数法在不等式约束优化问题上的泛化。当原问题是凸优化问题时,满足KKT条件的解也是原问题和对偶问题的最优解。

KKT条件中需要关注的是$b^_j g_j (x^) =0$,称为互补松弛条件。如果最优解$x^$出现在不等式约束的边界上$g_j(x) = 0$,则$b^_j>0$;如果$x^$出现在不等式约束的内部$g_j(x) < 0$,则$b^_j=0$。互补松弛条件说明当最优解出现在不等式约束的内部,则约束失效。

更多关于拉格朗日和KKT的文章可以参考:

数学优化类型和优化算法介绍完了,如果觉得不错,动动小手分享给更多人看吧!


【技术服务】,详情点击查看: https://mp.weixin.qq.com/s/PtX9ukKRBmazAWARprGIAg


扫一扫 关注微信公众号!号主 专注于搜索和推荐系统,尝试使用算法去更好的服务于用户,包括但不局限于机器学习,深度学习,强化学习,自然语言理解,知识图谱,还不定时分享技术,资料,思考等文章!