最优化方法第三章

第1页，课件共38页，创作于2023年2月3.1直线搜索

直线搜索（一维搜索）是指求解如下一元函数极小化问题（3.3）的迭代方法，其中。在微积分中，解决问题（3.3）的范围一般限于方程（3.4）可以直接解出的情况。而这里介绍的直线搜索对严格的要求。当然，对于可以求出导数的情况，相应的求解方法一般也会简单些。不作直线搜索，理论上，分为精确的和不精确的。

精确的直线搜索方法主要分为两类：一类为区间收缩法，另一类为函数逼近法。本节将相应地介绍两种常用的精确的直线搜索方法：适用于一般函数的黄金分割法和适用于一般连续函数的抛物线插值法。最后还将介绍实用的不精确一维搜索技术。第2页，课件共38页，创作于2023年2月

精确的直线搜索算法的实现通常是在所谓的搜索区间上进行的1.搜索区间的确定在以下讨论中，总假定一元函数是单谷函数。定义3.1

设，是

在L上的全局极小点。如果对于L上任意的两点，当时，

；当时，

，那么称是区间L上的单谷函数。下图给出了单谷函数的基本图形。第3页，课件共38页，创作于2023年2月定义3.2

设,是在L上的全局极小点。如果能够找到，使得

那么闭区间就称为极小点的一个搜索区间，记为

。搜索区间有时也记作，其中显然，单谷函数的定义域区间是搜索区间。单谷函数的性质。定理3.1

设是单谷函数极小点的一个搜索区间。在内任取两点

，若，则

是极小点的一个搜索区间；若

，则是极小点的一个搜索区间。直线搜索算法的第一步一般得先确定的一个

（初始）搜索区间。根据定理3.1，可以给出确定搜索区间的如下算法。第4页，课件共38页，创作于2023年2月算法3.1（确定搜索区间）已知：目标函数。选定初始点和步长。②计算，，。③若，则置，，，，，。，转⑤；否则转④。④置⑤计算，。若，则转⑥；否则转④。⑥置，（即为搜索区间），计算结束。上述过程开始时，必须选定初试点和步长。对于任意给定的，一般来说，无固定选取模式。第5页，课件共38页，创作于2023年2月但对于在下降算法模式中所引入的而言，可选取等于0（理论上）或接近0（实际计算中）。而对于，如果选得过小，那么需要迭代许多次才能找到一个搜索区间；如果选得太大，虽然很少几步就可能把极小点包括进来，但是这又会给下一步搜索极小点的过程增加负担。下面是确定的一种比较合理而有效的方法。第6页，课件共38页，创作于2023年2月第一次迭代（，即从到的迭代）时，

的初始步长可取为1，或根据问题中出现的数据的数量级估计选定。而以后各次迭代的初始步长可按公式（3.5）计算，（3.5）其中。这是因为从到的距离一般比从到的距离小或接近，所以把按（3.5）算出的作为下一次迭代的初始步长是合适的。在实际计算中，当较小时，相应的可取得小些，而随着的增大，相应的可取得接近1。第7页，课件共38页，创作于2023年2月第8页，课件共38页，创作于2023年2月2.直线搜索的方法（1）黄金分割法

黄金分割法属于区间收缩法。它适用于任何单谷函数求极小值问题。对函数除“单谷”外，不作其它要求，甚至可以不连续。因此这种方法的适用面相当广。

黄金分割法的思想是：在每次迭代中，合理地设置两个插入点的位置，以使得在计算函数值次数同样多的条件下，将区间缩小得最快。设区间的长为1。在距点分别为和的地方插入和。为了确定和，提出以下条件：

第一，希望和在中的位置是对称的。按这一条件，有第9页，课件共38页，创作于2023年2月即.（3.6）这样无论删去哪一段，总保留长为的区间。第二，删掉一段，例如删掉，在保留下来的区间，使得里再插入一个点在中的位置与在中的位置具有相同的比例，从而保证每次迭代都能缩小区间。按这一条件，有以同一比率即或.（3.7）把（3.7）代入（3.6）中，得到关于的一元二次方程其合理的根是（3.8）第10页，课件共38页，创作于2023年2月代回（3.6），得

在古代，人们认为按比率0.618分割线段是最协调的，胜似黄金，故称黄金分割。因此，上述按比率0.618缩小搜索区间的迭代方法称为黄金分割法或0.618法。算法3.2（黄金分割法）P145第11页，课件共38页，创作于2023年2月第12页，课件共38页，创作于2023年2月（2）抛物线插值法

抛物线插值法属于函数逼近法。它适用于连续的单谷函数求极小值问题。抛物线插值法的思想是：设在搜索区间上连续。记

和。

如果（3.9）与（3.10）（两等号不同时成立）同时成立，那么可以过和

三点作抛物线插值，设抛物线方程为（3.11）其实是在区间上对所作的一个曲线拟合。第13页，课件共38页，创作于2023年2月记的极小点为，则根据

提供的信息，我们可以将搜索区间缩小，然后在缩小了的区间上再作抛物线插值。如此下去，最终可以求到在

中的极小点。

令(3.12）解出（3.13）第14页，课件共38页，创作于2023年2月根据插值条件和，列出关于

和的线性方程组由此解出，，并代入（3.13）中，得（3.14）第15页，课件共38页，创作于2023年2月这个公式的使用条件仅仅是和

三点不共线。可以证明（习题3.5），在（3.9）和（3.10）（两等号不同时成立）同时成立的条件下，由（3.14）所确定的是的极小点，并且。以下讨论算法的终止准则和缩小搜索区间的方法。按（3.14）计算出。由极限理论知道，如果

与都很小，那么也必然很小，当然也应该很小。

计算经验指出，可以采用（3.15）

作为终止准则。第16页，课件共38页，创作于2023年2月当终止准则满足时，取和中函数值较小的点提供的缩小。这个过程如下：作为极小点；当终止准则未满足时，则需要利用信息将原来的搜索区间①比较和的大小，有两种情况：若，则转②；否则，转③。②若，则置，转④；

若，则，，转④。

置③若，则置，转④；

若，则，，转④。置④转向计算新的搜索区间上的插值抛物线的极小点算法流程图见书上图3-5。第17页，课件共38页，创作于2023年2月第18页，课件共38页，创作于2023年2月

包括黄金分割法和抛物线插值法在内的许多一维问题的迭代方法全部依赖于函数单谷性的假设。但在许多问题中，这一假设不成立或难以验证。解决这一困难的办法，尤其当初始搜索区间很大的时候，是将搜索区间分成若干个较小区间，然后在每个子区间上寻求极小，最后又在所有子区间的极小中选取最小的一个作为问题的最优解。（3）不精确一维搜索技术

精确的一维搜索过程往往需要花费很大的计算量才有可能求到符合精度要求的最优步长因子。当多维问题的迭代点距极小点较远时，显然精确地求解一维子问题对求解多维问题本身没有太大的意义。另外很多最优化方法，如Newton法和拟Newton法，其收敛速度也并不依赖于精确的一维搜索过程。因此，在实际计算中，只要选取的步长因子能够保证目标函数在每一步的迭代中都有“满意的”下降就可以了。这样，既会大大地节省计算量，同时还会从整体上加快计算进程。第19页，课件共38页，创作于2023年2月考虑由多维问题引出的一维问题（3.16）其中具有一阶连续偏导数。Goldstein(1965年)和Powell（1975年）给出了用来设计（3.16）不精确一维搜索过程的两个条件：ⅰ）；

（3.17）ⅱ）

(3.18).其中使得，而是给定的常数，通常取

。条件ⅰ）表示应使新迭代点的函数值相对上一迭代点

的函数值的下降幅度须不低于某个量，而条件ⅱ）则表示目标函数

在新迭代点处沿

方向的方向导数应不小于

在上一迭代点第20页，课件共38页，创作于2023年2月处沿方向的方向导数的

倍。换句话说，若满足条件ⅰ），则认为在点处已获得“满意的”函数值的下降。而若满足条件ⅱ），这时有两种可能性，

要么已是点

方向处的上升方向，

要么方向虽然还是点下降方向，

处的但函数在点

处沿方向的下降率已低于

处沿方向的下降率在点

倍，这时若继续沿

方向作一维搜索，只会徒增计算量，而不会再获得函数值的较大下降量，因此，一旦满足条件ⅱ）就需要确定。新的搜索方向

以上分析表明，在实际计算中，选取满足（3.17）和（3.18）的作为确定的步长因子是合适的，

即。第21页，课件共38页，创作于2023年2月一般地，越小，一维搜索越精确，但计算量也越大。。

不精确的一维搜索不要求过小的而越小，条件ⅰ）越容易满足。

在实际计算中，通常取或更小的值值的选取不太敏感），。（由此得出的解通常对算法3.3（不精确一维搜索）已知：，且。①给定

（通常取），初始（可取1或参照（3.5）给出）。步长②计算。置。③计算；④若（3.18）成立，则转⑤；否则，置，然后转③；第22页，课件共38页，创作于2023年2月⑤若（3.17）成立，则打印，计算结束；否则，，然后转③。置

算法说明：ⅰ）第④步中若（3.18）不成立，则表明沿方向有继续前进的必要；ⅱ）第⑤步中若（3.17）不成立，这表明当前步长过大，需缩小搜索范围。第23页，课件共38页，创作于2023年2月不精确一维搜索的算法流程图第24页，课件共38页，创作于2023年2月3.2最速下降法

最速下降法是最早的求解多元函数极值的数值方法。它直观、简单。它的缺点是，收敛速度较慢、实用性差。1.基本思想求解问题（3.1）。假设迭代已得到。在点处，取搜索方向为（3.19）沿进行直线搜索，由此确定（3.20）其中步长因子满足（3.21）（3.20）、（3.21）简单地合记为（3.22）第25页，课件共38页，创作于2023年2月3.20）或（3.22）称为最速下降迭代公式，由该公式产生的算法称为最速下降法。今后记2.算法算法3.4（最速下降法）P151第26页，课件共38页，创作于2023年2月第27页，课件共38页，创作于2023年2月将最速下降法应用于正定二次函数（3.23）可以推出显式迭代公式。设第迭代点为，求的表达式。由（3.24）

（3.25），（3.26），，，（直线搜索性质）得即第28页，课件共38页，创作于2023年2月由此解出（3.27）例3.1P1523.锯齿现象

最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线：后一次搜索方向与前一次搜索方向总是相互垂直的，称它为锯齿现象。这一点在前面的例题中已得到验证。除极特殊的目标函数（如等值面为球面的函数）和极特殊的初始点外，这种现象一般都要发生。第29页，课件共38页，创作于2023年2月

从直观上可以看到，在远离极小点的地方，每次迭代都有可能使目标函数值有较多的下降，但在接近极小点的地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小。因而收敛速度不快。

已有结论表明，最速下降法对于正定二次函数关于任意初始点都是收敛的，而且恰好是线性收敛的。第30页，课件共38页，创作于2023年2月3.3Newton法如果目标函数在上具有连续的二阶偏导数，其Hesse矩阵

正定且可以表达成显式（今后记），那么使用Newton法求解（3.1）会很快地得到极小点。1.基本思想考虑从到的迭代过程。在点处，对按Taylor级数展开到第三项，即（3.29）因为正定，所以是正定二次函数。令得（3.30）第31页，课件共38页，创作于2023年2月由此解出的极小点，记为，即（3.31）是极小点的新的近似点。

（3.31）称为Newton迭代公式，由该公式产生的算法称为Newton法。注意到，当目标函数是正定二次函数（3.36）时，。这说明：对于正定二次函数，Newton法一次迭代就会得到最优解。（3.31）有直观的几何解释。函数过点的等值面方程为（3.32）在点处，用一个与曲面（3.32）最密切的二次曲面来代替它，这个二次曲面的方程即是第32页，课件共38页，创作于2023年2月当正定时，它是一个超椭球面，的极小点

正是这个超椭球面的中心。我们就用作为极小点

的新的近似点。下图画出了二维情况时的几何解释。例3.2P1542.算法算法3.5（Newton法）P155第33页，课件共38页，创作于2023年2月第34页，课件共38页，创作于2023年2月3.修正Newton法Newton法的优点是收敛速度快、程序简单。特别是前一个优点，在最优化方法中尤为突出。但计算实践指出，Newton算法在运行时经常失败。下面将找出失败的原因，并给出解决办法。以下讨论仅假定