最优化方法第三章(1).

《最优化方法第三章(1).》由会员分享，可在线阅读，更多相关《最优化方法第三章(1).（38页珍藏版）》请在金锄头文库上搜索。

1、 从本章起，以后两章将讨论非线性规划问题。本章首 先讨论无约束最优化问题，其一般形式为 （3.1） 其中 求解无约束问题的最优化方法可以分为两大类：一类 是根据目标函数的梯度（即一阶导数），有时还要根据 Hesse矩阵（即二阶导数）提供的信息构造出来的方法 导数方法。本章介绍其中的最速下降法、Newton法、 共轭梯度法和拟Newton法。另一类是不使用导数，仅仅 利用目标函数值的信息构造出来的方法直接方法。本 章将介绍其中的步长加速法、方法加速法和单纯形替换法 。两类方法各有利弊。前者收敛速度快，但需要计算梯度 ，甚至需要计算Hesse矩阵；后者不涉及导数，适应性强 ，但收敛速度慢。一般的经

2、验是，在可以求得目标函数导 数的情况下，尽可能使用导数方法。 3.1 直线搜索 直线搜索（一维搜索）是指求解如下一元函数极小化 问题 （3.3） 的迭代方法，其中。 在微积分中，解决问题（3.3）的范围一般限于方程 （3.4） 可以直接解出的情况。而这里介绍的直线搜索对 严格的要求。当然，对于可以求出导数的情况，相应的求 解方法一般也会简单些。 不作 直线搜索，理论上，分为精确的和不精确的。 精确的直线搜索方法主要分为两类：一类为区间收缩 法，另一类为函数逼近法。本节将相应地介绍两种常用的 精确的直线搜索方法：适用于一般函数的黄金分割法和适 用于一般连续函数的抛物线插值法。最后还将介绍实用的

3、不精确一维搜索技术。 精确的直线搜索算法的实现通常是在所谓的搜索区间 上进行的 1. 搜索区间的确定 在以下讨论中，总假定一元函数是单谷函数。 定义义3.1 设 ， 是 在L上的全局 极小点。如果对于L上任意的两点 ，当 时， ；当时， ，那么称 是区间L上的单谷函数。 下图给出了单谷函数的基本图形。 定义3.2 设 , 是在L上的 全局极小点。如果能够找到 ，使得 那么闭区间就称为极小点的一个搜索区间间， 记为 。搜索区间有时也记作，其中 显然，单谷函数的定义域区间是搜索区间。 单谷函数的性质。 定理3.1 设是单谷函数 极小点的一个搜索区 间。 在内任取两点 ，若，则 是极小点的一个搜索区

4、间；若 ，则 是极小点的一个搜索区间。 直线搜索算法的第一步一般得先确定的一个 （初始）搜索区间。根据定理3.1，可以给出确定搜索区 间的如下算法。 算法3.1（确定搜索区间） 已知：目标函数 。 选定初始点和步长。 计算， 。 若 ，则置 ， ， ，。 ， 转； 否则转。 置 计算，。若，则转； 否则转。 置，（即为 搜索区间），计算结束。 上述过程开始时，必须选定初试点 和步长 。对于 任意给定的 ，一般来说， 无固定选取模式。 但对于在下降算法模式中所引入的 而言，可选取等于0（理论上）或接近0（实际计算中）。 而对于 ，如果选得过小，那么需要迭代许多次才能找到 一个搜索区间；如果选得太

5、大，虽然很少几步就可能把极 小点包括进来，但是这又会给下一步搜索极小点的过程增 加负担。下面是确定 的一种比较合理而有效的方法。 第一次迭代（，即从到的迭代）时， 的初始步长可取为1，或根据问题中出现的数据的数量级 估计选定。而以后各次迭代的初始步长可按公式（3.5） 计算， （3.5） 其中 。这是因为从 到 的距离 一 般比从 到 的距离 小或接近，所以把按（ 3.5）算出的作为下一次迭代的初始步长是合适的。在实 际计算中，当 较小时，相应的 可取得小些，而随着 的 增大，相应的 可取得接近1。 2. 直线搜索的方法 （1）黄金分割法 黄金分割法属于区间收缩法。它适用于任何单谷函 数求极小

6、值问题。对函数除“单谷”外，不作其它要求，甚 至可以不连续。因此这种方法的适用面相当广。 黄金分割法的思想是：在每次迭代中，合理地设置两 个插入点的位置，以使得在计算函数值次数同样多的条件 下，将区间缩小得最快。 设区间 的长为1。在距点 分 别为 和 的地方插入 和 。 为了确定 和 ，提出以下条 件： 第一，希望 和 在 中的位置是对称的。按这 一条件，有 即 . （3.6） 这样无论删去哪一段，总保留长为 的区间。 第二，删掉一段，例如删掉，在保留下来的区间 ，使得里再插入一个点在中的位置与 在中的位置具有相同的比例，从而保证每次迭代都能 缩小区间。按这一条件，有以同一比率 即 或 .

7、（3.7） 把（3.7）代入（3.6）中，得到关于 的一元二次方程 其合理的根是 （3.8） 代回（3.6），得 在古代，人们认为按比率0.618分割线段是最协调的 ，胜似黄金，故称黄金分割。因此，上述按比率0.618缩 小搜索区间的迭代方法称为黄金分割法或0.618法。 算法3.2 （黄金分割法）P145 （2）抛物线插值法 抛物线插值法属于函数逼近法。它适用于连续的单谷 函数求极小值问题。 抛物线插值法的思想是：设 在搜索区间 上连续。记 和 。 如果 （3.9） 与（3.10） （两等号不同时成立）同时成立，那么可以过 和 三点作抛物线插值，设抛物线方程为 （3.11） 其实是在区间上对

8、所作的一个 曲线拟合。 记的极小点为，则根据 提供的信息， 我们可以将搜索区间 缩小，然后在缩小了的区间上 再作抛物线插值。如此下去，最终可以求到 在 中的极小点 。 令(3.12） 解出 （3.13） 根据插值条件和，列出关于 和的线性方程组 由此解出 ， ， 并代入（3.13）中，得 （3.14） 这个公式的使用条件仅仅是和 三点不共线。可以证明（习题3.5），在（3.9）和 （3.10）（两等号不同时成立）同时成立的条件下，由（ 3.14）所确定的 是的极小点，并且 。 以下讨论算法的终止准则和缩小搜索区间的方法。 按（3.14）计算出。由极限理论知道，如果 与 都很小，那么 也必然很小

9、，当然 也应该很小。 计算经验指出，可以采用 （3.15） 作为终止准则。 当终止准则满足时，取和中函数值较小的点 提供的 缩小。这个过程如下： 作为极小点；当终止准则未满足时，则需要利用 信息将原来的搜索区间 比较和的大小，有两种情况：若，则 转；否则，转。 若，则置，转； 若，则 ，转。 置 若，则置，转； 若，则 ， ，转。置 转向计算新的搜索区间上的插值抛物线 的极小点 算法流程图见书上图3-5。 包括黄金分割法和抛物线插值法在内的许多一维问题 的迭代方法全部依赖于函数单谷性的假设。但在许多问题 中，这一假设不成立或难以验证。解决这一困难的办法， 尤其当初始搜索区间很大的时候，是将搜索

10、区间分成若干 个较小区间，然后在每个子区间上寻求极小，最后又在所 有子区间的极小中选取最小的一个作为问题的最优解。 （3）不精确一维搜索技术 精确的一维搜索过程往往需要花费很大的计算量才有 可能求到符合精度要求的最优步长因子。当多维问题的迭 代点距极小点较远时，显然精确地求解一维子问题对求解 多维问题本身没有太大的意义。另外很多最优化方法，如 Newton法和拟Newton法，其收敛速度也并不依赖于精确 的一维搜索过程。因此，在实际计算中，只要选取的步长 因子能够保证目标函数在每一步的迭代中都有“满意的”下 降就可以了。这样，既会大大地节省计算量，同时还会从 整体上加快计算进程。 考虑由多维问

11、题引出的一维问题 （3.16） 其中具有一阶连续 偏导数。 Goldstein(1965年)和Powell（1975年）给出了用来 设计（3.16）不精确一维搜索过程的两个条件： ）； （3.17） ） (3.18). 其中使得，而是给定 的常数，通常取 。条件）表示应使新迭代点 的函数值相对上一迭代点 的函数值的下降幅度须不低于 某个量，而条件）则表示目标函数 在新迭代点 处沿 方向的方向导数应不小于 在上一迭代点 处沿方向的方向导数的 倍。换句话说，若 满足 条件），则认为在点 处已获得“满意的”函数值的下降。 而若满足条件），这时有两种可能性， 要么 已是点 方向 处的上升方向， 要么方

12、向虽然还是点 下降方向， 处的 但函数在点 处 沿 方向的下降率已低于 处沿方向的下降率在点 倍，这时若继续沿 方向作一维搜索，只会徒增计算量，而不会再获得函数值 的较大下降量，因此，一旦 满足条件）就需要确定 。新的搜索方向 以上分析表明，在实际计算中，选取满足（3.17）和 （3.18）的 作为确定的步长因子是合适的， 即 。 一般地， 越小，一维搜索越精确，但计算量也越大。 。 不精确的一维搜索不要求过小的而越小，条件） 越容易满足。 在实际计 算中，通常取或更小的值 值的选取不太敏感）， 。 （由此得出的解通常对 算法3.3（不精确一维搜索） 已知：，且 。 给定 （通常取），初始 （

13、可取1或参照（3.5）给出）。步长 计算。置。 计算 ； 若（3.18）成立，则转；否则，置 ，然后转； 若（3.17）成立，则打印，计算结束；否则， ，然后转。置 算法说明： ）第步中若（3.18）不成立，则表明沿 方向 有继续前进的必要； ）第步中若（3.17）不成立，这表明当前步长过 大，需缩小搜索范围。 不精确一维搜索的算法流程图 3.2 最速下降法 最速下降法是最早的求解多元函数极值的数值方法。 它直观、简单。它的缺点是，收敛速度较慢、实用性差。 1. 基本思想 求解问题（3.1）。假设迭代已得到。在点 处，取搜索方向为 （3.19） 沿进行直线搜索，由此确定 （3.20） 其中步长

14、因子满足 （3.21） （3.20）、（3.21）简单地合记为 （3.22） 3.20）或（3.22）称为最速下降迭代公式，由该公式 产生的算法称为最速下降法。 今后记 2. 算法 算法3.4（最速下降法） P151 将最速下降法应用于正定二次函数 （3.23） 可以推出显式迭代公式。 设第迭代点为，求的表达式。由 （3.24） （3.25） ， （3.26） ， ， ，（直线搜索性质） 得 即 由此解出 （3.27） 例3.1 P152 3. 锯齿现象 最速下降法的迭代点在向极小点靠近的过程中，走的 是曲折的路线：后一次搜索方向 与前一次搜索方向 总是相互垂直的，称它为锯齿现象。这一点在前面

15、的例题 中已得到验证。除极特殊的目标函数（如等值面为球面的 函数）和极特殊的初始点外，这种现象一般都要发生。 从直观上可以看到，在远离极小点的地方，每次迭代 都有可能使目标函数值有较多的下降，但在接近极小点的 地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小 。因而收敛速度不快。 已有结论表明，最速下降法对于正定二次函数关于任 意初始点都是收敛的，而且恰好是线性收敛的。 3.3 Newton法 如果目标函数在上具有连续的二阶偏导数， 其Hesse矩阵 正定且可以表达成显式（今后记 ），那么使用Newton法求解（3.1）会很快 地得到极小点。 1. 基本思想 考虑从到的迭代过程。在点处，对 按Taylor级数展开到第三项，即 （3.29） 因为正定，所以是正定二次函数。令 得 （3.30） 由此解出的极小点，记为，即 （3.31） 是极小点的新的近似点。 （3.31）称为Newton 迭代公式，由该公式产生的算法称为Newton法。 注意到，当目标函数是正定二次函数（3.36）时， 。这说明：对于正定二次函数，Newton法一 次迭代就会得到最优解。 （3.31）有直观的几何解释。函数 过点的等值 面方程为 （3.32） 在点 处，用一个与曲面（3.32）最密切的二次曲面来 代替它，这个二次曲面的方程即是 当正定时，它是一个超椭