最优化理论与算法(第二章).doc

第二章 一维搜索

§2.1. 引言
一、精确与非精确一维搜索
如前所述，最优化算法的迭代格式为：

因而算法的关键就是选择合适的搜索方向，然后再确定步长因子。若设

现在的问题是从出发，沿方向搜索，希望找到，使得，这就是所谓的一维搜索或称为线搜索(line search)问题。
⑴ 若求得的，使目标函数沿方向达到最小，即使得

或 ，
则称为最优一维搜索，或精确一维搜索。相应的称为最优步长因子。
⑵ 如果选取，使目标函数获得可以接受的改善，即
，
则称之为近似一维搜索，或非精确一维搜索。
注：精确搜索与非精确搜索在最优化算法中均广泛应用，它们存在各自的优缺点。

二、一维搜索的基本框架
一维搜索实际上是一元函数的极值问题，其基本的解决框架是：
⑴ 确定包含最优解的初始搜索区间；
⑵ 采用某些区间分割技术或插值方法不断缩小搜索区间，最后得到解。
注：值得注意的是，这样得到的解大多数情况下均为近似解。因此，即便采用精确一维搜索策略，只要应用了数值方法，最终得到的结果都不一定是真正数学意义上的最佳步长因子。
初始搜索区间的确定
定义2.1 设，是函数的最小值点，即。若存在闭区间，使 ，则称为一维极小化问题的搜索区间。
确定初始搜索区间的进退法
基本思想：从一点出发，按一定步长探测，试图找到函数值呈高－低－高变化的三点。具体地，从初始点出发，取初始步长为。若，则下一步从新点出发，加大步长，再向前搜索。若，则下一步仍从出发，沿反方向搜索，直到上升，即为止。
在确定了初始搜索区间后，剩下就是采用具体的一维搜索方法确定出。后面将分别介绍几种常用的一维搜索方法，这些方法主要是针对所谓单峰函数设计的。
单峰函数的定义
定义2.2 设，。若存在，使得函数在上单调下降，而在上单调上升，则称是函数的单峰区间，是上的单峰函数（准确地说应是单谷函数）。
单峰函数还可以等价地定义如下
定义2.3 如果存在唯一的，使得对于任意的且，有
⑴ 若，则；
⑵ 若，则。
则称是上的单峰函数。
下面定理表明，对单峰函数，可以通过简单地比较函数值，缩小搜索区间。
定理2.4 设是上的一个单峰函数，，且。
⑴ 若，则是的单峰区间；
⑵ 若，则是的单峰区间。
证明：略

§2.2. 精确一维搜索的收敛理论
一、基于精确一维搜索的极小化算法
无约束最优化问题算法的基本框架：
⑴ 给出初始点，允许误差，置
⑵ 计算下降方向
⑶ 利用一维搜索，确定步长因子，使
⑷ 令，若，则停止，输出最优解。
否则，置，转⑵。
在上面算法中，采用了精确一维搜索。下面证明基于精确一维搜索的极小化算法的收敛性。

二、算法收敛性
定理2.5 设是的解，若，则有：

证明：由定理假设，有
，
令 （若要，则必须，即与成锐角），
，
定理证毕。
注：⑴ 由证明过程可以看出，必须和成锐角。
⑵ 给出了精确搜索前提下，每步迭代所得改进量的估计式，显然与有关。
定理2.6 设是开集上的连续可微函数，若某一极小化算法满足：
，，
又设是序列的聚点，是满足的指标集。假定存在，使得，有，又设是序列的任意聚点，则

进一步，若在上二次连续可微，则还有
。
证明：设是满足 的指标集，下面用反证法证明。若定理结论不成立，
即 ，
由于 ，
注意到时， ，
则有 ，
因而必有 。 （﹡）
于是存在的邻域和指标集，使得当，时，有
， （由（﹡）式可得）
设是一个充分小的正数，使得对所有，及所有，都有
， （由，有界可得）
则

，
与为有限值矛盾，故必有。
同样地，若
不成立，则必有 。
类似地，有

此矛盾表明必有： ，定理证毕。
定理2.7 设在水平集上存在且一致连续，算法产生的方向与的夹角满足：
， （是某个正数）
则或者对某个，使，或者有，或者有。
证明： 若有某个，使，则结论已证。因此，可设，。又由于是一个下降序列，若其无下界，则有，结论也成立。故可设有下界，因此存在。从而有：。
下证。反证：若，那么，不论多大，都存在，，使得 。
从而
由 （位于与之间）

，
注意到在上一致连续，故存在，使得当时，有

若在上面的不等式中取，则得

故有
这与矛盾。故必有。
注：⑴ 上述收敛定理不仅仅针对某一个特定算法。实际上，前述算法模式中任意算法只要满足定理所需条件中，就都是收敛的。
⑵ ，意味着的任何极限点均为稳定点，但它并不保证本身收敛。

三、采用精确搜索的极小化算法的收敛速度
引理1 设函数在闭区间上二次连续可微，且。若在上的极小点，则 。其中满足，。
证明：构造辅助函数
，
它有唯一零点 。
注意到
即的图像总位于之下，再由是单调上升函数，由此可得：的零点必位于零点的右边。即

事实上，在零点的左边，。由，有。故的零点不可能位于的左边。故必有。
引理2 设在上二阶连续可微，则对任意向量，和任意实数，有：
.
证明： （为积分变量）
（再分部积分）

.
引理3 设在极小点的邻域内二阶连续可微，且存在，和，
使得当时，
， .
那么当 时，有
，
.
证明：在引理2中取，再令，则

注意到及引理条件即得:
.
又由 ，
因此有

由此即得 .
利用上述引理，可得下面的收敛速度定理。
定理2.8 设极小化算法产生的序列收敛到的极小点，若在的某一邻域内二阶连续可微，且存在，和，使得当时，有
，
则线性收敛。
证明：由。故当充分大时，有
，，
因而，存在，使得

(这是由于在每次迭代中，搜索方向可取为单位向量，故有界)。
记
由于 ，
故当时，有

又注意到
，
由引理1知在上的极小点满足

（其中为夹角）
（为的下限）
若记 ，
则有 。
令
由于位于与决定的线段上，因而到的距离不会超过到与到中距离的最大者，即

由引理2，

（由的取法）
（由引理3）

（由引理3）
因此，
令 ，
显然
且有
再由引理3
其中，.
上式可进一步改写为

由此即得迭代点列线性收敛。
特别地，若在所讨论的算法模式中，每次迭代均取为（即取为最速下降方向），则得到的算法称为最速下降算法。值得指出的是：最速下降算法中相继两次迭代的搜索方向是正交的
事实上，第次迭代搜索方向为
，
考虑 ，
其最优步长因子应满足 ，
即 ，
由于
因此有 ，
而恰好是第次迭代方向，故
，
即知相继两次迭代的搜索方向是正交的。鉴于这一特点，可以断言基于精确一维搜索的最速下降法实际下降速度并不快（迭代点列呈锯齿状趋于最优解）。

§2.3 0.618法和Fibonacci法
下面介绍一些实现精确一维搜索常见方法。0.618法，Fibonacci法，二分法等基本思想都是通过取试探点并进行函数值比较，然后不断缩小搜索区间，当区间长度缩到一定程度后，区间内各点均可作为近似解。这类方法仅需计算函数值，十分简便，尤其适合于非光滑及导数表达式复杂或写不出的情形，用途很广。

一、 0.618法（黄金分割法）
设是搜索区间上的单峰函数。记其在第次迭代时搜索区间为，现取两个试探点，，且，计算和。根据前面关于单峰函数的性质：
⑴ 若，则令，
⑵ 若，则令，
对两个试探点、，我们要求满足下列条件：
⑴ 和到搜索区间的端点等距，即
⑵ 每次迭代，搜索区间长度的缩短率相同。即
（是与无关的常数）
因此有
由此得 ，
注意到第次计算的两个点，中总有一个落入第次搜索区间中，若这个点可以被重复使用的话，将减少一次函数值的计算。
为确定起见，设（此时含在中）。为进一步缩短区间，需取试探点，，

若取，使得
， 则
这样，新的试探点处的函数值就不必重新计算。
对情形，有类似结论：若取，则。这表明当区间缩短率取得满足时，每次迭代仅需计算一个函数值即可。由，解方程得
，
再由，故 。
由此，0.618法的计算公式具体为：

注：1）0.618法每次迭代实际只需计算一个点的函数值；
2）经过次迭代，搜索区间的长度缩短为，故0.618法的收敛速度是线性的；
3）0.618法也称黄金分割法，满足 ，由于它还兼具美学意义与一些奇妙的性质，故称为黄金分割点，相应的方法称为黄金分割法。

二、 改进的0.618法
0.618法要求一维搜索的函数是单峰，而实际上很多情形都不是单峰。这个时候往往容易丢掉最优点。(1976)提出了一种改进措施。每次两个内点与两个边界点的函数值都进行比较。当函数值最小的点为左端点或第二个点时，丢弃右端点，否则丢弃左端点。经过这样修改后，算法要相对可靠些，即在缩短搜索区间时，丢掉极小点的可能性减小了。值得注意的是，即便如此，仍不能保证迭代过程不丢掉极小点。下图所描述的情形给出了很好的解释。

按规则，首次就去掉右端点，剩下区间为，显然极小点被丢掉了。这表明
用0.618法进行一维搜索并不是任何时候都能找到极小点。

三、 Fibonacci法（分数法、优选法）
1．优选法的基本思想
通过选择试探点，并利用试探点处的函数值信息，可以不断缩短搜索区间。在函数值计算总次数一定的情况下，最初搜索区间与最终搜索区间长度的比值越大，说明选点方式越好，最优的选点方式应使这个比值达到最大。设函数值计算总次数为，最初区间长度为，最终区间长度为1，因此最优取点方式应使达到最大，下面先来估计的上确界。
设的上确界为，（），即表示当允许计算次函数值时，初始区间长度的上确界（当然最终区间长度为1）。显然，要缩短区间，至少需计算两次函数值。也就是，如果只允许计算零次或一次函数值，区间不会得到缩短，故有

下面考虑允许计算次函数值时，初始区间的长度的上确界。设最初的两个试探点为，那么余下还可计算次函数值，而极小点可能位于或。
⑴ 若极小点位于中，由于我们仅可在此区间中再计算次函数值。故有

⑵ 若极小点位于中，由于除可再计算次函数值外，还可利用处的函数值。因而

由此立即得
于是有
2．Fabonacci数列
由下述递归关系式给出的数列称为Fabonacci数列：
，，
由上一段分析，显然有。
因此若某种取点方式能保证在计算函数值次后，能将长度为的初始区间缩短为1，或等价地，把搜索区间缩减为最初区间的，那么就有理由认为这种取点方式是最优的。分数法根据Fabonacci数列来构造、选取试验点，它恰好具有上述所希望的性质。因而是最优选点方式，故称之为优选法。
3．Fabonacci法中探测点的取法

⑴ 每次迭代区间收缩率为，收缩率不为常数；
⑵ ，关于区间的端点对称；
⑶ ，
由此即知经过次函数值计算后，最终区间缩为初始区间的，故为最优选点方式；
⑷ 每次仅需计算一个函数值。
事实上，若（同样考虑），可验证必有，因而处的函数值不必重复计算。而仅需计算处的函数值，故每次迭代，仅需计算一个函数值。
4. Fibonacci法与0.618法的联系
令，将其带入差分方程，
得
解之得 。
因而差分方程的通解为：。再利用边界条件，得

解得
故有
由此立即可得 .
这说明当时，Fibonacci法与0.618法的区间收缩率相同，因而Fibonacci法也是线性收敛的。
由于Fibonacci法选点方式是最优的，而0.618法与其近似，故应用上将它们统称为优选法。

四、二分法
二分法是求的根的一种简单方法。它每次将区间对分，再利用连续函数的零点定理，确定应该保留的半区间，区间收缩率为常数，因此它也具有线性收敛速度。但当的表达式很难求，或不可微时，方法的应用遇到困难。

§2.4 插值法
一、二次插值法
1．牛顿插值法
其基本思想是用在一点的二阶展开式近似，而以二次展开式的极小点作为极小点近似。设
。
令 ，
得
解之得 。
因此，牛顿法的迭代公式为：

牛顿法不仅算法简单，而且具有较快的收敛速度（局部）。
定理2.9 设三阶连续可微， ，则当初始点充分靠近时，由牛顿迭代公式：

产生的点列收敛，即。且

即该算法具有局部二阶收敛性质。
证明： 由牛顿迭代公式有：

再由及的连续性，必定存在，使得对任何，有 。
因而当时，
。
从而当时，有
，
由此可知
收敛性得证。
又由 ，
这里
由此可得
。
即有
从而得 ，
定理证毕。
2. 二点二次插值法
1）设已给两点，，利用、，以及或进行插值。
设二次插值函数形式为：
。
则

解出，得

的驻点为
一般迭代格式为
2）若利用，和进行插值
则
解之得 。
一般迭代格式为 .
注：与牛顿法比较，在第一种公式中，

逼近误差为；而在第二个公式中，

逼近误差为。可见后一种逼近程度略差一些。
二点二次插值法的收敛速度
定理2.10 设三阶连续可微，满足 ，则二点二次插值公式产生的序列收敛到，且收敛速度的阶为。
证明：参见袁亚湘等著《最优化理论与方法》（略）。
3）三点二次插值法
利用、、进行二次均值，用插值多项式的驻点近似的驻点。
一般迭代格式：
。
定理2.11 设四阶连续可微，满足 ，则上述插值法产生的序列收敛到，且收敛速度的阶约为1.32。

二、三次均值法
用三次函数逼近被极小化的函数，需四个条件确定插值多项式的系数。这些条件可以是：1）四点函数值，2）三点函数值及一点导数值，3）两点函数值及导数值。
三次插值法得到的迭代点列具有较快的收敛速度（为二阶收敛），但由于涉及更高阶导数的计算，增加了应用的困难。关于这方面的详细讨论，可参阅袁亚湘等著《最优化理论与方法》。

§2.5 不精确一维搜索方法
一维搜索是最优化算法的基本组成部分。前述的精确一维搜索往往需要花费大量计算量，导致整个算法不是十分有效。另外，在很多算法如牛顿算法和拟牛顿算法，其收敛速度也并不依赖于精确一维搜索。因此，另一种变通的方法是在每次一维搜索过程中，保证目标函数都有满意的下降就够了，这就是所谓的不精确一维搜索。
在进行不精确一维搜索时，怎样才叫达到了满意的程度，从而结束一维以为搜索，必须要有便于操作的准则。下面介绍一些最重要、最常用的准则，为简单计，仍以单峰函数为考察对象。但应该指出的是：并不一定要求函数为单峰，这方面的详细讨论可参阅席少霖著《非线性最优化方法》。

一、 Armijo-Goldstain准则
1）， 其中是给定的数。
2）

Armijo-Goldstain准则的直观意义是：避免取在区间的两个端点附近，因为取在两端点附近都会导致目标函数的改进量不大。从上图可以看出，区间上的点都可取为可接受步长，故称为可接受区间。若记
，
那么Armijo-Goldstain准则可改写为：

注意到，因此当时，上面两个不等式互相矛盾。由此可见，的要求是自然的。一旦给定，图中两条直线就同时给定，可接受区间也随之确定，而且越接近于0，可接受区间越大，而越趋近于，则可接受区间越小。

二、 Wolfe-Powell准则
Armijo-Goldstain准则有时候会将最佳步长因子排斥在可接受区间之外。为此，Wolfe-Powell给出了一个简单的替代准则：
1）
2'）
亦即：。
注：1) 准则2'）的几何解释：在可接受点处的切线斜率大于或等于初始斜率的倍。由于，因而接收点处的切线更平坦些；
2) 可以证明：当时，满足Wolfe-Powell准则的可接受步长因子是存在的；
3) 从另一个观点看，，是精确一位搜索满足的正交条件的某种近似。但这种近似，即使，也不能导致精确一维搜索。若将 Wolfe-Powell准则中第二式换为

则当时，接近精确搜索准则。而且取得越小，越接近精确搜索，工作量也越大。应该指出的是不精确搜索，不要求过小的，应用上通常取，。
Wolfe-Powell准则下可接受步长因子的存在性
定理2.12 设有下界，且，则必定存在步长因子，使得Wolfe-Powell准则满足。即存在步长因子，使得：
1）
2）， 或 满足。
证明： 令 ，
则 。
令满足，考虑集合。由于有下界，且

故非空。事实上，若，即对所有，都有

因而
当时，可推得，这与有下界矛盾，所以。
令
则显然，这是因为当充分小时，。事实上，当充分小时，
，
由此即得 。
故当时，
（*）
由的定义必有 （由的连续性）
故 （由及）
再由的连续性，必定存在，当时，有

这也就是 ，。
再由(*)式

故有 (由及)
由的连续性，存在，当时，

此即 。
令，则当时，同时有
，
。
这表明，满足Wolfe-Powell准则的步长因子不仅存在，而且有很多。
当采用Wolfe-Powell方法准则时，下述性质成立。
定理2.13 设函数连续可微，满足Lipschitz条件：。若时，下有界，则对满足Wolfe-Powell准则的任何，均有

证明：略

三、Armijo-Goldstein和Wolfe—Powell不精确一维搜索方法
前面介绍了几种不精确一维搜索准则，下面给出几个具体的不精确一维搜索算法。
1．Armijo-Goldstein方法
当试探的取得不合适时，用求区间中点的方法选取新的试探点，算法如下：
算法迭代步骤
1) 在搜索区间（或）中取定初始点，计算，给出。令（或），。
2) 计算，若，转3）；否则，令，转4）。
3) 若，停止迭代，输出；否则，，若，转4）；否则，，转2）。
4) 选取新的探索点。取。
2．Wolfe—Powell方法
当试探的取得不合适时，用两点插值公式确定新的试探点，见下面框图：
选取初始数据

计算
第一准则是否成立？
计算和
第二准则是否成立？
令 停
利用二次插值公式计算

利用二次插值公式计算

N
Y
Y
N

四、简单准则和后退方法
在实际计算中，有时仅采用Armijo-Goldstein准则中的第一个准则

称之为简单准则，而后退方法则是建立在这种准则之下的一种不精确搜索算法。其基本思想是：开始令，若不可接受，则减少（后退），直到为可接受为止。
后退算法的迭代步骤：
1） 给定，取；
2） 检验。
3） 若上式不满足，取，转2）；
若上式满足，取，令
上面介绍了三种最常见的不精确搜索准则，利用这些准则，可以构造很多具体的不精确搜索方法（主要是试探点的不同选取方式，搜索区间的不同缩减方法）。

五、不精确一维搜索的收敛性定理
为了保证算法的下降性，我们总要求每次搜索方向与其梯度方向成锐角。并且要求其夹角满足：，。
采用不精确一维搜索的一般下降算法（模式算法）
1） 给出初始点，允许误差，置；
2） 若，算法停止，；否则求出满足的下降方向；
3） 求出步长因子，使其满足Armijo-Goldstein准则或Wolfe-Powell准则；
4） 令，，转2）。
下面给出基于这些不精确一维搜索的一般下降算法的总体收敛性定理。
定理2.14 若上述算法中，步长因子满足Armijo-Goldstein准则或Wolfe-Powell准则，且
，
若在水平集上一致连续。那么，或者对某个，有，或者，或者。
证明：1）若存在某个，使，或无下界，则结论已证。
2）设，，且有下界，由单调下降，故存在，因而有。由Armijo-Goldstein准则1，立即可得：
，
用反证法证明 若不趋于零，那么存在和一个子序列，使得时，，
由此可推得 。
事实上，由 ，有
。
再由
即得 。
另一方面，由的一致连续性有：

故有
注意到，时，有
（前一因子极限为0，后一因子有界）。
事实上：。
由此即得 ，
这与矛盾。
类似的，若采用Wolfe-Powell准则，由的连续性，
（）
由此得： （由于当时，）
这与Wolfe—Powell第二准则 矛盾，从而定理得证。
下面是另一形式的收敛定理：
定理2.15 设函数连续可微，满足Lipschitz条件：
。
又设算法采用Wolfe-Powell准则，且与的夹角满足

那么由算法产生的点列，或者对某个，有，或者，或者。
证明：不妨设，，且有下界。由定理2.13（用到Lipschitz条件）
，
这里 。
于是：
令，则有：

由有

从而级数收敛，故。
下面定理给出不精确一维搜索条件下，每步迭代目标函数下降量的估计式。
定理2.16 设满足不精确一维搜索准则中第一条，若函数还满足：
，
则必有：。
证明：1）若，则

（最后一个不等式由得）
2）若，由，则必存在使得
。
在处将函数展开，有

又由，因而有

解得：
或
再由满足第一准则，故有：
， 定理证毕。

27