最優(yōu)化方法復習

1、第1章最優(yōu)化問題的基本概念1.1最優(yōu)化的概念最優(yōu)化就是依據(jù)最優(yōu)化原理和方法，在滿足相關(guān)要求的前提下，以盡可能高的效率 求得工程問題最優(yōu)解決方案的過程。1.2最優(yōu)化問題的數(shù)學模型最優(yōu)化問題的一般形式find x , x , A , xmin f (x , x , A , x ) TOC o 1-5 h z 12ns.t. g (x , x , A , x ) 0 u = 1,2, A , pu12nh (x , x ,A , x ) = 0 v = 1,2,A , qv12n最優(yōu)化問題的向量表達式find Xmin f (X)一 一s.t. G(X) 0，使得 VX e N(X*,5 ) c D

2、(X。X*)都有 f (X*) f (X)，則稱 X* 為 f (X)的局部 極小點；若f (X*) f (X)，則稱X*為f (X)的嚴格局部極小點。若VX e D，都有f (X*) f (X)，則稱X*為f (X)的全局極小點，若f (X*) f (X)，則稱X*為f (X)的全局嚴格極小點。find X對最優(yōu)化問題min f (X) s.t. G(X) 0而言滿足所有約束條件的向量X = xi,x2,A ,xt稱為上述最優(yōu)化問題的一個可行解，全 體可行解組成的集合稱為可行解集。在可行解集中，滿足：f (X*) = min f (X)的解稱為優(yōu)化問題的最優(yōu)解。凸集和凸函數(shù)凸集：設D u R

3、n，若對所有的X1、X2 e D，及以e 0,1，都有aX 1 + (1 a)X2 g D， 則稱D為凸集。凸函數(shù)：設f : D u Rn r R1，D是凸集，如果對于所有的X1、X2 e D，及a e 0,1，都有 f aX 1 + (1 a) X 2 af (X1) + (1 a) f (X 2)，則稱 f (X)為 D 上的凸函數(shù)。二、局部極小點的判別條件駐點：設f (X)是定義在n維空間Rn的子集D上的n元實值函數(shù)，X*是D的點，若 Nf (X*) = 0，則稱X*為f (X)的駐點。局部極小點的判別：設f (X)是定義在n維空間Rn的子集D上的n元實值函數(shù)，具 有連續(xù)的二階偏導數(shù)。若

4、X*是f (X)的駐點，且V2f (X*)是正定矩陣，則X*是f (X)的 嚴格局部極小點。第3章無約束優(yōu)化方法3.1下降迭代算法及終止準則一、數(shù)值優(yōu)化方法的基本思想基本思想就是在設計空間選定一個初始點Xk，從該點出發(fā)，按照某一方向Sk (該 方向的確定原則是使函數(shù)值下降)前進一定的步長ak，得到一個使目標函數(shù)值有所下 降的新設計點Xk+1，然后以該點為新的初始點，重復上面過程，直至得到滿足精度要求 的最優(yōu)點X*。該思想可用下式表示：Xk+1 = Xk +a kSk二、迭代計算的終止準則工程中常用的迭代終止準則有3種：點距準則相鄰兩次迭代點之間的距離充分小時，迭代終止。數(shù)學表達為：|Xk+1

5、X8函數(shù)下降量準則(值差準則)相鄰兩次迭代點的函數(shù)值之差充分小，迭代終止。數(shù)學表達為：|f(Xk+1) f(Xk)|8梯度準則目標函數(shù)在迭代點處的梯度模充分小時，迭代終止。數(shù)學表達為：|W(Xz)| 0及L、k0，使當k k0時下式：忡+1 - X*| k 0時下式：|Xk+1 - X 0都存在k0 0，使當k k0時下式：Xk+1 - x f (x2)，說明極小點在x2右側(cè)，應加大步長向前搜索。轉(zhuǎn)；若f (x ) f (x )，說明極小點在x左側(cè)，應以x點為基準反向小步搜索。轉(zhuǎn)； 1211大步向前搜索：令h u 2h，取x3 = x2 + h，計算f (x3)； TOC o 1-5 h z

6、若 f (x ) f (x3)，說明極小點在x3右側(cè)，應加大步長向前搜索。此時要注意做變換：舍棄原x點，以原x點為新的x點，原x點為新的x點。轉(zhuǎn)，直至出現(xiàn)“高一 12132一低一一高”排列，則單峰區(qū)間可得；反向小步搜索(要注意做變換)：為了保證x3點計算公式的一致性，做變換：將原x點記為新x點，原x點記為新x點，令h u - h，取x = x + h，轉(zhuǎn)2112432例：用進退法確定函數(shù)f (x) = x2 -6x + 9的單峰區(qū)間a，b，設初始點x0 = 0 ，h = 1。解：。x0 = 0 h = 1. x = x = 0 x = x + h = 1 f (x ) = 9 f (x ) =

7、 4102112。f (氣) f (x2)說明極小點在x點右側(cè)，應加大步長向前搜索2則 f (x= 0令 h u 2h = 2 x 1 = 2 ，取 x3 = x2 + h = 1 + 2 = 3。f ( x 2) f ( x3)說明極小點在x點右側(cè)，應加大步長向前搜索3f (x 2)= 0舍棄原x1 = 0的點，令x1 = 1x 2 = 3，則f (x1) = 4令 h u 2h = 2 x 2 = 4 ，取 x3 = x2 + h = 3 + 4 = 7 貝 U f (x3) = 16 f (x2) = 0f (氣)、f (x2)、f (x3)呈“高一一低一一高”排列.x1，x3為單峰區(qū)間

8、，即區(qū)間1，7即為所求二、黃金分割法黃金分割法是基于區(qū)間消去思想的一維搜索方法，其搜索過程必須遵循以下的原 則：對稱取點的原則：即所插入的兩點在區(qū)間位置對稱；插入點繼承的原則：即插入的兩點中有一個是上次縮減區(qū)間時的插入點；等比收縮的原則：即每一次區(qū)間消去后，單峰區(qū)間的收縮率人保持不變。設初始區(qū)間為a , b，則插入點的計算公式為：x = a + 0.382(b - a)x = a + 0.618(b - a)黃金分割法的計算步驟如下：給定初始區(qū)間a，b和收斂精度e ；給出中間插值點并計算其函數(shù)值：x = a + 0.382(b - a)f (x )x = a + 0.618(b a)f (x

9、)；比較f(氣)、f(x2)，確定保留區(qū)間得到新的單峰區(qū)間a，b；收斂性判別：計算區(qū)間a，b長度并與比較，若b - a ，輸出x * = (a + b)2否則轉(zhuǎn)；在保留區(qū)間繼承一點、插入一點，轉(zhuǎn)。-3 x f (x1).舍棄(1.944，5，保留-3, 1.944 1.944-(-3) 繼承原 x1 點，即 x2 = 0.056f (x2) = 0.115插入氣=a + 0.382(b - a) =-3 + 0.382 x (1.944 + 3) = -1.111f (氣)=-0.987/ f (x 2) f (氣).舍棄(0.056，1.944，保留-3,0.0560.056 - (-3)

10、；繼承原 x1 點，即x2 =-1.111f (x2) = -0.987插入氣=a + 0.382(b - a) =-3 + 0.382 x (0.056 + 3) = -1.832f (氣)=-0.306/ f (x2) ；繼承原 x 2 點，即氣=-1.111f (x1) = -0.987插入 x =-1.832 + 0.618 x (0.056 +1.832) = -0.665f (x ) = -0.88822/ f (X2) f (氣).保留-1.832，-0.665如此迭代，到第 8 次，保留區(qū)為-1.111,-0.940 -0.940-(-1.111) = 0.171 8x* =

11、1 x (-1.111 + 0.940) = -1.0255f (x*) = -0.99923.3梯度法一、基本思想對于迭代式Xk+1 = Xk +以kSk，當取搜索方向Sk =-Vf (Xk)時構(gòu)成的尋優(yōu)算法，稱 為求解無約束優(yōu)化問題的梯度法。二、迭代步驟給定出發(fā)點Xk和收斂精度8 ；計算Xk點的梯度NF(Xk)，并構(gòu)造搜索方向Sk =-VF(Xk)；令Xk+1 = Xk +以kSk，通過一維搜索確定步長a k，即：min F(X k +a kSk)求得新點Xk+1收斂判斷：若|VF(Xk+1)| e成立，輸出X* = Xk+1、F(X*) = F(Xk+1)，尋優(yōu)結(jié) 束；否則令ku k +

12、1轉(zhuǎn)繼續(xù)迭代，直到滿足收斂精度要求。三、梯度法的特點梯度法尋優(yōu)效率受目標函數(shù)性態(tài)影響較大。若目標函數(shù)等值線為圓，則一輪搜索就 可找到極致點；若當目標函數(shù)等值線為扁橢圓時，收斂速度則顯著下降。梯度法中相鄰兩輪搜索方向相互垂直。3.4牛頓法牛頓法分為基本牛頓法和阻尼牛頓法兩種。對于迭代式Xk+1 = Xk +akSk，當取a k三1且搜索方向Sk =-V2f (Xk)-1 Vf (Xk)時 構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的基本牛頓法；對于迭代式 Xk+1 = Xk +a kSk，取搜索方向 Sk =-V 2 f (Xk)-1 Vf (Xk)，a k 為從 Xk 出發(fā)、沿牛頓方向做一維搜索獲

13、得的最優(yōu)步長，所構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu) 化問題的阻尼牛頓法。搜索方向Sk = -V2 f (Xk)-1 Vf (Xk)稱為牛頓方向。這里需要注意的是會求海塞陣的逆矩陣。3.5變尺度法我們把具有Xe = Xk a kAk Nf (Xk)迭代模式的尋優(yōu)算法稱為變尺度法。其搜索方向表達式為：Sk = AkNf (Xk)，稱為擬牛頓方向，其中Ak稱為變尺度矩 陣。在迭代開始的時候，A 0 = I ；隨著迭代過程的繼續(xù)，Ak -N 2 f (Xk)i Nf (Xk)。因此，變尺度法從梯度法出發(fā)，隨著迭代過程的繼續(xù)最終趨向于牛頓法。3.6共軛梯度法一、共軛方向的概念設H為對稱正定矩陣，若有兩個n

14、維向量S1和S 2，滿足St H - S2 = 0，則稱向量S1 與S2關(guān)于矩陣H共軛，共軛向量的方向稱為共軛方向。若有一組非零向量S，S ，S滿足St H -S = 0(i。j)，則稱這組向量關(guān)于12nij矩陣H共軛。對于n元正定二次函數(shù)，依次沿著一組共軛方向進行一維搜索，最多n次即可得到 極值點。二、共軛方向的形成對于函數(shù) f (X) = f (孔，x2,A ,x ) = 2XtHX + BtX + C沿任意方向S0在設計空間上任意做兩條平行線，分別與目標函數(shù)等值線切于點Xi、X2，令S1 = X2 X1，則S0、S1關(guān)于矩陣H共軛。三、共軛梯度法對于迭代式 X k +1 = X k +a

15、 kS k，取搜索方向 S k+1 = Nf (X k +1) + & S kkNf (Xk+1)|2其中：S0 = Nf(X0)，& = k|W( Xk )|2共軛梯度法相鄰兩輪搜索方向是一對共軛方向。3.7鮑威爾法基本迭代公式仍舊是：Xk+1 = Xk +a kSk基本鮑威爾法每輪搜索分為兩步：一環(huán)的搜索+在該環(huán)搜索完畢后生成的新方向上 的一維搜索。對于基本鮑威爾法，相鄰兩輪搜索生成的搜索方向是共軛的。修正鮑威爾法與基本鮑威爾法類似，所不同的是每環(huán)搜索后生成的新方向要利用鮑威爾條件判別其可用性。注意掌握鮑威爾條件的表達式和應用！每環(huán)搜索方向組的生成：第一環(huán)的搜索方向組就是各坐標軸方向2下一

16、環(huán)的搜索方向組由本環(huán)搜索方向組和本環(huán)生成的新方向共同確定，方法是： 若本環(huán)的搜索結(jié)果滿足鮑威爾條件，則將本環(huán)搜索方向組中使目標函數(shù)下降量最大的方 向去掉，并將本環(huán)生成的新方向遞補進去，就形成下一環(huán)的搜索方向組；若本環(huán)的搜索 結(jié)果不滿足鮑威爾條件，則下一環(huán)的搜索方向組仍舊沿用本環(huán)搜索方向組不變。下一環(huán)搜索起點的確定：下一環(huán)搜索起點由本環(huán)搜索結(jié)果確定，方法是：若本環(huán)的搜索結(jié)果滿足鮑威爾條件， 則以本環(huán)搜索終點為起點，沿新生成的方向作一維搜索，得到的新點作為本輪的搜索終 點，也是下一輪的搜索起點；若本環(huán)的搜索結(jié)果不滿足鮑威爾條件，則取本環(huán)搜索終點 和反射點中目標函數(shù)值小的點作為本輪的搜索終點，也是下

17、一輪的搜索起點。這里需要注意的是反射點的計算：X,= 2 Xk - X k式中：Xk是本環(huán)起點Xk相對于本環(huán)終點Xk沿新生成方向的反射點。n+20n例：對于無約束目標函數(shù) min f (X) = xi + 2x2 -4氣-2x1 x2，利用修正 Powell法從11. 一 一X 0 = 1出發(fā)求最優(yōu)解。1解：令 X 0 = X0 = 1P1 = P 0 =(匕，e)11 + aX1 = X1 +a=1001令 f(X 1) = 0得:a =03 -X1 = X1 +a=2111 + a則：2令 f(X 1) = 0 得：a = 0.5貝J： X1 =221.5該環(huán)生成的新搜索方向為：S1 =

18、X123121.5-1=0.5-X10對S1進行有效性判別：/1 = f (X 0) = -3f2=f (X2)= -7.5f3 = f (x 4)= -7A1 = f (X 0) 一 f (X1) = -3 - (-7) = 4=f (X11)一 f (X 2)= -7 -(-7.5) = 0.53151.5一1=20反射點 X1 = 2 X1 - X1 = 242故最大下降量A = A1 = 4故：f f 和(f - 2 f + f )(f - f3112312-)2 2A(f1 - f3)2 均成立方向S1可用以X1為起點，沿S1方向作一維搜索： 232+a=1.50.53 + 2a1.

19、5 + 0.5aX1 = X1 + aS 1 =32由 min f (X1) = f (X2 +aS1)得a = 2/5 = 0.4故,本輪尋優(yōu)的終點為：X1 = X 3 =3.8一1.7做收斂性判別：X1 -X。| =1：2.82 + 0.72，應繼續(xù)搜索下一輪尋優(yōu)過程的起點為：X j =3.8一1.7下一輪尋優(yōu)過程的搜索方向組為：(。2,S 1)約束優(yōu)化方法約束優(yōu)化方法要求大家重點掌握懲罰函數(shù)法，包括點法、外點法、混合法。一、外點法構(gòu)造懲罰函數(shù)：min4 (X, rk) = f (X) + rk ma沖 g (X),0)2 + rkh (X)2 uv外點法既可以處理不等式約勺束優(yōu)化問題，又可以芟理等式約束優(yōu)化問題。需要注意的是：懲罰因子rk隨迭代次數(shù)的增加是遞增的，當rk 8時得到的解就是原問題的最優(yōu)解。例：用外點法求解min f (X) = x 2 + x 2 - 2 x +1 s.t. 3 - X 0時 當3-X2 0時人合4令 Q= 2 氣-2 = 01例 = 2X2 + 2rk (x2 - 3) = 01得：氣=13rkV 1 + rkx * = lim x = 3