【原】最优化笔记

一维搜索

一维搜索又称线性搜索，就是指单变量函数的最优化。迭代格式为：

其关键就是构造搜索方向和步长因子。设

这样，从出发，沿搜索方向，确定步长因子，使

的问题就是关于的一维搜索问题。

如果求得，使目标函数沿方向达到极小，即使得

或

则称这样的一维搜索为最优一维搜索，或精确一维搜索，叫最优步长因子。如果选取，使目标函数得到可接受的下降量，即使得下降量是用户可接受的则称这样的一维搜索为近似一维搜索，或不精确一维搜索。

0.618法和Fibonacci法

0.618法和Fibonacci法都是分割方法其基本思想是通过试探点和进行函数值的比较，使包含极小值点的搜索区间不断缩小，当区间长度缩短到一定程度时，区间上各点的函数值均接近极小值，从而可以看做极小值的近似，这类方法仅需要计算函数值，用途很广，尤其适用于非光滑及倒数表达式复杂或写不出来的种种情形。

0.618法

设

是搜索区间上的单峰函数，设在第k次迭代时搜索区间为，去2个试探点，且，计算和；

(1)    若，则令。

(2)    若，则令。

要求2个试探点和满足以下条件：

1.      和到搜索区间的端点等距，

2.      每次迭代，搜索区间长度上午缩短率相同，

则

0.168法计算步骤：

1.      选取初始数据，确定初始搜索区间和精度要求。计算最初2个试探点：

计算和，令。

2.      比较函数值，，若，则转步3；若，则转步4.

3.      若，则停止计算，输出；否则令，，，计算，转步5.

4.      若，则停止计算，输出，否则，令，，，，，计算，转步5.

5.      ，转步2.

0.168法的改进形式

1.      选取初始数据，确定初始搜索区间和精度要求。计算最初2个试探点：

计算，，和，令，比较函数值，令。

2.      ，若转步4，否则转步3.

3.      若，则停止计算，输出，否则令，，，，，，计算，如果，令转步2，否则转步2.

4.      若，则停止计算，输出，否则令，，，，，，计算，如果，令转步2，否则转步2.

插值法

插值法是一类重要的一维搜索方法，其基本思想是在搜索区间中不断用低次（通常不超过3次）多项式来近似目标函数，并逐步用插值多项式的极小点来逼近一维搜索问题的极小点。当函数具有比较好的解析性质时，插值方法比直接方法（如0.618法和Fibonascci法）效果更好。

二次插值

一点二次插值法（牛顿法） 

考虑利用一点出的函数值、一阶和二阶导数值构造二次插值函数，设二次插值多项式为，则，故极小点处就是计算近似极小点的公式，插值条件为：

解得，

故，此即牛顿法。

牛顿法的优点是收敛速度快，具有局部二阶收敛速度。

二点二次插值法（1）

给出二点，函数值，导数值，。构造二次插值函数，插值条件满足：

解得

从而

上式通常写成如下迭代格式

二点二次插值法（2）

给出二点，要求插值条件满足：

解得

写成迭代格式：

上式也称割线公式或试位法，可直接有Lagrange插值公式得到：

割线法逼近的主要误差是，二点二次插值法（1）逼近的主要误差是，割线法的效果较差。二点二次插值法收敛速度的阶为1.618.

三点二次插值法

考虑利用，，三点处的函数值，，构造二次函数，要求插值条件满足：

解得

于是

上式也可写成

也可直接利用拉格朗日插值公式求得到。

三点二次插值法的收敛速度约为1.32.

不精确的一维搜索方法

 

最速下降法

最速下降法以负梯度方向作为极小化算法的下降方向，又称梯度法，是无约束优化中最简单的方法。

设函数在附近连续可微，且。由Taylor展式

可知，若记，则满足的方向是下降方向，当确定后，的值越小，函数下降的越快。又

故当且仅当时，最小，从而称是最速下降方向。

最速下降法的迭代格式为：

这个方法的计算步骤如下：

1）给出；

2）计算；如果，则停止；

3）由一维搜索求步长因子，使得

4）计算；

5），转2）。

牛顿法

牛顿法的基本思想是利用目标函数的二次Taylor展开，并将其极小化。

设是二次可微实函数，，Hesse矩阵正定。在附近用Taylor展开近似：

其中，，为的二次近似，将上市右边极小化，即，使得

这就是牛顿法迭代公式，在这个公式这步长因子，令，，则

显然，牛顿法可以看成椭球范数下的最速下降法，事实上，对于，是极小化问题的解。当采用范数时，所得方法是最速下降法。当采用椭球范数时，，所得方法是牛顿法。

应当注意的是，当初始点远离最优解时，不一定正定，牛顿方向不一定是下降方向，其收敛性不能保证，这说明恒取步长因子为1的牛顿法是不合适的，应该在牛顿法中采用某种一维搜索来确定步长因子，但是应该强调，仅当步长因子收敛到1是牛顿法才是二阶收敛的，这时牛顿法的迭代公式为：

其中是一维搜索产生的步长因子。

1）选取初始数据，取初始点，终止误差，令；

2）计算，若，停止迭代，输出，否则进行步3；

3）解方程组构造牛顿方向，即解，求出；

4）进行一维搜索，求使得，令转步2.

 

信赖域法

数学模型：

自变量s就是要求上午位移，

第k次迭代实际下降量

第k次迭代预测下降量

(1)    从初始点 ，初始信赖域半径  开始迭代

(2)    到第 k 步时，计算  和 

(3)    解信赖域模型，求出位移 ，计算 

(4)    若 ，说明步子迈得太大了，应缩小信赖域半径，令 

(5)    若  且  ，说明这一步已经迈到了信赖域半径的边缘，并且步子有点小，可以尝试扩大信赖域半径，令

(6)    若 ，说明这一步迈出去之后，处于“可信赖”和“不可信赖”之间，可以维持当前的信赖域半径，令 

(7)    若  ，说明函数值是向着上升而非下降的趋势变化了（与最优化的目标相反），这说明这一步迈得错得“离谱”了，这时不应该走到下一点，而应“原地踏步”，即  ，并且和上面的情况一样缩小信赖域。反之，在  的情况下，都可以走到下一点，即 。