最優(yōu)化方法第三章(1)

1、 從本章起，以后兩章將討論非線性規(guī)劃問題。本章首先討論無約束最優(yōu)化問題，其一般形式為)(minxf（3.1） 其中 1:RRfn 求解無約束問題的最優(yōu)化方法可以分為兩大類：一類是根據(jù)目標(biāo)函數(shù)的梯度（即一階導(dǎo)數(shù)），有時還要根據(jù)Hesse矩陣（即二階導(dǎo)數(shù)）提供的信息構(gòu)造出來的方法導(dǎo)數(shù)方法導(dǎo)數(shù)方法。本章介紹其中的最速下降法、Newton法、共軛梯度法和擬Newton法。另一類是不使用導(dǎo)數(shù)，僅僅利用目標(biāo)函數(shù)值的信息構(gòu)造出來的方法直接方法直接方法。本章將介紹其中的步長加速法、方法加速法和單純形替換法。兩類方法各有利弊。前者收斂速度快，但需要計算梯度，甚至需要計算Hesse矩陣；后者不涉及導(dǎo)數(shù)，適應(yīng)性強，

2、但收斂速度慢。一般的經(jīng)驗是，在可以求得目標(biāo)函數(shù)導(dǎo)數(shù)的情況下，盡可能使用導(dǎo)數(shù)方法。3.1 直線搜索直線搜索 直線搜索（一維搜索）是指求解如下一元函數(shù)極小化問題min( ) t（3.3） 的迭代方法，其中11:RR 。在微積分中，解決問題（3.3）的范圍一般限于方程0)( t（3.4）可以直接解出的情況。而這里介紹的直線搜索對 嚴(yán)格的要求。當(dāng)然，對于可以求出導(dǎo)數(shù)的情況，相應(yīng)的求解方法一般也會簡單些。不作直線搜索，理論上，分為精確的和不精確的。 精確的直線搜索方法主要分為兩類：一類為區(qū)間收縮法，另一類為函數(shù)逼近法。本節(jié)將相應(yīng)地介紹兩種常用的精確的直線搜索方法：適用于一般函數(shù)的黃金分割法和適用于一般連

3、續(xù)函數(shù)的拋物線插值法。最后還將介紹實用的不精確一維搜索技術(shù)。 精確的直線搜索算法的實現(xiàn)通常是在所謂的搜索區(qū)間上進(jìn)行的 1. 搜索區(qū)間的確定搜索區(qū)間的確定在以下討論中，總假定一元函數(shù))(t是單谷函數(shù)。11:RRL*t)(t定義定義3.1 設(shè)，是 在L上的全局極小點。如果對于L上任意的兩點 1212,t ttt，當(dāng)*2tt 時， )()(21tt；當(dāng)*1tt 時， )()(21tt，那么稱 )(t是區(qū)間L上的單谷函數(shù)單谷函數(shù)。下圖給出了單谷函數(shù)的基本圖形。定義定義3.2 設(shè) 11:RRL,*t是)(t在L上的全局極小點。如果能夠找到 Ltt21,*12 , ,tt t，使得 ,21tt)(t那么閉

4、區(qū)間就稱為極小點的一個搜索區(qū)間搜索區(qū)間，記為 ,21tt132 , , t t t132ttt。搜索區(qū)間有時也記作，其中顯然，單谷函數(shù)的定義域區(qū)間是搜索區(qū)間。單谷函數(shù)的性質(zhì)。,ba)(t定理定理3.1 設(shè)是單谷函數(shù)極小點的一個搜索區(qū)間。),(ba1212,t ttt在內(nèi)任取兩點 ，若)()(21tt，則 ,2ta)(t是極小點的一個搜索區(qū)間；若 )()(21tt,1bt)(t，則是極小點的一個搜索區(qū)間。 直線搜索算法的第一步一般得先確定)(t的一個 （初始）搜索區(qū)間。根據(jù)定理3.1，可以給出確定搜索區(qū)間的如下算法。算法算法3.1（確定搜索區(qū)間）已知：目標(biāo)函數(shù))(t。0th選定初始點和步長。)(

5、00thtt02)(22t計算，。0201tt 若，則置，01tt 0120tt 20hh2，。01,hh ，轉(zhuǎn)； 否則轉(zhuǎn)。置htt02)(22t02計算，。若，則轉(zhuǎn)；否則轉(zhuǎn)。,min21tta ,max21ttb ,ba置，（即為搜索區(qū)間），計算結(jié)束。上述過程開始時，必須選定初試點 0th和步長 。對于 任意給定的 )(t，一般來說， 無固定選取模式。)()(kkp txft0t但對于在下降算法模式中所引入的而言，可選取等于0（理論上）或接近0（實際計算中）。而對于 ，如果選得過小，那么需要迭代許多次才能找到一個搜索區(qū)間；如果選得太大，雖然很少幾步就可能把極小點包括進(jìn)來，但是這又會給下一步搜

6、索極小點的過程增加負(fù)擔(dān)。下面是確定 的一種比較合理而有效的方法。hh0k0 x1x第一次迭代（，即從到的迭代）時， )(t的初始步長可取為1，或根據(jù)問題中出現(xiàn)的數(shù)據(jù)的數(shù)量級估計選定。而以后各次迭代的初始步長可按公式（3.5）計算， kkkpxxh1（3.5）其中 。這是因為從 到 的距離 一般比從 到 的距離 小或接近，所以把按（3.5）算出的作為下一次迭代的初始步長是合適的。在實際計算中，當(dāng) 較小時，相應(yīng)的 可取得小些，而隨著的 增大，相應(yīng)的 可取得接近1。kx1kxkkxx1101kxkx1kkxxkk2. 直線搜索的方法直線搜索的方法（1）黃金分割法 黃金分割法屬于區(qū)間收縮法。它適用于任

7、何單谷函數(shù)求極小值問題。對函數(shù)除“單谷”外，不作其它要求，甚至可以不連續(xù)。因此這種方法的適用面相當(dāng)廣。 黃金分割法的思想是：在每次迭代中，合理地設(shè)置兩個插入點的位置，以使得在計算函數(shù)值次數(shù)同樣多的條件下，將區(qū)間縮小得最快。 a設(shè)區(qū)間 的長為1。在距點 分別為 和 的地方插入 和 。為了確定 和 ，提出以下條件： 1t2t,baa 第一，希望 和 在 中的位置是對稱的。按這一條件，有1t2t,babtat21即 1. （3.6）這樣無論刪去哪一段，總保留長為的區(qū)間。,2bt第二，刪掉一段，例如刪掉3t，在保留下來的區(qū)間，使得里再插入一個點13,tt,2ta12,t t,ba在中的位置與在中的位置

8、具有相同的比例，從而保證每次迭代都能縮小區(qū)間。按這一條件，有以同一比率abatatat221即 1或 2. （3.7）把（3.7）代入（3.6）中，得到關(guān)于的一元二次方程其合理的根是618. 0215（3.8）代回（3.6），得382. 0253 在古代，人們認(rèn)為按比率0.618分割線段是最協(xié)調(diào)的，勝似黃金，故稱黃金分割。因此，上述按比率0.618縮小搜索區(qū)間的迭代方法稱為黃金分割法黃金分割法或0.618法法。算法算法3.2 （黃金分割法）（黃金分割法）P145（2）拋物線插值法 拋物線插值法屬于函數(shù)逼近法。它適用于連續(xù)的單谷函數(shù)求極小值問題。 拋物線插值法的思想是：設(shè) 11:RR 在搜索區(qū)間

9、,321ttt上連續(xù)。記 1122( ),( )tt)(33t和。 如果321ttt（3.9） 與123（3.10）（兩等號不同時成立）同時成立，那么可以過 1122( ,),( ,)tt),(33t和 三點作拋物線插值，設(shè)拋物線方程為rqtpttQ2)(（3.11）( )yQ t13 , t t( )yt其實是在區(qū)間上對所作的一個曲線擬合。( )yQ t4t4t記的極小點為，則根據(jù) 提供的信息，我們可以將搜索區(qū)間 13 , t t縮小，然后在縮小了的區(qū)間上再作拋物線插值。如此下去，最終可以求到 )(t,31tt在 中的極小點*t。 令( )20Q tptq(3.12）解出 pqt24（3.1

10、3）1122( ),( )Q tQ t33)(tQ根據(jù)插值條件和，列出關(guān)于 qp,r和的線性方程組211122222333ptqtrptqtrptqtr由此解出)()()()()(133221321213132ttttttttttttp，)()()()()(133221322212212312322ttttttttttttq，并代入（3.13）中，得)()()(2)()()(3212131323222122123123224ttttttttttttt（3.14）1122( ,),( ,)tt),(33t這個公式的使用條件僅僅是和 三點不共線。可以證明（習(xí)題3.5），在（3.9）和（3.10）（

11、兩等號不同時成立）同時成立的條件下，由（3.14）所確定的 4t)(tQ341ttt是的極小點，并且。以下討論算法的終止準(zhǔn)則和縮小搜索區(qū)間的方法。按（3.14）計算出4t。由極限理論知道，如果 *2tt *4tt 42tt24與都很小，那么也必然很小，當(dāng)然也應(yīng)該很小。 計算經(jīng)驗指出，可以采用1224（3.15） 作為終止準(zhǔn)則。4t2t4t,321ttt當(dāng)終止準(zhǔn)則滿足時，取和中函數(shù)值較小的點提供的縮小。這個過程如下：作為極小點；當(dāng)終止準(zhǔn)則未滿足時，則需要利用信息將原來的搜索區(qū)間4t2t24tt 比較和的大小，有兩種情況：若，則轉(zhuǎn)；否則，轉(zhuǎn)。243434,tt若，則置，轉(zhuǎn)； 2421tt 2412

12、24,tt 若，則，轉(zhuǎn)。 置241414,tt若，則置，轉(zhuǎn)； 2423tt 243224,tt 若，則，轉(zhuǎn)。置,321ttt轉(zhuǎn)向計算新的搜索區(qū)間上的插值拋物線的極小點算法流程圖見書上圖3-5。 包括黃金分割法和拋物線插值法在內(nèi)的許多一維問題的迭代方法全部依賴于函數(shù)單谷性的假設(shè)。但在許多問題中，這一假設(shè)不成立或難以驗證。解決這一困難的辦法，尤其當(dāng)初始搜索區(qū)間很大的時候，是將搜索區(qū)間分成若干個較小區(qū)間，然后在每個子區(qū)間上尋求極小，最后又在所有子區(qū)間的極小中選取最小的一個作為問題的最優(yōu)解。（3）不精確一維搜索技術(shù) 精確的一維搜索過程往往需要花費很大的計算量才有可能求到符合精度要求的最優(yōu)步長因子。當(dāng)多

13、維問題的迭代點距極小點較遠(yuǎn)時，顯然精確地求解一維子問題對求解多維問題本身沒有太大的意義。另外很多最優(yōu)化方法，如Newton法和擬Newton法，其收斂速度也并不依賴于精確的一維搜索過程。因此，在實際計算中，只要選取的步長因子能夠保證目標(biāo)函數(shù)在每一步的迭代中都有“滿意的”下降就可以了。這樣，既會大大地節(jié)省計算量，同時還會從整體上加快計算進(jìn)程?？紤]由多維問題引出的一維問題),()(minkkp txft（3.16）其中1:RRfn具有一階連續(xù)偏導(dǎo)數(shù)。 Goldstein(1965年)和Powell（1975年）給出了用來設(shè)計（3.16）不精確一維搜索過程的兩個條件： ）1()()()Tkkkkkf

14、 xf xtf xp ； （3.17）1()()TTkkkkf xpf xp (3.18).ktkkkkptxx1) 10(,其中使得，而是給定的常數(shù)，通常取 210。條件）表示應(yīng)使新迭代點1kx的函數(shù)值相對上一迭代點 kx的函數(shù)值的下降幅度須不低于某個量，而條件）則表示目標(biāo)函數(shù) f在新迭代點1kx處沿 kp方向的方向?qū)?shù)應(yīng)不小于 ff在上一迭代點 kx處沿kp方向的方向?qū)?shù)的 倍。換句話說，若 1kx滿足 條件），則認(rèn)為在點 1kx處已獲得“滿意的”函數(shù)值的下降。 而若1kx滿足條件），這時有兩種可能性， 要么kp已是點 方向1kx處的上升方向， kp1kx要么方向雖然還是點下降方向， 處的

15、f1kx但函數(shù)在點 處沿kp方向的下降率已低于 處沿kp方向的下降率f在點kx 倍，這時若繼續(xù)沿 kp方向作一維搜索，只會徒增計算量，而不會再獲得函數(shù)值的較大下降量，因此，一旦 1kx滿足條件）就需要確定1kp。新的搜索方向 以上分析表明，在實際計算中，選取滿足（3.17）和（3.18）的 kt作為確定1kx的步長因子是合適的， 即kkkkptxx1。一般地， 越小，一維搜索越精確，但計算量也越大。 不精確的一維搜索不要求過小的而越小，條件）越容易滿足。 0.14 . 0在實際計算中，通常取或更小的值值的選取不太敏感），。（由此得出的解通常對算法算法3.3（不精確一維搜索）( )()kktf

16、xtp()0Tkkf xp已知：，且。給定1),1 ,(),21, 0( 2t（通常取），初始（可取1或參照（3.5）給出）。步長(),()kkkkff xgf x 0,0abj 計算。置。計算11111,(),()kkkkkkkxxt pff xgf x ；若（3.18）成立，則轉(zhuǎn)；否則，置,min,1abat tajj，然后轉(zhuǎn)； ttk,1abbt tjj若（3.17）成立，則打印，計算結(jié)束；否則，然后轉(zhuǎn)。置 算法說明：）第步中若（3.18）不成立，則表明沿kp方向有繼續(xù)前進(jìn)的必要； ）第步中若（3.17）不成立，這表明當(dāng)前步長過大，需縮小搜索范圍。不精確一維搜索的算法流程圖3.2 最速下

17、降法最速下降法 最速下降法是最早的求解多元函數(shù)極值的數(shù)值方法。它直觀、簡單。它的缺點是，收斂速度較慢、實用性差。1. 基本思想基本思想1,kxxkx求解問題（3.1）。假設(shè)迭代已得到。在點處，取搜索方向為()kkpf x （3.19）沿kp進(jìn)行直線搜索，由此確定1()kkkkxxtf x （3.20） 其中步長因子kt滿足()min()kkkkktf xtf xf xt f x （3.21） （3.20）、（3.21）簡單地合記為1(,()kkkxls xf x（3.22） 3.20）或（3.22）稱為最速下降迭代公式最速下降迭代公式，由該公式產(chǎn)生的算法稱為最速下降法最速下降法。 今后記()(

18、)kkkgg xf x 2. 算法算法算法算法3.4（最速下降法） P151將最速下降法應(yīng)用于正定二次函數(shù)1( )2TTf xx Qxb xc（3.23） 可以推出顯式迭代公式。kkx1kx設(shè)第迭代點為，求的表達(dá)式。由( )g xQxb（3.24）kkgQxb （3.25）1kkkkxxt g， （3.26），10Tkkgg，（直線搜索性質(zhì)）得 ()0TkkkkQ xt gbg即0Tkkkkgt Qgg由此解出TkkkTkkg gtg Qg （3.27） 例例3.1 P1523. 鋸齒現(xiàn)象鋸齒現(xiàn)象 最速下降法的迭代點在向極小點靠近的過程中，走的是曲折的路線：后一次搜索方向 1kp與前一次搜索方

19、向 kp總是相互垂直的，稱它為鋸齒現(xiàn)象鋸齒現(xiàn)象。這一點在前面的例題中已得到驗證。除極特殊的目標(biāo)函數(shù)（如等值面為球面的函數(shù)）和極特殊的初始點外，這種現(xiàn)象一般都要發(fā)生。 從直觀上可以看到，在遠(yuǎn)離極小點的地方，每次迭代都有可能使目標(biāo)函數(shù)值有較多的下降，但在接近極小點的地方，由于鋸齒現(xiàn)象，每次迭代行進(jìn)的距離開始逐漸變小。因而收斂速度不快。 已有結(jié)論表明，最速下降法對于正定二次函數(shù)關(guān)于任意初始點都是收斂的，而且恰好是線性收斂的。3.3 Newton法法( )f xnR如果目標(biāo)函數(shù)在上具有連續(xù)的二階偏導(dǎo)數(shù)，其Hesse矩陣 2( )f x正定且可以表達(dá)成顯式（今后記 2( )( )G xf x ），那么使

20、用Newton法求解（3.1）會很快地得到極小點。 1. 基本思想基本思想kx1kxkx( )f x考慮從到的迭代過程。在點處，對按Taylor級數(shù)展開到第三項，即1( )( )()() ()()()()2TTkkkkkkf xQ xf xg xxxxxG xxx （3.29） ()kG x( )Q x因為正定，所以是正定二次函數(shù)。令( )()()()0kkkQ xG xxxg x 得()()()kkkG xxxg x （3.30） ( )Q x1kx由此解出的極小點，記為，即11()()kkkkxxG xg x（3.31） 1kx( )f x*x是極小點的新的近似點。 （3.31）稱為New

21、ton迭代公式迭代公式，由該公式產(chǎn)生的算法稱為Newton法法。( )f x( )( )f xQ x注意到，當(dāng)目標(biāo)函數(shù)是正定二次函數(shù)（3.36）時，。這說明：對于正定二次函數(shù)，Newton法一次迭代就會得到最優(yōu)解。( )f xkx（3.31）有直觀的幾何解釋。函數(shù)過點的等值面方程為( )()kf xf x（3.32）在點kx處，用一個與曲面（3.32）最密切的二次曲面來代替它，這個二次曲面的方程即是( )()kQ xf x()kG x( )Q x當(dāng)正定時，它是一個超橢球面，的極小點 1kx正是這個超橢球面的中心。我們就用 1kx( )f x*x作為極小點 的新的近似點。下圖畫出了二維情況時的幾何解釋。例例3.2 P1542. 算法算法算法算法3.5（Newton法） P1553. 修正修正Newton法法 Newton法的優(yōu)點是收斂速度快、程序簡單。特別是前一個優(yōu)點，在最優(yōu)化方法中