第6章--无约束问题的优化方法.doc

第6章 无约束问题的优化方法§6.1 最速下降法和牛顿法6.1.1 最速下降法的基本原理、计算步骤和特点基本原理：考虑无约束问题从某一点出发，选择一个目标函数值下降最快的方向，可以尽快达到极小点1847年法国数学家Cauchy提出了最速下降法后来，Curry等人作了进一步研究最速下降方向是目标函数的负梯度方向：最速下降法的迭代公式：取为在点处的最速下降方向：为进行一维搜索的步长，满足：计算步骤：(l)给定初点，允许误差，置.(2)计算搜索方向.(3)若，则停止计算；否则，从出发，沿进行一维搜索，求，使(4)令,置，转步骤（2）.例1 解问题初点，. （最优解）第1次迭代：目标函数在点处的梯度令搜索方向 从出发，沿方向进行一维搜索，求步长，即令(一般应采用不精确一维搜索求解)，解得在直线上的极小点： 第2次迭代： 解得 第3次迭代：解得 这时有满足精度要求，得到近似解最速下降算法的特点：最速下降算法在一定条件下是收敛的最速下降法产生的序列是线性收敛的，而且收敛性质与极小点处Hesse矩阵的特征值有关定理1: 设存在连续二阶偏导数，是局部极小点，Hesse矩阵的最小特征值，最大特征值为，算法产生的序列收敛于点，则目标函数值的序列以不大于的收敛比线性地收敛于.最速下降法存在锯齿现象：从局部看，最速下降方向确是函数值下降最快的方向从全局看，由于锯齿现象的影响，即使向着极小点移近不太大的距离，也要经历不小的弯路，使收敛速率大为减慢注1：最速下降法并不是收敛最快的方法，从全局看，它的收敛是比较慢的注2：最速下降法一般适用于计算过程的前期迭代或作为间插步骤当接近极小点时，使用最速下降法达到迭代终止，这样做并不有利6.1.2 牛顿法的基本原理、计算步骤和特点1.牛顿法在点的二阶Taylor展开为求的平稳点，令,即 (1)设可逆，得到牛顿法的迭代公式产生序列，在适当的条件下，这个序列收敛例2：解问题： (最优解)目标函数的梯度和Hesse矩阵分别为 取初点.第l次迭代: 第2次迭代: 继续迭代，得到,注3：当牛顿法收敛时，有下列关系：c是某个常数因此，牛顿法至少2级收敛，收敛速率是很快的注4：对二次凸函数，用牛顿法求解经1次迭代即达极小点设有二次凸函数: 用极值条件求解：令得到最优解用牛顿法求解：任取初始点，根据牛顿法的迭代公式有以后还会遇到一些算法，把它们用于二次凸函数时，类似于牛顿法，经有限次迭代必达到极小点这种性质称为二次终止性注5: 当初始点远离极小点时，牛顿法可能不收敛牛顿方向不一定是下降方向，经迭代，目标函数值可能上升.即使目标函数值下降，得到的点也不一定是沿牛顿方向的最好点或极小点对牛顿法进行修正，提出了阻尼牛顿法2. 阻尼牛顿法阻尼牛顿法增加沿牛顿方向的一维搜索，迭代公式:为牛顿方向.由一维搜索得到:由于阻尼牛顿法含有一维搜索，因此每次迭代目标函数值一般有所下降（绝不会上升）可以证明，阻尼牛顿法在适当的条件下具有全局收敛性，且为2 级收敛阻尼牛顿法的计算步骤：(l)给定初点，允许误差，置.(2)计算，.(3)若，则停止计算；否则，令（4）从出发，沿进行一维搜索，求，使(5)令,置，转步骤（2）.3.牛顿法的进一步修正原始牛顿法和阻尼牛顿法有共同缺点：（1）可能出现Hesse矩阵奇异的情形，因此不能确定后继点；（2）即使非奇异，也未必正定，因而牛顿方向不一定是下降方向，就可能导致算法失效例3: 用阻尼牛顿法求解：取初始点. 在点处，有，牛顿方向从出发，沿作一维搜索令 , 则 .用阻尼牛顿法不能产生新点，而点并不是问题的极小点原因在于Hesse矩阵非正定为使牛顿法从任一点开始均能产生收敛于解集合的序列，要做进一步修正,克服Hesse矩阵非正定考虑（1）式，记搜索方向，得到 (2)阻尼牛顿法所用搜索方向是上述方程的解：解决Hesse矩阵非正定问题的基本思想：修正，构造一个对称正定矩阵.在（2）中，用取代矩阵,得到方程 (3)解此方程，得到在点处的下降方向构造矩阵的方法之一: 令是一个适当的正数只要选择得合适，就是对称正定矩阵注6: 当为鞍点时，有 及 不定此时（3）式不能使用这时可取为负曲率方向：当不定时，这样的方向必定存在，而且沿此方向进行一维搜索必能使目标函数值下降§6.2 共轭梯度法6.2.1 共轭方向的基本原理和定理共轭梯度法是基于共轭方向的一种算法定义1：设是对称正定矩阵，若中的两个方向和满足则称这两个方向关于共轭，或称它们关于正交若， ，是中个方向，它们两两关于共轭，即满足则称这组方向是共轭的，或称它们为的个共轭方向注1：如果为单位矩阵，则两个方向关于共轭等价于两个方向正交共轭是正交概念的推广注2：如果是一般的对称正定矩阵，和关于共轭，也就是方向与方向正交共轭的几何意义（以正定二次函数为例）：二次函数函数的等值面是以为中心的椭球面，是极小点.设是在某个等值面上的一点，该等值面在点处的法向量又设是这个等值面在处的一个切向量记与正交，即，因此有即等值面上一点处的切向量与由这一点指向极小点的向量关于共轭.依次沿着和进行一维搜索，则经两次迭代必达到极小点共轭方向的重要性质:定理1: 设是阶对称正定矩阵， ，是个共轭的非零向量，则这个向量组线性无关定理2（扩张子空间定理）: 设有函数其中是阶对称正定矩阵， ，是共轭的非零向量以任意的为初始点，依次沿， ，进行一维搜索，得到点， ，则是函数在线性流形上的惟一极小点特别地，当时，是函数的惟一极小点其中是， ，生成的子空间推论: 在定理2的条件下，必有 定理2表明: 对于二次凸函数，若沿一组共轭方向（非零向量）搜索，经有限步迭代必达到极小点6.2.2 用于正定二次函数的共轭梯度法共轭梯度法最初由Hesteness和Stiefel于1952年提出本节重点介绍Fletcher-Reeves共轭梯度法(FR法)共轭梯度法的基本思想:把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，沿这组方向进行搜索，求出目标函数的极小点根据共轭方向的基本性质，这种方法具有二次终止性考虑如下正定二次函数优化问题的求解方法:令.任意给定一个初始点,计算出目标函数在这点的梯度，,则停止计算；否则，令沿方向搜索，得到点计算在处的梯度，若，则利用和构造第2个搜索方向，再沿搜索一般地，若已知点和搜索方向，则从出发，沿进行搜索，得到步长满足.此时可求出的显式表达令,根据及二次函数的梯度的表达式，得到 (1)计算在处的梯度，若，则停止计算;否则用和构造下一个搜索方向，并使和关于共轭按此设想，令上式两端左乘，并令由此得到 再从出发，沿方向搜索可以证明,按上述方法构造的一组搜索方向,是关于A共轭的因此，上述方法具有二次终止性定理3: 对于正定二次函数，具有精确一维搜索的FR法在次一维搜索后即终止，并且对所有)，下列关系成立：(l) (2) (3) 证明: 用归纳法可证注3: 在FR法中，初始搜索方向必须取最速下降方向如果选择别的方向作为初始方向，其余方向均按FR法构造，那么极小化正定二次函数时，构造出来的一组方向并不能保证共轭性可以证明: 对于正定二次函数，运用FR法时，不作矩阵运算就能求出因子定理4: 对于正定二次函数，FR法中因子, (2)对于二次凸函数，FR法计算步骤：(1) 给定初始点，置.(2) 计算，若，则停止计算，得点；否则，进行下一步.(3)构造搜索方向，令.当时，,当时，按（2）式计算因子.(4)令,步长按（1）式计算(5)若，则停止计算，得点；否则，置，返回步骤(2). 例1: 用FR法求解问题：,取初始点.目标函数梯度: 第1次迭代: 令,从沿方向作一维搜索，得 第2次迭代: 在点处，目标函数的梯度构造搜索方向计算因子.令从出发,沿方向作一维搜索,得 点处,目标函数梯度,已达到极小点.6.2.3 将共轭梯度法用于求解非正定二次函数优化问题用于极小化任意函数的共轭梯度法与用于极小化二次函数的共轭梯度法主要差别: (1)步长不用计算，必须用其它一维搜索方法来确定(2)凡用到矩阵A之处，需要用现行点处的Hesse矩阵用这种方法求任意函数极小点，一般来说用有限步迭代是达不到的迭代延续可以采取不同的方案：·直接延续，即总是用构造搜索方向；·把n步作为一轮，每搜索一轮之后，取一次最速下降方向，开始下一轮称为“重新开始”或“重置”每n次迭代后以最速下降方向重新开始的共轭梯度法，有时称为传统的共轭梯度法计算步骤：(1)给定初始点，允许误差置, (2)若 ,则停止计算；否则，作一维搜索，求，满足令.(3)如果，则进行步骤(4)；否则，进行步骤(5).(4)令,其中置，转步骤(2).(5)令，,，置, ，转步骤(2). 注4:可以采用不同公式计算因子:(1)（FR法）(2)(Polak,Ribiere&Polyak，PRP法)(3) (Sorenson和Wolfe)(4) (Daniel)（1）当极小化正定二次函数，初始搜索方向取负梯度时，四个公式是等价的（2）用于一般函数时，得到的搜索方向不同（3）有人认为PRP方法优于FR法但据一些人的计算结果，几种方法彼此差别并不很大，难以给出绝对的比较结论注5: 运用共轭梯度法时应该注意，均假设采用精确一维搜索.精确一维搜索需付出较大代价，因此许多情形下采用不精确一维搜索不精确一维搜索会出现新的问题，按照构造的搜索方向可能不是下降方向解决方法:(1)当不是下降方向时，以最速下降方向重新开始当一维搜索比较粗糙时，这样的重新开始可能是大量的，因此会降低计算效率(2)计算过程中增加附加检验设，,表示在检验点处计算出的，和,如满足则取作为步长；否则，进行精确一维搜索，求最优步长共轭梯度法的收敛性:对于一般函数, 共轭梯度法在一定条件下是收敛的.Crowder和Wolfe证明: 共轭梯度法的收敛速率不坏于最速下降法; 不用标准初始方向,共轭梯度法的收敛速率可能像线性速率那样慢. 共轭梯度法的优点:存储量小：FR法只需存储3个n维向量.求解变量多的大规模问题可用共轭梯度法§6.3 拟牛顿法6.3.1 拟牛顿法简介牛顿法的最大优点是收敛速度快，原因是牛顿法在迭代点附近对目标函数进行二次近似时，利用了目标函数的曲率信息（Hesse矩阵）。使用Hesse矩阵存在一些缺点：计算量大、Hesse矩阵可能非正定，导致牛顿方向可能不是一个下降方向等。愿望：寻找一种算法，既具有牛顿法收敛速度快的优点，又能克服计算工作量大、产生非下降方向等缺点。拟牛顿法（quasi-Newton method）的基本思想：在迭代过程中只利用目标函数和梯度信息，构造Hesse矩阵的近似矩阵，由此获得一个搜索方向，生成新的迭代点。近似矩阵的不同构造方式，对应着拟牛顿法的不同变形。拟牛顿法是一类收敛速度比较快的算法，是公认的比较有效的无约束优化方法。6.3.2 拟牛顿条件及拟牛顿法的主要步骤设在第k次迭代后，得到点，将目标函数在点作二阶Taylor展开近似：目标函数梯度在附近可近似为对的附近点，有或 记 有又设Hesse矩阵可逆，则计算出和后，可根据上式估计在处的Hesse 矩阵的逆为了用不包含二阶导数的矩阵取代牛顿法中的Hesse矩阵的逆矩阵，有理由令满足 （1）(1)式称为拟牛顿条件拟牛顿法的计算步骤：(1)初始化：给定初始点，正定矩阵，；计算 置.(2)平稳点检验：若，则停止计算；否则，计算搜索方向.(3)一维搜索：求出步长，令.(4)修正拟牛顿方程：计算 并对矩阵进行校正，得到，使之满足拟牛顿条件（1）；置，转步骤（2）.6.3.3 对称秩1校正满足拟牛顿条件的矩阵应与Hesse矩阵的逆阵一样，是n阶对称正定矩阵构造近似矩阵的一般策略：取为任意一个n阶对称正定矩阵，通常选择为单位矩阵I，然后通过修正给出.令称为校正矩阵确定的方法之一令是n维列向量这样定义的是秩为l的对称矩阵的选择应使(1)式得到满足，令 （2）得到 (2a)另一方面，(2)式两端左乘，经整理得到 （3）利用（2a）式和（3）式可得到秩1校正公式： （4）利用秩l校正极小化函数时，在第k次迭代中，令搜索方向然后沿方向搜索，求步长，满足确定出后继点. 可以证明：秩1校正方法在一定条件下是收敛的，并且具有二次终止性运用秩l 校正存在一些困难，应用有某种局限性：（1）仅当时，由（4）式得到的才能确保正定性，而这一点是没有保证的（2）即使由于舍入误差的影响，可能导致无界，从而产生数值计算上的困难6.3.4 DFP和BFGS校正(对称秩2校正)1.DFP算法DFP方法由Davidon首先提出，后来又被Fletcher和Powell改进，又称为变尺度法校正矩阵（DFP公式）： （5） （6）可以验证，这样定义的校正矩阵满足拟牛顿条件（1）.DFP方法计算步骤：(1)给定初始点，允许误差.(2)置，计算,置.(3)令.(4)从出发，然后沿方向搜索，求步长，满足令. (5)检验是否满足收敛准则，若，则停止迭代，得到点；否则，返回步骤（6） . (6)若，则令，返回步骤（2）；否则，进行步骤（7）. (7)令利用（6）式计算，置，返回步骤（3）.例1：用DFP法求解问题：取初始点及初始矩阵.目标函数的梯度第1次迭代：在点处的梯度令搜索方向 从出发作一维搜索：解得 ， 第2次迭代：， 计算矩阵令 从出发，沿方向搜索：解得 ， 得到最优解注1：此例经两次搜索达到极小点，这不是偶然的可证明，DFP方法具有二次终止性定理1：若，则DFP方法构造的矩阵为对称正定矩阵证明：用归纳法可证定理2：设用DFP方法求解下列问题：A为n阶对称正定矩阵取初点，令是n阶对称正定矩阵，则成立其中证明：用归纳法可证推论：在定理2的条件下，必有.注2：由于，因此,，关于A共轭等价于,，关于A共轭可见，DFP方法中构造出来的搜索方向是一组A共轭方向，DFP方法具有二次终止性若目标函数为正定二次函数，则DFP法经有限步迭代必达极小点。DFP方法用于一般函数时的收敛性：定理3：如果是上的二次连续可微实函数，对任意，存在常数，使得当,时，有则DFP方法产生的序列或终止于或收敛于在上惟一极小点2.BFGS公式Broyden,Fletcher,Goldfarb和Shanno于1970年提出它比DFP公式还好，得到广泛应用BFGS法中用矩阵近似Hesse矩阵，给出另一种形式的拟牛顿条件： （7）在（l）式中，用取代，同时交换和，恰好得出（7）式，因此只需在的递推公式中互换和，并用和分别取代和，就能得到的递推公式，而不必从（7）式出发另行推导的修正公式（称为关于矩阵B 的BFGS 修正公式，也称为DFP公式的对偶公式）： （8）设可逆，则由（7）式可知此式表明，满足拟牛顿条件（1），因此可令 （9）根据（8）式求，得到关于H的BFGS公式： （10）例2：用BFGS法求解问题：取初始点及初始矩阵，.目标函数的梯度，所以第1次迭代：搜索方向 从出发作一维搜索：解得 ， 根据，由（10）式计算出第2次迭代：搜索方向（可以验证，该方向也是共轭梯度法中生成的方向）通过求解一维搜索：解得新的迭代点，对应的函数值.，所以就是希望的最优解.拟牛顿法优点:(1) 迭代中仅需一阶导数，不必计算Hesse矩阵;(2) 当使正定时，算法产生的方向均为下降方向;(3) 具有二次终止性，对于一般情形，具有超线性收敛速率而且还具有n步二级收敛速率拟牛顿法的缺点：（1） 所需存储量较大；（2） 对于大型问题，可能遇到存储方面的困难习题分别用最速下降法、FR共轭梯度法、DFP法和BFGS法求解问题取初始点