4.无约束优化方法.ppt

1、,第四章,无约束最优化方法, 4.1 最速下降法,问题提出,问题：,在点,处，,沿什么方向,下降最快?,分析：,考查：,柯西不等式：,问题：,在点,处，,沿什么方向,下降最快?,分析：,考查：,显然当,时，,取极小值,因此：,结论：,负梯度方向使,下降最快，,亦即最速,下降方向,*可取最优步长或下降步长,一）基本思想,2）迭代公式,1）沿负梯度方向搜索：,二）终止判别条件,* 前后两个方向正交,从 出发，沿 搜索得,* “最速下降性”只是迭代点邻域的局部性质。从全局看，并非最速下降方向。,三)迭代步骤,例1：,用最速下降法求解：,解：,最速下降法优点,(1),程序设计简单，计算量小，存储量小，

2、,对初始点没有特别要求,(2),有着很好的局部收敛性，,最速下降法缺点,有时是,很慢的线性收敛,原因：,仅反映,在,处,的局部性质,相继两次迭代中搜索,方向是正交的,习题,P66 5, 4.2 牛顿法,基本思想,利用目标函数,在点,处的二阶Taylor,展开式去近似目标函数，,用二次函数的极小点,去逼近目标函数的极小点,算法构造,问题：,设,二阶连续可微，,海赛阵,正定,如何从,因为,正定，,则,有唯一极小点，,用这个,极小点作为,所以要求：,即：,因此：,这就是牛顿法迭代公式,注：,这里,牛顿法算法,1.,给出,2.,计算,如果,停,3.,否则计算,4.,令,转步.,并且求解方程,得出,例1

3、：,用牛顿法求解：,解：,从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念 对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升，即出现f(xk+1)f(xk)的现象,正定，可逆,阻尼牛顿法算法,1.,给出,2.,计算,如果,停,3.,否则计算,4.,沿,并且求解方程,得出,进行线搜索，,得出,5.,令,转2.,例2：,用阻尼牛顿法求解：,解：,显然,不是正定的，,但：,于是，,沿方向,进行线搜索，,得其极小点,从而迭代不能继续下去,2020/8/12,22,牛顿法的特点,牛顿法和阻尼牛顿法统称为牛顿型方法 主要缺点 每次迭代都要计算

4、函数的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维数高时工作量更大 从计算机存储方面考虑，牛顿型方法所需的存储量也是很大的 最速下降法的收敛速度比牛顿法慢，而牛顿法又存在上述缺点。针对这些缺点，近年来人们研究了很多改进的算法 如针对最速下降法(梯度法) 提出只用梯度信息，但比最速下降法收敛速度快的共轭梯度法； 针对牛顿法提出变尺度法等, 4.3 共轭方向法 与共轭梯度法,算法特点,（）建立在二次模型上，具有二次终止性,（）有效的算法，克服了最速下降法的慢,收敛性，又避免了牛顿法的计算量大和局部收,性的缺点,（）算法简单，易于编程，需存储空间小等,优点，是求解大规模问题的主

5、要方法,共轭方向及其性质,定义1:,设,是,中任一组,非零向量，,如果：,则称,是关于,共轭的,注：,若,则是正交的，因此共轭是,正交的推广,定理1:,设,为,阶正定阵，,非零向量组,关于,共轭，,则必线性无关,证明：,设,推论1:,设,为,阶正定阵，,非零向量组,关于,共轭，,则向量构成,的一组基,推论2:,设,为,阶正定阵，,非零向量组,关于,共轭，,若向量,与,关于,共轭，,则,共轭方向法算法,Step1:,给出,计算,和初始下降方向,Step2:,如果,停止迭代,Step3:,计算,使得,Step4:,采用某种共轭方向法计算,使得：,Step5:,令,转Step2.,共轭方向法基本定理

6、,定义2:,设,维向量组,线性无关，,向量集合,为,与,生成的,维超平面,引理1:,设,是连续可微的严格凸函数，,维向量组,线性无关，,则：,是,在,上,唯一极小点的充要条件是：,证：,定理2:,设,为,阶正定阵，,向量组,关于,共轭，,对正定二次函数,由任意,开始，,依次进行,次精确线搜索：,则：,（）,（）,是,在,上的极小点,推论:,当,时，,为正定二次函数在,上的极小点,共轭梯度法,记：,左乘,并使,得：,取：,共轭梯度法基本性质,定理3:,对于正定二次函数，,采用精确线搜索,的共轭梯度法在,步后终止，,且对,成立下列关系式：,（共轭性）,（正交性）,（下降条件）,FR共轭梯度法算法,

7、Step1:,给出,Step2:,计算,如果,停,Step3:,Step4:,由精确线搜索求,Step5:,转Step2.,例4：,用FR共轭梯度法求解：,解：,(2),作业：p66, 4, 9,Newton法最突出的优点是收敛速度快,在这一点上其它算法无法比拟的.因此,建议凡是Hesse矩阵比较容易求出的问题尽可能使用Newton法求解. 然而Newton法还有一个严重缺陷,就是每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵,当问题的维数n较大时,计算量迅速增加,从而就抵消了Newton法的优点,4.4 变尺度法,为此，人们开始寻找一种算法既可以保持Newton法收敛速度快的优点，又可

8、以摆脱关于Hesse矩阵的计算，这就是本节要给大家介绍的变尺度算法 变尺度法是一种非常好的方法其中DFP算法和BFGS算法，可以说直到目前为止在不用Hesse矩阵的方法中是最好的算法,一、变尺度法基本原理 在Newton法中，由基本迭代格式 其中 令 于是有 其中 是初始点， 和 分别是目标函数 在 点 的梯度和Hesse矩阵,为了消除这个迭代公式中的Hesse逆矩阵 可用某种近似矩阵 来替换它，即构造一个矩阵序列 去逼近Hesse逆矩阵序列 此时迭代式变为 事实上,式中 无非是确定了第 次迭代的搜索方向.为了取得更大的灵活性,我们考虑更一般的迭代公式 其中步长因子 通过从 出发沿 作直线搜

9、索来确定,此式是代表很广的一类迭代公式. 例如,当 （单位矩阵）时，它变为最速下降法的迭代 公式为使 确实与 近似并且有容易计算的特点， 必须对 附加某些条件： 第一，为保证迭代公式具有下降性质，要求 中的每 一个矩阵都是对称正定的理由是，为使搜索方向 是下降方向，只要 成立即可，即 成立 当 对称正定时,此式必然成立,从而保证 具有下降性质,第二，要求 之间的迭代具有简单形式显然， 是最简单的形式了其中 称为校正矩阵，称为校正公式 第三， 必须满足拟Newton条件,所谓拟Newton 条件由下面的推导给出 设迭代过程已进行到 步， 和 均已求出，现在推导 所必须满足的条件 设目标函数 具有

10、连续的二阶偏导数现在将 在 处展成二阶泰勒公式: 令 ，于是有 即,当 正定时， 当用 近似 时，由此看出 也必须满足 就是称为 近似Newton 条 件为了今后书写方便，记 于是拟Newton条件可写为,二、变尺度法迭代步骤（拟Newton法） 已知目标函数 及其梯度 终止限 （1）选定初始点 ；计算 ；选定初 始矩阵 ,要求 对称正定（例如 ）;置 （2）计算搜索方向 （3）作直线搜索 ，计算,（4）判别终止准则是否满足：若满足，则 就是 所求的极小点，打印，停机；否则转（5） （5）计算 （6） , 转（2） 其中校正矩阵 可由确定的公式来计算不同 的公式对应不同的拟Newton算法,拟

11、Newton算法的流程如图所示,以下将要讨论各种公式的构成以及相应算法但是不论哪个公式都必须满足拟Newton条件. 必须满足 或 由此可见， 与 ， 和 有关 满足条件的 有无穷多个，因此上述拟Newton算法构成一族算法下面分别介绍两个常用的公式,（一）DFP算法 DFP算法首先是由Davidon（1959年）提出来的，后来，Fletcher和Powell（1963年）对Davidon的方法作了改进，最后才形成DFP算法 D，F，P是这三位学者名字的字头这种算法是无约束最优化方法最有效的方法之一,DFP校正公式,是,维待定向量,要求：,所以：,令：,得：,因此：,所以：,（DFP校正公式）

12、,已知目标函数 及其梯度 ,问题的维数 ,终止限 (1)选定初始点计算 (2)置 (3)作直线搜索 计算 (4)判别终止准则是否满足:若满足,则打印 停机；否则转(5) (5)若 则置 转(2);否则,转(6). (6)计算 置 转(3).,DFP算法迭代步骤,例4.4 用DFP算法求 取 解:,以下用DFP法作第二次迭代 按DFP算法中的第（6）步计算 因为 所以,搜索方向为 从 X1出发沿d1进行直线搜索，即 由 知 ， 所以 ， 由于 所以 是极小点,例6：,用DFP算法求解：,取,解：,(1),(2),（二）BFGS算法 我们再介绍另一个有效和著名的变尺度算法由于它是Broyden，

13、Fletcher（1970年），Goldfarb（1969年）和Shanno（1970年）共同研究的结果，因而叫做BFGS算法,1BFGS算法基本原理 考虑如下形式的校正公式 式中 这时校正矩阵为,式中有一个参数 ，它可以取任何实数，每取一个实数就对应一种拟Newton算法 容易验证，当取 时就是DFP校正公式 令 就转变为著名的DFGS校正公式,作业,(1)用FR共轭梯度法求解：,(2)用DFP算法求解：,2020/8/12,68,4.5 坐标轮换法,1)几何描述(以二维问题为例）,二）迭代步骤,依次沿个n个正交坐标轴的方向搜索：,一）搜索方向,2020/8/12,69,2) 坐标轮换法流程

14、图,2020/8/12,70,三) 算法特点,如:(1)等值线为椭圆,且长短轴分别平行于坐标轴时-高效,(2)等值线为如图脊线时-无效,(3)一般情况-低效,1）编程简单，容易掌握； 2）收敛速度通常较低（其有效性取决于目标函数的性态），仅适于低维的情况。,例 用坐标轮换法求 初始点 解: 从初始点出发，依次沿方向 搜索，以第一步为例,从X0出发,沿e1方向搜索,求得 点,得 即 于是得 再从 出发，沿 方向搜索，求得 点 求 可得 ，即取 于是有,终止判别 因终止条件不满足,需继续迭代,取 进行第二轮循环迭代,各轮迭代计算数据见下表,最优解为,2020/8/12,74,4.6 鲍威尔方法,3

15、）若目标函数为正定二次函数，n轮结束后即可到达最优点。,2）每轮迭代产生一个新方向取代原来的第一方向，n轮迭代后可产生n个彼此共轭的方向；(证明）,1）开始采用坐标轴方向；,一）Powell基本算法,2020/8/12,75,二）Powell法（ Powell修正算法）,应用 Powell基本算法时，若有一次搜索的最优步长为0，且该方向被换掉，则该算法失效。,1）问题的提出,2020/8/12,76,2)Powell对基本算法的改进 在获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向.,* 根据Powell条件判定是否需换方向；,如需换向，则换掉函数值下降量最大的方向.,2020/8/12,77,三）Powell条件,如下述两不等式 同时成立则需换向，否则仍取原方向组。,计算:,（映射计算）,2020/8/12,78,四）更换方向的步骤,3）更换方向：,2）构造新方向：,1）找出该轮迭代中目标函数值下降量最大的方向（假定其标号为m）；,202