




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、第1章最優(yōu)化冋題的基本概念.1最優(yōu)化的概念最優(yōu)化就是依據(jù)最優(yōu)化原理和方法,在滿足相關(guān)要求的前提下,以盡可能高的效率 求得工程問題最優(yōu)解決方案的過程。1.2最優(yōu)化問題的數(shù)學(xué)模型1. 最優(yōu)化問題的一般形式f i n dx1,X2,Xnm i nf (X1,X2,Xn)s.t. gu(X1,X2,,Xn) 0 u =1,2,p hv(X1,X2,,Xn) =0 v=1,2,q2. 最優(yōu)化問題的向量表達式? i n d Xm i nf(X)s.t. G(X) 0,使得 YX 己 N(X*P)c D(X HX*)都有 f(X*) f(X),則稱 X* 為 f (X)的局部 極小點;若f(X*)f(X),
2、則稱X*為f(X)的嚴格局部極小點。, , * * *若VX D,都有f(X ) f(X),則稱X為f(X)的全局極小點,若f (X ) f (X), 則稱X*為f(X)的全局嚴格極小點。find X對最優(yōu)化問題n f (X)而言st. G(X) 0H(X)=0滿足所有約束條件的向量X =Xi,X2,XnT稱為上述最優(yōu)化問題的一個可行解,全 體可行解組成的集合稱為可行解集。在可行解集中,滿足:f(X*) =mi nf(X)的解稱為優(yōu)化問題的最優(yōu)解。2.凸集和凸函數(shù)凸集:設(shè)D匸Rn,若對所有的X1、X2迂D,及a C 0,1,都有aX1 +(1a)X2壬D,則稱D為凸集。凸函數(shù):設(shè)f : D U
3、 RnT R1,D是凸集,如果對于所有的X1、X2壬D,及a 0,1,都有 fktX(a)X2Uaf(X1H(a)f(X2),則稱 f(X)為 D 上的凸函數(shù)。、局部極小點的判別條件駐點:設(shè)f(X)是定義在n維空間Rn的子集D上的n元實值函數(shù),X是D的內(nèi)點, 若7 f(X*) =0,則稱X*為f(X)的駐點。局部極小點的判別:設(shè)f(X)是定義在n維空間Rn的子集D上的n元實值函數(shù),具 有連續(xù)的二階偏導(dǎo)數(shù)。若X*是f (X)的駐點,且V2f(X*)是正定矩陣,則X*是f(X)的 嚴格局部極小點。三、全局極小點的判別1.凸規(guī)劃對于優(yōu)化問題:盯叢爲.1.-,p若f(X)、gi(X)都是凸函數(shù),貝U稱
4、該優(yōu)化問題為凸規(guī)劃。2.全局極小點的判別若優(yōu)化問題為凸規(guī)劃,貝U該優(yōu)化問題的可行集為凸集,其任何局部最優(yōu)解都是全局 最優(yōu)解。(能否證明)第3章無約束優(yōu)化方法3.1下降迭代算法及終止準則一、數(shù)值優(yōu)化方法的基本思想方向的確定原則是使函數(shù)值下降)前進一定的步長 降的新設(shè)計點Xk半,然后以該點為新的初始點, 的最優(yōu)點X* 0基本思想就是在設(shè)計空間內(nèi)選定一個初始點Xk,從該點出發(fā),按照某一方向S(該 a k,得到一個使目標函數(shù)值有所下 重復(fù)上面過程,直至得到滿足精度要求該思想可用下式表示:Xk=Xk+akSk、迭代計算的終止準則工程中常用的迭代終止準則有3種:點距準則相鄰兩次迭代點之間的距離充分小時,迭
5、代終止。 數(shù)學(xué)表達為:Xk*-Xk|8函數(shù)下降量準則(值差準則)相鄰兩次迭代點的函數(shù)值之差充分小,迭代終止。 數(shù)學(xué)表達為:f(x5)- f (Xk) 梯度準則目標函數(shù)在迭代點處的梯度模充分小時,迭代終止。 數(shù)學(xué)表達為:Vf(Xk*) 0及L、ko,使當k k。時下式:|xk X*| ko時下式:|xk+-X*|kLTk成立,則稱&k 為線性收斂。3.超線性收斂設(shè)序列k 收斂于解X*,若任給P 0都存在ko 0,使當k ko時下式:|xM-x*卜 P|xk x*|成立,則稱&k 為超線性收斂。3.2 一維最優(yōu)化方法一、確定初始區(qū)間的進退法任選一個初始點x0和初始步長h,由此可確定兩點Xj = x
6、0和X2 =為+ h,通過比較 這兩點函數(shù)值f(xi)、f (X2)的大小,來決定第三點X3的位置。比較這三點函數(shù)值是否 呈“高一一低一一高”排列特征,若是則找到了單峰區(qū)間,否則向前或后退繼續(xù)尋求下 一點。進退法依據(jù)的基本公式:Xj =X0X3 =X2 +h具體步驟為:任意選取初始點Xo和恰當?shù)某跏疾介Lh ;f(Xi)、X2右側(cè),f(X2);應(yīng)加大步長向前搜索。轉(zhuǎn);令 為=x0,取X2 = x1 + h,計算若f(Xi)f(X2),說明極小點在若f(Xi) C f(X2),說明極小點在X1左側(cè),應(yīng)以Xi點為基準反向小步搜索。轉(zhuǎn);高”排列,說明Xi, X3大步向前搜索:令h= 2h,取XXh,計
7、算f(x3); 若 f(X2) f(X3),說明極小點在X3右側(cè),應(yīng)加大步長向前搜索。此時要注意做變 換:舍棄原X1點,以原X2點為新的X1點,原X3點為新的X2點。轉(zhuǎn),直至出現(xiàn)“高一 低一一高”排列,則單峰區(qū)間可得;反向小步搜索(要注意做變換):為了保證X3點計算公式的一致性,做變換:將 原x2點記為新xi點,原xi點記為新x2點,令h U -丄h,取X3 = X2 + h,轉(zhuǎn)41。例:用進退法確定函數(shù)f(x)=x2-6x+9的單峰區(qū)間a,b,設(shè)初始點X0=O, h =解:寫X0 =0 h =1;.Xj =x0 =0X2 =*4 +h =1 f (xj =9 f (x2)= 4寫 f(Xi)
8、f(X2)說明極小點在X2點右側(cè),應(yīng)加大步長向前搜索令 hu 2h =2咒1 =2,取 x3 =X2 +h =1 +2=3則 f(X3)=0常 f(X2)A f(X3)說明極小點在X3點右側(cè),應(yīng)加大步長向前搜索舍棄原x1 =0的點,令Xj = 1 X2 = 3,則f (x1)=4 f(X2)= 0令 hu2h=2%2=4,取 x3=X2+h=3+4 = 7則 f(X3)=16 A f(X2)=0、f(X2)、f(X3)呈“高一一低一一高”排列/.Xi,X3為單峰區(qū)間,即區(qū)間1,7即為所求、黃金分割法黃金分割法是基于區(qū)間消去思想的一維搜索方法,其搜索過程必須遵循以下的原則:對稱取點的原則:即所插
9、入的兩點在區(qū)間內(nèi)位置對稱;插入點繼承的原則:即插入的兩點中有一個是上次縮減區(qū)間時的插入點;等比收縮的原則:即每一次區(qū)間消去后,單峰區(qū)間的收縮率A保持不變。設(shè)初始區(qū)間為a,b,則插入點的計算公式為:x1 =a +0.382(b-a)X2 =a +0.618(b a)黃金分割法的計算步驟如下: 給定初始區(qū)間a,b和收斂精度名; 給出中間插值點并計算其函數(shù)值:Xj =a+0.382(ba)f (X1)X2 = a+0.618(b-a) f (x2).?比較f(Xi)、f(x2),確定保留區(qū)間得到新的單峰區(qū)間a, b;收斂性判別:計算區(qū)間a, b長度并與s比較,若b-a s ;繼承原 x1 點,即 X
10、2 =0.056 f(X2)=0.115插入 xa +0.382(b -a) = 3 +0.382x(1.944 + 3) = 1.111 f (xj = -0.987V f(X2) f (xj舍棄(0.056 , 1.944,保留-3 , 0.0560.056-(3)名;繼承原 X1 點,即 X2=1.111f(X2)=0.987插入 為=a +0.382(b -a) = -3+0.382 咒(0.056 +3) = -1.832f (x1H -0.306V f(x2 f (x1)保留-1.832 ,0.0560.056(1.832) s ;繼承原 X2 點,即 X1=-1.111f(X1)
11、=-0.987插入 X2 = -1.832 +0.618x(0.056 +1.832) = -0.665f (x2H -0.888 f(X2) f(X1)保留-1.832 , -0.665如此迭代,到第8次,保留區(qū)為-1.111,-0.940_0.940 -(1.111) =0.171 8 X* 二丄咒匸行“ +0.940) = -1.0255f(x*) =0.99923.3梯度法、基本思想對于迭代式Xk=Xk+akSk,當取搜索方向Sk =Xf(Xk)時構(gòu)成的尋優(yōu)算法,稱 為求解無約束優(yōu)化問題的梯度法。、迭代步驟給定出發(fā)點xk和收斂精度計算Xk點的梯度F(Xk),并構(gòu)造搜索方向S-VF(Xk
12、);令X心=xk乜kSk,通過一維搜索確定步長ak,即: L /k . k k .min F (X S )2成立,輸出X* =Xk*、F(X*) =F(X心),尋優(yōu)結(jié)求得新點收斂判斷:若IVF(Xk)|束;否則令k= k+1轉(zhuǎn)繼續(xù)迭代,直到滿足收斂精度要求。三、梯度法的特點梯度法尋優(yōu)效率受目標函數(shù)性態(tài)影響較大。若目標函數(shù)等值線為圓,則一輪搜索就 可找到極致點;若當目標函數(shù)等值線為扁橢圓時,收斂速度則顯著下降。梯度法中相鄰兩輪搜索方向相互垂直。(是否會證明) 3.4牛頓法牛頓法分為基本牛頓法和阻尼牛頓法兩種。= -2f(xk)-Vf(xk)時對于迭代式xk+ = xk +ksk,當取k三1且搜索
13、方向Sk構(gòu)成的尋優(yōu)算法,稱為求解無約束優(yōu)化問題的基本牛頓法;對于迭代式XkP=Xk+akSk,取搜索方向Sk =-W2f(Xk)d可f(Xk),k為從xk出發(fā)、沿牛頓方向做一維搜索獲得的最優(yōu)步長,所構(gòu)成的尋優(yōu)算法,稱為求解無約束優(yōu) 化問題的阻尼牛頓法。搜索方向Sk =TV2f(xk)dVf(xk)稱為牛頓方向。這里需要注意的是會求海塞陣的逆矩陣。3.5變尺度法我們把具有Xk屮=Xk-akAf(Xk)迭代模式的尋優(yōu)算法稱為變尺度法。2其搜索方向表達式為:在迭代開始的時候,sk = Apf(xk),稱為擬牛頓方向,其中Ak稱為變尺度矩陣。A0=l ;隨著迭代過程的繼續(xù),AkT J于f(Xk)L叭(
14、Xk)。因此,變尺度法從梯度法出發(fā),隨著迭代過程的繼續(xù)最終趨向于牛頓法。3.6共軛梯度法一、共軛方向的概念設(shè)H為對稱正定矩陣,若有兩個n維向量S1和S2,滿足SiTS2 = 0 ,則稱向量S與S關(guān)于矩陣H共軛,共軛向量的方向稱為共軛方向。若有一組非零向量Si,S2,Sn滿足ST H ”Sj =0(i工j),則稱這組向量關(guān)于 矩陣H共軛。對于n元正定二次函數(shù),依次沿著一組共軛方向進行一維搜索,最多n次即可得到極值點。、共軛方向的形成1對于函數(shù) f(X f(x1,x2 ,xn) =-XThX +bTx +C2沿任意方向S0在設(shè)計空間上任意做兩條平行線,分別與目標函數(shù)等值線切于點 X1、X2,令S1
15、 = x2 -X1,則S0、S1關(guān)于矩陣H共軛。(能否給出證明)三、共軛梯度法對于迭代式Xk+ = xk +aksk,取搜索方向Sk+ =Xf(Xk+) + PkSk其中:s0=Xf(X0),Pk =可(Xk + ) Ff(xk)共軛梯度法相鄰兩輪搜索方向是一對共軛方向。3.7鮑威爾法基本迭代公式仍舊是:xk十=X k +aksk基本鮑威爾法每輪搜索分為兩步:一環(huán)的搜索 +在該環(huán)搜索完畢后生成的新方向上的一維搜索。對于基本鮑威爾法,相鄰兩輪搜索生成的搜索方向是共軛的。修正鮑威爾法與基本鮑威爾法類似,所不同的是每環(huán)搜索后生成的新方向要利用鮑 威爾條件判別其可用性。注意掌握鮑威爾條件的表達式和應(yīng)用
16、!每環(huán)搜索方向組的生成:1第一環(huán)的搜索方向組就是各坐標軸方向2 .下一環(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é)果不滿足鮑威爾條件,
17、則取本環(huán)搜索終點 和反射點中目標函數(shù)值小的點作為本輪的搜索終點,也是下一輪的搜索起點。這里需要注意的是反射點的計算:X爲=2Xnk -Xok式中:Xk七是本環(huán)起點Xok相對于本環(huán)終點Xk沿新生成方向的反射點。例:對于無約束目標函數(shù) minf (X)+2x2 -4xi -2xX2,利用修正 Powell 法從X0=出發(fā)求最優(yōu)解。解:令 x0=x0 _1 _ 0p= P=(e,e2)X; =x0 乜0令 f (xl) -。得:a =2則:xl=【3令 f X 2)=0 得:a = 0.5 貝U: x21h5該環(huán)生成的新搜索方向為:S1 = x2-x(1435引尤對s1進行有效性判別:反射點X1 =
18、2X2 -x0-*1511.512f1 =f(x0)=3f2= f(x2) = 7.5f3 = f(x4)=7Ai = faOlfMi1)二3 (7) =4,也 2 = f (Xi1) - f(x2) =7-(7.5) =0.5故最大下降量im =d =4故:f3f1 和(f1-2f2+f3)(f1-f2m)2m(f1-f3)2 均成立方向S1可用以x2為起點,沿S1方向作一維搜索:x3 =x2 + J31+訂2 13 21.5卜丄3 + 2 I0.51.5 + 0.50由 min f(x3)= f(X2 + aS1)得=2/5 =0.4故,本輪尋優(yōu)的終點為:X1 = x3 =;.;做收斂性判別:=丿2.82 +0.72,應(yīng)繼續(xù)搜索x x0下一輪尋優(yōu)過程的起點為:x2 - x3 = F8!L1.7下一輪尋優(yōu)過程的搜索方向組為:2, S1) 繼續(xù)依樣搜索直至滿足收斂精度解:構(gòu)造懲罰函數(shù)*(X,rk)(X,rki ;:臺+X2k-2X, +1+r (3-X2)-2% +1令旦cx1=2捲-2 =0cx1= 2x2
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 感染科疫情防控工作總結(jié)與反思計劃
- 胃癌治療進展
- 會計人員如何制定周密的工作計劃
- 開放式課堂激發(fā)幼兒探索精神計劃
- 前臺文員創(chuàng)新工作的實踐計劃
- 《貴州勁同礦業(yè)有限公司清鎮(zhèn)市麥格鄉(xiāng)貴耐鋁土礦(修編)礦產(chǎn)資源綠色開發(fā)利用方案(三合一)》專家組評審意見
- 第22課 活動課:唱響《國際歌》 教學(xué)設(shè)計-2023-2024學(xué)年浙江省部編版歷史與社會九年級上冊
- 2025年浙江道路貨運從業(yè)資格證模擬考試
- 腎部專業(yè)知識培訓(xùn)課件
- 2025年杭州貨運從業(yè)資格證年考試題目
- 2025年榆林市公共交通總公司招聘(57人)筆試參考題庫附帶答案詳解
- 醫(yī)院培訓(xùn)課件:《多發(fā)性骨髓瘤》
- 2025年遼寧石化職業(yè)技術(shù)學(xué)院單招職業(yè)傾向性測試題庫審定版
- 2025年湖南省長沙市單招職業(yè)傾向性測試題庫及參考答案
- 十八項核心制度培訓(xùn)課件
- 2024年遠程教育行業(yè)市場運營現(xiàn)狀及行業(yè)發(fā)展趨勢報告
- 2025年2月上海市高三聯(lián)考高考調(diào)研英語試題(答案詳解)
- 2024-2025學(xué)年六年級上學(xué)期數(shù)學(xué)第三單元3.1-搭積木比賽(教案)
- DeepSeek從入門到精通
- 植保機械技術(shù)培訓(xùn)課件
- 2024年水利工程建設(shè)行業(yè)市場發(fā)展監(jiān)測及投資潛力預(yù)測報告
評論
0/150
提交評論