無約束最優(yōu)化方法

無約束最優(yōu)化方法第1頁，共118頁，2023年，2月20日，星期六主要內(nèi)容5.1最速下降法

5.2共軛梯度法

5.3牛頓法

5.4變尺度法

5.5步長加速法

5.6旋轉(zhuǎn)方向法5.7方向加速法

5.8信賴域方法

5.9最小二乘法

第2頁，共118頁，2023年，2月20日，星期六無約束最優(yōu)化問題的求解方法：解析法和直接法。解析法需要計(jì)算函數(shù)的梯度，直接法僅通過比較目標(biāo)函數(shù)值的大小來移動(dòng)迭代點(diǎn)。一般來說，無約束最優(yōu)化問題的求解是通過一系列一維搜索來實(shí)現(xiàn)。如何選擇搜索方向是求解無約束最優(yōu)化問題的核心問題，搜索方向的不同選擇，形成不同的求解方法。第3頁，共118頁，2023年，2月20日，星期六5.1最速下降法

5.1.1最速下降法原理第4頁，共118頁，2023年，2月20日，星期六第5頁，共118頁，2023年，2月20日，星期六5.1.2最速下降法的計(jì)算步驟第6頁，共118頁，2023年，2月20日，星期六第7頁，共118頁，2023年，2月20日，星期六第8頁，共118頁，2023年，2月20日，星期六clearsymsx1x2;%定義符號(hào)變量fx=2*x1^2+x2^2;%定義符號(hào)函數(shù)X0=[1,1];%初值g=jacobian(fx,[x1,x2]);%求符號(hào)函數(shù)的梯度H=jacobian(g,[x1,x2]);%求符號(hào)函數(shù)的海塞矩陣x1=X0(1,1);x2=X0(1,2);%賦初值g0=eval(g);H0=eval(H);%求符號(hào)函數(shù)在x1=1、x2=1梯度、海塞矩陣k=0;fprintf('\n')whilenorm(g0)>eps

%停機(jī)判斷條件

lamda=g0*g0‘/(g0*H0*g0’);

%求lamdafprintf('k=%2d,lamda=%19.16f,x1=%19.16f,x2=%19.16f,fx=%19.16f,norm(p)=%19.16f\n',k,lamda,x1,x2,eval(fx),norm(g0))X0=X0-lamda*g0;x1=X0(1,1);x2=X0(1,2);g0=eval(g);H0=eval(H);k=k+1;end第9頁，共118頁，2023年，2月20日，星期六5.1.3最速下降法的收斂性第10頁，共118頁，2023年，2月20日，星期六第11頁，共118頁，2023年，2月20日，星期六由定理5-1知，在最速下降法中，前后兩次的搜索方向垂直（見圖5-1）。鋸齒形的搜索軌跡使最速下降法效率低下。最速下方向反映了目標(biāo)函數(shù)的一種局部性質(zhì)。從局部看，最速下降方向的確是函數(shù)值下降最快的方向，選擇這樣的方向進(jìn)行搜索是有利的，從全局看，由于鋸齒現(xiàn)象的出現(xiàn)，當(dāng)在極小點(diǎn)附近時(shí)，即使向著極小點(diǎn)移動(dòng)不太大的距離，也要經(jīng)歷不少的彎路，從而使收斂速度大為減慢。第12頁，共118頁，2023年，2月20日，星期六最速下降法不僅簡單，而且具有全局收斂性，并且是線性收斂的。為避免鋸齒現(xiàn)象對(duì)收斂速度的影響，在計(jì)算初期可使用最速下降法，在迭代一段時(shí)間以后，改用其它更有效的方法，如牛頓法等。對(duì)一般的下降算法，只要搜索方向與迭代點(diǎn)處的負(fù)梯度方向的夾角小于90°，使用精確一維搜索和不精確一維搜索在一定的條件下，可以證明下降算法具有全局收斂性。第13頁，共118頁，2023年，2月20日，星期六共軛梯度法最初由Hesteness和Stiefel于1952年為求解線性方程組而提出，1964年Fietcher和Reever在此基礎(chǔ)上，首先提出了求解無約束最優(yōu)化問題的共軛梯度法。共軛梯度法的基本思想：把共軛性與最速下降法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行一維搜索，求出目標(biāo)函數(shù)的極小點(diǎn)。該方法具有收斂速度快、存儲(chǔ)空間小等特點(diǎn)，尤其是對(duì)于正定二次函數(shù)能在有限步內(nèi)達(dá)到極小點(diǎn)，即具有二次終結(jié)性。5.2共軛梯度法

第14頁，共118頁，2023年，2月20日，星期六5.2共軛梯度法

5.2.1共軛方向與共軛方向法第15頁，共118頁，2023年，2月20日，星期六第16頁，共118頁，2023年，2月20日，星期六第17頁，共118頁，2023年，2月20日，星期六第18頁，共118頁，2023年，2月20日，星期六第19頁，共118頁，2023年，2月20日，星期六復(fù)習(xí)

第20頁，共118頁，2023年，2月20日，星期六復(fù)習(xí)

第21頁，共118頁，2023年，2月20日，星期六復(fù)習(xí)

第22頁，共118頁，2023年，2月20日，星期六第23頁，共118頁，2023年，2月20日，星期六你能找到A共軛方向嗎？第24頁，共118頁，2023年，2月20日，星期六第25頁，共118頁，2023年，2月20日，星期六第26頁，共118頁，2023年，2月20日，星期六第27頁，共118頁，2023年，2月20日，星期六第28頁，共118頁，2023年，2月20日，星期六P(0)和p(1)正交嗎？第29頁，共118頁，2023年，2月20日，星期六（5-2）第30頁，共118頁，2023年，2月20日，星期六5.2.2正定二次函數(shù)的共軛梯度法

第31頁，共118頁，2023年，2月20日，星期六第32頁，共118頁，2023年，2月20日，星期六第33頁，共118頁，2023年，2月20日，星期六第34頁，共118頁，2023年，2月20日，星期六第35頁，共118頁，2023年，2月20日，星期六第36頁，共118頁，2023年，2月20日，星期六5.2.3共軛梯度法的計(jì)算步驟

第37頁，共118頁，2023年，2月20日，星期六5.2.4非二次函數(shù)的共軛梯度法第38頁，共118頁，2023年，2月20日，星期六復(fù)習(xí)第39頁，共118頁，2023年，2月20日，星期六第40頁，共118頁，2023年，2月20日，星期六5.2.5共軛梯度法的收斂性第41頁，共118頁，2023年，2月20日，星期六第42頁，共118頁，2023年，2月20日，星期六第43頁，共118頁，2023年，2月20日，星期六第44頁，共118頁，2023年，2月20日，星期六第45頁，共118頁，2023年，2月20日，星期六5.3牛頓法

對(duì)一維搜索方法中的牛頓法加以推廣，就得到了求解無約束優(yōu)化問題的牛頓法。該方法具有收斂速度快的特點(diǎn)，在牛頓法基礎(chǔ)上的改進(jìn)算法如阻尼牛頓法在實(shí)際中被廣泛應(yīng)用。第46頁，共118頁，2023年，2月20日，星期六5.3.1牛頓法原理利用二次函數(shù)近似目標(biāo)函數(shù)。

第47頁，共118頁，2023年，2月20日，星期六第48頁，共118頁，2023年，2月20日，星期六第49頁，共118頁，2023年，2月20日，星期六第50頁，共118頁，2023年，2月20日，星期六第51頁，共118頁，2023年，2月20日，星期六第52頁，共118頁，2023年，2月20日，星期六第53頁，共118頁，2023年，2月20日，星期六5.3.2牛頓法的特點(diǎn)與收斂性牛頓法優(yōu)點(diǎn)：牛頓法具有二階收斂速度。對(duì)二次正定函數(shù)，僅需一步迭代即可達(dá)到最優(yōu)解，具有二次終結(jié)性。牛頓法缺點(diǎn)：（1）牛頓法是局部收斂的，即初始點(diǎn)選擇不當(dāng)，可能會(huì)導(dǎo)致不收斂；（2）牛頓法不是下降算法，當(dāng)二階Hesse陣非正定時(shí)，不能保證是下降方向；（3）二階Hesse陣必須可逆，否則算法將無法進(jìn)行下去；（4）對(duì)函數(shù)分析性質(zhì)要求苛刻，計(jì)算量大，僅適合小規(guī)模優(yōu)化問題。由于牛頓法有良好收斂速度，人們對(duì)它的缺點(diǎn)進(jìn)行了多方面改進(jìn)和修正。第54頁，共118頁，2023年，2月20日，星期六5.3.3牛頓法的改進(jìn)1.阻尼（廣義）牛頓法第55頁，共118頁，2023年，2月20日，星期六第56頁，共118頁，2023年，2月20日，星期六2.Goldstein-Price方法第57頁，共118頁，2023年，2月20日，星期六第58頁，共118頁，2023年，2月20日，星期六5.4變尺度法

第59頁，共118頁，2023年，2月20日，星期六5.4.1變尺度法原理

第60頁，共118頁，2023年，2月20日，星期六第61頁，共118頁，2023年，2月20日，星期六5.4.2DFP變尺度法第62頁，共118頁，2023年，2月20日，星期六第63頁，共118頁，2023年，2月20日，星期六第64頁，共118頁，2023年，2月20日，星期六5.4.3BFGS變尺度法與初始尺度矩陣的修正第65頁，共118頁，2023年，2月20日，星期六第66頁，共118頁，2023年，2月20日，星期六5.4.4變尺度法的計(jì)算步驟第67頁，共118頁，2023年，2月20日，星期六第68頁，共118頁，2023年，2月20日，星期六第69頁，共118頁，2023年，2月20日，星期六第70頁，共118頁，2023年，2月20日，星期六第71頁，共118頁，2023年，2月20日，星期六第72頁，共118頁，2023年，2月20日，星期六第73頁，共118頁，2023年，2月20日，星期六使用MATLAB軟件實(shí)現(xiàn)DFP算法第74頁，共118頁，2023年，2月20日，星期六例5-5最優(yōu)解搜索過程

第75頁，共118頁，2023年，2月20日，星期六例5-5三維圖

第76頁，共118頁，2023年，2月20日，星期六5.4.5變尺度法的性質(zhì)與收斂性

第77頁，共118頁，2023年，2月20日，星期六5.5步長加速法解析法：最速下降法、共軛梯度法、牛頓法和變尺度法需要計(jì)算目標(biāo)函數(shù)的梯度。直接法：不需要求目標(biāo)函數(shù)的梯度。5.5.1步長加速法的基本思想又稱模式搜索法（PatternSearchMethod）。由胡克（Hooke）和基夫斯（Jeeves）于1961年提出的。它不僅易于編制計(jì)算機(jī)程序，而且具有追循谷線加速移向最優(yōu)點(diǎn)的性質(zhì)?；舅枷霃膸缀紊现v，就是尋找具有較小函數(shù)值的“山谷”，力圖使迭代產(chǎn)生的序列沿“山谷”逼近極小點(diǎn)。第78頁，共118頁，2023年，2月20日，星期六5.5.2步長加速法的搜索過程步長加速法由“探測(cè)移動(dòng)”和“模式搜索”兩個(gè)交替的動(dòng)作構(gòu)成。探測(cè)移動(dòng)：依次沿n個(gè)坐標(biāo)軸進(jìn)行，用以確定新的基點(diǎn)和有利于函數(shù)值下降的方向。模式搜索：沿相鄰兩個(gè)基點(diǎn)連線方向進(jìn)行，試圖順著“山谷”使函數(shù)值下降的更快（見圖5-4）。第79頁，共118頁，2023年，2月20日，星期六第80頁，共118頁，2023年，2月20日，星期六第81頁，共118頁，2023年，2月20日，星期六5.5.3步長加速法的計(jì)算步驟第82頁，共118頁，2023年，2月20日，星期六第83頁，共118頁，2023年，2月20日，星期六第84頁，共118頁，2023年，2月20日，星期六第85頁，共118頁，2023年，2月20日，星期六5.6旋轉(zhuǎn)方向法5.6.1旋轉(zhuǎn)方向法的基本思想

第86頁，共118頁，2023年，2月20日，星期六5.6.2旋轉(zhuǎn)方向法的搜索過程第87頁，共118頁，2023年，2月20日，星期六第88頁，共118頁，2023年，2月20日，星期六第89頁，共118頁，2023年，2月20日，星期六5.6.3旋轉(zhuǎn)方向法的計(jì)算步驟第90頁，共118頁，2023年，2月20日，星期六第91頁，共118頁，2023年，2月20日，星期六第92頁，共118頁，2023年，2月20日，星期六第93頁，共118頁，2023年，2月20日，星期六第94頁，共118頁，2023年，2月20日，星期六請(qǐng)讀者比較步長加速法和旋轉(zhuǎn)方向法的區(qū)別第95頁，共118頁，2023年，2月20日，星期六5.7方向加速(powell)法

5.7.1方向加速法的基本思想方向加速（Powell）法的基本思想：把整個(gè)搜索（計(jì)算）過程分為若干個(gè)階段（輪），每個(gè)輪迭代由n+1次一維搜索組成。即在算法的每一輪中，先依次沿著n個(gè)已知的方向搜索，得到一個(gè)最好點(diǎn)，然后沿該輪的初始點(diǎn)與該最好點(diǎn)連線方向進(jìn)行搜索，求得這一輪的最好點(diǎn)。再用最后的搜索方向取代前n個(gè)方向之一，進(jìn)行下一輪的迭代。Powell法的特點(diǎn)：理論體系嚴(yán)密，本質(zhì)是共軛方向法在一定條件下具有二次終結(jié)性第96頁，共118頁，2023年，2月20日，星期六5.7.2基本powell法的計(jì)算步驟

第97頁，共118頁，2023年，2月20日，星期六第98頁，共118頁，2023年，2月20日，星期六5.7.3powell法的二次終結(jié)性

第99頁，共118頁，2023年，2月20日，星期六第100頁，共118頁，2023年，2月20日，星期六5.7.4改進(jìn)的powell法

第101頁，共118頁，2023年，2月20日，星期六5.8信賴域法

5.8.1信賴域法的基本思想無約束最優(yōu)化問題的一般求解策略是，給定點(diǎn)后，定義搜索方向，再從出發(fā)沿作一維搜索，得到新的點(diǎn)。信賴域方法另辟蹊徑，其基本思想：給定點(diǎn)后，確定一個(gè)變化范圍，通常取以為中心的球域（稱為信賴域），在此域內(nèi)優(yōu)化目標(biāo)函數(shù)的二次逼近式，按一定的模式求出后繼點(diǎn)。如果不滿足精度要求，再定義以為中心的信賴域，并在此域內(nèi)優(yōu)化新的二次逼近式，直到滿足精度要求為止。