最优化算法

概念

多元函数

若无特殊说明，《最优化方法》中的x含义都是向量，f是多元函数。

目标函数f(x)

因为自变量x是向量，而函数的值是一个实数，因此目标函数是一个高维空间到一维空间的映射。

比如，在某次经济大萧条时期，基本的饮食也需要精打细算的时候，面包单价 c1 元，牛奶单价 c2 元，鸡蛋单价 c3 元，购买数量分别是x1，x2，x3，那么目标函数就可以写作f(x)=c1×x1+c2×x2+c3×x3

此时求解这个目标函数最小值的最优解是什么呢？可以发现当购买数量全部为0时，目标函数值最小，开销最小。

但每个人都有最低营养摄入需求，每天都需要摄入热量 b1，蛋白质 b2，维生素 b3，这便是约束条件。

线性拟合中的目标函数

给定一组由x->y映射的坐标点，现要求找出一条直线，这条直线最能够体现这些点变化的趋势，那么这条直线的表达式即线性拟合中的目标函数。

邻域

约束

欧式范数

梯度(gradient)

多元函数的梯度可以与一元函数的导数类比，梯度是个向量

由初等微积分的知识可知，某一点处的梯度方向是函数值增长最快的方向，那么梯度的反方向就是函数值下降最快的方向。因此在函数一阶可微的情况下，我们直接求取 ，那么 就是函数下降方向最快的方向了。

注：下降最快不代表下降幅度最大

Hessian矩阵

最优解的概念

基础

一元函数的导数与泰勒展开式

多元函数的梯度与泰勒展开式

梯度的计算

Hessian阵的计算

函数的下降方向

局部最优解的一阶必要条件

一阶条件的非充分性，稳定点与鞍点

局部最优解的二阶必要条件

二阶必要条件的非充分性

二阶充分条件

求最优性条件的例题

迭代计算

二阶充分必要条件，满足梯度为0，且H矩阵大于0的点即为所求的最小值点。

但实际情况的目标函数往往非常复杂，没办法求得这两个条件，因此用迭代计算的方法来求得最优解。

梯度下降法/最速下降法

原理

算法步骤

例题

我的通俗理解：先算梯度，负梯度的方向就是下降最快的方向，这是第一次迭代，把0代入梯度表达式中的各个未知数计算，可以算出具体的方向d(0)，然后算范数（也是直接把0代入），满足条件就可以结束了，若不满足条件，确定方向之后算步长λ，易知第一次迭代这一小步走完后的表达式为f(x(0)+λd(0))，那么令其导数等于0，可得此表达式的极值点，此点即为延d(0)方向下降最快的点，可算出λ(0)，第一次迭代结束。

d(0)和λ(0)都算出来了，现在进入第二次迭代，算出第二次迭代的初点x(1)，然后计算梯度（和第一次迭代时的梯度表达式一样，只不过第二次迭代是把所有未知数=1代入表达式计算），然后算范数，满足条件，结束。参考1，参考2

牛顿法

用目标函数的二阶泰勒展开近似该目标函数，通过求解这个二次函数的极小值来求解凸优化的搜索方向。

理解原理

上述是一元函数的牛顿法原理，对于多元函数的最优化问题，按下面这样的对应关系替换类比即可：

"除以二阶导数"这个运算换算成"Hessian矩阵的逆矩阵"。

算法步骤

例题

优缺点

牛顿法的优点是收敛速度非常快，缺点是对初始点、目标函数要求高，要求Hessian矩阵必须可逆，计算量、存储量大（需要计算、存储Hesse矩阵及其逆）。

共轭梯度法(Conjugate gradient method)

共轭梯度法（Conjugate Gradient）是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hessian矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。

二次终止性

注：对于n元正定二次目标函数，如果从任意初始点出发经过有限次迭代就能够求到极小点，那么称这种算法具有二次终止性。例如，Newton法对于二次函数只须经过一次迭代就可以求到极小点，因此是二次终止的；共轭梯度法、拟Newton法等也是二次终止的；而最速下降法就不具有二次终止性。

注：共轭梯度法对于更高次的函数在有限步之内也可以达到极值点。

共轭方向

线性共轭梯度法的迭代公式

线性共轭梯度法基本步骤

例题