第二章無約束非線性規(guī)劃[1]

1、第二章第二章 非線性規(guī)劃非線性規(guī)劃2.1 非線性函數(shù)和非線性規(guī)劃的概念非線性函數(shù)和非線性規(guī)劃的概念線性函數(shù)線性函數(shù):(1) f(kx)=kf(x) (2) f(x1+x2)=f(x1)+f(x2)則非線性函數(shù)就是不滿足以上兩個(gè)條件的函則非線性函數(shù)就是不滿足以上兩個(gè)條件的函數(shù)數(shù)非線性規(guī)劃：非線性規(guī)劃：如果目標(biāo)函數(shù)或約束條件中，如果目標(biāo)函數(shù)或約束條件中，有一個(gè)或多個(gè)是變量的非線性函數(shù)，就稱為有一個(gè)或多個(gè)是變量的非線性函數(shù)，就稱為非線性規(guī)劃非線性規(guī)劃非線性規(guī)劃問題非線性規(guī)劃問題例例1 1 曲線的最優(yōu)擬合問題曲線的最優(yōu)擬合問題t n1i221)( min3 itciietcc 例例2 2 構(gòu)件容積問題

2、構(gòu)件容積問題x1x2x30, 0 2 . .) 3/1 ( max212121222211221xxSxxxxaxxtsxxaV非線性規(guī)劃問題非線性規(guī)劃問題例例3 3非線性規(guī)劃問題非線性規(guī)劃問題例例3 3非線性規(guī)非線性規(guī)劃劃通常情況下，目標(biāo)函數(shù)通常情況下，目標(biāo)函數(shù)f(x)和約束條件和約束條件hi(X)和和gi(X)為自變量的非線性函數(shù)為自變量的非線性函數(shù)非線性規(guī)非線性規(guī)劃劃Xx ULP的可行解或可行點(diǎn)的可行解或可行點(diǎn)qjxhpixgRxXjin,.,1, 0)(,.,1, 0)(約束集或可行域約束集或可行域向量化表示向量化表示當(dāng)當(dāng)p=0,q=0時(shí)，稱為時(shí)，稱為無約束非線性規(guī)劃無約束非線性規(guī)劃或

3、者或者無約束最優(yōu)無約束最優(yōu)化問題化問題。否則，稱為否則，稱為約束非線性規(guī)劃約束非線性規(guī)劃或者或者約束最優(yōu)化問題約束最優(yōu)化問題。最優(yōu)解和極小點(diǎn)最優(yōu)解和極小點(diǎn)最優(yōu)解和極小點(diǎn)最優(yōu)解和極小點(diǎn)極值存在的條件極值存在的條件必要條件必要條件：設(shè)是：設(shè)是n n維歐氏空間的某維歐氏空間的某一區(qū)域，一區(qū)域，f(Xf(X) )為定義在上的實(shí)值函數(shù)，為定義在上的實(shí)值函數(shù)，是區(qū)域的內(nèi)點(diǎn)，若是區(qū)域的內(nèi)點(diǎn)，若f(f(）在）在處處可微，且在該點(diǎn)取得局部極小值，則必可微，且在該點(diǎn)取得局部極小值，則必有有1 . 50*)(*)(*)(21nxXfxXfxXf或或2.50*)(xf極值存在的條件極值存在的條件其中，其中，0*)(,

4、*)(,*)(*)(21nxXfxXfxXfxf為函數(shù)為函數(shù)f(xf(x) )在在處的梯度，梯度的方向處的梯度，梯度的方向?yàn)闉閒(Xf(X) )的等值面（等值線）的法線方向，的等值面（等值線）的法線方向，沿這個(gè)方向函數(shù)值增加最快沿這個(gè)方向函數(shù)值增加最快滿足上式的點(diǎn)稱為滿足上式的點(diǎn)稱為駐點(diǎn)駐點(diǎn)，在區(qū)域內(nèi)部，在區(qū)域內(nèi)部，極值點(diǎn)必為駐點(diǎn)；但駐點(diǎn)不一定是極值點(diǎn)必為駐點(diǎn)；但駐點(diǎn)不一定是極值極值點(diǎn)點(diǎn)14二次型二次型二次型是X=(x1,x2,xn)T的二次齊次函數(shù)：ninjTjiijnnnnnnnAXXxxaxaxxaxxaxaxxaxxaxaXf11222322322221121122111.2.22.2

5、)(aij=aji,A為n*n對(duì)稱矩陣。若A的所有元素均為實(shí)數(shù)，則為實(shí)二次型。一個(gè)二次型唯一對(duì)應(yīng)一個(gè)對(duì)稱矩陣，反之，一個(gè)對(duì)稱矩陣也唯一確定一個(gè)二次型。二次型（對(duì)稱矩陣）正定，負(fù)定，不定。半正定，半負(fù)定。二次型二次型二次型正定的充要條件，是它的矩陣的左上角各階主子式都大于零。二次型負(fù)定的充要條件，是它的矩陣的左上角各階主子式都負(fù)、正相間。 例：判定正負(fù)性。 402062225A極值存在的條件極值存在的條件充分條件充分條件：設(shè)是：設(shè)是n n維歐氏空間的某一維歐氏空間的某一區(qū)域，區(qū)域，f(Xf(X) )為定義在上的實(shí)值函數(shù)，為定義在上的實(shí)值函數(shù)，是區(qū)域的內(nèi)點(diǎn)，是區(qū)域的內(nèi)點(diǎn)，f(f(）在上二次連）在上

6、二次連續(xù)可微，若續(xù)可微，若f(）在）在且處滿足（且處滿足（5 5）或（或（5 5）式，且對(duì)任何非零矢量均有）式，且對(duì)任何非零矢量均有則則f(xf(x) )在取嚴(yán)格局部極小值，此處在取嚴(yán)格局部極小值，此處（x x* *) )為為f(xf(x) )在點(diǎn)在點(diǎn)處的海賽處的海賽（HesseHesse) )矩陣矩陣) 3 . 5(0*)(ZxHZT極值存在的條件極值存在的條件此處（此處（x x* *) )為為f(xf(x) )在點(diǎn)在點(diǎn)處的海賽處的海賽（HesseHesse) )矩陣矩陣)4 .5(*)(*)(*)(*)(*)(*)(*)(*)(*)(*)(2222122222212212212212nnn

7、nnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxH極值存在的條件極值存在的條件例求目標(biāo)函數(shù)例求目標(biāo)函數(shù)的梯度和的梯度和HesseHesse矩陣矩陣解解: :因?yàn)橐驗(yàn)?, ,所以所以3123332122223213112464624xxxxxfxxxxfxxxxxf23132221233241432)(xxxxxxxxxxf3123321222321312464624)(xxxxxxxxxxxxf極值存在的條件極值存在的條件又因?yàn)橛忠驗(yàn)樗运?23232222223312121222121226, 4,122,2,212xxfxxfxxfxxxfxxxfxxxf1321

8、3122122642412222212)(xxxxxxxxxf即為即為HesseHesse矩陣矩陣極值存在的條件極值存在的條件例例2 2試研究函數(shù)試研究函數(shù)f(xf(x1 1,x,x2 2)=x)=x2 22 2-x-x1 1的駐的駐點(diǎn)點(diǎn)解：令解：令02),(02),(22211121xxxxfxxxxf得（，）點(diǎn)為駐點(diǎn)，得（，）點(diǎn)為駐點(diǎn)，x1=0 x1=0是一無函數(shù)是一無函數(shù)f(x1,0)=-xf(x1,0)=-x1 12 2的極大點(diǎn)，而的極大點(diǎn)，而x2=0 x2=0卻是一元函數(shù)卻是一元函數(shù)f(0,x2)=xf(0,x2)=x2 22 2的極小點(diǎn)，即：的極小點(diǎn)，即：), 0 () 0 , 0

9、 () 0 ,(21xffxf故駐點(diǎn)（，）不是極值點(diǎn)，而是一個(gè)鞍點(diǎn)故駐點(diǎn)（，）不是極值點(diǎn)，而是一個(gè)鞍點(diǎn)極值存在的條件極值存在的條件例例3 3試求函數(shù)試求函數(shù)f(xf(x1 1,x,x2 2)=2x)=2x1 12 2-8x-8x1 1+2x+2x2 2-4x-4x2 2+20+20的的極值和極值點(diǎn)極值和極值點(diǎn)解：令解：令044),(084),(22211121xxxxfxxxxf得（得（2,12,1）點(diǎn)為駐點(diǎn)）點(diǎn)為駐點(diǎn)0),(),(4),(,04),(21212212122221221212xxxxfxxxxfxxxfxxxf極值存在的條件極值存在的條件其海賽矩陣之行列式其海賽矩陣之行列式可知

10、（可知（2,12,1）點(diǎn)為極小點(diǎn)）點(diǎn)為極小點(diǎn), ,其極小值為其極小值為: :0164004102014122822) 1 , 2(22f凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃q凸函數(shù)及其性質(zhì)凸函數(shù)及其性質(zhì)q凸規(guī)劃及其性質(zhì)凸規(guī)劃及其性質(zhì)凸函數(shù)及其性質(zhì)凸函數(shù)及其性質(zhì)凸函數(shù)的性質(zhì)凸函數(shù)的性質(zhì)凸函數(shù)的判定凸函數(shù)的判定凸函數(shù)的判定凸函數(shù)的判定例例4 4 判定下述函數(shù)是凸函數(shù)還是凹函數(shù)判定下述函數(shù)是凸函數(shù)還是凹函數(shù)解解: :因?yàn)橐驗(yàn)?, 4, 0614, 261222122222122211 xxfxxfxfxfxxfxxf10223)()(2221212, 1xxxxxxfxf0244006H其海賽陣的行列式為：

11、其海賽陣的行列式為：故其海賽陣處處正定，由定理故其海賽陣處處正定，由定理2.2.42.2.4得得f(Xf(X) )為嚴(yán)格凸為嚴(yán)格凸函數(shù)函數(shù)凸函數(shù)的判定凸函數(shù)的判定例例5 5 試證明為凹函數(shù)試證明為凹函數(shù)證證: (1): (1)首先由定義來證明，任取兩點(diǎn)首先由定義來證明，任取兩點(diǎn)a1,a2,a1,a2,看下式看下式是否成立？是否成立？2221)(xxXf或或由于，故顯然，不管由于，故顯然，不管a a1 1,a,a2 2取什么值，總有（）式成立，故取什么值，總有（）式成立，故f(xf(x1 1)=-x)=-x1 12 2為凹為凹函數(shù)，同理可證函數(shù)，同理可證f(xf(x2 2)=-x)=-x2 22

12、 2也是凹函數(shù)也是凹函數(shù)2212221)(1 ()1 (aaaa0)()(2)(222221221aaaa或或)3(0)(2212aa1002凸函數(shù)的判定凸函數(shù)的判定證證: (: () )用定理用定理2.2.42.2.4來證明，由于來證明，由于故海賽矩陣處處負(fù)定，故故海賽矩陣處處負(fù)定，故f(Xf(X) )為嚴(yán)格凹函數(shù)為嚴(yán)格凹函數(shù)0.02,022,21222122222122211xxfxfxfxfxxfxxf042002H凸函數(shù)的判定凸函數(shù)的判定證證: (: () )用定理用定理5.2.35.2.3來證明，任意取第一點(diǎn)來證明，任意取第一點(diǎn)，第二點(diǎn)，這樣，第二點(diǎn)，這樣TbaX),(11) 1 (

13、TbaX),(22) 2(2121) 1 ()(baXf2222) 2()(baXfTxxXf)2,2()(21TbaXf)2,2()(11) 1 (現(xiàn)看下式是否成立現(xiàn)看下式是否成立12121121212222)22(bbaabababa)(2)(212112121212222bbbaaababa0)2()2(212122212122bbbbaaaa或或或或證證: (: () )用定理用定理2.2.32.2.3來證明，任意取第一點(diǎn)來證明，任意取第一點(diǎn)，第二點(diǎn)，這樣，第二點(diǎn)，這樣TbaX),(11) 1 (凸函數(shù)的判定凸函數(shù)的判定不管不管a a1 1,a,a2 2和和b b1 1,b,b2 2取

14、什么值，上式均成立從取什么值，上式均成立從而證明而證明f(f(）是凹函數(shù)）是凹函數(shù)0)()(212212bbaa或或凸規(guī)劃及其性質(zhì)凸規(guī)劃及其性質(zhì) qjxhpixgtsxfji,.10,)( (MP) ,.,1, 0)( .)( min qjxhpixgRxXjin,.,1, 0)(,.,1, 0)(約束集如果如果(MP)的約束集的約束集X是凸集，目標(biāo)函數(shù)是凸集，目標(biāo)函數(shù)f是是X上的凸函數(shù)，則上的凸函數(shù)，則(MP)叫做叫做非線性非線性凸規(guī)劃凸規(guī)劃，或簡(jiǎn)稱為，或簡(jiǎn)稱為凸規(guī)劃凸規(guī)劃。定理定理 2.2.6 凸規(guī)劃的任一局部最優(yōu)解都是凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。它的整體最優(yōu)解。凸規(guī)劃及其性

15、質(zhì)凸規(guī)劃及其性質(zhì)由于線性函數(shù)也既是凸函數(shù)，又是凹函數(shù)，由于線性函數(shù)也既是凸函數(shù)，又是凹函數(shù)，故線性規(guī)劃也屬于凸規(guī)劃故線性規(guī)劃也屬于凸規(guī)劃凸規(guī)劃及其性質(zhì)凸規(guī)劃及其性質(zhì) 0,01)(0244)(21221221112221xxxxxgxxxgxxxXfMin例例6 6試分析非線性規(guī)劃試分析非線性規(guī)劃解：解：f(Xf(X) )和和g g2 2(X)(X)的海賽矩陣的行列式是的海賽矩陣的行列式是042002)()()()(222122212212xXfxxXfxxXfxXfH00002)()()()(22221222212221222xXgxxXgxxXgxXgg凸規(guī)劃及其性質(zhì)凸規(guī)劃及其性質(zhì)由上可知由

16、上可知f(Xf(X) )為嚴(yán)格凸函數(shù)為嚴(yán)格凸函數(shù),g,g2 2(x)(x)為凹函數(shù)，為凹函數(shù)，由于為線性函數(shù)，故上述約束條件構(gòu)成的可由于為線性函數(shù)，故上述約束條件構(gòu)成的可行域?yàn)橥辜?，這是一個(gè)凸規(guī)劃，點(diǎn)為最優(yōu)行域?yàn)橥辜?，這是一個(gè)凸規(guī)劃，點(diǎn)為最優(yōu)點(diǎn)：點(diǎn)：（0.58,1.34)0.58,1.34)T T, ,目標(biāo)函數(shù)的最優(yōu)目標(biāo)函數(shù)的最優(yōu)值為值為f(Xf(X* *)=3.8.)=3.8.g1(X)g2(X)=0C目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線算法及有關(guān)概念算法及有關(guān)概念最優(yōu)化問題的數(shù)值解法及理論根據(jù)：最優(yōu)化問題的數(shù)值解法及理論根據(jù)：1 在集合上的迭代算法是指：在集合上的迭代算法是指：開始：選定一個(gè)初始點(diǎn)

17、開始：選定一個(gè)初始點(diǎn) ,置置k=0,然后再按某種規(guī)則把然后再按某種規(guī)則把k次迭代的次迭代的x(k)映射為新映射為新的一點(diǎn)的一點(diǎn)x(k+1),記為這稱為第記為這稱為第k+1次迭次迭代這個(gè)過程無限進(jìn)行下去，就產(chǎn)生一個(gè)點(diǎn)列代這個(gè)過程無限進(jìn)行下去，就產(chǎn)生一個(gè)點(diǎn)列，其中規(guī)則稱為算法若收斂于問題，其中規(guī)則稱為算法若收斂于問題的最優(yōu)解，就稱算法在上是收斂的，否則的最優(yōu)解，就稱算法在上是收斂的，否則是發(fā)散的是發(fā)散的)0(x)(kx)(kx)()() 1(kkxAx算法及有關(guān)概念算法及有關(guān)概念一種算法除了滿足計(jì)算終止準(zhǔn)則的迭代點(diǎn)外一種算法除了滿足計(jì)算終止準(zhǔn)則的迭代點(diǎn)外,還還應(yīng)滿足應(yīng)滿足:下降算法下降算法:若對(duì)于

18、每個(gè)若對(duì)于每個(gè)k,都有都有 ,則稱則稱A為下降迭代算法為下降迭代算法,簡(jiǎn)稱下降算法簡(jiǎn)稱下降算法.許多最優(yōu)化方法都采用將多維問題轉(zhuǎn)化為一維許多最優(yōu)化方法都采用將多維問題轉(zhuǎn)化為一維問題的方法來求解問題的方法來求解.)()()()1(kkxfxf算法及有關(guān)概念算法及有關(guān)概念 如如:設(shè)第設(shè)第k次迭代點(diǎn)次迭代點(diǎn)xk已求得已求得,若它不滿足終止準(zhǔn)若它不滿足終止準(zhǔn)則則,在該點(diǎn)必存在下降方向在該點(diǎn)必存在下降方向.對(duì)于可微目標(biāo)函數(shù)對(duì)于可微目標(biāo)函數(shù),即即是滿足是滿足 的的d. 按某種規(guī)則從中選取一個(gè)按某種規(guī)則從中選取一個(gè),例如例如dk,再沿這個(gè)方再沿這個(gè)方向適當(dāng)邁進(jìn)一步向適當(dāng)邁進(jìn)一步,即在直線即在直線 上適當(dāng)確定

19、上適當(dāng)確定一個(gè)新點(diǎn)一個(gè)新點(diǎn) , 使使 那我們就說完成了第那我們就說完成了第k+1次迭代次迭代,其中其中 稱為步長(zhǎng)因子稱為步長(zhǎng)因子.0)()(dxfTkkkdxx)(kkkkdxx)() 1()()()()()() 1(kkkkkxfdxfxf)(k算法及有關(guān)概念算法及有關(guān)概念迭代過程中應(yīng)滿足兩個(gè)準(zhǔn)則迭代過程中應(yīng)滿足兩個(gè)準(zhǔn)則: 1 是下降方向是下降方向dk的選取的選取; 2是步長(zhǎng)因子是步長(zhǎng)因子 的選取的選取 各種迭代法的區(qū)別就在于得出方向各種迭代法的區(qū)別就在于得出方向 dk 與步與步 長(zhǎng)長(zhǎng) 的方式不同的方式不同.對(duì)于非線性規(guī)劃對(duì)于非線性規(guī)劃,總結(jié)出總結(jié)出:)(k)(k非線性規(guī)劃方法概述非線性規(guī)劃

20、方法概述非線性規(guī)劃基本迭代格式非線性規(guī)劃基本迭代格式無約束優(yōu)化無約束優(yōu)化: :最優(yōu)解的分類和條件最優(yōu)解的分類和條件)(xfMinx給定一個(gè)函數(shù)給定一個(gè)函數(shù) f( (x),),尋找尋找 x* 使得使得 f( (x*)最小，即最小，即nTnxxxx),(21其中其中局部最優(yōu)解局部最優(yōu)解全局最優(yōu)解全局最優(yōu)解必要條件必要條件0),()(1*Txxnffxfx*f(x)xlxgo充分條件充分條件0)(, 0)(*2*xfxfHessian陣陣nnjixxff22最優(yōu)解在可行域邊界上取得時(shí)不能用無約束優(yōu)化方法求解最優(yōu)解在可行域邊界上取得時(shí)不能用無約束優(yōu)化方法求解2 2 迭代法中直線搜索及其性質(zhì)：迭代法中直

21、線搜索及其性質(zhì)： 在搜索方向已經(jīng)確定的前提下在搜索方向已經(jīng)確定的前提下,步長(zhǎng)因子的步長(zhǎng)因子的選取有多種方法選取有多種方法,如如 i)取步長(zhǎng)因子為某個(gè)常數(shù)取步長(zhǎng)因子為某個(gè)常數(shù),但不能保證使目標(biāo)函但不能保證使目標(biāo)函數(shù)值下降數(shù)值下降; ii)可接受點(diǎn)算法，只要能使目標(biāo)函數(shù)下降，可可接受點(diǎn)算法，只要能使目標(biāo)函數(shù)下降，可任意選取步長(zhǎng)任意選取步長(zhǎng);iii)基于沿搜索方向使目標(biāo)函數(shù)值下降最多，基于沿搜索方向使目標(biāo)函數(shù)值下降最多，沿射線沿射線 求目標(biāo)函數(shù)的極小值：求目標(biāo)函數(shù)的極小值：)()(kkdXX)(min:)()(kkkdxf2 2 迭代法中直線搜索及其性質(zhì)：迭代法中直線搜索及其性質(zhì)： 由于這項(xiàng)工作是求

22、以為變量的一元函數(shù)由于這項(xiàng)工作是求以為變量的一元函數(shù)的極小點(diǎn)，故稱這一過程為的極小點(diǎn)，故稱這一過程為一維搜索一維搜索（線搜索線搜索），這），這樣確定的步長(zhǎng)為樣確定的步長(zhǎng)為最佳步長(zhǎng)最佳步長(zhǎng),實(shí)際計(jì)算中常用此方法實(shí)際計(jì)算中常用此方法.一維搜索有個(gè)性質(zhì)：在搜索方向上所得最優(yōu)點(diǎn)處一維搜索有個(gè)性質(zhì)：在搜索方向上所得最優(yōu)點(diǎn)處的梯度和搜索方向正交的梯度和搜索方向正交定理：設(shè)目標(biāo)函數(shù)定理：設(shè)目標(biāo)函數(shù)f(X)具有一階連續(xù)偏導(dǎo)數(shù)，具有一階連續(xù)偏導(dǎo)數(shù)，x(k+1)按下列規(guī)劃產(chǎn)生：按下列規(guī)劃產(chǎn)生：則有則有k)()()(kkkdXf)()()1()()()(min:kkkkkkkdXXdxf0)()()1(kTkdXf

23、3 3 收斂速度收斂速度 一個(gè)算法不光能收斂于解一個(gè)算法不光能收斂于解, ,還必須以還必須以較快的速度收斂于解較快的速度收斂于解, ,這才是這才是好的算法好的算法; ; 我們用以下收斂的階來我們用以下收斂的階來度量度量一個(gè)算一個(gè)算法的收斂速度法的收斂速度. .3 3 收斂速度收斂速度 定義定義: :設(shè)序列設(shè)序列 收斂于收斂于 , ,而且而且 若若 , ,則稱則稱 為為線性收斂線性收斂的的, , 為收斂比為收斂比; ; 若若 , ,則稱則稱 為為超線性收斂超線性收斂. . 定義定義: :設(shè)序列設(shè)序列 收斂于收斂于 , ,若對(duì)于某若對(duì)于某個(gè)實(shí)數(shù)個(gè)實(shí)數(shù) , ,有有 則稱序列則稱序列 為為 階收斂的階

24、收斂的)(kx)(kxxxxxxkkk1lim10)(kx0)(kx)(kxx1p1limkpkkxxxx0p3 3 收斂速度收斂速度 一般來說一般來說, ,線性收斂是線性收斂是比較慢比較慢的的, ,而而二階收斂則是二階收斂則是很快的很快的, ,超線性收斂超線性收斂居中居中, ,如果一個(gè)算法具有如果一個(gè)算法具有超線性以上的收斂超線性以上的收斂速速度度, ,我們就認(rèn)為它是一個(gè)很好的算法了我們就認(rèn)為它是一個(gè)很好的算法了. .50因真正的極值點(diǎn)事先并不知道，故在實(shí)用上只能根據(jù)相繼兩次迭代得到的計(jì)算結(jié)果來判斷是否已達(dá)到要求，從而建立終止迭代計(jì)算的準(zhǔn)則。常用的終止迭代準(zhǔn)則有：（1）根據(jù)相繼兩次迭代結(jié)果的

25、絕對(duì)誤差。4. 終止迭代準(zhǔn)則終止迭代準(zhǔn)則1)()1(kkXX2)()1()()(kkXfXf（2）根據(jù)相繼兩次迭代結(jié)果的相對(duì)誤差。3)()()1(kkkXXX4)()()1()()()(kkkXfXfXf（3）根據(jù)函數(shù)梯度的模足夠小。5)()(kXf迭代終止準(zhǔn)則 點(diǎn)距準(zhǔn)則 函數(shù)值下降準(zhǔn)則 梯度準(zhǔn)則2.2 一維搜索方法一維搜索方法精確一維搜索方法精確一維搜索方法 0.618法法 Newton法法非精確一維搜索方法非精確一維搜索方法 Goldstein法法 Armijo法法一維搜索一維搜索 上節(jié)提到上節(jié)提到,在大多數(shù)無約束極值的算法中在大多數(shù)無約束極值的算法中,為了確定為了確定最優(yōu)解最優(yōu)解,一般用

26、解析的方法是很難得到的一般用解析的方法是很難得到的,即精確解通常即精確解通常是計(jì)算不出來的是計(jì)算不出來的,故我們常采用的是數(shù)值的方法來得到故我們常采用的是數(shù)值的方法來得到其近似解其近似解,上節(jié)我們提到上節(jié)我們提到,數(shù)值解法最常用的一種方法是數(shù)值解法最常用的一種方法是迭代法迭代法. 為了確定極小化點(diǎn)列為了確定極小化點(diǎn)列,要沿逐次確定的系列射線求要沿逐次確定的系列射線求極小點(diǎn)極小點(diǎn),即所謂的一維搜索即所謂的一維搜索. 一維搜索可歸結(jié)為單變量函數(shù)求極小的問題一維搜索可歸結(jié)為單變量函數(shù)求極小的問題,設(shè)目標(biāo)設(shè)目標(biāo)函數(shù)為函數(shù)為 ,過點(diǎn)過點(diǎn) 沿方向沿方向 的直線可用點(diǎn)集表示為的直線可用點(diǎn)集表示為: ,)()

27、(kkdxxxL)(xf)(kd)(kx 求 在直線L上的極小點(diǎn)轉(zhuǎn)化為求一元函數(shù) 的極小點(diǎn). 如果 的極小點(diǎn)為 ,通常稱 為沿方向 的步長(zhǎng)因子 或簡(jiǎn)稱步長(zhǎng). 函數(shù) 在直線上的極小點(diǎn)就是 一維搜索的方法一般有以下幾類： 1. 數(shù)學(xué)分析中所講的方法，即解方程，此方法稱為精確解方程，此方法稱為精確線性搜索線性搜索. 2. 試探法試探法: 按照某種方式試探點(diǎn),通過一系列試探點(diǎn)的比較確定極小點(diǎn).)(xf)()()()(kkdxf)(kk)(kd)(kd)1( kx)()(kkkdx 3. 函數(shù)逼近法函數(shù)逼近法: 用比較簡(jiǎn)單的曲線近似代替原來的曲線,用近似曲線的極小點(diǎn) 來估計(jì)原來的極小點(diǎn). 下面我們將分別

28、具體介紹幾種方法: 一 .平分法 根據(jù)以前我們所學(xué)習(xí)的知識(shí),我們知道，在 的極小點(diǎn) 處 有 ,并且當(dāng) 時(shí),函數(shù)是遞減的,即 ;而 當(dāng) 時(shí),函數(shù)遞增,即 . 注: 因?yàn)?為極小點(diǎn),若: 此時(shí) 為極大點(diǎn).)(xfx0)( xf0)( xf xx0)( xfxxxxfxxxf, 0)( , 0)( x 我們找到了一個(gè)區(qū)間 ,具有性質(zhì) 則在 間必然有 的極小點(diǎn) ,且 .為了找到 , 我們?nèi)?. 1. 若 ,則在 中有極小點(diǎn), 2 .若 ,則在 中有極小點(diǎn).y=f(x)00 xy)(11xfy xxtgxfxf)0( , 0)( )(1xxtgxfxf)0( , 0)( )(2,ba. 0)( , 0)

29、( bfafba,)(xfx0)( xfx2/ )(0bax0)( 0 xf,0 xa0)( 0 xf,0bxx)(22xfy 若情形1滿足時(shí),此時(shí)以 作為新的區(qū)間; 若情形2滿足時(shí),此時(shí)以 作為新的區(qū)間. 繼續(xù)上述過程,逐步將區(qū)間換小,當(dāng)區(qū)間 充分小時(shí),或者當(dāng) 充分小時(shí),即可將區(qū)間 中點(diǎn)取做極小點(diǎn)的近似,此時(shí)有:0 xy0 xy)(xfy )(xfy aa0 x0 xbb,0 xa,0bx,ba)( 0 xf,ba2/ )(2/ )(abbax 注:也可以用以下的收斂準(zhǔn)則: 1 . 成立, 2. 成立. 但是我們?nèi)绾蝸泶_定初始區(qū)間 呢?下面我們將解決這個(gè)問題。 ab)( 0 xf,ba搜索區(qū)

30、間 的選取可采用如下的進(jìn)退算法：給定初始點(diǎn) ，初始步長(zhǎng) ，求搜索區(qū)間 ：1）計(jì)算 2）若 ,(此時(shí)稱搜索成功，下一步搜索就大步前進(jìn))，則步長(zhǎng)加倍，計(jì)算 若 ， 則 ；否則步長(zhǎng)再加倍，并重復(fù)上面的運(yùn)算；,bath,ba)(),(htt)()(htt)3(ht )3()(hththtbta3,3）若 ,(此時(shí)稱搜索失敗，下一步就小步后退),則步長(zhǎng)縮為原來的1/4，并改變符號(hào)，即新步長(zhǎng)為 ，若 則 ；否則步長(zhǎng)再加倍， 繼續(xù)后退。)()(htt4h),4()(htthtbhta,4二、二、0.618法（近似黃金分割法）法（近似黃金分割法）上的單谷函數(shù)上的單谷函數(shù)為為稱稱上嚴(yán)格遞增上嚴(yán)格遞增且在且在上嚴(yán)

31、格遞減上嚴(yán)格遞減在在使得函數(shù)使得函數(shù)如果如果,)(,)(,batbttatbat 的單谷區(qū)間。的單谷區(qū)間。稱為稱為)(,tba 單谷函數(shù)單谷函數(shù)上唯一的極小點(diǎn)。上唯一的極小點(diǎn)。在在為為顯然此時(shí)顯然此時(shí),)(batt 退 出前一頁后一頁搜索法求解：搜索法求解：(t)min0 t(t)minmax0 tt 或或基本過程：基本過程：給出給出a,b,使得使得t*在在a,b中。中。a,b稱為稱為搜索區(qū)間搜索區(qū)間。迭代縮短迭代縮短a,b的長(zhǎng)度。的長(zhǎng)度。當(dāng)當(dāng)a,b的長(zhǎng)度小于某個(gè)預(yù)設(shè)的值，或者導(dǎo)數(shù)的絕的長(zhǎng)度小于某個(gè)預(yù)設(shè)的值，或者導(dǎo)數(shù)的絕對(duì)值小于某個(gè)預(yù)設(shè)的正數(shù)，則迭代終止。對(duì)值小于某個(gè)預(yù)設(shè)的正數(shù)，則迭代終止。退

32、 出前一頁后一頁假定：已經(jīng)確定了單谷區(qū)間假定：已經(jīng)確定了單谷區(qū)間a,b(t)min0 t(t)minmax0 tt (t)min bta )(1t )(2t t)(1t )(2t tt1t2ababt1t2新搜索區(qū)間為新搜索區(qū)間為a,t2新搜索區(qū)間為新搜索區(qū)間為t1,b退 出前一頁后一頁區(qū)間縮小比例的確定：區(qū)間縮小比例的確定：區(qū)間縮短比例為區(qū)間縮短比例為(t2-a)/(b-a)縮短比例為縮短比例為(b-t1)/(b-a)縮短比例縮短比例 滿足：滿足：每次插入搜索點(diǎn)使得兩個(gè)區(qū)間每次插入搜索點(diǎn)使得兩個(gè)區(qū)間a,t2和和t1,b相等；相等；每次迭代都以相等的比例縮小區(qū)間。每次迭代都以相等的比例縮小區(qū)間

33、。618. 0215 縮短比例縮短比例0.618法法)(1t )(2t )(1t )(2t t1t2ababt1t2退 出前一頁后一頁確定確定a,b,計(jì)算探索點(diǎn)計(jì)算探索點(diǎn)t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解題步驟：法解題步驟：)()(21tt 是是否否 at2是是停止，輸出停止，輸出t1否否以以a,t2為新的搜索區(qū)間為新的搜索區(qū)間 1tb是是停止，輸出停止，輸出t2否否以以t1,b為新的搜索區(qū)間為新的搜索區(qū)間退 出前一頁后一頁例：例：5 . 0,3 , 0 12)(min 30精度精度其中單谷區(qū)間其中單谷區(qū)間求解求解 tttt 解：解：t1t2)(1t )

34、(2t 30t 1、第一輪：、第一輪：t1=1.146, t2=1.8546648. 3)(,2131. 0)(21 tt t200.5退 出前一頁后一頁2、第二輪：、第二輪：t2=1.146, t1=0.7082131. 0)(0611. 0)(21 tt t20=1.1460.53、第三輪：、第三輪：t1=0.438, t2=0.7082082. 0)(0611. 0)(12 tt b-t1=1.146-0.4380.51.8540t t2t11.4160 tt2t1退 出前一頁后一頁4、第四輪：、第四輪：t2=0.876, t1=0.7080798. 0)(0611. 0)(21 tt

35、b-t1=1.146-0.7080.5輸出：輸出：t*=t2=0.876為最優(yōu)解，最優(yōu)值為為最優(yōu)解，最優(yōu)值為-0.07980 1.416tt1t2退 出前一頁后一頁68例例 求解求解 f(xf(x)=-18x)=-18x2 2+72x+28 +72x+28 的極大值點(diǎn)，的極大值點(diǎn)， 0.10.1，起始搜索區(qū)間為，起始搜索區(qū)間為0,30,3解：用間接法：令解：用間接法：令 f f(x(x)=-36x+72=0)=-36x+72=0，得駐點(diǎn)，得駐點(diǎn) x=2x=2 又因?yàn)橛忠驗(yàn)閒 f(x(x)=-36)=-360 0，故，故 x=2 x=2 為為f(xf(x) )的極大值點(diǎn)，的極大值點(diǎn)，f fmax

36、max=100=100 用直接法中的黃金分割法：令用直接法中的黃金分割法：令 n-1n-1= = ，得，得n=1+(lgn=1+(lg )/)/(lg(lg )5.78442)5.78442 約約6 6步即可，計(jì)算結(jié)果見下表：步即可，計(jì)算結(jié)果見下表：ka ak kb bk kf(ak)f(bk)pk= bk- akpk/ p0 x x1 1k k= =ak+ pkx x2 2k k= =bk- pkf (x x2 2k k) f (x x1 1k k)0032882311.8541.14686.999.62f(xf(x) )x xo o3 3x x1 1x x2 2100f ,2x*max*

37、1 1.146386.9821.8540.6182.2921.85499.62 98.462 1.1462.29286.998.461.1460.3821.8541.58496.8999.623 1.5842.29296.8998.460.7080.2362.0221.85499.62 99.994 1.8542.29299.6298.460.4380.1462.1252.02299.99 98.725 1.8542.12599.6299.720.2710.0903三、三、Newton法法0)()(),(min ttt 二次可微，二次可微，其中其中考慮考慮Newton法基本思想：法基本思想：用

38、探索點(diǎn)用探索點(diǎn)tk處的二階處的二階Taylor展開式近似代替目標(biāo)展開式近似代替目標(biāo)函數(shù)，以展開式的最小點(diǎn)為新的探索點(diǎn)。函數(shù)，以展開式的最小點(diǎn)為新的探索點(diǎn)。2)(21)()()(kkkkkttttttttg 展開式：展開式：)()(:,0)(1kkkktttttg 求導(dǎo)得求導(dǎo)得的點(diǎn)的點(diǎn)的最小點(diǎn)即導(dǎo)數(shù)為的最小點(diǎn)即導(dǎo)數(shù)為退 出前一頁后一頁解題步驟：解題步驟：給定初始點(diǎn)給定初始點(diǎn)t1和精度和精度 1|( )|t 是是是是停止，輸出停止，輸出t10)(1 t 是是否否停止，解題失敗停止，解題失敗)()(1112tttt 計(jì)計(jì)算算21|tt 否否停止，輸出停止，輸出t2否否退 出前一頁后一頁例：例： tx

39、dxt0arctan)(min 求解求解解：解：取取t1=1,計(jì)算：計(jì)算：211)(,arctan)(tttt 迭代過程如下表：迭代過程如下表：1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411kkt)(kt )(kt 退 出前一頁后一頁3、非精確一維搜索法、非精確一維搜索法數(shù)值方法的關(guān)鍵是從一個(gè)點(diǎn)迭代到下一個(gè)點(diǎn)。數(shù)值方法的關(guān)鍵是從一個(gè)點(diǎn)迭代到下一個(gè)點(diǎn)。確定下一個(gè)點(diǎn)的關(guān)鍵是確定搜索方向和步長(zhǎng)確定下一個(gè)點(diǎn)的關(guān)鍵是確定搜索方向和步長(zhǎng)如果已經(jīng)確定了搜索方向如果已經(jīng)確定了搜索方向pk,則只要確定一個(gè)最佳則只要確定一個(gè)最佳的步長(zhǎng)即可。的步

40、長(zhǎng)即可。所謂的最佳步長(zhǎng)即是在所謂的最佳步長(zhǎng)即是在pk方向上走一個(gè)最好的長(zhǎng)方向上走一個(gè)最好的長(zhǎng)度使得目標(biāo)函數(shù)下降的最多，即下述的最優(yōu)化問題：度使得目標(biāo)函數(shù)下降的最多，即下述的最優(yōu)化問題：)(min0kkttpxf 這樣的最優(yōu)化問題不需要太高的精度，只要滿這樣的最優(yōu)化問題不需要太高的精度，只要滿足某些更寬松的精度要求即可。足某些更寬松的精度要求即可。這樣的搜索方法稱之為這樣的搜索方法稱之為非精確一維搜索方法非精確一維搜索方法退 出前一頁后一頁Goldstein法原理：法原理：yt0)(ty bcda,dcbatk 在下面的直線上方。在下面的直線上方。同時(shí)保證同時(shí)保證在上面的直線的下方，在上面的直線

41、的下方，使得使得選取選取)()(kkkttt Y= (0)+ (0)tY= (0)+ m2 (0)tY= (0)+ m1 (0)t退 出前一頁后一頁是是Goldstein算法算法確定確定m1,m2,t0, a=0,b=+ (t0) (0)+m1 (0)t0 (t0) (0)+m2 (0)t0是是停止停止,輸出輸出t0否否a=a, b=t0, t1=(a+b)/2否否a=t0,b=b, t1=(a+b)/2 (若若b=+,則則t1= a)退 出前一頁后一頁第第 1 步步 給給定定滿滿足足1021 mm的的正正數(shù)數(shù)21,mm，增增大大探探索索點(diǎn)點(diǎn)系系數(shù)數(shù)1 ； 初初始始探探索索點(diǎn)點(diǎn)),0(0 t（

42、或或,0(maxt）。令令 :,0:00ba（或或maxt），0: k 第第 2 步步 計(jì)計(jì)算算)(kt 若若)0()0()(1 kktmt，進(jìn)進(jìn)行行第第 3 步步；否否則則，令令kkkktbaa :,:11 轉(zhuǎn)轉(zhuǎn)第第 4 步步； 第第 3 步步 若若)0()0()(2 kktmt，停停止止迭迭代代，輸輸出出kt。否否則則，令令 kkkkbbta :,:11 若若 1kb，進(jìn)進(jìn)行行第第 4 步步；否否則則，令令1:,:1 kkttkk ，轉(zhuǎn)轉(zhuǎn)第第 2 步步； 第第 4 步步 取取2:111 kkkbat，令令1: kk，轉(zhuǎn)轉(zhuǎn)第第 2 步步。 Goldstein法步驟法步驟Armijo法法)0(

43、 )(ty tmy)0()0( ktkMt取取定定Mm 10，用用一一下下兩兩個(gè)個(gè)式式子子限限定定kt不不太太大大也也不不太太小?。?)0()0()( kkmtt )0()0()( kkmMtMt 82無約束條件下多變量函數(shù)尋優(yōu)無約束條件下多變量函數(shù)尋優(yōu)一、爬山法原理：一、爬山法原理： 通過點(diǎn)的直接移動(dòng)，逐步改善目標(biāo)函數(shù)取值，直至達(dá)到極值點(diǎn)為止。通過點(diǎn)的直接移動(dòng)，逐步改善目標(biāo)函數(shù)取值，直至達(dá)到極值點(diǎn)為止。 由以下二部分組成：由以下二部分組成： 選定搜索方向；選定搜索方向； 在選定的方向上爬山搜索。在選定的方向上爬山搜索。二、變量輪換法二、變量輪換法( (或降維法或降維法):):選擇與坐標(biāo)軸平行

44、的方向?yàn)樗阉鞣较蜻x擇與坐標(biāo)軸平行的方向?yàn)樗阉鞣较?設(shè)設(shè) S=S=f(Xf(X)=f(x)=f(x1 1,x,x2 2, , ,x xn n) )，極值點(diǎn)存在的區(qū)間為，極值點(diǎn)存在的區(qū)間為 x x1 1* * aa1 1,b,b1 1 ，x x2 2* * aa2 2,b,b2 2 ， ，x xn n* * a an n,b,bn n 1 1、原理：從起點(diǎn)、原理：從起點(diǎn) X X(0) (0) 出發(fā)，沿平行于出發(fā)，沿平行于 x x1 1 軸的方向軸的方向P P(1)(1)進(jìn)行一維搜索，進(jìn)行一維搜索， 求得求得 f(Xf(X) ) 在該方向在該方向P(1)P(1)上近似極值點(diǎn)上近似極值點(diǎn) X X(1)

45、 (1) ； 從點(diǎn)從點(diǎn) X X(1) (1) 出發(fā)，沿平行于出發(fā)，沿平行于 x x2 2 軸的方向軸的方向P P(2)(2)進(jìn)行一維搜索，進(jìn)行一維搜索， 求得求得 f(Xf(X) ) 在該方向在該方向P(2)P(2)上近似極值點(diǎn)上近似極值點(diǎn) X X(2) (2) ； 從點(diǎn)從點(diǎn) X X(2) (2) 出發(fā)，照此交替進(jìn)行下去，直至滿足給定的精度出發(fā)，照此交替進(jìn)行下去，直至滿足給定的精度 為止為止 | |f(Xf(X(k(k) ) ) -f(X-f(X(k-1)(k-1)|)| 或或 |S|S(k)(k)-S-S(k-1)(k-1)| | 83 2 2、算法步驟：、算法步驟： 設(shè)設(shè) S=S=f(Xf

46、(X)=f(x)=f(x1 1,x,x2 2) )，極值點(diǎn)存在的區(qū)間為，極值點(diǎn)存在的區(qū)間為x x1 1* * aa1 1,b,b1 1 ，x x2 2* * aa2 2,b,b2 2 第一步：從第一步：從 X X(0)(0)=(x=(x1 1(0)(0),x,x2 2(0)(0) )T T出發(fā)出發(fā) 先固定先固定x x1 1=x=x1 1(0)(0): : 求以求以x x2 2為單變量的目標(biāo)函數(shù)的極值點(diǎn)，為單變量的目標(biāo)函數(shù)的極值點(diǎn)， 得得 X X(1)(1)=(x=(x1 1(0)(0),x,x2 2(1)(1) )T T ，S S(1)(1)=f(X=f(X(1)(1) ) 再固定再固定x x

47、2 2=x=x2 2(1)(1): : 求以求以x x1 1為單變量的目標(biāo)函數(shù)的極值點(diǎn)，為單變量的目標(biāo)函數(shù)的極值點(diǎn)， 得得 X X(2)(2)=(x=(x1 1(2)(2),x,x2 2(1)(1) )T T ，S S(2)(2)=f(X=f(X(2)(2) ) 此時(shí)此時(shí)S S(2)(2)優(yōu)于優(yōu)于S S(1)(1)，且搜索區(qū)間縮短為，且搜索區(qū)間縮短為x x1 1* * x x1 1(2)(2),b,b1 1 ，x x2 2* * x x2 2(1)(1),b,b2 2 第二步：如此交替搜索，直至滿足給定精度第二步：如此交替搜索，直至滿足給定精度 為止為止 | |f(Xf(X(k(k) ) )

48、-f(X-f(X(k-1)(k-1)|)| 或或 |S|S(k)(k)-S-S(k-1)(k-1)| | o ox x1 1X X(0)(0) X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 284例例 求求 S = S = f(xf(x) = x) = x1 12 2 + x+ x2 22 2 - x- x1 1x x2 2 -10 x-10 x1 1 - 4x- 4x2 2 + 60 + 60 的極小值點(diǎn)，的極小值點(diǎn)， =0.01=0.01解：設(shè)起始點(diǎn)解：設(shè)起始點(diǎn) X X(0)(0)=(0,0)=(0,0)T T，用變量輪換法，用變量輪換法計(jì)算：計(jì)算： 先

49、固定先固定x x1 1=x=x1 1(0)(0)=0: =0: 則則 f(0,x2)=x22 - 4x2 +60， 尋優(yōu)得尋優(yōu)得 x x2 2(1)(1)=2=2 于是于是 X X(1)(1)=(x=(x1 1(0)(0),x,x2 2(1)(1) )T T=(0,2)=(0,2)T T ，S S(1)(1)=f(X=f(X(1)(1)=56)=56 再固定再固定x x2 2=x=x2 2(1)(1)=2: =2: 則則 f(x1,2)=x12 - 12x1 +56，尋優(yōu)得尋優(yōu)得 x x1 1(2)(2)=6=6 于是于是 X X(2)(2)=(x=(x1 1(2)(2),x,x2 2(1)(

50、1) )T T=(6,2)=(6,2)T T ，S S(2)(2)=f(X=f(X(2)(2)=20)=20 如此交替搜索，直至滿足給定精度如此交替搜索，直至滿足給定精度 =0.01 =0.01 為止為止 | |f(Xf(X(k(k) ) ) -f(X-f(X(k-1)(k-1)|)|0.01 0.01 或或 |S|S(k)(k)-S-S(k-1)(k-1)| |0.010.01 最后得極小點(diǎn)最后得極小點(diǎn) X X* *=(8,6)=(8,6)T T，f(Xf(X* *)=8)=8o ox x1 1X X(0)(0) X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x

51、2 2計(jì)算結(jié)果見下表：計(jì)算結(jié)果見下表：858)X(f ,)6 ,8(X*T* k固定的固定的x xi i單變量的目標(biāo)函數(shù)單變量的目標(biāo)函數(shù)f(xj)求得極點(diǎn)求得極點(diǎn)xj目標(biāo)值目標(biāo)值S S(k)(k)|S|S( k ) ( k ) - - S S( k-1 )( k-1 )| |12345678x x1 1=x=x1 1(0)(0)=0=0 x x2 2=x=x2 2(1)(1)=2=2x x1 1=x=x1 1(2)(2)=6=6x x2 2=x=x2 2(3)(3)=5=5x x1 1=x=x1 1(4)(4)=7.5=7.5x x2 2=x=x2 2(5)(5)=5.75=5.75x x1

52、1=x=x1 1(6)(6)=7.88=7.88x x2 2=x=x2 2(7)(7)=5.94=5.94f(0,x2)=x22 - 4x2 +60f(x1,2)=x12 - 12x1 +56f(6,x2)=x22 - 10 x2 +36f(x1,5)=x12 - 15x1 +65f(7.5,x2)=x22 11.5x2 +41.25f(x1,5.75)=x12 15.75x1 +70.06f(7.88,x2)=x22 11.88x2 +43.27f(x1,5.94)=x12 15.94x1 +71.50 x x2 2=x=x2 2(1)(1)=2=2x x1 1=x=x1 1(2)(2)=6

53、=6x x2 2=x=x2 2(3)(3)=5=5x x1 1=x=x1 1(4)(4)=7.5=7.5x x2 2=x=x2 2(5)(5)=5.75=5.75x x1 1=x=x1 1(6)(6)=7.875=7.875x x2 2=x=x2 2(7)(7)=5.94=5.94x x1 1=x=x1 1(8)(8)=7.97=7.975620118.758.18758.04698.01178.00293692.250.56250.14060.03520.0088o ox x1 1X X(0)(0) X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 2缺點(diǎn)缺點(diǎn)

54、：很大程度上取決于目標(biāo)函數(shù)性質(zhì)。：很大程度上取決于目標(biāo)函數(shù)性質(zhì)。 目標(biāo)函數(shù)等高線的性質(zhì)很重要。目標(biāo)函數(shù)等高線的性質(zhì)很重要。 道路迂回曲折，多次變換方向，道路迂回曲折，多次變換方向， 在極點(diǎn)附近，目標(biāo)值改進(jìn)更小，在極點(diǎn)附近，目標(biāo)值改進(jìn)更小， 收斂速度慢。故不是一個(gè)有利方向。收斂速度慢。故不是一個(gè)有利方向。最速下降法是是X(k)處函數(shù)值下降最快的方向。處函數(shù)值下降最快的方向。當(dāng)當(dāng) 時(shí)，時(shí)，p(k)是是 f (X)在在 X(k) 處的處的下降方向下降方向。函數(shù)函數(shù)f (X)在在X(k)處的負(fù)梯度方向處的負(fù)梯度方向)()(kXf 梯度的性質(zhì)：梯度的性質(zhì)：1 1、迭代原理、迭代原理)()()()()()

55、()()()( kTkkkkpXfXfpXf證明：證明：)()()()( kTkpXf充分小時(shí)充分小時(shí) )()()()()()()(hhxfxfhxfkkk 0 0 )()()()()()()()()( kTkkkkpXfXfpXf結(jié)論：結(jié)論：( )( )()0kTkf Xp)()(kXf )(kP)(kP)(kX)(kP)(kP一元函數(shù)泰勒公式：一元函數(shù)泰勒公式： 1cos( )kX( )( )kkXp ( )kp 2.2.迭代原理迭代原理),(00Xfp 0 0 0p0X000pX )(min000pXf 0001pXX )()(10XfXf )(minXfnRX ),(000pXf ,0

56、X最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng),0X),(00Xfp 0 0p0X)(min000pXf 0001pXX )(minXfnRX ),(000pXf 最速下降法迭代原理：最速下降法迭代原理：0(1,1) ,TX 42122xx 312()(4,2)Tf Xxx 00()(4,2)Tpf X 00141 4121 2Xp 0042()(1 4 )(1 2 )2( )f XpF 000min ()( )f XpF 一維搜索找極小點(diǎn)一維搜索找極小點(diǎn) ：1)確定確定0 , 1, 精度精度0.10 2)用用0.618法得到法得到00.34375 1X040.53184 ( )F ,0X),(00Xfp 0 0p0X)

57、(min000pXf 0001pXX )(minXfnRX ),(000pXf 最速下降法迭代原理：最速下降法迭代原理：0(1,1) ,TX 42122xx 312()(4,2)Tf Xxx 00()(4,2)Tpf X 00141 4121 2Xp 0042()(1 4 )(1 2 )2( )f XpF 000min ()( )f XpF 00.34375 1(1,1)0.34375(4,2)( 0.375,0.3125)TTTX 10()2.11743()4f Xf X 1X線性規(guī)劃3-4,0X),(00Xfp 0 0p0X1X)(min000pXf 0001pXX )()(10XfXf

58、)(minXfnRX ),(000pXf 1p,1X),(11Xfp )(min110pXf ),(111pXf 1112pXX 111pX 1 )(2Xf 1 2.2.迭代原理迭代原理0 最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng),0X),(00Xfp 0 0p0X1X)(min000pXf 0001pXX )()(10XfXf )(minXfnRX ),(000pXf 1p,1X),(11Xfp )(min110pXf ),(111pXf 1112pXX 2X)(2Xf ,kX),(kkXfp )(min0kkpXf ),(kkkpXf kkkkpXX 11()()kkf Xf X XXkk)()1

59、13( Th線性收斂線性收斂2.2.迭代原理迭代原理1 1 0 最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng),)()( 嚴(yán)格嚴(yán)格kXf),103( Th得到一個(gè)點(diǎn)列：得到一個(gè)點(diǎn)列：01(),kXXX可以證明：可以證明：,0X),(00Xfp )(min000pXf 0001pXX )(minXfnRX ),(000pXf ,1X),(11Xfp )(min110pXf ),(111pXf 1112pXX ,kX),(kkXfp )(min0kkpXf ),(kkkpXf kkkkpXX 1,:)(10kXXX得得到到一一個(gè)個(gè)點(diǎn)點(diǎn)列列2.2.迭代原理迭代原理()()kf X 嚴(yán)嚴(yán)格格證明：證明：)()()(

60、)()()()()()( kTkkkkpXfXfpXf)()()()( kTkpXf充分小時(shí)充分小時(shí)0 0 )()()()()()()()()( kTkkkkpXfXfpXf0 ,)()( 嚴(yán)格嚴(yán)格kXf XXkk)(0)(2)( kXf)()()()()()()(kTkkTkXfXfpXf ( )( )( )()() 0kkkkf Xpf X 1kX 3.3.迭代步驟迭代步驟0:, 0)(,1)0(0 kX令令精精度度容容許許誤誤差差取取初初始始點(diǎn)點(diǎn) )(2)()(0kkXfp 計(jì)計(jì)算算0)()(04,?3否否則則轉(zhuǎn)轉(zhuǎn)取取若若是是迭迭代代終終止止檢檢驗(yàn)驗(yàn)kkXXp )()(min:4)()(