哈工大优化算法复习重点

terminatedandtheminimumpointisfound.terminatedandtheminimumpointisfound.如果达到精度要求，通过比较中间点和xp的值大小选取小的那个点作为最优点；否则的话继续缩小区间；Taylorseriesofafunctionwithmultiplevariablesis:f(X)*(Xk)+叼(Xk沙(X-Xk)+2(x-Xk)tV2f(Xk)(x-Xk)Extremumconditions:i)Vf^X*)=0andV2fG*'ositivedefinite—Minimumii)Vf^X*)=0andV2fk*Negativedefinite—Maximumiii)Vf^X*)=0andV2fk*)ndefinite—NotaExtremum

TOC\o"1-5"\h\z1(x2 —x2 )f +(x2 —x2)f +(x2 —x2 )fx= 2 3 1 3 1 2 1 2 Tp2(x—x)f+(x—x)f+(x—x)f2 3 1 3 1 2 1 2 3ConvergenceJudgement:if|x2-xp|<E,thenthesearchcanbeShorteningthesearchinterval：fpfxp<x2,newIUis[x1,x2]xp变为下次计算的中间点；fp<f2,xp>x2,newIUis[x2,x3]xp变为下次计算的中间点；fpfxp<x2,newIUis[xp,x3]x2变为下次计算的中间点;fp>f2,xp>x2,newIUis[x1,xp]x2变为下次计算的中间点.ThealgorithmoftheGSM:1.initialpointX0,initialstephandtheconvergenceaccuracyearegiven；DetermineInitialsearchinterval[a,b];TheinterpolationpointsaregeneratedbyGSM,thefunctionvaluesarealsocomputed:X1=a+0.382(b-a) f1=f(X1)X2=a+0.618(b-a) f2=f(X2)Comparef1andf2todeterminethenewinterval:iff1<f2,thenthenewsearchintervalis[a,X2];iff1>f2,thenthenewsearchintervalis[X1,b];Convergencejudgement:whenb-a<eissatisfied,thealgorithmisterminatedandtheminimumpointisX*=(b+a)/2;otherwisegotocontinuethesearch.ThealgorithmoftheFSM:Fibonaccisequenceisgeneratedas:F=F=1F=F+Fk=2,3,…0 1 kk-1k-2Determinen:Fn，G—a)庇由此来确定n的值其余步骤与GSM相似，其中比例系数的计算如下：'广"L+1 ^T，2,…,^Theinterpolationpoints:X=a+-^~^(b-a)x=a+f1-~Fn-^K-a)1 F-k+1 2IF.k+1JThealgorithmoftheQIM:GiveninitialpointX0,initialstephandtheconvergenceaccuracye>0;Determineinitialsearchinterval[a,b]andanotherpointcinsidethisinterval；Letx1=a<x2=c<x3=bandf1=f(x1)>f2=f(x2)<f3=f(x3);Calculatetheinterpolationpointxpandfp=f(xp):ThealgorithmoftheCIM:1.Calculatef0=f(x0)andG0=andfeanddeterminea(normallyk=2).2.Evaluatefa=f(x0+a)andGa=;checkthatG0<0;八0+a)IfGa>0orfa>f0,gotoStep5;otherwisegotoStep4.Replaceaby2a,evaluatenewfa,Ga,backtoStep3.5.Interpolateontheinterval[0,a]forinterpolationformula:Z=G0+"3(f0-Ewr人G+Z+woT=G0+G^+2Zchoosekusingthecubic然后计算f(x0+Xm)以及G(x0+Xm)的值6.ReturntoStep5torepeattheinterpolationonsmallerinterval[0,气]Or[人机，a]ifff(x+人)>0Orff(x+人)<07.Stopif入miswithinedistancetotheendpointsorthelengthoftheintervalislessthane.ThealgorithmoftheSDM:1.GiveninitialpointX0andtheconvergenceaccuracye>0,andsetk=0.2.CalculatethegradientatthispointandconstructthesearchdirectionSk=-Vf3.Usethe1-Dsearchtofindthenewiterationpoint:f(X，+^Sk)=minf(X，+^Sk)求最小值时直接对a求导即可得到使f最小的a值，然后令Xk+1=Xk+aSk4.Convergencejudgment:ifV/Gk+1)V8,thenthesearchcanbeterminatedandtheoptimalsolutionisX*=Xk+1;otherwiseletk=k+1,gotoStep2continue.ThealgorithmoftheNewton’sMethod:GiveninitialpointX0andtheconvergenceaccuracye>0,andsetk=0;Calculatethegradient,theHessiananditsinverseatpointXk;ConstructNewton’sdirection:

J=g-gS=Xk+1-Xkletk=k+1,returntoStep2.以上为DFP算法，接下来是BFGS算法：步骤大致与DFP一样，但更新公式不同。yjtHsstHd=—H-1gH=H+—k_k——kkk——kkkkk+1k yTS STHSkkkkk共轭梯度法CGM：GiveninitialpointX0apdtheconvergenceaccuracyE>0,andsetk=0,S0=—g0=—VfG0)G0=V2fG0)Developthe1-DsearchalongthedirectionSktoobtainthesteplengthSkandthenextiterationpoint:

2.a=argminf^Xk+aS^Xk+1=Xk+aSk3.Sk+1=-vfGk+1)+pSk.kXk+1=Xk+aS;在基本牛顿法中a=1，而在阻尼牛顿法中，ka的取值与SDM算法中的步骤三一致；5.Convergencejudgment:if||V/Gk+1)V8,thenthesearchcanbeterminatedandtheoptimalsolutionisX*=Xk+1;otherwiseletk=k+1,andreturntoStep2andcontinue.gTGpr_gT(gCGM:6=k+\k+1kPRP:P= —kk pTGp kllgkl2收敛判断与拟牛顿法一致IgklI2ThealgorithmoftheQuasi-Newton’sMethod:1.X0'H01.X0'H0(usuallyH0given;Setk=0andcompute3.Choosedk=-Hkgk

asthesearchdirection.4.Develop1-Dsearchanddeterminetheoptimalsteplengtha,identifythenewiterationpointXk+1=Xk+E然后求得k5.Convergencejudgment:ifa=argminfGk+