哈工大优化算法复习重点

1、1(X； 一 X； ) f(X3- Xt2) f2(Xt2 - X2 ) f32 TX；Xp5. Convergence Judgement: if |x2-xp| ?, then the searchcan be terminated and the minimum point is found. 如果达至咪青度要求， 通过比较中间点和 xp的值大小选取小的那个点作为最优点； 否则的话继续缩小区间；Taylor series of a function with multiple variables is:f(X) ：、f(X：； f(Xk)(X _Xk) 1(X _xk)Ti2f(xk)(

2、x -Xk)2Extremum conditions:* 2*ip. f X ；=oand V. f X positive definite 宀 Minimum* 2*iip, f X Y=0and f X negative definite 宀 Maximumiii) f X =0and、2f X indefinite f Not a Extremum-X3)仇 (X3 - Xj f2(Xt -X2) f6. Shortening the search interval :i) fp f xp夯x2, new IU is x2, x3 xp变为下次计算的中间点iii) fp f xp#x2,

3、 new IU is x1, xp x2变为下次计算的中间点The algorithm of the GSM:1.initial point X0, initial step hand the convergence accurac/are given;2. Determine Initial search interval a,b;3. The interpolation points are generated by GSM, the function values are also computed:X1 = a + 0.382(b-a) fl = f (X1)X2 = a + 0.61

4、8(b-a) f2 = f (X2)4. Compare fl and f2 to determine the new interval:a) if f1f2, then the new search interval is X1, b;5. Convergence judgement: when b-a?is satisfied, the algorithm is terminated and the minimum point is X* = (b+a)/2; otherwise go to continue the search.The algorithm of the CIM:1. C

5、alculate f0=f(x0) and G0= f X0 ;check that G00or f af0 , go to Step 5; otherwise go to Step 4.4. Replace aby 2 a, evaluate new f a G a, back to Step 3.5. Interpolate on the interval 0, a for m using the cubic interpolation formula:Z = G G：. 3 fo- f：.： w = . Z2 -GoG：.Go +Z +wThe algorithm of the FSM:

6、Fibonacci sequence is generated as:Fo=F1=1Fk=Fk4FkQk =2,3,Determine n:Go G 2Z然后计算f(x0+ m)以及G(x0+ m )的值6. Return to Step 5 to repeat the interpolation on smallerinterval0,ORp-m , aFn _ b - a / ；由此来确定n的值其余步骤与GSM相似,其中比例系数的计算如下:if f X m - 0 OR f X0 m ： 0k - Fn _k . Fn x：1k =1,2, ,nThe interpolation poin

7、ts:7. Stop if m is within ?distance to the endpoints or the length of the interval is less than ?._a)X2 =a + 1 Fn kThe algorithm of the QIM:1. Given initial point X0, initial step hand the convergence accuracy?0;2. Determine initial search interval a, b and another point c insidethis interval ；3. Le

8、t x1=a x2=c f2=f(x2)0, and set k=0.2. Calculate the gradient at this point and construct the searche kdirection Sk 一 - f X ;3. Use the 1-D search to find the new iteration point:f Xk ： Sk = min f Xk ： Sk求最小值时直接对 a求导即可得到使f最小的a值，然后令k 1kyk = gk 1 - gk 2= X- X4. Convergence judgment: if f Xk1 -； ,then t

9、he search cank+1be terminated and the optimal solution is X*=X ; otherwise let k=k+1, go to Step 2 continue.7. let k=k+1, return to Step 2.以上为DFP算法，接下来是BFGS算法: 步骤大致与DFP一样，但更新公式不同。The algorithm of the NewtonsMethod:01. Given initial point X and the convergence accuracy ?0, and set k=0;T dkHkgkHk.1 =H

10、k 华 ykSk共轭梯度法CGMH kSkSk H ksk H k skk2. Calculate the gradient, the Hessian and its inverse at point X ;3. Construct Newton s direction:1. Given initial point X and the convergence accuracy?0, and set k=0, & 二-g。jf X0 , Gv 2f X0 ;sk2f Xk rf Xk ;4. Develop the 1-D search along the direction Sk to obt

11、ain the stepkkk：；1kk2.： =argmin f X 亠 S X X 亠：Slength Sk and the next iteration point:3. sk1 _ - 订 xk1 kskk -J1kX =X：x；sk；在基本牛顿法中a=1，而在阻尼牛顿法中,CGM: : ka的取值与SDM算法中的步骤三一致;iGk.iPkPRPk pk Gk 1 pk_ gk 1 (gk 1 - gk)gk25. Convergence judgment: ifk 1-；,then the search canFRk =gk12一厂收敛判断与拟牛顿法一致gk5. Convergenc

12、e judgment: ifIf xkthen the search cank+1be terminated and the optimal solution is X*=X ; otherwise let k=k+1, and return to Step 2 and continue.The algorithm of the Quasi-NewtonsMethod:01. X , H 0 (usually H 0 = I ) and convergence accuracy ?0 are given;2. Set k=0 and compute gk 八 f xk ;3. Choosedk = -H kgk as the search direction.4. Develop 1-D search and determine the optimal step length -： , identify the new iteration poi