第6章--無約束問題的優(yōu)化方法(共18頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第6章 無約束問題的優(yōu)化方法6.1 最速下降法和牛頓法6.1.1 最速下降法的基本原理、計(jì)算步驟和特點(diǎn)基本原理：考慮無約束問題從某一點(diǎn)出發(fā)，選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向，可以盡快達(dá)到極小點(diǎn)1847年法國數(shù)學(xué)家Cauchy提出了最速下降法后來，Curry等人作了進(jìn)一步研究最速下降方向是目標(biāo)函數(shù)的負(fù)梯度方向：最速下降法的迭代公式：取為在點(diǎn)處的最速下降方向：為進(jìn)行一維搜索的步長，滿足：計(jì)算步驟：(l)給定初點(diǎn)，允許誤差，置.(2)計(jì)算搜索方向.(3)若，則停止計(jì)算；否則，從出發(fā)，沿進(jìn)行一維搜索，求，使(4)令,置，轉(zhuǎn)步驟（2）.例1 解問題初點(diǎn)，. （最優(yōu)解）第1次迭代

2、：目標(biāo)函數(shù)在點(diǎn)處的梯度令搜索方向 從出發(fā)，沿方向進(jìn)行一維搜索，求步長，即令(一般應(yīng)采用不精確一維搜索求解)，解得在直線上的極小點(diǎn)： 第2次迭代： 解得 第3次迭代：解得 這時(shí)有滿足精度要求，得到近似解最速下降算法的特點(diǎn)：最速下降算法在一定條件下是收斂的最速下降法產(chǎn)生的序列是線性收斂的，而且收斂性質(zhì)與極小點(diǎn)處Hesse矩陣的特征值有關(guān)定理1: 設(shè)存在連續(xù)二階偏導(dǎo)數(shù)，是局部極小點(diǎn)，Hesse矩陣的最小特征值，最大特征值為，算法產(chǎn)生的序列收斂于點(diǎn)，則目標(biāo)函數(shù)值的序列以不大于的收斂比線性地收斂于.最速下降法存在鋸齒現(xiàn)象：從局部看，最速下降方向確是函數(shù)值下降最快的方向從全局看，由于鋸齒現(xiàn)象的影響，即使向

3、著極小點(diǎn)移近不太大的距離，也要經(jīng)歷不小的彎路，使收斂速率大為減慢注1：最速下降法并不是收斂最快的方法，從全局看，它的收斂是比較慢的注2：最速下降法一般適用于計(jì)算過程的前期迭代或作為間插步驟當(dāng)接近極小點(diǎn)時(shí)，使用最速下降法達(dá)到迭代終止，這樣做并不有利6.1.2 牛頓法的基本原理、計(jì)算步驟和特點(diǎn)1.牛頓法在點(diǎn)的二階Taylor展開為求的平穩(wěn)點(diǎn)，令,即 (1)設(shè)可逆，得到牛頓法的迭代公式產(chǎn)生序列，在適當(dāng)?shù)臈l件下，這個(gè)序列收斂例2：解問題： (最優(yōu)解)目標(biāo)函數(shù)的梯度和Hesse矩陣分別為 取初點(diǎn).第l次迭代: 第2次迭代: 繼續(xù)迭代，得到,注3：當(dāng)牛頓法收斂時(shí)，有下列關(guān)系：c是某個(gè)常數(shù)因此，牛頓法至少2

4、級(jí)收斂，收斂速率是很快的注4：對(duì)二次凸函數(shù)，用牛頓法求解經(jīng)1次迭代即達(dá)極小點(diǎn)設(shè)有二次凸函數(shù): 用極值條件求解：令得到最優(yōu)解用牛頓法求解：任取初始點(diǎn)，根據(jù)牛頓法的迭代公式有以后還會(huì)遇到一些算法，把它們用于二次凸函數(shù)時(shí)，類似于牛頓法，經(jīng)有限次迭代必達(dá)到極小點(diǎn)這種性質(zhì)稱為二次終止性注5: 當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時(shí)，牛頓法可能不收斂牛頓方向不一定是下降方向，經(jīng)迭代，目標(biāo)函數(shù)值可能上升.即使目標(biāo)函數(shù)值下降，得到的點(diǎn)也不一定是沿牛頓方向的最好點(diǎn)或極小點(diǎn)對(duì)牛頓法進(jìn)行修正，提出了阻尼牛頓法2. 阻尼牛頓法阻尼牛頓法增加沿牛頓方向的一維搜索，迭代公式:為牛頓方向.由一維搜索得到:由于阻尼牛頓法含有一維搜索，因此每次

5、迭代目標(biāo)函數(shù)值一般有所下降（絕不會(huì)上升）可以證明，阻尼牛頓法在適當(dāng)?shù)臈l件下具有全局收斂性，且為2 級(jí)收斂阻尼牛頓法的計(jì)算步驟：(l)給定初點(diǎn)，允許誤差，置.(2)計(jì)算，.(3)若，則停止計(jì)算；否則，令（4）從出發(fā)，沿進(jìn)行一維搜索，求，使(5)令,置，轉(zhuǎn)步驟（2）.3.牛頓法的進(jìn)一步修正原始牛頓法和阻尼牛頓法有共同缺點(diǎn)：（1）可能出現(xiàn)Hesse矩陣奇異的情形，因此不能確定后繼點(diǎn)；（2）即使非奇異，也未必正定，因而牛頓方向不一定是下降方向，就可能導(dǎo)致算法失效例3: 用阻尼牛頓法求解：取初始點(diǎn). 在點(diǎn)處，有，牛頓方向從出發(fā)，沿作一維搜索令 , 則 .用阻尼牛頓法不能產(chǎn)生新點(diǎn)，而點(diǎn)并不是問題的極小點(diǎn)原

6、因在于Hesse矩陣非正定為使牛頓法從任一點(diǎn)開始均能產(chǎn)生收斂于解集合的序列，要做進(jìn)一步修正,克服Hesse矩陣非正定考慮（1）式，記搜索方向，得到 (2)阻尼牛頓法所用搜索方向是上述方程的解：解決Hesse矩陣非正定問題的基本思想：修正，構(gòu)造一個(gè)對(duì)稱正定矩陣.在（2）中，用取代矩陣,得到方程 (3)解此方程，得到在點(diǎn)處的下降方向構(gòu)造矩陣的方法之一: 令是一個(gè)適當(dāng)?shù)恼龜?shù)只要選擇得合適，就是對(duì)稱正定矩陣注6: 當(dāng)為鞍點(diǎn)時(shí)，有 及 不定此時(shí)（3）式不能使用這時(shí)可取為負(fù)曲率方向：當(dāng)不定時(shí)，這樣的方向必定存在，而且沿此方向進(jìn)行一維搜索必能使目標(biāo)函數(shù)值下降6.2 共軛梯度法6.2.1 共軛方向的基本原理和

7、定理共軛梯度法是基于共軛方向的一種算法定義1：設(shè)是對(duì)稱正定矩陣，若中的兩個(gè)方向和滿足則稱這兩個(gè)方向關(guān)于共軛，或稱它們關(guān)于正交若， ，是中個(gè)方向，它們兩兩關(guān)于共軛，即滿足則稱這組方向是共軛的，或稱它們?yōu)榈膫€(gè)共軛方向注1：如果為單位矩陣，則兩個(gè)方向關(guān)于共軛等價(jià)于兩個(gè)方向正交共軛是正交概念的推廣注2：如果是一般的對(duì)稱正定矩陣，和關(guān)于共軛，也就是方向與方向正交共軛的幾何意義（以正定二次函數(shù)為例）：二次函數(shù)函數(shù)的等值面是以為中心的橢球面，是極小點(diǎn).設(shè)是在某個(gè)等值面上的一點(diǎn)，該等值面在點(diǎn)處的法向量又設(shè)是這個(gè)等值面在處的一個(gè)切向量記與正交，即，因此有即等值面上一點(diǎn)處的切向量與由這一點(diǎn)指向極小點(diǎn)的向量關(guān)于共軛

8、.依次沿著和進(jìn)行一維搜索，則經(jīng)兩次迭代必達(dá)到極小點(diǎn)共軛方向的重要性質(zhì):定理1: 設(shè)是階對(duì)稱正定矩陣， ，是個(gè)共軛的非零向量，則這個(gè)向量組線性無關(guān)定理2（擴(kuò)張子空間定理）: 設(shè)有函數(shù)其中是階對(duì)稱正定矩陣， ，是共軛的非零向量以任意的為初始點(diǎn)，依次沿， ，進(jìn)行一維搜索，得到點(diǎn)， ，則是函數(shù)在線性流形上的惟一極小點(diǎn)特別地，當(dāng)時(shí)，是函數(shù)的惟一極小點(diǎn)其中是， ，生成的子空間推論: 在定理2的條件下，必有 定理2表明: 對(duì)于二次凸函數(shù)，若沿一組共軛方向（非零向量）搜索，經(jīng)有限步迭代必達(dá)到極小點(diǎn)6.2.2 用于正定二次函數(shù)的共軛梯度法共軛梯度法最初由Hesteness和Stiefel于1952年提出本節(jié)重點(diǎn)

9、介紹Fletcher-Reeves共軛梯度法(FR法)共軛梯度法的基本思想:把共軛性與最速下降方法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，沿這組方向進(jìn)行搜索，求出目標(biāo)函數(shù)的極小點(diǎn)根據(jù)共軛方向的基本性質(zhì)，這種方法具有二次終止性考慮如下正定二次函數(shù)優(yōu)化問題的求解方法:令.任意給定一個(gè)初始點(diǎn),計(jì)算出目標(biāo)函數(shù)在這點(diǎn)的梯度，,則停止計(jì)算；否則，令沿方向搜索，得到點(diǎn)計(jì)算在處的梯度，若，則利用和構(gòu)造第2個(gè)搜索方向，再沿搜索一般地，若已知點(diǎn)和搜索方向，則從出發(fā)，沿進(jìn)行搜索，得到步長滿足.此時(shí)可求出的顯式表達(dá)令,根據(jù)及二次函數(shù)的梯度的表達(dá)式，得到 (1)計(jì)算在處的梯度，若，則停止計(jì)算;否則用和構(gòu)造下一個(gè)搜索

10、方向，并使和關(guān)于共軛按此設(shè)想，令上式兩端左乘，并令由此得到 再從出發(fā)，沿方向搜索可以證明,按上述方法構(gòu)造的一組搜索方向,是關(guān)于A共軛的因此，上述方法具有二次終止性定理3: 對(duì)于正定二次函數(shù)，具有精確一維搜索的FR法在次一維搜索后即終止，并且對(duì)所有)，下列關(guān)系成立：(l) (2) (3) 證明: 用歸納法可證注3: 在FR法中，初始搜索方向必須取最速下降方向如果選擇別的方向作為初始方向，其余方向均按FR法構(gòu)造，那么極小化正定二次函數(shù)時(shí)，構(gòu)造出來的一組方向并不能保證共軛性可以證明: 對(duì)于正定二次函數(shù)，運(yùn)用FR法時(shí)，不作矩陣運(yùn)算就能求出因子定理4: 對(duì)于正定二次函數(shù)，F(xiàn)R法中因子, (2)對(duì)于二次凸

11、函數(shù)，F(xiàn)R法計(jì)算步驟：(1) 給定初始點(diǎn)，置.(2) 計(jì)算，若，則停止計(jì)算，得點(diǎn)；否則，進(jìn)行下一步.(3)構(gòu)造搜索方向，令.當(dāng)時(shí)，,當(dāng)時(shí)，按（2）式計(jì)算因子.(4)令,步長按（1）式計(jì)算(5)若，則停止計(jì)算，得點(diǎn)；否則，置，返回步驟(2). 例1: 用FR法求解問題：,取初始點(diǎn).目標(biāo)函數(shù)梯度: 第1次迭代: 令,從沿方向作一維搜索，得 第2次迭代: 在點(diǎn)處，目標(biāo)函數(shù)的梯度構(gòu)造搜索方向計(jì)算因子.令從出發(fā),沿方向作一維搜索,得 點(diǎn)處,目標(biāo)函數(shù)梯度,已達(dá)到極小點(diǎn).6.2.3 將共軛梯度法用于求解非正定二次函數(shù)優(yōu)化問題用于極小化任意函數(shù)的共軛梯度法與用于極小化二次函數(shù)的共軛梯度法主要差別: (1)步長

12、不用計(jì)算，必須用其它一維搜索方法來確定(2)凡用到矩陣A之處，需要用現(xiàn)行點(diǎn)處的Hesse矩陣用這種方法求任意函數(shù)極小點(diǎn)，一般來說用有限步迭代是達(dá)不到的迭代延續(xù)可以采取不同的方案：直接延續(xù)，即總是用構(gòu)造搜索方向；把n步作為一輪，每搜索一輪之后，取一次最速下降方向，開始下一輪稱為“重新開始”或“重置”每n次迭代后以最速下降方向重新開始的共軛梯度法，有時(shí)稱為傳統(tǒng)的共軛梯度法計(jì)算步驟：(1)給定初始點(diǎn)，允許誤差置, (2)若 ,則停止計(jì)算；否則，作一維搜索，求，滿足令.(3)如果，則進(jìn)行步驟(4)；否則，進(jìn)行步驟(5).(4)令,其中置，轉(zhuǎn)步驟(2).(5)令，,，置, ，轉(zhuǎn)步驟(2). 注4:可以采

13、用不同公式計(jì)算因子:(1)（FR法）(2)(Polak,Ribiere&Polyak，PRP法)(3) (Sorenson和Wolfe)(4) (Daniel)（1）當(dāng)極小化正定二次函數(shù)，初始搜索方向取負(fù)梯度時(shí)，四個(gè)公式是等價(jià)的（2）用于一般函數(shù)時(shí)，得到的搜索方向不同（3）有人認(rèn)為PRP方法優(yōu)于FR法但據(jù)一些人的計(jì)算結(jié)果，幾種方法彼此差別并不很大，難以給出絕對(duì)的比較結(jié)論注5: 運(yùn)用共軛梯度法時(shí)應(yīng)該注意，均假設(shè)采用精確一維搜索.精確一維搜索需付出較大代價(jià)，因此許多情形下采用不精確一維搜索不精確一維搜索會(huì)出現(xiàn)新的問題，按照構(gòu)造的搜索方向可能不是下降方向解決方法:(1)當(dāng)不是下降方向時(shí)，以最速下降方

14、向重新開始當(dāng)一維搜索比較粗糙時(shí)，這樣的重新開始可能是大量的，因此會(huì)降低計(jì)算效率(2)計(jì)算過程中增加附加檢驗(yàn)設(shè)，,表示在檢驗(yàn)點(diǎn)處計(jì)算出的，和,如滿足則取作為步長；否則，進(jìn)行精確一維搜索，求最優(yōu)步長共軛梯度法的收斂性:對(duì)于一般函數(shù), 共軛梯度法在一定條件下是收斂的.Crowder和Wolfe證明: 共軛梯度法的收斂速率不壞于最速下降法; 不用標(biāo)準(zhǔn)初始方向,共軛梯度法的收斂速率可能像線性速率那樣慢. 共軛梯度法的優(yōu)點(diǎn):存儲(chǔ)量小：FR法只需存儲(chǔ)3個(gè)n維向量.求解變量多的大規(guī)模問題可用共軛梯度法6.3 擬牛頓法6.3.1 擬牛頓法簡介牛頓法的最大優(yōu)點(diǎn)是收斂速度快，原因是牛頓法在迭代點(diǎn)附近對(duì)目標(biāo)函數(shù)進(jìn)行二

15、次近似時(shí)，利用了目標(biāo)函數(shù)的曲率信息（Hesse矩陣）。使用Hesse矩陣存在一些缺點(diǎn)：計(jì)算量大、Hesse矩陣可能非正定，導(dǎo)致牛頓方向可能不是一個(gè)下降方向等。愿望：尋找一種算法，既具有牛頓法收斂速度快的優(yōu)點(diǎn)，又能克服計(jì)算工作量大、產(chǎn)生非下降方向等缺點(diǎn)。擬牛頓法（quasi-Newton method）的基本思想：在迭代過程中只利用目標(biāo)函數(shù)和梯度信息，構(gòu)造Hesse矩陣的近似矩陣，由此獲得一個(gè)搜索方向，生成新的迭代點(diǎn)。近似矩陣的不同構(gòu)造方式，對(duì)應(yīng)著擬牛頓法的不同變形。擬牛頓法是一類收斂速度比較快的算法，是公認(rèn)的比較有效的無約束優(yōu)化方法。6.3.2 擬牛頓條件及擬牛頓法的主要步驟設(shè)在第k次迭代后，

16、得到點(diǎn)，將目標(biāo)函數(shù)在點(diǎn)作二階Taylor展開近似：目標(biāo)函數(shù)梯度在附近可近似為對(duì)的附近點(diǎn)，有或 記 有又設(shè)Hesse矩陣可逆，則計(jì)算出和后，可根據(jù)上式估計(jì)在處的Hesse 矩陣的逆為了用不包含二階導(dǎo)數(shù)的矩陣取代牛頓法中的Hesse矩陣的逆矩陣，有理由令滿足 （1）(1)式稱為擬牛頓條件擬牛頓法的計(jì)算步驟：(1)初始化：給定初始點(diǎn)，正定矩陣，；計(jì)算 置.(2)平穩(wěn)點(diǎn)檢驗(yàn)：若，則停止計(jì)算；否則，計(jì)算搜索方向.(3)一維搜索：求出步長，令.(4)修正擬牛頓方程：計(jì)算 并對(duì)矩陣進(jìn)行校正，得到，使之滿足擬牛頓條件（1）；置，轉(zhuǎn)步驟（2）.6.3.3 對(duì)稱秩1校正滿足擬牛頓條件的矩陣應(yīng)與Hesse矩陣的逆陣

17、一樣，是n階對(duì)稱正定矩陣構(gòu)造近似矩陣的一般策略：取為任意一個(gè)n階對(duì)稱正定矩陣，通常選擇為單位矩陣I，然后通過修正給出.令稱為校正矩陣確定的方法之一令是n維列向量這樣定義的是秩為l的對(duì)稱矩陣的選擇應(yīng)使(1)式得到滿足，令 （2）得到 (2a)另一方面，(2)式兩端左乘，經(jīng)整理得到 （3）利用（2a）式和（3）式可得到秩1校正公式： （4）利用秩l校正極小化函數(shù)時(shí)，在第k次迭代中，令搜索方向然后沿方向搜索，求步長，滿足確定出后繼點(diǎn). 可以證明：秩1校正方法在一定條件下是收斂的，并且具有二次終止性運(yùn)用秩l 校正存在一些困難，應(yīng)用有某種局限性：（1）僅當(dāng)時(shí)，由（4）式得到的才能確保正定性，而這一點(diǎn)是沒

18、有保證的（2）即使由于舍入誤差的影響，可能導(dǎo)致無界，從而產(chǎn)生數(shù)值計(jì)算上的困難6.3.4 DFP和BFGS校正(對(duì)稱秩2校正)1.DFP算法DFP方法由Davidon首先提出，后來又被Fletcher和Powell改進(jìn)，又稱為變尺度法校正矩陣（DFP公式）： （5） （6）可以驗(yàn)證，這樣定義的校正矩陣滿足擬牛頓條件（1）.DFP方法計(jì)算步驟：(1)給定初始點(diǎn)，允許誤差.(2)置，計(jì)算,置.(3)令.(4)從出發(fā)，然后沿方向搜索，求步長，滿足令. (5)檢驗(yàn)是否滿足收斂準(zhǔn)則，若，則停止迭代，得到點(diǎn)；否則，返回步驟（6） . (6)若，則令，返回步驟（2）；否則，進(jìn)行步驟（7）. (7)令利用（6）

19、式計(jì)算，置，返回步驟（3）.例1：用DFP法求解問題：取初始點(diǎn)及初始矩陣.目標(biāo)函數(shù)的梯度第1次迭代：在點(diǎn)處的梯度令搜索方向 從出發(fā)作一維搜索：解得 ， 第2次迭代：， 計(jì)算矩陣令 從出發(fā)，沿方向搜索：解得 ， 得到最優(yōu)解注1：此例經(jīng)兩次搜索達(dá)到極小點(diǎn)，這不是偶然的可證明，DFP方法具有二次終止性定理1：若，則DFP方法構(gòu)造的矩陣為對(duì)稱正定矩陣證明：用歸納法可證定理2：設(shè)用DFP方法求解下列問題：A為n階對(duì)稱正定矩陣取初點(diǎn)，令是n階對(duì)稱正定矩陣，則成立其中證明：用歸納法可證推論：在定理2的條件下，必有.注2：由于，因此,，關(guān)于A共軛等價(jià)于,，關(guān)于A共軛可見，DFP方法中構(gòu)造出來的搜索方向是一組A共軛方向，DFP方法具有二次終止性若目標(biāo)函數(shù)為正定二次函數(shù)，則DFP法經(jīng)有限步迭代必達(dá)極小點(diǎn)。DFP方法用于一般函數(shù)時(shí)的收斂性：定理3：如果是上的二次連續(xù)可微實(shí)函數(shù)，對(duì)任意，存在