最优化理论与算法(第二章).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）。显然，要缩短区间，至少需计算两次函数值。也就是，如果只允许计算零次或一次函数值，区间不会得到缩短，故有下面考虑允许计算次函数值时，初始区间的长度的上确界。设最初的两个试探点为，那么余下还可计算次函数值，而极小点可能位于或。 若极小点位于中，由于我们仅可在此区间中再计算次函数值。故有 若极小点位于中，由于除可再计算次函数值外，还可利用处的函数值。因而 由此立即得 于是有 2Fabonacci数列由下述递归关系式给出的数列称为Fabonacci数列： ，由上一段分析，显然有。因此若某种取点方式能保证在计算函数值次后，能将长度为的初始区间缩短为1，或等价地，把搜索区间缩减为最初区间的，那么就有理由认为这种取点方式是最优的。分数法根据Fabonacci数列来构造、选取试验点，它恰好具有上述所希望的性质。因而是最优选点方式，故称之为优选法。3Fabonacci法中探测点的取法 每次迭代区间收缩率为，收缩率不为常数； ，关于区间的端点对称； ，由此即知经过次函数值计算后，最终区间缩为初始区间的，故为最优选点方式； 每次仅需计算一个函数值。事实上，若（同样考虑），可验证必有，因而处的函数值不必重复计算。而仅需计算处的函数值，故每次迭代，仅需计算一个函数值。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和WolfePowell不精确一维搜索方法前面介绍了几种不精确一维搜索准则，下面给出几个具体的不精确一维搜索算法。1Armijo-Goldstein方法当试探的取得不合适时，用求区间中点的方法选取新的试探点，算法如下：算法迭代步骤1) 在搜索区间（或）中取定初始点，计算，给出。令（或），。2) 计算，若，转3）；否则，令，转4）。3) 若，停止迭代，输出；否则，若，转4）；否则，转2）。4) 选取新的探索点。取。2WolfePowell方法当试探的取得不合适时，用两点插值公式确定新的试探点，见下面框图：选取初始数据计算第一准则是否成立？计算和第二准则是否成立？令 停利用二次插值公式计算 利用二次插值公式计算 NYYN四、简单准则和后退方法在实际计算中，有时仅采用Armijo-Goldstein准则中的第一个准则称之为简单准则，而后退方法则是建立在这种准则之下的一种不精确搜索算法。其基本思想是：开始令，若不可接受，则减少（后退），直到为可接受为止。后退算法的迭代步骤：1） 给定，取；2） 检验。3） 若上式不满足，取，转2）；若上式满足，取，令上面介绍了三种最常见的不精确搜索准则，利用这些准则，可以构造很多具体的不精确搜索方法（主要是试探点的不同选取方式，搜索区间的不同缩减方法）。五、不精确一维搜索的收敛性定理为了保证算法的下降性，我们总要求每次搜索方向与其梯度方向成锐角。并且要求其夹角满足：，。采用不精确一维搜