帅天平帅天平北京邮电大学数学系Email:tpshuaigmail.com,Tel:62281308, Rm:主楼81410， 使用导数的最优化方法最优化理论与算法1TP SHUAI第十章 使用导数的最优化方法最速下降法牛顿法共轭梯度法拟牛顿法信赖域法2TP SHUAI10.1最速下降法10.110.1最速下降法最速下降法 考虑无约束问题 min f(x), xRn (10.1.1)其中 f(x)具有一阶连续偏导数。在处理这类问题时，一般策略是，希望从某一点出发，选择一个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点，基于这一思想，Cauchy于1847年提出了最速下降法。这是无约束最优化中最简单的方法。3TP SHUAI10.1最速下降法1函数f(x)在点x处沿方向d的变化率可用方向导数表示，当函数可微时有，方向导数求函数f(x)在点x处下降最快的方向,归结为求4TP SHUAI10.1最速下降法2由上式知.当时等号成立.故在点x处沿(1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向最速下降方向.注意注意:在不同的尺度下最速下降方向是不同的.5TP SHUAI10.1最速下降法3最速下降算法最速下降算法最速下降算法的迭代公式为6TP SHUAI10.1最速下降法4算法描述算法描述7TP SHUAI例1.1 用最速下降法求解下列问题第一次迭代目标函数f(x)在点x处的梯度8TP SHUAI令搜索方向9TP SHUAI令在直线上的极小点第二次迭代10TP SHUAI令11TP SHUAI得到第三次迭代12TP SHUAI令13TP SHUAI此时已经满足精度要求,得近似解问题的最优解为x*=(0.0)14TP SHUAI算法的收敛性算法的收敛性证明证明:最速下降算法A可表示为合成映射A=MD其中D(x)=(x,-f(x),是En En En的映射.每给定一点x,经算法D作用,得到点x和在x处的负梯度(从x出发的方向d).算法M是En En En15TP SHUAI 映射.每给定一点x及方向d=-f(x),经M作用,即一维搜索,得到一个新点,在这一点,与前面的迭代点相比,具有较小的目标函数值,根据Th1.1,当 f(x) 0时,M是闭映射.由于f(x)是连续可微实函数, 故D连续,据Th8.1.1推论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,算法收敛最后,按假设,x(k)含于紧集16TP SHUAI在上述定理中,若令r=A/a,则17TP SHUAI 定理表明:条件数越小,收敛越快;条件数越大,收敛越慢.最速下降法存在锯齿现象18TP SHUAI 容易证明,用最速下降法极小化目标函数时,相邻两个搜索方向是正交的.令19TP SHUAI10.2 牛顿法10.2.1 迭代格式迭代格式20TP SHUAI即10.2 牛顿法 (x)=0为求 (x)的驻点,令21TP SHUAI 注意注意:牛顿法的迭代格式也可以从最速下降方向的角度来理解.下求A度量下的最速下降方向,为此,考虑10.2 牛顿法下面介绍一下A度量及其意义下的最速下降方向.设A为对称正定矩阵,向量d的A范数定义为22TP SHUAI由A, A-1对称正定,故存在对称平方根A1/2 , A-1/2,使得于是10.2 牛顿法23TP SHUAI去掉绝对值符号,有根据Schwartz不等式,得到10.2 牛顿法24TP SHUAI即为得到在点x处下降最快的方向,按下式选取d这时上式等号成立,由此确定的方向即度量度量A A意义下意义下的最速下降方向的最速下降方向10.2 牛顿法25TP SHUAI若取则牛顿法的搜索方向实际上是关于向量椭球范数10.2 牛顿法26TP SHUAI10.2 牛顿法例 用牛顿法求解下列问题第1次迭代27TP SHUAI10.2牛顿法第2次迭代28TP SHUAI10.2 牛顿法第3次迭代继续下去,第4次迭代,得到点列收敛于(1,0),此为最优解.29TP SHUAI10.2 牛顿法10.2.2 局部收敛性30TP SHUAI10.2 牛顿法证明:根据(10.2.2)，牛顿算法映射定义为下证(x) 是关于解集合和算法A的下降函数.31TP SHUAI10.2 牛顿法于是可得从而(x) 是关于解集合和算法A的下降函数32TP SHUAI10.2 牛顿法33TP SHUAI10.2 牛顿法当牛顿法收敛时,有下列关系特别的,对于二次凸函数,用牛顿法求解,经一次迭代即达到极小点.设有二次凸函数其中A是对称正定矩阵34TP SHUAI10.2 牛顿法先用极值条件求解.令得最优解下用牛顿法解,任取一初始点x(1)定义:若一个算法用于求解严格二次凸函数极小值问题时从任意初始点出发,算法在有限次迭代后可到达函数的极小值点,称此算法具有二次终止性.于是牛顿法具有二次终止性35TP SHUAI10.2 牛顿法注意,当初始点远离极小点时,牛顿法可能不收敛阻尼牛顿法阻尼牛顿法基本思想:增加了沿牛顿方向的一维搜索.迭代公式为36TP SHUAI10.2 牛顿法算法(阻尼牛顿法)37TP SHUAI10.2 牛顿法10.2.3 修正牛顿法修正牛顿法例 用阻尼牛顿法求解下列问题牛顿方向38TP SHUAI10.2 牛顿法显然,用阻尼牛顿法不能产生新点, 而点x(1) =(0,0) T并不是问题极小点.可见从x(1)出发,用阻尼牛顿法求不出问题的极小点, 原因在于 Hessian 矩阵 2f (x(1)非正定再令39TP SHUAI10.2 牛顿法考虑 (10.2.2),记搜索方向d(k) = x- x(k) 阻尼牛顿法所用搜索方向是上述方程的解此处假设逆矩阵 存在40TP SHUAI10.2 牛顿法再沿此方向作一维搜索41TP SHUAI10.2 牛顿法算法 修正牛顿法42TP SHUAI10.2 牛顿法43TP SHUAI10.3共轭梯度法1 1 共轭方向与扩张子空间定理共轭方向与扩张子空间定理定义定义10.3.110.3.1 设A是nn对称矩阵,若Rn 中的两个方向d 1 和d2满足 (d 1)T Ad 2 =0 （10.3.1）则称这两个方向关于A共轭,或称它们关于A正交.则称这组方向是A共轭共轭,或称它们为A的的k个共轭方向个共轭方向44TP SHUAI10.3 共轭梯度法几何意义几何意义设有二次函数其中A是nn对称正定矩阵, x是一个定点.是以x为中心的椭球面,A正定,故x是f(x)的极小值点.f(x)的等值面由于45TP SHUAI10.3共轭梯度法设 x(1)是在某等值面上一点,此面在点x(1)处的法向量又设d (1)是在该等值面在点x (1)处的一切向量.d (2) = x - x (1) 即等值面上一点x(1)处的切向量与由这点指向极小点的向量关于A共轭.46TP SHUAI10.3共轭梯度法47TP SHUAI10.3共轭梯度法48TP SHUAI10.3共轭梯度法49TP SHUAI10.3共轭梯度法用归纳法证之,为方便,用g j表示函数f(x)在x(j)处的梯度,即50TP SHUAI10.3共轭梯度法利用上式可以将 gm+2 和d (i) 的内积写成当i=m+1时,由一维搜索定义,知当1im+1时,由归纳假设知由二次函数梯度的表达式和点x(k+1)的定义,有51TP SHUAI10.3共轭梯度法即由10.3.8-11,知52TP SHUAI10.3共轭梯度法上述定理表明,对于二次凸函数,若沿一组共轭方向(非零向量)搜索,经有限步迭代必到达极小点.2 线性共轭梯度法与二次终止性线性共轭梯度法与二次终止性Hesteness和Stiefel于1952年为解线性方程组而提出基本思想:把共轭性与最速下降法相结合,利用已知点处的梯度构造一组共轭方向,并沿着这组方向进行搜索,求出目标函数的极小点53TP SHUAI10.3共轭梯度法先讨论对于二次凸函数的共轭梯度法,考虑问题求解方法54TP SHUAI10.3共轭梯度法55TP SHUAI10.3共轭梯度法56TP SHUAI10.3共轭梯度法 综上分析,在第一个搜索方向取负梯度的前提下,重复使用公式3.14,3.17-3.19就能伴随计算点的增加,构造出一组搜索方向.57TP SHUAI10.3共轭梯度法 定理定理10.3.3 对于正定二次函数(10.3.12),具有精确一维搜索的Fletcher-Reeves法在mn次一维搜索后即终止,并且对所有i(1 i m),下列关系成立:证明: 显然m1,下用归纳法(对i)证之. 58TP SHUAI10.3共轭梯度法设对某个im,这些关系均成立,我们证明对于i+1也成立.先证2),由迭代公式两端左乘A,再加上b,得其中 由式(10.3.17)确定,即59TP SHUAI10.3共轭梯度法考虑到(10.3.20)和(10.3.18),则60TP SHUAI10.3共轭梯度法当ji时,根据归纳假设,式(10.3.22)等号右端各项均为0再证1),运用(10.3.18)和(10.3.20),则当j=i时,把(10.3.19)代入上式第一个等号的右端,立得61TP SHUAI10.3共轭梯度法当ji时,由前面已经证明的结论和归纳假设,式中第2个等号右端显然为0,因此最后证3),易知综上,对i+1,上述三种关系成立62TP SHUAI10.3共轭梯度法注意,初始搜索方向选择最速下降方向十分重要, 如果选择别的方向作为初始方向,其余方向均按FR方法构造,则极小化正定二次函数时,这样构造出来的一组方向并不能保证共轭性.例例 考虑下列问题取初始点和初始搜索方向分别为63TP SHUAI10.3共轭梯度法显然, 不是目标函数在 处的最速下降方向.下面,我们用FR法构造两个搜索方向.令64TP SHUAI10.3共轭梯度法根据公式(10.3.19),有因此65TP SHUAI10.3共轭梯度法令根据公式(10.3.19),有66TP SHUAI10.3共轭梯度法注意注意,在在FR法中法中,初始搜索方向必须取最速下降方向初始搜索方向必须取最速下降方向因此67TP SHUAI10.3共轭梯度法可以证明,对于正定二次函数,运用FR法时不作矩阵运算就能求出因子i定理定理10.3.4 对于正定二次函数,FR法中因子i具有下述表达式证明:68TP SHUAI10.3共轭梯度法69TP SHUAI10.3共轭梯度法FR法(对二次凸函数)70TP SHUAI10.3共轭梯度法例3.2 用FR法求解下列问题71TP SHUAI10.3共轭梯度法令第一次迭代，目标函数f(x)在点x处的梯度72TP SHUAI10.3共轭梯度法第2次迭代目标函数在点x 处的梯度(2)73TP SHUAI10.3共轭梯度法构造搜索方向d .先计算因子(2)1令74TP SHUAI10.3共轭梯度法75TP SHUAI10.3 共轭梯度法一般迭代格式l3用于一般函数的共轭梯度法非线性共轭梯度法76TP SHUAI10.3共轭梯度法-PRP(Polak-Ribiere-Polyar-SW(Sorenson-Wolfe-Daniel -Dixon77TP SHUAI10.3共轭梯度法 FR共轭梯度法78TP SHUAI10.3共轭梯度法3,如果j n,转步4,否则,转5可以证明,对一般函数,共轭梯度法在一定条件下是收敛的,79TP SHUAI10.3共轭梯度法FR算法中使用精确线搜索，我们有如下收敛性结果80TP SHUAI4. 1 拟牛顿条件和算法步骤拟牛顿条件和算法步骤10.4 拟牛顿法基本思想基本思想:牛顿法成功的关键在于利用了Hesse矩阵提供的曲率信息，而计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出，这就导致仅利用目标函数一阶导数的方法,拟牛顿法就是利用目标函数值f和一阶导数g的信息,构造出目标函数的曲率近似，而不需要明显形成Hesse矩阵，同时具有收敛速度快的优点。81TP SHUAI牛顿法的迭代公式为10.4 拟牛顿法82TP SHUAI10.4拟牛顿法83TP SHUAI记10.4 拟牛顿法则84TP SHUAI(10.4.8)称为拟牛顿条件拟牛顿条件(方程方程)，也称为割线方程割线方程.怎样确定满足这个条件的H k+1 ?10.4 拟牛顿法算法 拟牛顿法拟牛顿法85TP SHUAI10.4 拟牛顿法4. 2 对称秩对称秩1 1校正校正86TP SHUAIHk称为校正矩阵校正矩阵.确定Hk的一个方法是令10.4 拟牛顿法(10.4.10)(10.4.11)从而(10.4.12)87TP SHUAI利用(10.4.10),(10.4.12-13),(10.4.9)可写成10.4 拟牛顿法(10.4.13)(10.4.14)-秩秩1 1校正公式校正公式利用秩1校正极小化函数f(x),在第k次迭代中,令搜索方向(10.4.15)88TP SHUAI10.4 拟牛顿法确定后继点(10.4.16)89TP SHUAI4.3 对称秩对称秩2 2校正校正10.4 拟牛顿法定义校正矩阵(10.4.17)DFP(Davidon-Fletcher-Power)公式(10.4.18)则1，DFP算法算法(变尺度法变尺度法)90TP SHUAIDFP算法10.4 拟牛顿法91TP SHUAI10.4拟牛顿法92TP SHUAI例1用DFP方法求解下列问题10.4拟牛顿法初始点及初始矩阵分别为93TP SHUAI第1次迭代10.4拟牛顿法令搜索方向得到94TP SHUAI令10.4拟牛顿法95TP SHUAI第2次迭代10.4拟牛顿法96TP SHUAI10.4拟牛顿法97TP SHUAI令10.4拟牛顿法98TP SHUAI10.4拟牛顿法得到令99TP SHUAI于是得最优解10.4拟牛顿法100TP SHUAI2 DFP算法的正定性及二次终止性算法的正定性及二次终止性10.4拟牛顿法证明:用归纳法 DFP方法中, H1是给定的对称正定矩阵.设Hj是对称正定矩阵,下证Hj+1也是对称正定矩阵.根据定义,对称性是显然的,下证正定性101TP SHUAI(10.4.19)10.4拟牛顿法102TP SHUAI令10.4拟牛顿法则于是(10.4.19)可写为(10.4.21)103TP SHUAI由Schwartz不等式,有10.4拟牛顿法(10.4.22)考虑到一维搜索及方向的定义,(10.4.21)右端第一项的分母104TP SHUAI于是10.4拟牛顿法下证(10.4.22)和(10.4.24)不同时为0.若不然,(10.4.22)为0,则p/q,即p=q(0).从而105TP SHUAI综上,知10.4拟牛顿法定理10.4.2 设用DFP方法求解下列问题其中A为n阶对称正定矩阵.取初点x(1) En ,令H1为n阶对称正定矩阵,则成立:106TP SHUAI证明:对k归纳. k=1时有10.4拟牛顿法(10.4.27)由于代入(10.4.27)即得即(10.4.26)成立.107TP SHUAI当k=2时,10.4拟牛顿法由此结果,易证k=2时(10.4.26)亦成立下设k=m时(10.4.25-26)成立,下证当k=m+1时上述关系式也成立.先证k=m+1时(10.4.25)成立. 由归纳假设,只需证:108TP SHUAI由对(10.4.26)的归纳假设,当1im时有10.4拟牛顿法由此有(10.4.29)根据Th10.3.2的推论,有109TP SHUAI由(10.4.29),知10.4拟牛顿法再证当k=m+1时(10.4.26)成立对于1im+1有(10.4.30)当i=m+1时,由(10.4.28)知110TP SHUAI将其代入(10.4.30)得10.4拟牛顿法当im+1时,根据关于(10.4.26)的归纳假设及当k=m+1时(10.4.25)成立,考虑到(10.4.28),则有从而可得Q.E.D.111TP SHUAI推论:在Th10.4.2的条件下,必有10.4拟牛顿法DFP方法中构造出来的搜索方向是一组A共轭方向DFP方法具有二次终止性.112TP SHUAI3 BFGS公式及 Broyden簇10.4拟牛顿法(10.4.33)可得修正公式-关于矩阵B的BFGS修正公式113TP SHUAI10.4拟牛顿法(10.4.35)114TP SHUAI上述公式由Broyden,Fletcher,Goldfarb,Shanno(1970)给出.10.4拟牛顿法定义-Broyden簇115TP SHUAI显示表达式10.4拟牛顿法(10.4.37)其中(10.4.38)116TP SHUAI10.4拟牛顿法定理10.4.3 设其中A为n阶对称正定矩阵. 则对于Broyden方法,成立:117TP SHUAI线搜索方法：每次迭代时产生一搜索方向，在此方向上进行精确或不精确一维搜索，得到下一迭代点。缺点：可能由于步长过大导致算法失败，特别当问题病态时。Ch10.5 信赖域方法主要数值方法1：118TP SHUAI主要数值方法2：信赖域方法： 在每次迭代时，强制性要求新迭代点与当前迭代点之间的距离不超过某一控制量。实际上是，在以当前迭代点为中心的邻域内对一近似于原问题的简单模型求极值。优点：算法稳定性好、收敛性强。119TP SHUAI主要内容：1 无约束优化信赖域法： 1.1 算法描述 1.2 收敛性2 约束优化（带一个等式约束）： 2.1 逐步二次规划法（SQP） 2.2 Marotos 效应 2.3 信赖域方法120TP SHUAI1 无约束优化信赖域方法问题：基本思想：给定初始迭代点，确定一个以其为中心的邻域，在此域内优化目标函数的二次逼近式，得到下一迭代点。121TP SHUAI信赖域子问题：信赖域内原问题的逼近问题：122TP SHUAI1.1 算法描述Step1 给定初始点Step2 若 ，则停止计算，得解；否则，解子问题得最优解Step3 计算 ，令选取下一信赖域半径使其满足Step4 产生 转step2123TP SHUAI定理： 是信赖域子问题的解当且仅当它是子问题的K-T点，且 是半正定矩阵。124TP SHUAI1.2 收敛性在一定条件下，信赖域方法具有全局收敛性。设 是 上的实函数， 是给定初始点， 是有界闭集， 和 在 上连续，用信赖域方法求得序列 ，则 .125TP SHUAI2 等式约束非线性优化问题(2.1)：其中：126TP SHUAI2.1 逐步二次规划(SQP)SQP方法是求解非线性规划的一般方法，是线搜索方法的一种。基本方法：求解原问题可以转化为求解一系列二次规划子问题。 是原问题K-T点当且仅当：其实就是拉格朗日函数的稳定点127TP SHUAISQP给定当前迭代点 通过下面的等式求迭代步 ，可得到下一个迭代点 . （2.2）其中，128TP SHUAISQP解等式（2.2）相当于求解子问题得到的 作为第k次迭代的搜索方向129TP SHUAI收敛性：在一定条件下，算法产生的点列 的任何聚点都是原问题的K-T点。对原问题若 处的二阶充分条件成立 对子问题若 处的一阶必要条件成立，则 是一超线性收敛步，算法具有超线性收敛性：130TP SHUAI2.2 Marotos效应在无约束情形，超线性收敛步都是可以接受的：如果 是稳定点且二阶充分条件成立，则在算法迭代过程中，对所有充分大的k，都有：约束优化时不成立：尽管 是一超线性收敛步（ 比 远近于 ），但无论从目标函数值或约束违反度来看， 都是一个“坏”点。Marotos效应指出，对于许多罚函数，超线性收敛步不一定能被接受，破坏了算法收敛性。131TP SHUAI例子：等式约束优化极小点为132TP SHUAI克服Marotos效应的方法放松接受试探步的条件引进二阶校正步在算法中用光滑精确罚函数作价值函数133TP SHUAI2.3 信赖域方法问题（3.1）将SQP中子问题与信赖域要求合并得到信赖域子问题： （3.2）134TP SHUAI2.3.1线性化约束不相容(1):将线性化约束的约束函数值项都乘上一个(0,1上的参数： （3.3）相当于将每个约束的可行域往远点方向压缩。参数取值：使（3.2）尽量可行，取值应尽量靠近1，但为使子问题有一定自由度，取值不能过大。135TP SHUAI参数取值构造问题：其最小范数解为Gauss-Newton步当且仅当（3.3）有可行点，为不使参数太小，要求则136TP SHUAI2.3.1线性化约束不相容(2)：用一个平方和约束代替（3.2）中的等式约束条件 （3.4）137TP SHUAI2.3.2 CDT子问题由Celis，Dennis，Tapia(1985)提出 (3.5)只有在 时，(3.5)才相容。138TP SHUAI先考虑若仅有一可行点，则此点有如下形式：其中 ，如果 则 ； 只可能在 时才可能奇异若可行域不只一个点，则 (3.6)139TP SHUAI将（3.5）转化成无约束信赖域子问题由(3.6)必有 其中令 是由 零空间的一组正交基组成的矩阵，通过变换 可将(3.5)化为用前面的无约束信赖域算法求解140TP SHUAI在下面讨论中，均假设定理（必要条件）：设 是（3.5）的解，则必存在Lagrange乘子 和 使得 （3.7）如果乘子是唯一的，则矩阵至多只有一个负特征值。141TP SHUAI定理（充分条件）：设 是子问题的可行点，如果存在 和 使得（3.7）成立， 且 是半正定矩阵，则 是子问题（3.5）的解。推论1：假定 正定，则 是子问题的解，当且仅当存在 和 使得（3.7）成立，此时，解有如下形式： （3.8）142TP SHUAI推论2：设 正定，前面定义的 是子问题的解当且仅当它是可行点，且下列之一成立：143TP SHUAI