北邮最优化课件 10使用导数的最优化方法.ppt

《北邮最优化课件 10使用导数的最优化方法.ppt》由会员分享，可在线阅读，更多相关《北邮最优化课件 10使用导数的最优化方法.ppt（143页珍藏版）》请在三一办公上搜索。

1、帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼81410，使用导数的最优化方法,最优化理论与算法,第十章 使用导数的最优化方法,最速下降法牛顿法共轭梯度法拟牛顿法信赖域法,10.1最速下降法,10.1最速下降法,考虑无约束问题 min f(x),xRn(10.1.1)其中 f(x)具有一阶连续偏导数。,在处理这类问题时，一般策略是，希望从某一点出发，选择一个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点，基于这一思想，Cauchy于1847年提出了最速下降法。这是无约束最优化中最简单的方法。,10.1最速下降法1,函数f(x)在点x处沿方向d的变化率可用方

2、向导数表示，当函数可微时有，方向导数,求函数f(x)在点x处下降最快的方向,归结为求,10.1最速下降法2,由上式知.当,时等号成立.故在点x处沿(1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.,注意:在不同的尺度下最速下降方向是不同的.,10.1最速下降法3,最速下降算法,最速下降算法的迭代公式为,10.1最速下降法4,算法描述,例1.1 用最速下降法求解下列问题,第一次迭代,目标函数f(x)在点x处的梯度,令搜索方向,令,在直线上的极小点,第二次迭代,令,得到,第三次迭代,令,此时,已经满足精度要求,得近似解,问题的最优解为x*=(0.0),算法的收敛性,证明:最速下降算法A

3、可表示为合成映射,A=MD,其中D(x)=(x,-f(x),是En En En的映射.,每给定一点x,经算法D作用,得到点x和在x处的负梯度(从x出发的方向d).算法M是En En En,映射.每给定一点x及方向d=-f(x),经M作用,即一维搜索,得到一个新点,在这一点,与前面的迭代点相比,具有较小的目标函数值,根据Th1.1,当 f(x)0时,M是闭映射.由于f(x)是连续可微实函数,故D连续,据推论2,A在x(f(x)0)处是闭的.,其次,当x时,d=-f(x)0,则f(x)T d0,因此对于yA(x),有f(y)f(x),由此知f(x)是关于A和的下降函数,因此根据Th8.2.1,算法

4、收敛,最后,按假设,x(k)含于紧集,在上述定理中,若令r=A/a,则,定理表明:条件数越小,收敛越快;条件数越大,收敛越慢.,最速下降法存在锯齿现象,容易证明,用最速下降法极小化目标函数时,相邻两个搜索方向是正交的.令,10.2 牛顿法,10.2.1 迭代格式,即,10.2 牛顿法,注意:牛顿法的迭代格式也可以从最速下降方向的角度来理解.,下求A度量下的最速下降方向,为此,考虑,10.2 牛顿法,下面介绍一下A度量及其意义下的最速下降方向.设A为对称正定矩阵,向量d的A范数定义为,由A,A-1对称正定,故存在对称平方根A1/2,A-1/2,使得,于是,10.2 牛顿法,去掉绝对值符号,有,根

5、据Schwartz不等式,得到,10.2 牛顿法,即,10.2 牛顿法,若取,则牛顿法的搜索方向实际上是关于向量椭球范数,10.2 牛顿法,10.2 牛顿法,例 用牛顿法求解下列问题,第1次迭代,10.2牛顿法,第2次迭代,10.2 牛顿法,第3次迭代,继续下去,第4次迭代,得到点列收敛于(1,0),此为最优解.,10.2 牛顿法,10.2.2 局部收敛性,10.2 牛顿法,证明:根据(10.2.2)，牛顿算法映射定义为,下证(x)是关于解集合和算法A的下降函数.,10.2 牛顿法,于是可得,从而(x)是关于解集合和算法A的下降函数,10.2 牛顿法,10.2 牛顿法,当牛顿法收敛时,有下列关

6、系,特别的,对于二次凸函数,用牛顿法求解,经一次迭代即达到极小点.设有二次凸函数,其中A是对称正定矩阵,10.2 牛顿法,先用极值条件求解.令,得最优解,下用牛顿法解,任取一初始点x(1),定义:若一个算法用于求解严格二次凸函数极小值问题时从任意初始点出发,算法在有限次迭代后可到达函数的极小值点,称此算法具有二次终止性.,于是牛顿法具有二次终止性,10.2 牛顿法,注意,当初始点远离极小点时,牛顿法可能不收敛,阻尼牛顿法,基本思想:增加了沿牛顿方向的一维搜索.,迭代公式为,10.2 牛顿法,算法(阻尼牛顿法),10.2 牛顿法,10.2.3 修正牛顿法,例 用阻尼牛顿法求解下列问题,牛顿方向,

7、10.2 牛顿法,显然,用阻尼牛顿法不能产生新点,而点x(1)=(0,0)T并不是问题极小点.可见从x(1)出发,用阻尼牛顿法求不出问题的极小点,原因在于 Hessian 矩阵 2f(x(1)非正定,再令,10.2 牛顿法,考虑(10.2.2),记搜索方向d(k)=x-x(k),阻尼牛顿法所用搜索方向是上述方程的解,此处假设逆矩阵 存在,10.2 牛顿法,再沿此方向作一维搜索,10.2 牛顿法,算法 修正牛顿法,10.2 牛顿法,10.3共轭梯度法,1 共轭方向与扩张子空间定理,定义 设A是nn对称矩阵,若Rn 中的两个方向d 1 和d2满足(d 1)T Ad 2=0（）则称这两个方向关于A共

8、轭,或称它们关于A正交.,10.3 共轭梯度法,几何意义,f(x)的等值面,由于,10.3共轭梯度法,设 x(1)是在某等值面上一点,此面在点x(1)处的法向量,又设d(1)是在该等值面在点x(1)处的一切向量.,即等值面上一点x(1)处的切向量与由这点指向极小点的向量关于A共轭.,10.3共轭梯度法,10.3共轭梯度法,10.3共轭梯度法,10.3共轭梯度法,用归纳法证之,为方便,用g j表示函数f(x)在x(j)处的梯度,即,10.3共轭梯度法,利用上式可以将 gm+2 和d(i)的内积写成,当i=m+1时,由一维搜索定义,知,当1im+1时,由归纳假设知,由二次函数梯度的表达式和点x(k

9、+1)的定义,有,10.3共轭梯度法,即,由10.3.8-11,知,10.3共轭梯度法,上述定理表明,对于二次凸函数,若沿一组共轭方向(非零向量)搜索,经有限步迭代必到达极小点.,2 线性共轭梯度法与二次终止性,Hesteness和Stiefel于1952年为解线性方程组而提出,基本思想:把共轭性与最速下降法相结合,利用已知点处的梯度构造一组共轭方向,并沿着这组方向进行搜索,求出目标函数的极小点,10.3共轭梯度法,先讨论对于二次凸函数的共轭梯度法,考虑问题,求解方法,10.3共轭梯度法,10.3共轭梯度法,10.3共轭梯度法,综上分析,在第一个搜索方向取负梯度的前提下,重复使用公式就能伴随计

10、算点的增加,构造出一组搜索方向.,10.3共轭梯度法,定理 对于正定二次函数(10.3.12),具有精确一维搜索的Fletcher-Reeves法在mn次一维搜索后即终止,并且对所有i(1 i m),下列关系成立:,证明:显然m1,下用归纳法(对i)证之.,10.3共轭梯度法,设对某个im,这些关系均成立,我们证明对于i+1也成立.先证2),由迭代公式两端左乘A,再加上b,得,其中 由式(10.3.17)确定,即,10.3共轭梯度法,考虑到(10.3.20)和(10.3.18),则,10.3共轭梯度法,当ji时,根据归纳假设,式(10.3.22)等号右端各项均为0,再证1),运用(10.3.1

11、8)和(10.3.20),则,当j=i时,把(10.3.19)代入上式第一个等号的右端,立得,10.3共轭梯度法,当ji时,由前面已经证明的结论和归纳假设,式中第2个等号右端显然为0,因此,最后证3),易知,综上,对i+1,上述三种关系成立,10.3共轭梯度法,注意,初始搜索方向选择最速下降方向十分重要,如果选择别的方向作为初始方向,其余方向均按FR方法构造,则极小化正定二次函数时,这样构造出来的一组方向并不能保证共轭性.,例 考虑下列问题,取初始点和初始搜索方向分别为,10.3共轭梯度法,显然,不是目标函数在 处的最速下降方向.,下面,我们用FR法构造两个搜索方向.,令,10.3共轭梯度法,

12、根据公式(10.3.19),有,因此,10.3共轭梯度法,令,根据公式(10.3.19),有,10.3共轭梯度法,注意,在FR法中,初始搜索方向必须取最速下降方向,因此,10.3共轭梯度法,可以证明,对于正定二次函数,运用FR法时不作矩阵运算就能求出因子i,定理 对于正定二次函数,FR法中因子i具有下述表达式,证明:,10.3共轭梯度法,10.3共轭梯度法,FR法(对二次凸函数),10.3共轭梯度法,例3.2 用FR法求解下列问题,10.3共轭梯度法,令,第一次迭代，,目标函数f(x)在点x处的梯度,10.3共轭梯度法,第2次迭代,10.3共轭梯度法,令,10.3共轭梯度法,10.3 共轭梯度

13、法,一般迭代格式,3用于一般函数的共轭梯度法非线性共轭梯度法,10.3共轭梯度法,-PRP(Polak-Ribiere-Polyar,-SW(Sorenson-Wolfe,-Daniel,-Dixon,10.3共轭梯度法,FR共轭梯度法,10.3共轭梯度法,3,如果j n,转步4,否则,转5,可以证明,对一般函数,共轭梯度法在一定条件下是收敛的,10.3共轭梯度法,FR算法中使用精确线搜索，我们有如下收敛性结果,4.1 拟牛顿条件和算法步骤,10.4 拟牛顿法,基本思想:牛顿法成功的关键在于利用了Hesse矩阵提供的曲率信息，而计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计

14、算，甚至不好求出，这就导致仅利用目标函数一阶导数的方法,拟牛顿法就是利用目标函数值f和一阶导数g的信息,构造出目标函数的曲率近似，而不需要明显形成Hesse矩阵，同时具有收敛速度快的优点。,牛顿法的迭代公式为,10.4 拟牛顿法,10.4拟牛顿法,记,10.4 拟牛顿法,则,(10.4.8)称为拟牛顿条件(方程)，也称为割线方程.怎样确定满足这个条件的H k+1?,10.4 拟牛顿法,算法 拟牛顿法,10.4 拟牛顿法,4.2 对称秩1校正,Hk称为校正矩阵.确定Hk的一个方法是令,10.4 拟牛顿法,(10.4.10),(10.4.11),利用(10.4.10),(10.4.12-13),(

15、10.4.9)可写成,10.4 拟牛顿法,(10.4.13),10.4 拟牛顿法,4.3 对称秩2校正,10.4 拟牛顿法,1，DFP算法(变尺度法),DFP算法,10.4 拟牛顿法,10.4拟牛顿法,例1用DFP方法求解下列问题,10.4拟牛顿法,初始点及初始矩阵分别为,第1次迭代,10.4拟牛顿法,令搜索方向,得到,令,10.4拟牛顿法,第2次迭代,10.4拟牛顿法,10.4拟牛顿法,令,10.4拟牛顿法,10.4拟牛顿法,得到,令,于是得最优解,10.4拟牛顿法,2 DFP算法的正定性及二次终止性,10.4拟牛顿法,证明:用归纳法 DFP方法中,H1是给定的对称正定矩阵.,设Hj是对称正

16、定矩阵,下证Hj+1也是对称正定矩阵.,根据定义,对称性是显然的,下证正定性,(10.4.19),10.4拟牛顿法,令,10.4拟牛顿法,则,由Schwartz不等式,有,10.4拟牛顿法,(10.4.22),考虑到一维搜索及方向的定义,(10.4.21)右端第一项的分母,于是,10.4拟牛顿法,下证(10.4.22)和(10.4.24)不同时为0.,若不然,(10.4.22)为0,则p/q,即p=q(0).,从而,综上,知,10.4拟牛顿法,证明:对k归纳.k=1时有,10.4拟牛顿法,(10.4.27),由于,当k=2时,10.4拟牛顿法,由此结果,易证k=2时(10.4.26)亦成立,下

17、设k=m时(10.4.25-26)成立,下证当k=m+1时上述关系式也成立.,先证k=m+1时(10.4.25)成立.,由归纳假设,只需证:,由对(10.4.26)的归纳假设,当1im时有,10.4拟牛顿法,由此有,(10.4.29),根据的推论,有,由(10.4.29),知,10.4拟牛顿法,再证当k=m+1时(10.4.26)成立,对于1im+1有,(10.4.30),当i=m+1时,由(10.4.28)知,将其代入(10.4.30)得,10.4拟牛顿法,当im+1时,根据关于(10.4.26)的归纳假设及当k=m+1时(10.4.25)成立,考虑到(10.4.28),则有,推论:在的条件

18、下,必有,10.4拟牛顿法,DFP方法中构造出来的搜索方向是一组A共轭方向DFP方法具有二次终止性.,3 BFGS公式及 Broyden簇,10.4拟牛顿法,(10.4.33),可得修正公式,-关于矩阵B的BFGS修正公式,10.4拟牛顿法,(10.4.35),上述公式由Broyden,Fletcher,Goldfarb,Shanno(1970)给出.,10.4拟牛顿法,定义,-Broyden簇,显示表达式,10.4拟牛顿法,(10.4.37),其中,(10.4.38),10.4拟牛顿法,定理10.4.3 设,其中A为n阶对称正定矩阵.则对于Broyden方法,成立:,线搜索方法：每次迭代时产

19、生一搜索方向，在此方向上进行精确或不精确一维搜索，得到下一迭代点。缺点：可能由于步长过大导致算法失败，特别当问题病态时。,Ch10.5 信赖域方法,主要数值方法1：,主要数值方法2：,信赖域方法：在每次迭代时，强制性要求新迭代点与当前迭代点之间的距离不超过某一控制量。实际上是，在以当前迭代点为中心的邻域内对一近似于原问题的简单模型求极值。优点：算法稳定性好、收敛性强。,主要内容：,1 无约束优化信赖域法：1.1 算法描述 1.2 收敛性2 约束优化（带一个等式约束）：2.1 逐步二次规划法（SQP）2.2 Marotos 效应 2.3 信赖域方法,1 无约束优化信赖域方法,问题：基本思想：给定

20、初始迭代点，确定一个以其为中心的邻域，在此域内优化目标函数的二次逼近式，得到下一迭代点。,信赖域子问题：,信赖域内原问题的逼近问题：,1.1 算法描述,Step1 给定初始点Step2 若，则停止计算，得解；否则，解子问题得最优解Step3 计算，令选取下一信赖域半径使其满足Step4 产生 转step2,定理：是信赖域子问题的解当且仅当它是子问题的K-T点，且 是半正定矩阵。,1.2 收敛性,在一定条件下，信赖域方法具有全局收敛性。设 是 上的实函数，是给定初始点，是有界闭集，和 在 上连续，用信赖域方法求得序列，则.,2 等式约束非线性优化,问题(2.1)：其中：,2.1 逐步二次规划(S

21、QP),SQP方法是求解非线性规划的一般方法，是线搜索方法的一种。基本方法：求解原问题可以转化为求解一系列二次规划子问题。是原问题K-T点当且仅当：其实就是拉格朗日函数的稳定点,SQP,给定当前迭代点 通过下面的等式求迭代步，可得到下一个迭代点.（2.2）其中，,SQP,解等式（2.2）相当于求解子问题得到的 作为第k次迭代的搜索方向,收敛性：,在一定条件下，算法产生的点列 的任何聚点都是原问题的K-T点。对原问题若 处的二阶充分条件成立 对子问题若 处的一阶必要条件成立，则 是一超线性收敛步，算法具有超线性收敛性：,2.2 Marotos效应,在无约束情形，超线性收敛步都是可以接受的：如果

22、是稳定点且二阶充分条件成立，则在算法迭代过程中，对所有充分大的k，都有：约束优化时不成立：尽管 是一超线性收敛步（比 远近于），但无论从目标函数值或约束违反度来看，都是一个“坏”点。Marotos效应指出，对于许多罚函数，超线性收敛步不一定能被接受，破坏了算法收敛性。,例子：,等式约束优化极小点为,克服Marotos效应的方法,放松接受试探步的条件引进二阶校正步在算法中用光滑精确罚函数作价值函数,2.3 信赖域方法,问题（3.1）将SQP中子问题与信赖域要求合并得到信赖域子问题：（3.2）,线性化约束不相容(1):,将线性化约束的约束函数值项都乘上一个(0,1上的参数：（3.3）相当于将每个约

23、束的可行域往远点方向压缩。参数取值：使（3.2）尽量可行，取值应尽量靠近1，但为使子问题有一定自由度，取值不能过大。,参数取值,构造问题：其最小范数解为Gauss-Newton步当且仅当（3.3）有可行点，为不使参数太小，要求则,线性化约束不相容(2)：,用一个平方和约束代替（3.2）中的等式约束条件（3.4）,2.3.2 CDT子问题,由Celis，Dennis，Tapia(1985)提出(3.5)只有在 时，(3.5)才相容。,先考虑,若仅有一可行点，则此点有如下形式：其中，如果 则；只可能在 时才可能奇异若可行域不只一个点，则(3.6),将（3.5）转化成无约束信赖域子问题,由(3.6)必有 其中令 是由 零空间的一组正交基组成的矩阵，通过变换 可将(3.5)化为用前面的无约束信赖域算法求解,在下面讨论中，均假设,定理（必要条件）：设 是（3.5）的解，则必存在Lagrange乘子 和 使得（3.7）如果乘子是唯一的，则矩阵至多只有一个负特征值。,定理（充分条件）：设 是子问题的可行点，如果存在 和 使得（3.7）成立，且 是半正定矩阵，则 是子问题（3.5）的解。推论1：假定 正定，则 是子问题的解，当且仅当存在 和 使得（3.7）成立，此时，解有如下形式：（3.8）,推论2：设 正定，前面定义的 是子问题的解当且仅当它是可行点，且下列之一成立：,