第二章无约束优化问题的算法

《第二章无约束优化问题的算法》由会员分享，可在线阅读，更多相关《第二章无约束优化问题的算法（19页珍藏版）》请在装配图网上搜索。

1、授课章节第二章无约束优化问题的算法目的要求常用的线性搜索法；无约束最优化方法重点难点常用的线性搜索法；无约束最优化方法第一节常用线性搜索法在算法的迭代格式x(k1)=x(k)；kd(k)中，在假设迭代点x(k)和下降搜索方向d(k)为已知的情况下，求步长：“，使f(x(j)=f(x(k)：)：f(x(k)成立。下面介绍几种求步长:-k的算法。一、直接法(0.618法)(求步长)单谷函数(下单峰函数)：设t*为一元函数;：(t)的极小点，若ti：讥2，当t2:t时，必有仇)址2)；当1_t*时，必有魚)八色)，则称：(t)为单谷函数(-个谷)。1搜索区间的确定：搜索区间的选取采取如下算法一进-退

2、算法：给定初始点t，初始步长h。(1) 计算(t),：(t-h)；若，(t)：(th)，搜索成功，歩长加倍，若;：(th;:(t-3h)，则a,b二a,t3h，否则步长继续加倍;若申(t)v(t+h),搜索失败，后退一步长，若(t)v(t),则44=ha,b二t-一，th，否则继续加倍后退步长。420.618算法的原理规定In1=讥_212=1-a=b_t2=b-a_lIq_li=l-IoIo解得-0.618。由此可得1=a(1_%)(b_a)t2二a(ba)30.618算法Stepi确定(t)的初始搜索区间a,b(进-退搜索法)、精度；Step2计算ti=a(1)(ba),1V(tJ；Ste

3、p3计算t2=a，(b-a),笃二即住);*a+hStep4若半1徨，则令a=1,如果ba|名，取t=，停止计算。否2则令ti2,1二2，转Step3,(此时a二G鮎=t2，在新的a,b区间计算t?);皿皿*a+bStep5若1兰笃，则令b=t2，如果baR，且f(x)xTAxbTxc2其中A为正定矩阵。下面讨论从任意初值点x(0)出发，最多经过两步迭代可达到其极小点(最优解x(*)。思路：选取与d(0)-、f(x(0)线性无关的向量d，且保证f(x(*)Td(0)=0和Vf(x(*)Td=0(这里x(*)=x(2)=x+id)，推出Vf(x(*)=0。分析：任意初值点x(0)，令下降方向为d

4、(0)=(x*)，迭代公式x=xg0d(0)，有线性搜索法确定：0，且满足Co)八f(x)Td(0)=0。假若x(*)=x(2)=x(1)+ctid(1)(最优解x(*)，则必有f(x(*)=Ax(*)b=0=A(x：id)b=0=Axb：Ad(1)=0=f(x)：嗣(1)=0左乘d(0)T=d(0)f(x(1)r:-1d(0)TAd(10这里要求d(0)TAd(1)=0o年月曰课程名称优化理论与方法编写时间：20由于If(x)Td(0)=O，得if(x)与d(0)是线性无关的，所以向量d可由f(x)和d(0)线性表示(因为是二维空间)，设d八f(x厂td(0)左乘d(0)TA得d(0)TAd

5、=d(0)TAf(x)td(0)TAd(0)=0由于A是正定矩阵，所以d(0)TAd(0)0,即得+d(0)TAf(x(1)td(0)TAd(0)则d(1)=f(xe)-dd；AAdx：)d。dAd可以证明d(1),d(0)是线性无关的，因为如果线性相关，d可由d(0)线性表示，dd(0)(，O)，f(x)十7；們(：0：)2(0)，得if(x)和d(0)d(0)TAd(0)线性相关，矛盾。由线性搜索法得，且满足f(x(*)Td=0，由于d(0)Tf(x)Jd(0)TAd=0d，可得if(x(*)Td(0)=0，即f(x(*)T(d(0),d(1)0故f(x(*)=0，即x(*)是最优解。以下

6、讨论的是n个变量的二次型问题的最优化的问题二、共轭方向的概念与性质1概念：共轭向量组：(1) A为nn阶正定矩阵；(2) p1,p2/,pm为Rn中m个非零向量。若pApj=0(j=j,i,j=1,2,m),则称口，P2,Pm为A共轭向量组(或为A年月曰课程名称优化理论与方法编写时间：20正交向量组)。注：当A=l时，共轭性即为通常的正交性。2性质：定理2.2设A为A为nn阶正定矩阵，p1,p2，pm为Rn中m个非零向量，且关于A两两共轭向量组，则p,p2,，pm线性无关。证明：设存在一组数&、二2，覚m，使得lPl*2P2血叱mPm成立，用p：A(j=1,2,m)左乘，得:jpTApj=0(

7、j=1,2,m)，由于A是正定的，Pj=0，即P；APj-0，所以:-j=0,故P2,Pm线性无关。引理2.1(n维直交定理)设P!,P2/,Pm为线性无关的n维向量，若Rn,且xTpj=0(j=1,2,m)，则X=0。A定理2.3设f(X)二xTAxbTXc,P!,P2,，Pm为任意一组关于A两两共2轭向量组，则从任意初始点X出发，依次沿Pi,p2,，Pm执行线性搜索，到达X(m)至多n步迭代得到极小最优解x*。证明思路：(1) 设迭代公式设为x(k1)=x(k)心；pk(m_n,k二1,2,)；(2) 证明X(xn1)=0。x(k1x(k：pk=x(k书.:kPkj：kPk(j)*二X*j

8、Pj*j1Pj.Pk4*kPkWx(k1)=Ax(k1)b=AxbApj:j1Apj：人卩2Apk课程名称优化理论与方法编写时间：20年月曰八f(Xj)：jApj:jiApj.j八：kApkT(k1)、PjR(X)=PjjLf(Xj)+GjPjApj+ctj卑PjApj卑+akPjApk+GkPj_iApkPj穴f(x()=pjJ-f(Xj)、卫jpj/Apjj1pjdApj1-nJ.pjJApnJ-npjJApn=0这里2乞j乞n。PT，f(Xj)=0是由于在搜索步长时满足C)八f(x(k)Ipk)TPk=0，即(；)八f(x(k1)TPk=0；*t:nPjlAPk=0(jkn)是由于Pi,

9、P2,，Pm为关于A两两共轭的向量组。由于P0f(xn1)=0,所以pE彳仪小)=0(k=1,2,，n),由定理2.2得Pl,P2/,Pm线性无关，再由引理2.1可得、f(Xni)=0，所以(n1)(n)：nPn是最优解。三、产生共轭方向的方法利用点x(k)的梯度来构造共轭方向。思路：给出d八f(x(1)=0，及迭代公式d(k1)=-f(x(k1)kd(k)(由minf(x(k)d(k)=f(x(k)gkd(k)、；一k=(k)、f(x(k)d(k)Td(k)=0=f(x(k1)Td(k)=0)由要求d，d，d(k)(1乞k乞n)关于A两两共轭=d(kd)Ad(k0得出共轭向量由迭代公式d(k

10、o=、f(x(k1)rd(k)求出.(1).(2)(k)d,d,d用Ad(k)右乘d(k1)-”f(x(j1)kd(k)的转置，得d(k1)TAd(k)=-f(x(k1)TAd(k)kd(k)TAd(k)=0由A的正定性，得d(k)TAd(k)=0，所以vf(x(k1)TAd(k)d(k)TAd(k),(k=1,2,n-1)四、共轭梯度法算法用不同的方法构造出不同的A共轭向量组，得到不同的算法，这些算法都是利用点x(k)的梯度来构造共轭方向，因而称这种算法为共轭梯度法算法(简称共轭梯度算法)。(1)对于正定二次函数的共轭梯度法若令gk=pf(x(k)，由上述分析可得正定二次函数的共轭梯度算法公

11、式为dgi(k1)(k)一.(k)xx-kd(k1)(k)dgk1kd其中:kIf(x(k1)TAd(k)d(k)TAd(k),(k=1,2,n-1).终止条件gk八f(x(k)=o.3212例用共轭梯度算法求解minf(x)X1X2-X1X2-2x1,取初始点为x(1)珂-2,4)丁.对于非正定二次函数的共轭梯度法略。第四节Newton法及其改进一、Newton法基本原理Newton法是以二次近似作为基础而提出的非二次函数的优化算法。设f(x)是二阶连续可微函数，x是f(x)无约束极小解，在初值点x(0)进行Taylor二阶展开，求出展开的二次函数极小点x，在x进行二阶Taylor展开，求出

12、展开的二次函数极小点x(2)，得出一系列极小点*(k)f去逼近f(x)的极小解x*。年月曰课程名称优化理论与方法编写时间：20设f(x)在x(k)处的二阶Taylor展开，得近似二次函数，即f(x)Qk(x)(k)、T(k)(k)T(k)二f(x)gjx-x)(x-x)Gk(x-x)2其中gk、f(x(k)，Gk八2f(x(k)，若令iQk(x)=0，则Gk(x-x(k)=-gk，若Gk正定(对称)，则有x=x(k)-Ggk由极值必要条件知，Qk(x(k)=0，即x(j=x(k)-Gkgk。称x1)=x-GkgkNewton迭代公式，Gkd-gk的解d-G1gk为Newton方向。当初始点x(

13、0)与最优解X*很近且Gk正定时迭代公式x(k1)=x(k)-Ggk以二次收敛速度收敛于最优解x*，但很难检验是否接近，所以很难保证方向d(k)二-Ggk是下降方向。二、改进Newton法算法1对Gk强迫正定分解设A是对称正定矩阵，则可唯一分解为A=LDLt其中D是对角矩阵，对角线元素I,2,n恰是A的特征根，矩阵L是单位下三角矩阵。在实际计算中，由于误差积累，可能出现计算结果0，为此Gill-Murray提出了一种强迫正定分解法，即对一般对称矩阵A，存在单位下三角矩阵L和正定对角矩阵D，使得A=LDLT=A-E,其中E是对角矩阵。当对角矩阵A充分正定时，A=A。所谓充分正定是指A的特征根，的

14、绝对值足够大，避免出现由于误差积累k0。(强迫正定分解法我们不讲，计算公式参看教材P58)2改进Newton法算法年月曰课程名称优化理论与方法编写时间：20设gk、f(x(k),Gk八2f(x(k),f(x)：Q(x)(k)、T(k)(k)T(k)二f(x)gjx-x)(x-x)Gk(x-x)2对Gk进行强迫正定分解，得LkDkL：-GkEk,LkDkLk:Gk，令下降方向为LkDkL：d=-gk的解，得d(k-(Lk1)TDLk1gk，得到迭代公式为x(k1)=x(k:-kd(k)(这里称:k为阻尼因子，即步长)，由线性搜索法得到步长:k。当f(X(k1)_f(x(k)时，终止迭代。3负曲率

15、方向算法负曲率方向：若f(x)在x(k)处的梯度gk=f(X(k)=0，而Hesse矩阵Gk八2f(x(k)至少有一个负根，即存在一个向量(方向)满足dT2f(x(k)d:0，称方向d为负曲率方向。设f(x)在x(k)处的梯度gk-；f(x(k)=0，Hesse矩阵即不正定也不负定(鞍点)，由二阶Taylor展开(x=x(k)+od(k)f(x)二f(x(k)2(x-x(k)TGk(x-x(k)o(X-X(k)设Gk的负曲率方向d(k)=0，满足(d(k)TGk(d(k)：0，且当:-足够小时有f(x)：f(x(k)。由此可见：(1)对于负曲率方向d，满足if(x(k)Td=0,d与-d都是下

16、降方向(如图)；教案课程名称优化理论与方法编写时间：20(2) 对于方向d，满足f(x(k)Td:0，则d是下降方向；(3) 对于方向d，满足f(x(k)Td.0,则-d是下降方向.三、Newton法的主要特征(1) Newton法应用于具有正定Hesse矩阵的二次函数时，只需一次迭代即可达到无约束优化问题的全局极小解，计算法具有二次收敛；当初始点接近极小解时，Newton法产生的迭代序列(k)以二阶收敛的速度趋于问题的平稳点，但当初始点远离极小解时，Hesse矩阵可能是奇异的，Newton方向不存在，或者Hesse矩阵不正定，d(k)不是下降方向，此时需要使用改进的Newton法，其收敛速度

17、大大降低。(2) Newton法对于目标函数要求高(二阶连续可微)，且需较多的存储单元，每次迭代均要进行矩阵求逆的运算。当Hesse矩阵不定时，可采取强迫矩阵正定分解策略，利用负曲率方向作为搜索方向。由此可见，改进Newton法保留了Newton法的一些优点，也克服了Newton法及其阻尼Newton法的一些不足，因此改进Newton法数值稳定，具有较快的收敛速度。第五节拟Newton法(变尺度法)(简述)拟Newton法的优势是吸收了Newton法的收敛速度快的特点，仅仅利用目标函数以及一阶可导的信息，由近似Newton方向建立迭代公式，该方法被认为是无约束优化问题(中小规模)问题中最有效的

18、算法。一、拟Newton法的迭代格式迭代格式：Stepl:输入初始点xRn，初始对称正定矩阵H,；Step2:确立搜索方向d(k)二-Hkgk；Step3：线性搜索步长:k，满足f(x(k)*kd(k)二minf(x(k)*d(k)；0Step：修正Hk1=Hk：=Hk；Step：迭代公式x(kx(k)d(k)注：拟Newton法是一族算法，每一种构造.：Hk的算法都是一种特殊的拟Newton法。二、构造Hk1的原则1拟Newton条件令gk、f(x(k),Gki八2f(x(k1)，且x(k1)-x(k)有中值定理有yk二gki_gk=g(x(k)：kd(k)_g(x(k)二G(x(k)rd(

19、k)、；k得k心(x(k)*(忸心必令-k二HkVk，则Hki、Gk；(由于Gki是对称的，所以要求Hz也是对称的,同理.Hk也是对称的)。方程飞=Hk-yk称为拟Newton方程或拟Newton条件。注：用该方法求出G1的近似解H-1较少运算过程中的储存，而保留了Newton法的收敛速度快的优点。三、构造Hki的具体过程(1)DFP变尺度算法迭代公式由二Hkk及Hk1二Hk=Hk可得r=(Hk*Hk)yk，即HkYk二、k-Hkyk令Hk=：uuT：vvT，其中u,vRn,：,：R,得:u(uTyQ：v(vTyQ二-Hkyk由于(uTyk)R,(vTyk)R，是数值，则:(uTyQu：(vT

20、yk)v二-Hkyk所以令u=6与v=HkykuTyk=1lBvTyk=-1则教案课程名称优化理论与方法编写时间：2011-11a=一=uyk、kykvykykHkyk得kkHkykykHkHk1:迭代校正矩阵公式为Hk1=Hk(2)BFGS变尺度算法迭代公式1若令Bk1=Hk1，完全类似可以推出ykJ（实际上就是Bk1=BkHk1二HkyT；-kykHkykHkykyM+yJkyk-HkykTykyk:Tyk-HkTZkyk-k中k与yk互换一下位置），从而拟ykHkykNewton方程十=Hk1yk变为yk二Bkrk，由该方程计算出Bk1，再导出Hk彳得Hk1kkk-Hkykk-kykHk

21、二Hk6其中；Tyk或写成Hk1Hk1=(|一-kyT-ky-Yk)Hk(I：k)上公式BFGS法和DFP法的迭代公式是相同的，由T腭k)Hk(Ikyk)、；k和Hk1心kykTyJHkykykHkHkTTykykHkyk应该产生相同的序列，但由于我们进行的都是线性搜索近似计算得出的结果，所以实际上是不同的，经验显示BFGS法明显优于DFP法，这也是我们经常遇到的现象,看是完全相同的计算法，只是计算顺序或计算公式稍加改变，得到的算法（结果）却不同。2通常设H1=I,令d-Ig-g1，线性搜索得到步长：1，得x二x，得yg?-g1和r=x一x，求的H2,作调整，令yiO-1HiH2作为新的初始值

22、，使H2满足条件=H1y1，得-T11，y1出Hiy1H1例1考虑无约束优化问题minf(x)=3x2取初始点x(1)=(o,o)T，精度；-10，试用拟Newton法(BFGS法和DFP法)求该解问题。解：梯度g(x)=(3x1X2-2,X2-xJT采取精确线性搜索，由f(x(k)r(k)mf(x(k)得步长公式为这里x(k)(2一3妒卅同“(x1k)x2k)d2(k)d1k)-d2k)22d1k)f(k)、.(k)、X1dCd1(k),赋值H1=H1(让初值H1更接近G)，由DFP法的迭代公式Hk1=H+kk_HkykykHkykyk-hkykH2二H1Jy-111丄“3010丄1010H

23、1y1y1TH1y；H1y12121x?-3xx2-2x2教案课程名称优化理论与方法编写时间：2011d=-H2g2=(一,)丁，：2=5,155(3)(2).(2)xX比2d(1,1),g3八f(x)T=(o,o)T由于|g/-,至此已满足终止准则，终止计算，得到问题的最优解为X(3)二X*=(1,1)T。2BFGS法(10)取初始对称正定矩阵为H1=01丿计算得g1=(2,0)t,显而易见|g第一次迭代计算搜索方向d二-H21=(2,0)t,从x出发沿d(1)进行线性搜索，得步长%，从而有x3=x(1).(1)/2c、T-：d(,0)。3计算得g2八f(X)T2=(0,-3)丁,显而易见|

24、g2第二次迭代求H2。=x(2)-x(1)(2T(1)=(3,0)，y=g27=(2,-：)t(1yT-11，修正矩阵H13yT-1y1H1H113，赋值H1=H1,由BFGS法的迭代公式Hk十=(I-)Hk(I厂八得-kyk-JykH21031010丿d(2)=_H2g2AA=(15,15)T，：5，教案课程名称优化理论与方法编写时间：20年月曰X(3)=x(2)乜2d(2)=(1,1)T,g3=Vf(x)T=(0,0)T由于的3|=农,至此已满足终止准则，终止计算，得到问题的最优解为(3)*/aaTX=X=(1,1)。四、拟Newton法的主要性质1矩阵列Hk的对称正定性；2搜索方向的共轭性；3具有二次终止性；4超线性收敛性；5线性变换下的不变形。授课章节目的要求重点难点沈阳大学教案课程名称优化理论与方法编写时间：20年月曰