无约束非线性最优化问题基本数学原理

求解无约束最优化问题的方法主要有两类，即直接搜索法（Direct search method）和梯度法（Gradient method）。

直接搜索法适用于目标函数高度非线性，没有导数或导数很难计算的情况。由于在实际工程中很多问题都是非线性的，故直接搜索法是一种有效的解决办法。常用的直接搜索法为单纯形法，此外还有Hooke-Jeeves搜索法、鲍威尔共轭方向法等，它们的缺点是收敛速度慢。

在函数的导数可求的情况下，梯度法是一种更优的方法。该方法利用函数的梯度（一阶导数）和Hess矩阵（二阶导数）构造算法，可以获得更快的收敛速度。函数f (x)的负梯度方向▽f (x)反映了函数的最大下降方向。当搜索方向为负梯度方向时，此方法被称为最速下降法。当需要最小化的函数有一个狭长的谷形值域时，该方法的效率很低，如Rosenbrock函数

f (x)=100(x1-x22)2+(1-x1)2

它的最小值解为x=[1,1]，最小值为f (x)=0。图3-1所示的是该函数的等值线图，图中还显示了从初值[-1.9,2]出发向最小值前进的路径。此函数在迭代1000次以后终止，此时距最小值仍有相当长的距离。图中的黑色粗线是该方法在谷的两侧不断进行“之”字形搜索形成的。

这种类型的函数又被称为香蕉函数。

常见的梯度法有最速下降法、牛顿法（Newton法）、马夸尔特法（Marquart法）、共轭梯度法和拟Newton法等。

在所有这些方法中，用得最多的是拟Newton法，这些方法在每次迭代过程中建立曲率信息，构成下式，得二次模型问题：

在上式中，Hess矩阵H为一个正定对称矩阵，C为常数向量，b为常数。对x求偏导数可以获得问题的最优解

x2x1x2x1

图3-1 香蕉函数的等值线图及最速下降法的搜索路径

解x* 可写成：

拟Newton法包括两个阶段，即确定搜索方向和一维搜索阶段。

1．Hess矩阵的更新

Newton法由于需要多次计算Hess矩阵，故计算量很大。而拟Newton法则通过构建一个Hess矩阵的近似矩阵来避开这个问题。

在优化工具箱中，通过将options参数HessUpdate设置为BFGS或DFP来决定搜索方向。当Hess矩阵H始终保持正定时，搜索方向总是保持为下降方向。

构建Hess矩阵的方法很多。对于求解一般问题，Broyden、Fletcher、Goldfarb和Shanno的方法（简称BFGS法）是最有效的。BFGS法的计算公式为

\[{H}_{k+1}={H}_{k}+\frac{{q}_{k}{q}_{k}^{T}}{{q}_{k}^{T}{S}_{k}}-\frac{{H}_{k}^{T}{S}_{k}^{T}{S}_{k}{H}_{k}}{{S}_{k}^{T}{H}_{k}{S}_{k}}\]

在上式中：\({S}_{k}={x}_{k+1}-{x}_{k}\)，\({q}_{k}=\nabla f({x}_{k+1})-\nabla f({x}_{k})\)

作为初值，H0可以被设为任意对称正定矩阵。

另一个有名的构造近似Hess矩阵的方法是DFP（Daridon-Fletcher-Powell）法。该方法的计算公式与BFGS法的形式一样，只是将qk替换为Sk。

梯度信息可以用解析方法得到，也可以用有限差分方法通过求偏导数得到。

在每一个主要的迭代过程中，在下式所示的方向上进行一维搜索：

\[d=-{H}_{k}^{-1}\cdot\nabla f({x}_{k})\]

图3-2演示了用拟Newton法时Rosenbrock函数的求解路径。可见，利用该方法，只需要140次迭代就可以达到最小值，比前面利用最速下降法要快得多。

\[\]

图3-2 拟Newton法的搜索路径