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

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

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

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

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

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

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

7、何單谷函數(shù)求極小值問題。對(duì)函數(shù)除“單谷”外，不作其它要求，甚至可以不連續(xù)。因此這種方法的適用面相當(dāng)廣。 黃金分割法的思想是：在每次迭代中，合理地設(shè)置兩個(gè)插入點(diǎn)的位置，以使得在計(jì)算函數(shù)值次數(shù)同樣多的條件下，將區(qū)間縮小得最快。 a設(shè)區(qū)間 的長(zhǎng)為1。在距點(diǎn) 分別為 和 的地方插入 和 。為了確定 和 ，提出以下條件： 1t2t,baa 第一，希望 和 在 中的位置是對(duì)稱的。按這一條件，有1t2t,babtat21即 1. （3.6）這樣無論刪去哪一段，總保留長(zhǎng)為的區(qū)間。,2bt第二，刪掉一段，例如刪掉3t，在保留下來的區(qū)間，使得里再插入一個(gè)點(diǎn)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）（兩等號(hào)不同時(shí)成立）同時(shí)成立，那么可以過 1122( ,),( ,)tt),(33t和 三點(diǎn)作拋物線插值，設(shè)拋物線方程為rqtpttQ2)(（3.11）( )yQ t13 , t t( )yt其實(shí)是在區(qū)間上對(duì)所作的一個(gè)曲線擬合。( )yQ t4t4t記的極小點(diǎn)為，則根據(jù) 提供的信息，我們可以將搜索區(qū)間 13 , t t縮小，然后在縮小了的區(qū)間上再作拋物線插值。如此下去，最終可以求到 )(t,31tt在 中的極小點(diǎn)*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這個(gè)公式的使用條件僅僅是和 三點(diǎn)不共線?？梢宰C明（習(xí)題3.5），在（3.9）和（3.10）（

11、兩等號(hào)不同時(shí)成立）同時(shí)成立的條件下，由（3.14）所確定的 4t)(tQ341ttt是的極小點(diǎn)，并且。以下討論算法的終止準(zhǔn)則和縮小搜索區(qū)間的方法。按（3.14）計(jì)算出4t。由極限理論知道，如果 *2tt *4tt 42tt24與都很小，那么也必然很小，當(dāng)然也應(yīng)該很小。 計(jì)算經(jīng)驗(yàn)指出，可以采用1224（3.15） 作為終止準(zhǔn)則。4t2t4t,321ttt當(dāng)終止準(zhǔn)則滿足時(shí)，取和中函數(shù)值較小的點(diǎn)提供的縮小。這個(gè)過程如下：作為極小點(diǎn)；當(dāng)終止準(zhǔn)則未滿足時(shí)，則需要利用信息將原來的搜索區(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)向計(jì)算新的搜索區(qū)間上的插值拋物線的極小點(diǎn)算法流程圖見書上圖3-5。 包括黃金分割法和拋物線插值法在內(nèi)的許多一維問題的迭代方法全部依賴于函數(shù)單谷性的假設(shè)。但在許多問題中，這一假設(shè)不成立或難以驗(yàn)證。解決這一困難的辦法，尤其當(dāng)初始搜索區(qū)間很大的時(shí)候，是將搜索區(qū)間分成若干個(gè)較小區(qū)間，然后在每個(gè)子區(qū)間上尋求極小，最后又在所有子區(qū)間的極小中選取最小的一個(gè)作為問題的最優(yōu)解。（3）不精確一維搜索技術(shù) 精確的一維搜索過程往往需要花費(fèi)很大的計(jì)算量才有可能求到符合精度要求的最優(yōu)步長(zhǎng)因子。當(dāng)多

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

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

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

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

17、降法最速下降法 最速下降法是最早的求解多元函數(shù)極值的數(shù)值方法。它直觀、簡(jiǎn)單。它的缺點(diǎn)是，收斂速度較慢、實(shí)用性差。1. 基本思想基本思想1,kxxkx求解問題（3.1）。假設(shè)迭代已得到。在點(diǎn)處，取搜索方向?yàn)?)kkpf x （3.19）沿kp進(jìn)行直線搜索，由此確定1()kkkkxxtf x （3.20） 其中步長(zhǎng)因子kt滿足()min()kkkkktf xtf xf xt f x （3.21） （3.20）、（3.21）簡(jiǎn)單地合記為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è)第迭代點(diǎn)為，求的表達(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)象 最速下降法的迭代點(diǎn)在向極小點(diǎn)靠近的過程中，走的是曲折的路線：后一次搜索方向 1kp與前一次搜索方

19、向 kp總是相互垂直的，稱它為鋸齒現(xiàn)象鋸齒現(xiàn)象。這一點(diǎn)在前面的例題中已得到驗(yàn)證。除極特殊的目標(biāo)函數(shù)（如等值面為球面的函數(shù)）和極特殊的初始點(diǎn)外，這種現(xiàn)象一般都要發(fā)生。 從直觀上可以看到，在遠(yuǎn)離極小點(diǎn)的地方，每次迭代都有可能使目標(biāo)函數(shù)值有較多的下降，但在接近極小點(diǎn)的地方，由于鋸齒現(xiàn)象，每次迭代行進(jìn)的距離開始逐漸變小。因而收斂速度不快。 已有結(jié)論表明，最速下降法對(duì)于正定二次函數(shù)關(guān)于任意初始點(diǎ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）會(huì)很快地得到極小點(diǎn)。 1. 基本思想基本思想kx1kxkx( )f x考慮從到的迭代過程。在點(diǎn)處，對(duì)按Taylor級(jí)數(shù)展開到第三項(xiàng)，即1( )( )()() ()()()()2TTkkkkkkf xQ xf xg xxxxxG xxx （3.29） ()kG x( )Q x因?yàn)檎?，所以是正定二次函?shù)。令( )()()()0kkkQ xG xxxg x 得()()()kkkG xxxg x （3.30） ( )Q x1kx由此解出的極小點(diǎn)，記為，即11()()kkkkxxG xg x（3.31） 1kx( )f x*x是極小點(diǎn)的新的近似點(diǎn)。 （3.31）稱為New

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