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

無約束最優(yōu)化方法第一頁，共一百一十八頁，編輯于2023年，星期三主要內(nèi)容5.1最速下降法

5.2共軛梯度法

5.3牛頓法

5.4變尺度法

5.5步長加速法

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

5.8信賴域方法

5.9最小二乘法

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

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

第十四頁，共一百一十八頁，編輯于2023年，星期三5.2共軛梯度法

5.2.1共軛方向與共軛方向法第十五頁，共一百一十八頁，編輯于2023年，星期三第十六頁，共一百一十八頁，編輯于2023年，星期三第十七頁，共一百一十八頁，編輯于2023年，星期三第十八頁，共一百一十八頁，編輯于2023年，星期三第十九頁，共一百一十八頁，編輯于2023年，星期三復(fù)習(xí)

第二十頁，共一百一十八頁，編輯于2023年，星期三復(fù)習(xí)

第二十一頁，共一百一十八頁，編輯于2023年，星期三復(fù)習(xí)

第二十二頁，共一百一十八頁，編輯于2023年，星期三第二十三頁，共一百一十八頁，編輯于2023年，星期三你能找到A共軛方向嗎？第二十四頁，共一百一十八頁，編輯于2023年，星期三第二十五頁，共一百一十八頁，編輯于2023年，星期三第二十六頁，共一百一十八頁，編輯于2023年，星期三第二十七頁，共一百一十八頁，編輯于2023年，星期三第二十八頁，共一百一十八頁，編輯于2023年，星期三P(0)和p(1)正交嗎？第二十九頁，共一百一十八頁，編輯于2023年，星期三（5-2）第三十頁，共一百一十八頁，編輯于2023年，星期三5.2.2正定二次函數(shù)的共軛梯度法

第三十一頁，共一百一十八頁，編輯于2023年，星期三第三十二頁，共一百一十八頁，編輯于2023年，星期三第三十三頁，共一百一十八頁，編輯于2023年，星期三第三十四頁，共一百一十八頁，編輯于2023年，星期三第三十五頁，共一百一十八頁，編輯于2023年，星期三第三十六頁，共一百一十八頁，編輯于2023年，星期三5.2.3共軛梯度法的計算步驟

第三十七頁，共一百一十八頁，編輯于2023年，星期三5.2.4非二次函數(shù)的共軛梯度法第三十八頁，共一百一十八頁，編輯于2023年，星期三復(fù)習(xí)第三十九頁，共一百一十八頁，編輯于2023年，星期三第四十頁，共一百一十八頁，編輯于2023年，星期三5.2.5共軛梯度法的收斂性第四十一頁，共一百一十八頁，編輯于2023年，星期三第四十二頁，共一百一十八頁，編輯于2023年，星期三第四十三頁，共一百一十八頁，編輯于2023年，星期三第四十四頁，共一百一十八頁，編輯于2023年，星期三第四十五頁，共一百一十八頁，編輯于2023年，星期三5.3牛頓法

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

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

第五十九頁，共一百一十八頁，編輯于2023年，星期三5.4.1變尺度法原理

第六十頁，共一百一十八頁，編輯于2023年，星期三第六十一頁，共一百一十八頁，編輯于2023年，星期三5.4.2DFP變尺度法第六十二頁，共一百一十八頁，編輯于2023年，星期三第六十三頁，共一百一十八頁，編輯于2023年，星期三第六十四頁，共一百一十八頁，編輯于2023年，星期三5.4.3BFGS變尺度法與初始尺度矩陣的修正第六十五頁，共一百一十八頁，編輯于2023年，星期三第六十六頁，共一百一十八頁，編輯于2023年，星期三5.4.4變尺度法的計算步驟第六十七頁，共一百一十八頁，編輯于2023年，星期三第六十八頁，共一百一十八頁，編輯于2023年，星期三第六十九頁，共一百一十八頁，編輯于2023年，星期三第七十頁，共一百一十八頁，編輯于2023年，星期三第七十一頁，共一百一十八頁，編輯于2023年，星期三第七十二頁，共一百一十八頁，編輯于2023年，星期三第七十三頁，共一百一十八頁，編輯于2023年，星期三使用MATLAB軟件實現(xiàn)DFP算法第七十四頁，共一百一十八頁，編輯于2023年，星期三例5-5最優(yōu)解搜索過程

第七十五頁，共一百一十八頁，編輯于2023年，星期三例5-5三維圖

第七十六頁，共一百一十八頁，編輯于2023年，星期三5.4.5變尺度法的性質(zhì)與收斂性

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

第八十六頁，共一百一十八頁，編輯于2023年，星期三5.6.2旋轉(zhuǎn)方向法的搜索過程第八十七頁，共一百一十八頁，編輯于2023年，星期三第八十八頁，共一百一十八頁，編輯于2023年，星期三第八十九頁，共一百一十八頁，編輯于2023年，星期三5.6.3旋轉(zhuǎn)方向法的計算步驟第九十頁，共一百一十八頁，編輯于2023年，星期三第九十一頁，共一百一十八頁，編輯于2023年，星期三第九十二頁，共一百一十八頁，編輯于2023年，星期三第九十三頁，共一百一十八頁，編輯于2023年，星期三第九十四頁，共一百一十八頁，編輯于2023年，星期三請讀者比較步長加速法和旋轉(zhuǎn)方向法的區(qū)別第九十五頁，共一百一十八頁，編輯于2023年，星期三5.7方向加速(powell)法

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

第九十七頁，共一百一十八頁，編輯于2023年，星期三第九十八頁，共一百一十八頁，編輯于2023年，星期三5.7.3powell法的二次終結(jié)性

第九十九頁，共一百一十八頁，編輯于2023年，星期三第一百頁，共一百一十八頁，編輯于2023年，星期三5.7.4改進(jìn)的powell法

第一百零一頁，共一百一十八頁，編輯于2023年，星期三5.8信賴域法

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