第四章-無約束非線性問題的解法-工程優(yōu)化課件-西電

本章要點：最速下降法的基本思想及特點牛頓方向Newton法基本思想及特點共軛方向、共軛方向法的基本定理共軛梯度法基本思想擬Newton法的基本思想第四章無約束非線性問題的解法

本章要點：第四章無約束非線性問題的解法學(xué)習(xí)的重要性：1、直接用于無約束的實際問題；2、其基本思想和邏輯結(jié)構(gòu)可以推廣到約束問題；3、約束問題可以轉(zhuǎn)化成無約束問題求解。方法分類：1、間接法：對簡單問題，求解必要條件或充分條件；2、迭代算法：零階法：只需計算函數(shù)值f(x)一階法：需計算▽f(x)二階法：需計算▽2f(x)直接法梯度法學(xué)習(xí)的重要性：1、直接用于無約束的實際問題；2、其基本思想和

本章主要介紹無約束最優(yōu)化方法，它的應(yīng)用比較廣泛，理論比較成熟。另一方面，通常可以把一些約束優(yōu)化問題轉(zhuǎn)化為無約束問題來處理，所以它是最優(yōu)化方法中的基本方法。

這些方法通常要用到函數(shù)的一階或二階導(dǎo)數(shù)。

在實際問題中，也常遇到函數(shù)的解析表達(dá)式比較復(fù)雜，有的甚至寫不出明顯的解析表達(dá)式，因而導(dǎo)數(shù)很難求出或無法求出，這時基于梯度的方法不能用，需要采取另一種所謂的直接法（或直接搜索法）。直接法是僅僅利用函數(shù)值的信息，去尋找最優(yōu)解的一類方法。在后面第九章有介紹。考慮無約束優(yōu)化問題：本章主要介紹無約束最優(yōu)化方法，它的應(yīng)用比較廣泛，直接搜索法收斂速度一般比較慢，需要計算大量的函數(shù)值。梯度反映了函數(shù)值變化的規(guī)律，充分利用梯度信息構(gòu)造算法，能加速收斂。使用函數(shù)的梯度（一階導(dǎo)數(shù)）或Hesse矩陣（二階導(dǎo)數(shù)）的優(yōu)化算法統(tǒng)稱為梯度法。算法目標(biāo)：求出平穩(wěn)點（滿足f(x)=0的x*）。由于f(x)=0一般是非線性方程組，解析法往往行不通，所以梯度法通常是逐次逼近的迭代法。假定：

f(x)和2f(x)連續(xù)存在直接搜索法收斂速度一般比較慢，需要計算大量的函數(shù)值。梯度反映§4.1最速下降法(Cauchy法)（一）基本思想x(k+1)=x(k)+tkd(k)x(k)x*d(k)=－f(x(k)

)x(k+1)d(k+1)=－f(x(k+1)

)瞎子下山：由于他看不到哪里是山谷，不可能沿直接指向山谷的路線走，他只能在當(dāng)前位置上，靠手杖作局部探索，哪里最陡就往哪里前進(jìn)一步，然后在新的位置上再用手杖尋找最陡方向，再下降一步。這就是最速下降法的形象比喻。？多變量最優(yōu)化迭代解法的一般迭代公式：可用一維搜索技術(shù)解決關(guān)鍵是如何確定搜索方向d(k)最速下降法迭代公式

x(k+1)=x(k)

－tkf(x(k)

)

1847年Cauchy提出。特點是直觀易懂，但收斂速度慢?！?.1最速下降法(Cauchy法)（一）基本思想x(k下面看一下理論推導(dǎo)：

設(shè)函數(shù)f(x)在xk附近連續(xù)可微，且gk=f(xk)≠0，由Taylor展式

可知，若記x-xk=tdk，則滿足(dk)Tgk<0的方向dk是下降方向。當(dāng)t取定后，(dk)Tgk的值越小，即-(dk)Tgk的值越大，函數(shù)下降的越快。由Cauchy-Schwartz不等式當(dāng)且僅當(dāng)dk=-gk時，(dk)Tgk

最小，從而-gk是最速下降方向。最速下降法的迭代格式為：下面看一下理論推導(dǎo)：

設(shè)函數(shù)f(x)在xk附近連續(xù)可微，且g（二）算法開始給定x(0),M,1,

2,令k=0計算f(x(k))||f(x(k))||<1否k>Mx*=x(k)是結(jié)束是一維搜索求tk精度為2否x(k+1)=x(k)

－tkf(x(k)

)

k=k+1（二）算法開始給定x(0),M,1,2,（三）最速下降法的搜索路徑呈直角鋸齒形定理4.1設(shè)從點x(k)出發(fā)，沿方向d作精確一維搜索，tk為最優(yōu)步長因子，即

f(x(k)+tkdk)=minf(x(k)+tdk)

則成立f(x(k)+tkd)Td=0,

即新點處的梯度與搜索方向垂直。即t>0x(k+1)d(k)x(k)f(x)等值面f(x(k+1)

)tkd(k+1)（三）最速下降法的搜索路徑呈直角鋸齒形定理4.1設(shè)從點二維情形下最速下降法搜索路徑：

由此可以看出，最速下降法僅是算法的局部性質(zhì)。對于許多問題，全局看最速下降法并非“最速下降”，而是下降的較緩慢。數(shù)值試驗表明，當(dāng)目標(biāo)函數(shù)的等值線接近于一個圓（球）時，最速下降法下降較快，而當(dāng)目標(biāo)函數(shù)的等值線是一個扁長的橢球時，最速下降法開始幾步下降較快，后來由于出現(xiàn)“鋸齒”現(xiàn)象，下降就比較緩慢。x(0)x(1)x(2)二維情形下最速下降法搜索路徑：由此可以看出，最f(x(k+1))Tdk=0，即f(x(k+1))Tf(x(k))=dk+1Tdk=0，這表明在相鄰的兩個迭代點上函數(shù)f(x)的兩個梯度方向是互相直交的，即，兩個搜索方向互相直交，這就產(chǎn)生了鋸齒形狀。當(dāng)接近極小點時，步長愈小，前進(jìn)愈慢。這就造成了最優(yōu)步長的最速下降法逼近極小點過程是“之”字形，并且越靠近極小點步長越小，移動越慢，以至在實際運用中在可行的計算時間內(nèi)得不到需要的結(jié)果。這似乎與“最速下降”的名稱矛盾。其實不然，因為梯度是函數(shù)局部性質(zhì)，從局部看，函數(shù)在這一點附近下降的很快，然而從整體看，則走過了許多彎路，因此反而是不好的。其原因就是精確一維搜索（最優(yōu)步長）滿足f(x(k+1))Tdk=0，即為了清除最優(yōu)步長最速下降法中兩個搜索方向正交的不良后果，人們發(fā)現(xiàn)了不少方法，如：(1)選擇不同初始點

例：問題：

取初點為求，沿方向從出發(fā)求的極小點即進(jìn)行線搜索則解得為了清除最優(yōu)步長最速下降法中兩個搜索方向正交的不良后果，人們?nèi)缓笤購拈_始新的迭代，經(jīng)過10次迭代，得最優(yōu)解計算中可以發(fā)現(xiàn)，開始幾次迭代，步長比較大，函數(shù)值下將降較快但當(dāng)接進(jìn)最優(yōu)點時，步長很小，目標(biāo)函數(shù)值下降很慢。如果不取初點為而取一步就得到了極小點。

雖然后一初點較前一初點離最優(yōu)點遠(yuǎn)，但迭代中不會出現(xiàn)上面的鋸齒現(xiàn)象。這時：然后再從開始新的迭代，經(jīng)過10次迭代，得最優(yōu)解（2）采用不精確的一維搜索：用一維搜索求出的步長為時，我們不取，而用的一個近似值作為,這樣可使相鄰兩個迭代點處的梯度不正交，從而改變收斂性?？梢姡涸斐删帻X現(xiàn)象與初始點的選擇有關(guān)，但怎樣選一個初始點也是一件困難的事。

對于最速下降法，有時為了減少計算工作量，不采用直線搜索確定步長，而采用固定步長λ的方法，稱為固定步長最速下降法。只要λ充分小，總有：

但λ到底取多大，沒有統(tǒng)一的標(biāo)準(zhǔn)，λ取小了，收斂太慢，而λ取大了，又會漏掉極小點?！痪_線搜索解決這個問題（2）采用不精確的一維搜索：用一維搜索求出的步長為（四）收斂性分析定理4.2

設(shè)目標(biāo)函數(shù)f(x)一階可微，且水平集有界，則最速下降法或者在有限步迭代后終止；或者得到點列，它的任何極限點都是f(x)的駐點。證明：見文中定理4.1的證明推論4.1

如果函數(shù)f(x)為凸函數(shù)，則應(yīng)用最速下降法，或者在有限步迭代后終止；或者得到點列的任何極限點都是全局極小點。下面討論最速下降法用于二次函數(shù)時的收斂性分析。證明：見課本P69推論4.2（四）收斂性分析定理4.2設(shè)目標(biāo)函數(shù)f(x)一用于二次函數(shù)時的收斂性分析并且定理4.3：對于二次函數(shù) Q為對稱正交，分別為其最小最大特征值，從任意初點出發(fā)，對此二次函數(shù)，用最速下降法產(chǎn)生的序列，對于有由于，則而函數(shù)的極小點恰好是。故最速下降法對于二次函數(shù)關(guān)于任意初點均收斂，而且是線性收斂的。用于二次函數(shù)時的收斂性分析并且定理4.3：對于二次函數(shù) 這個函數(shù)的等值線為(c＞0)

，改寫為：其中

下面說明最速下降法收斂性的幾何意義?？紤]具有對稱正定矩陣的函數(shù)這個函數(shù)的等值線為

這是以和為半軸的橢圓，從下面的分析可見兩個特征值的相對大小決定最速下降法的收斂性。（1）當(dāng)時，等值線變?yōu)閳A此時因而由上述定理知：即只需迭代一步就到了極小點，這表明最速下降法用于等值線為圓的目標(biāo)函數(shù)時，從任意初始點出發(fā)，只需迭代一步就到了極小點。（2）當(dāng)時,等值線為橢圓。此時對于一般的初始點將產(chǎn)生鋸齒現(xiàn)象。這是以和為（3）當(dāng)，等值線是很扁的橢圓，此時對于一般的初始點收斂速度可能十分緩慢，鋸齒現(xiàn)象嚴(yán)重。（3）當(dāng)，等值線是（五）優(yōu)缺點1、優(yōu)點：計算簡單，需記憶的容量小；對初始點要求低，穩(wěn)定性高；遠(yuǎn)離極小點時收斂快，常作為其它方法的第一步。2、缺點：收斂速度較慢（線性或不高于線性）。原因是最速下降方向只有在該點附近有意義。最速下降方向只是局部下降最快的方向，在全局來看，下降速度是比較慢的。尤其當(dāng)目標(biāo)函數(shù)等值面是很扁的橢圓、橢球或類似圖形時，收斂更慢。（五）優(yōu)缺點1、優(yōu)點：計算簡單，需記憶的容量??；對初始點要求例4.1用最速下降法求函數(shù)f(x1,x2)＝x12+4x22的極小點，（迭代兩次），并驗證相鄰兩個搜索方向是正交的。初始點取為x(0)=[1,1]T。解：梯度f(x)＝[2x1,8x2

]T。1.

第一次迭代：f(x(0))＝[2,8

]T，x(1)=x(0)+t0

p(0)=

x(0)－t0

f(x(0))＝[1,1]T－t0

[2,8

]T用一維搜索求t0

，對簡單f(x)，可用解析法求解：’0(t)＝520t－68＝0t0

＝0.130769x(1)=[0.738462,－0.046152]T設(shè)0

(t)＝f(x(1))＝f([1,1]T－t[2,8

]T)＝(1－2t)2+4(1－8t)2例4.1用最速下降法求函數(shù)f(x1,x2)＝x122.

第二次迭代：

f(x(1))＝[1.476924,－0.369216

]Tx(2)=x(1)－t1

f(x(1))=0.738462－1.476924t1－0.046152+0.369216t11(t)＝f(x(2))＝(0.738462－1.476924t)2+4(－0.046152+0.369216t)2’1(t)＝－2.317625t+5.453173t＝0t1

＝0.45005x(2)=[0.110762,0.110767]Tf(x(2))＝[0.221524,0.886136

]T3.驗證相鄰兩個搜索方向是正交的：f(x(0))Tf(x(1))=[2,8][1.476924,－0.369216

]T=0.000120f(x(1))Tf(x(2))=[1.476924,－0.369216

][0.221524,0.886136

]T=0.00000102.第二次迭代：f(x(1))＝[1.47建議大家對二次函數(shù)編程實踐(無需集成一維搜索算法)建議大家對一般函數(shù)結(jié)合一維搜索方法編程實踐.建議大家對二次函數(shù)編程實踐(無需集成一維搜索算法)建議大家對§4.2Newton法（二階方法）？由最速下降法可知，從全局角度來看，負(fù)梯度方向一般不是一個特別好的方向，有沒有更好的方向

?f(x)在x(k)處的二次近似函數(shù)（一）基本Newton法取f(?x;x(k))的平穩(wěn)點作為f(x)最優(yōu)點的一個近似點令f(?x;x(k))=f(x(k))+2f(x(k))x=0設(shè)函數(shù)f(x)的Hesse矩陣可逆，由上式可得：設(shè)函數(shù)f(x)是二次可微函數(shù)，又設(shè)函數(shù)x(k)是f(x)的極小點的一個估計，我們把設(shè)函數(shù)f(x)在x(k)展成Taylor級數(shù)，并取二階近似：§4.2Newton法（二階方法）？由最速下降法可知，x－x(k)=x=－2f(x(k))－1f(x(k))Newton法迭代公式：x(k+1)=

x(k)－2f(x(k))－1f(x(k))x(k)f(x(k))f(x;x(k))x(k+1)

或

x(k+1)=

x(k)－H(x(k))－1g(x(k))－H(x(k))－1g(x(k))!當(dāng)f(x)是二次函數(shù)時，一次迭代就可達(dá)到平穩(wěn)點！!當(dāng)f(x)是單變量函數(shù)時，本方法即為一維搜索的Newton法！這樣，知道x(k)后，算出在這一點處目標(biāo)函數(shù)的梯度和Hesse矩陣的逆，代入便得到后繼點x(k+1)

。x－x(k)=x=－2f(x(k))－1fNewton法的二次終止性設(shè)有二次凸函數(shù)f(x)=1/2xTAx+bTx+c其中A對稱正定矩陣。我們先用極值條件求解。令得最優(yōu)解：下面用Newton法求解。任取初始點x(1)，根據(jù)Newton法迭代公式有：顯然，即一步迭代達(dá)到最優(yōu)解。以后還會遇到一些算法，把它們用于二次凸函數(shù)時，類似于牛頓法，經(jīng)過有限次迭代比達(dá)到極小點。這種性質(zhì)稱為二次終止性。Newton法的二次終止性設(shè)有二次凸函數(shù)f(x)=1/2xT結(jié)束

基本Newton法的算法框圖：開始給定x(0),

,

令k=0計算g(k)=f(x(k))x*=x(k)是p(k)=－H(x(k))－1g(k)x(k+1)=x(k)+p(k)

k=k+1否計算

H(x(k))||g(k)||<

結(jié)束基本Newton法的算法框圖：開始給定x(0),例4.2用基本Newton法求函數(shù)f(x1,x2)＝8x12+4x1x2+5x22的極小點。初始點取為x(0)=[10,10]T。解：f(x)＝[16x1+4x2,4x1+10x2

]T2f(x)＝H(x)=164410H(x)－1=10－4

－4161144x(1)=

x(0)－H(x(0))－1f(x(0))1010=－＝10－4

－416114420014000因為f(x)是二次函數(shù)，所以一步迭代就達(dá)到平穩(wěn)點，又因為H(x(1))是正定矩陣，所以x(1)是極小點。例4.2用基本Newton法求函數(shù)f(x1,x2則：例4.3：用Newton法求的極小點。解：取初點代入Newton迭代公式得：此即為問題的最優(yōu)點則：例4.3：用Newton法求關(guān)于Newton法的幾點說明：1、基本Newton法要求Hesse矩陣具有逆矩陣。如果H(x(k))是正定的，則H(x(k))－1必存在，從而算法是可行的，并且保證求得的平穩(wěn)點是極小點。然而在迭代過程中要求H(x(k))是正定的這一條件不一定能保證，只有當(dāng)初始點合適時才能滿足。一般在極小點附近的Hesse矩陣容易為正定的。所以基本Newton法在極小點附近才比較有效。2、Newton法的搜索方向－H(x)－1f(x)不一定是下降方向。因為若是下降方向，則應(yīng)有f(x)T[－H(x)－1f(x)]<0，即f(x)TH(x)－1f(x)>0，但由于H(x)－1不一定是正定的，所以上式不一定成立。關(guān)于Newton法的幾點說明：1、基本Newton法要求He3、Newton法的最大優(yōu)點是：當(dāng)初始點選得合適時收斂很快，具有二階收斂速度，是目前講過的算法中最快的一種，且不需一維搜索。

對初始點要求高，一般要求初始點離極小點較近，否則不收斂。有時即使是收斂的，但因初始點離極大點或鞍點較近，會收斂于極大點或鞍點。4、方向－H(x)－1f(x)稱為Newton方向，是一個好方向，對二次函數(shù)此方向直指平穩(wěn)點。對于目標(biāo)函數(shù)是二次函數(shù)的無約束優(yōu)化問題，從任意初始點出發(fā)，利用Newton法一步迭代即可得到最優(yōu)解，也就是Newton法具有二次終止性。3、Newton法的最大優(yōu)點是：當(dāng)初始點選得合適時收斂很快，5、牛頓算法可視為橢球范數(shù)下的最速下降算法。

事實上，歐氏空間

中一般范數(shù)

下的方向?qū)?shù)定義為：

（它顯然與范數(shù)有關(guān)）

顯然，的最優(yōu)解就是函數(shù)在處對應(yīng)于范數(shù)的最速下降方向。容易理解，這個解與所取的范數(shù)有關(guān)。

a)當(dāng)取歐氏范數(shù)（2范數(shù)）時，可證是最速下降方向；5、牛頓算法可視為橢球范數(shù)下的最速下降算法。事實上，歐氏空b)若取橢球范數(shù)，最速下降方向則為事實上，即，有（意味著為方向?qū)?shù)下界）

b)若取橢球范數(shù)，最速下降方向則為事實上，即另一方面，若取時方向?qū)?shù)達(dá)到下界，故是對于橢球范數(shù)下的最速下降方向。

另一方面，若取時方向?qū)?shù)達(dá)到下界，故是對于橢球范數(shù)下的最速下6、牛頓算法實際上是非線性方程組的牛頓迭代法。等價于求解非線性方程組設(shè)是當(dāng)前迭代點，若，則是方程組的解，否則將在處線性化，得將上述線性方程組的解作為的近似解，得故有這恰好就是牛頓迭代公式。

由于求解若6、牛頓算法實際上是非線性方程組的牛頓迭代法。等價于求解非線由以上分析可知，固定的步長因子不能保證目標(biāo)函數(shù)有合理的改善，甚至不能保證算法下降，因此有必要對牛頓算法作一些改進(jìn)，一個最直接的改進(jìn)是：在牛頓算法中加入一維搜索。

（二）修正(阻尼)Newton法?怎樣才能使Newton法成為一個下降算法？修正Newton迭代公式：x(k+1)=

x(k)－tk

H(x(k))－1f(x(k))沿Newton方向一維搜索得到的最優(yōu)步長

保證了f(x(k+1))≤f(x(k))，且不必要求H(x)為正定矩陣。?出現(xiàn)(1)H(x(k))－1不存在；或(2)tk=0時怎么辦？改用最速下降法，即p(k)=－f(x(k))修正Newton法與基本Newton法的優(yōu)點是：缺點：要求計算Hesse矩陣及其逆矩陣，計算量大，尤其當(dāng)維數(shù)n較大時。收斂快，程序簡單。前者更實用可靠。由以上分析可知，固定的步長因子不能保證目標(biāo)函數(shù)有合理的改善，結(jié)束

阻尼Newton法的算法框圖：開始給定x(0),

,

令k=0計算g(k)=f(x(k))x*=x(k)是一維搜索求tkx(k+1)=x(k)+tkp(k)

k=k+1否計算

H(x(k))，若可逆p(k)=－H(x(k))－1g(k);否則p(k)=－g(k);||g(k)||<

常用如下Armijo不精確搜索結(jié)束阻尼Newton法的算法框圖：開始給定x(0),證明：見文P70中定理4.3的證明.阻尼Newton法的收斂性定理4.4

設(shè)f(x)存在連續(xù)二階偏導(dǎo)數(shù)，函數(shù)的Hessian矩陣

正定,且水平集有界，則阻尼牛頓法或者在有限步迭代后終止；或者得到的無窮點列有如下性質(zhì)1）為嚴(yán)格單調(diào)下降序列；2）有唯一極限點，它是f(x)的最小點。證明：見文P70中定理4.3的證明.阻尼Newton法的收斂Newton法與最速下降法結(jié)合(1)——Marquart法最速下降法的優(yōu)點：對初始點要求不高，穩(wěn)定性好；遠(yuǎn)離最優(yōu)點時收斂較快。缺點是離最優(yōu)點較近時收斂很慢。牛頓法的優(yōu)缺點剛好與最速下降法相反。1963年Marquardt提出將最速下降法與Newton法結(jié)合，開始用最速下降法，在接近最優(yōu)點時用Newton法。在迭代公式x(k+1)=x(k)+tkp(k)中，取步長tk＝1，搜索方向為p(k)

＝－[2f(x(k))

+kI]－1f(x(k))其中k同時起控制搜索方向和步長的作用，I為單位矩陣(1)

開始階段取很大，如0=104

，p(0)

＝－[2f(x(0))

+0I]－1f(x(0))－f(x(0))

10(2)

在迭代過程中，讓k0，p(k)－2f(x(k))－1f(x(k))（一）方法思想最速下降法

Newton法

具體在每一步是否縮小k，要通過檢驗?zāi)繕?biāo)函數(shù)值來決定：若f(x(k+1))<f(x(k))，取k+1<k;否則，取k+1=k,>1，重作第k步迭代。

Newton法與最速下降法結(jié)合(1)——Marquart法最（二）算法開始給定x(0),M，

,令k=0，0=104

x*=x(k)是結(jié)束p(k)=－[2f(x(k))

+kI]－1f(x(k))否否k>M是計算f(x(k))||f(x(k))||<

x(k+1)=x(k)+p(k)f(x(k+1))<f(x(k))k+1=0.5k,k=k+1是否k=2kI可推廣為半正定矩陣若[2f(x(k))

+kI]－1不存在x(k+1)=x(k)+tkp(k)（二）算法開始給定x(0),M，,令k=0，取d(k)=-[▽2f(x(k))]-1

▽f(x(k))，▽2f(x(k))正定

-▽f(x(k))，否則采用下列不精確一維搜索：求λk,滿足Goldstein準(zhǔn)則

1°f(x(k)+λkd(k))≤f(x(k))+δλk▽f(x(k))

Td(k)2°f(x(k)+λkd(k))≥f(x(k))+(1-δ)λk▽f(x(k))

Td(k)其中δ∈(0,1／2)特點：在一定條件下，G-P法全局收斂。但當(dāng)▽2f(x(k))非正定情況較多時，收斂速度降為接近線性。Newton法與最速下降法結(jié)合(2)——Goldstein-Price方法(G-P法)取d(k)=-[▽2f(x(k))]-1▽f(x最速下降法，計算步驟簡單，開始幾步收斂較快，但往后收斂速度越來越慢；在最優(yōu)解的附近，牛頓法以及修正牛頓法收斂速度快，但需要計算Hesse矩陣及其逆矩陣，計算量和存儲量都很大。§4.3共軛方向法因此人們希望能找到一種好的算法，它的收斂速度介于最速下降法與牛頓法之間，這種算法能夠具有牛頓法收斂速度快的優(yōu)點，又有最速下降法計算簡單的優(yōu)點，并且不需要計算Hesse矩陣的逆矩陣，對于二次函數(shù)只需有限次迭代就能達(dá)到最優(yōu)解。這就是我們要討論的共軛方向法。共軛梯度法就是其中一種，它是利用梯度生成共軛方向的共軛方向法。最速下降法，計算步驟簡單，開始幾步收斂較快，但往后收斂速度越（一）共軛方向下面我們先從幾何上直觀地介紹共軛方向，然后再給出嚴(yán)格的定義。Ap1CDp1B如圖所示，AB，CD過橢圓的中心，CD平行于橢圓上在點A，B的切線，在幾何上稱AB與CD為共軛直徑。AB與CD的方向稱為共軛方向。Martin和Tee提出可以利用上述橢圓的（或n維橢球）的這種共軛性質(zhì)來獲得較快的收斂速度。n=2時，若在橢圓上兩點A，B的切線平行，則直線AB必過橢圓的中心。在點A，B的切線方向與AB的方向稱為共軛方向。這種共軛關(guān)系如何表示呢？有如下定理：（一）共軛方向下面我們先從幾何上直觀地介紹共軛方向，然后再給引理4.4設(shè)f(x)=1/2xTAx+bTx+c，AT=A>0，給定方向p1，在與p1平行的兩條直線上（如圖），f(x)的最小點為x1，x2，則p1TAp2=0,（p2=x2-x1）證：因為g1=Ax1+b，g2=Ax2+b，則g2-g1=A(x2-x1)，又因為x1，x2為f(x)在此二直線上的最小點，則p1Tg1=0，p2Tg2=0，所以p1T(g2-g1)=0，綜上可得p1T(g2-g1)=p1TA(x2-x1)=0，所以p1TAp2=0,（p2=x2-x1）。x1x2p1p2注：該示意圖說明沿任意p1得到極小點后，沿其共軛方向p2必找到二維問題的極小點！引理4.4設(shè)f(x)=1/2xTAx+bTx+c，AT=定義：設(shè)A是n×n階對稱正定矩陣，

若A＝I（單位矩陣），則p(0)Tp(1)=0，即p(0)與p(1)是正交的?！肮曹棥笔恰罢弧备拍畹耐茝V

=||p(0)||.||p(1)||cosθ

（1）p(0),p(1)為兩個n維向量，若成立

p(0)TAp(1)=0

則稱向量p(0)與p(1)為A共軛或A正交，稱這兩向量的方向為A共軛方向。下面給出共軛的一般定義：（2）若有一組向量p(0),p(1),…,p(m)，滿足

p(i)TAp(j)=0，（i≠j，i,j=1,2,…m）則稱向量組p(0),p(1),…,p(m)為A共軛（或A正交）的向量組。定義：設(shè)A是n×n階對稱正定矩陣，若A＝I（單位矩陣），例1：設(shè)則p(0)與p(1)是A共軛的。解：因為驗證p(0)，p(1)為A共軛向量。例1：設(shè)則p(0)與p(1)是A共軛的。解：因為（二）共軛方向的性質(zhì)——共軛方向法的基本定理定理4.5：設(shè)A為n×n階對稱正定矩陣，p(1),p(2)，…,p(m)為m個相互A共軛的n維非零向量（即p(i)0,i=1,2,…,m,且p(i)TAp(j)=0，ij），則此向量組必線性無關(guān)。

推論：在n維空間中，互相共軛的非零向量的個數(shù)不超過n個。

引理4.6（n維直交定理）(1)

若p(0),p(1),…,p(n-1)是線性無關(guān)的n維向量組；(2)

若n維向量x和p(0),p(1),…,p(n-1)

都直交；則

x=0。（二）共軛方向的性質(zhì)——共軛方向法的基本定理定理4.5：設(shè)A命題：設(shè)A為n×n階對稱正定矩陣，p(0),p(1)，…,p(n-1)為n個相互A共軛的n維非零向量（即p(i)0,i=0,1,…,n-1,且p(i)TAp(j)=0，ij），則任意n維向量x可表示：

定理4.6：若p(0),p(1),…,p(n-1)是n個非零的A共軛向量，則二次目標(biāo)函數(shù)

f(x)=c+bTx+1/2xTAx的最優(yōu)點x*為!

可得到非二次函數(shù)最優(yōu)點的一個近似點；其中A是Hesse矩陣！?上式用于非二次函數(shù)，可否得到最優(yōu)點？命題：設(shè)A為n×n階對稱正定矩陣，p(0),p(1)，…,定理4.7:設(shè)A為n階對稱正定矩陣，對于二次目標(biāo)函數(shù)f(x)=c+bTx+1/2xTAx，從任意初始點x(1)出發(fā)，逐次進(jìn)行一維搜索，即

minf(x(i)+tp(i))=f(x(i)+tip(i))i≥0

若搜索方向p(1),p(2),…,p(n)是非零的A共軛向量，則至多進(jìn)行n次迭代必可得到極小點x*，即有

x(i+1)=x(i)+tip(i),i=1,2,…,nx*=x(k),1≤k≤n+1

上述搜索方法具有二次收斂性?對非二次函數(shù)，采用上述方法，n

次迭代是否也可得到極小點？?如何簡便地找出n個A共軛的向量？定理4.7:設(shè)A為n階對稱正定矩陣，對于二次目標(biāo)函數(shù)f(x定理:假設(shè)1.n元函數(shù)f(x)=c+bTx+1/2xTAx中的矩陣A是對稱正定的；2.向量p(0),p(1),…,p(m-1)(m<n)是互相A共軛的；3.x(0),x(1)是不同的任意兩點，分別從x(0),x(1)出發(fā)，依次沿p(0),p(1),…,p(m-1)

作精確一維搜索，設(shè)最后一次一維搜索的極小點分別為x(0)*和x(1)*,那么，向量p=x(0)*－x(1)*與p(0),p(1),…,p(m-1)互為A共軛。已知前m個共軛方向，就可以找到第m+1個共軛方向p(1)x(0)x(1)p(0)p(0)x(0)*x(1)*x*x(0)x(1)p(0)p(0)p(1)p(1)x(0)*x(1)*p(2)x*（三）Powell共軛方向法定理:假設(shè)已知前m個共軛方向，p(1)x(0)x(1)p表4.1Powell共軛方向法的迭代過程階段起點x(k,0)n+1次一維搜索過程新共軛方向Powell共軛方向法的基本思想…………………………一邊搜索，一邊找共軛方向共分n個階段，每一階段都進(jìn)行n+1次搜索，最后產(chǎn)生一個共軛方向任意n個線性無關(guān)的方向表4.1Powell共軛方向法的迭代過程階段起點x(k,二維空間中的Powell方法示意p(0)p(1)e(2)e(1)p(0)=e(1)p(1)=e(2)以二次函數(shù)f(x1,x2)為例x(1,0)x(1,1)x(1,2)p(1)x(2,2)x(2,0)x(2,1)x*對于二次函數(shù),x*即為極小點二維空間中的Powell方法示意p(0)p(1)e(2)e(Powell方法的原始算法框圖開始給定x(0),e(1),e(2),…,e(n)

及

否x(k)=x(k,n)+λkp(n-1)

其中λk為最優(yōu)步長k=1,p(i)=e(i+1),i=0,1,…,n-1j=0,x(k,j)=x(k-1)

x(k,j+1)=x(k,j)+λjp(j)

其中λj為最優(yōu)步長j=j+1j=n滿足精度否k=k+1x*=x(k+1)結(jié)束是是p(i)=p(i+1),i=0,1,…,n-2Powell方法的原始算法框圖開始給定x(0),e(1)幾點說明1、迭代中逐次產(chǎn)生的是共軛方向，是較好的搜索方向，所以Powell法又稱

方向加速法；2、原始算法僅有理論意義。因為只有在每次搜索均為一維完全精確搜索的條件下，每個階段產(chǎn)生的方向才是相互共軛的方向。但實際一維搜索都是近似的，產(chǎn)生的方向不一定共軛，有時甚至是線性相關(guān)的，導(dǎo)致搜索空間降維，這時將找不到真正的極小點。p(1)x(0)x(1)p(0)p(0)x(0)*x(1)*x*p’(1)

對于一般函數(shù),n個階段迭代后一般得不到極小點,但由于共軛方向的個數(shù)只有n個,如果繼續(xù)按上述方法迭代,產(chǎn)生的方向就不再是相互共軛方向了,收斂速度會變慢.幾點說明1、迭代中逐次產(chǎn)生的是共軛方向，是較好的搜索方向，所原始Powell算法一種簡便改進(jìn)重新開始：每進(jìn)行n個階段的迭代，或當(dāng)收斂速度變慢時，以當(dāng)前點為起點，回到第一步重新開始改進(jìn)的Powell算法基本思想:為克服搜索方向的線性相關(guān)問題，Powell對原始算法進(jìn)行了改進(jìn)。?如何判定方向組是“最相互共軛”的?在每個階段產(chǎn)生新的方向p后,更換方向組的方法不是一律去掉第一個方向p(0),而是有選擇地去掉某個方向p(J),原則是使新的方向組“最相互共軛”用新方向替換掉方向p(J)！詳細(xì)參閱教材P.263-276原始Powell算法一種簡便改進(jìn)重新開始：每進(jìn)行n個階段的迭§4.4

共軛梯度法

由Powell共軛方向法可知，共軛方向是好方向，是否有比Powell共軛方向法更簡單的方法構(gòu)建共軛方向？

共軛方向的選取有很大任意性，但高維空間構(gòu)造一組共軛方向卻非易事！作為迭代算法，我們自然希望共軛方向能在迭代過程中逐次生成。

下面介紹一種生成共軛方向的方法，它是利用每次一維最優(yōu)化所得到的點處的梯度來生成共軛方向，這種方法稱為共軛梯度法，具體做法如下：——其實教材p.78倒數(shù)第三行開始就討論共軛梯度法！§4.4共軛梯度法由Powell共軛方向法可共軛梯度法的基本思想

對f(x)=c+bTx+1/2xTAx，任取初始點x(0)

，取p(0)=－f(x(0))，k=0;然后沿著已得到的共軛方向p(k)進(jìn)行一維搜索：x(k+1)=x(k)+tkp(k)得下一個迭代點,并構(gòu)造新的方向p(k+1)=－f(x(k＋1))+kp(k)

,k=k+1返回!當(dāng)f(x)為二次函數(shù)時，至多經(jīng)過n次迭代就可得到極小點總結(jié)：構(gòu)造共軛方向p(0),…,p(n-1)的方法框架是p(0)=－f(x(0))

p(k+1)=－f(x(k＋1))+kp(k)

即下一個共軛方向是當(dāng)前點處負(fù)梯度方向與已求得的最后一個共軛方向的線性組合。p(0)=－f(x(0))－f(x(1))p(1)=－f(x(1))+0p(0)x(0)x(1)!要使得p(0),…,p(n-1)相互共軛，顯然k不能隨便??！共軛梯度法的基本思想對f(x)=c+b共軛梯度法的基本思想任取初始點x(0)

，取p(0)=－f(x(0))，k=0;然后沿著已得到的共軛方向p(k)進(jìn)行一維搜索：x(k+1)=x(k)+tkp(k)得下一個迭代點,并構(gòu)造新的方向p(k+1)=－f(x(k＋1))+kp(k)

,k=k+1返回!理論基礎(chǔ)——P79頁定理4.8:保證得到的n個方向是A-共軛的！P81頁詳細(xì)證明.P81(4)前面無負(fù)號.5個等價的公式(二次目標(biāo)函數(shù)時)共軛梯度法的基本思想任取初始點x(0)，取p(0)=記g(k)

=f(x(k))F－R共軛梯度法的迭代公式：x(k+1)=x(k)+tkp(k)p(k+1)=－g(k)+kp(k)

k=||g(k)||2

||g(k+1)||2

p(0)=－g(0)

以二次目標(biāo)函數(shù)f(x)=c+bTx+1/2xTAx為模型，其中A是對稱正定矩陣，從最速下降方向開始，構(gòu)造一組共軛方向，經(jīng)推導(dǎo)得：F－R共軛梯度法記g(k)=f(x(k))F－R共軛梯度法的迭代公幾點說明：1、“重新開始”的策略原因同Powell共軛梯度法（誤差、共軛梯度的個數(shù)）2、何時執(zhí)行重新開始步驟？由于共軛梯度法中各搜索方向的共軛性依賴于初始方向為負(fù)梯度方向，共軛方向只有n個，為了保證共軛方向的優(yōu)越性，所以每迭代n步后，重新從一個負(fù)梯度方向開始。一輪完成之后重新開始幾點說明：1、“重新開始”的策略原因同Powell共軛梯度法對于凸二次函數(shù)，為了避免計算原問題二階海賽矩陣，減少計算量，利用前面所得的公式，可以得到幾個等價的計算公式：——Daniel(1967)——Polyak-Polak-Ribiere(1969)——Myers(1972)——Sorenson-wolfe(1972)——Flecher-Reeves(1964)對于凸二次函數(shù)，為了避免計算原問題二階海賽矩陣，減少計算量，F(xiàn)－R法的算法框圖開始給定x(0),

||g(k+1)||<

否k=0，p(0)=－g(0)

x*=x(0)是結(jié)束g(0)=f(x(0))||g(0)||<

x(k+1)=x(k)+tkp(k),g(k+1)=f(x(k+1))其中tk為最優(yōu)步長x(0)=x(k+1)g(0)=g(k+1)是否ak=||g(k+1)||2/||g(k)||2

p(k+1)=－g(k+1)+kp(k)k=k+1x*=x(k+1)是結(jié)束k=n

否F－R法的算法框圖開始給定x(0),||g(k+1例4.2用F－R共軛梯度法解minf(x)＝60－10x1－4x2+x12+x22－x1x2

初始點取為x(0)=[0,0]T。解：f(x)＝[－10＋2x1－x2,－4＋2x2－x1

]Tp(0)＝－g(0)

＝－f(x(0))＝[10,4]T進(jìn)行一維搜索，對簡單f(x)，可用解析法求解：f(x(1))=

f(x(0)＋t

p(0))=f(x)|x=[10t,4t]T=60－116t+76t2f’(t)＝152t－116＝0t0

＝0.76315789x(1)=x(0)+t0

p(0)=[7.63157894,3.052631578]Tg(1)

＝f(x(1))＝[2.21052631,－5.52631579]Ta0=||g(1)||2/||g(0)||2=35.42659277/116p(1)=－g(1)+0p(0)=[0.84349308,6.747922437]T再用解析法求最優(yōu)步長t1得t1

＝0.436781609x(2)=x(1)+t1

p(1)=[7.999999993,5.999999997]Tg(2)

＝f(x(2))＝[0,0]T所以，x*=[8,6]Tf*=8例4.2用F－R共軛梯度法解minf(共軛梯度法評注1、共軛梯度法的優(yōu)點是不必計算Hesse矩陣及其逆矩陣，程序簡單，對大規(guī)模問題很有吸引力。對凸二次函數(shù)最多n步終止，而對一般函數(shù)為超線性收斂。2、收斂速度依賴于一維搜索的精確性及Hesse矩陣的特征值的分布。共軛梯度法評注1、共軛梯度法的優(yōu)點是不必計算Hesse矩陣及對一般函數(shù)的共軛梯度法注意問題把前面的共軛梯度法推廣到對于一般函數(shù)的共軛梯度法，需要注意的幾點:1.步長λk不能夠用前面的公式計算,用其他的一維搜索方法來確定。4.一種方法是直接延續(xù)，一直利用我們的方法做下去，即到了n步仍然不停止，直到滿足了停止條件。3.用這種方法求任意函數(shù)的極小點，一般來說，有限步迭代是達(dá)不到的。所以需要采取一些策略。2.凡用到矩陣A的地方，需要用現(xiàn)行點處的海賽矩陣▽2f(x(k))對一般函數(shù)的共軛梯度法注意問題把前面的共軛梯度法推廣到對于一5.另一種方法是把n步作為一輪，每搜索一輪后，取一次最速下降方向，開始下一輪。這種策略稱為“重新開始”或“重置”。——更常用由于共軛梯度法中各個搜索方向的共軛性依賴于初始方向為負(fù)梯度方向，共軛方向只有n個，為了保持共軛方向性，所以每次迭代n步后，重新從一個負(fù)梯度方向開始。另外由于每次計算的λk

和βk不精確，所以有積累誤差，它影響到算法的收斂性，通常為了避免積累誤差，所以重新開始整個算法。6.對于一般函數(shù)時，前面的幾種共軛梯度法計算βk得到的搜索方向是不同的，所以不是等價的。經(jīng)驗證對于二次凸規(guī)劃，一般用FR方法，對于一般函數(shù)利用PPR方法。5.另一種方法是把n步作為一輪，每搜索一輪后，取一次最速7.利用非精確一維搜索方法（1）得到的方法有可能不是下降方法，當(dāng)不是下降方向的時候，用最速下降方向重新開始。但是這樣的重新開始可能使大量的，因此會降低計算效率。（2）利用一個下降的原則去控制。算法的收斂性分析:2）的任意極限點都是f(x)的最優(yōu)解。證明：見文中P.85定理4.10的證明定理4.10

設(shè)f(x)存在連續(xù)一階偏導(dǎo)數(shù)，且函數(shù)為凸函數(shù)，且水平集有界，則由共軛梯度法得到的點列有如下性質(zhì)1）為嚴(yán)格單調(diào)下降序列，且存在；7.利用非精確一維搜索方法算法的收斂性分析:2）§4.5擬Newton法（變尺度法）Newton法的最大優(yōu)點是靠近極小點時收斂速度快，主要缺點是要計算Hesse矩陣及其逆矩陣，計算量大.?有沒有可能既保持Newton法快速的優(yōu)點，又不計算Hesse矩陣及其逆矩陣

?牛頓方向：p(k)=－

2f(x(k))-1g(k)

近似為p(k)=－H(k)

g(k)

H(k)稱為尺度矩陣，且迭代過程中H(k)是變化的，該算法為變尺度法;只要H(k)正定，方向必是下降方向;若變化H(k)不斷近似于

2f(x(k))-1，則算法可以保持牛頓法的快速收斂的優(yōu)勢！思想：1959年Davidon提出變尺度法，1963年經(jīng)Fletcher和Powell改進(jìn)，形成DFP法;1970年Broyden等人提出更穩(wěn)定的BFGS變尺度法。它被認(rèn)為是無約束優(yōu)化問題中最有效的方法之一。優(yōu)點：§4.5擬Newton法（變尺度法）Newton法的最x(1),H1對稱ε>0,k=1d(k)=-Hk

gk一維搜索得λk

x(k+1)=x(k)+λkdk||x(k+1)-x(k)||<ε?Hk+1=Hk+ΔHkStop.x(k+1)----解k=k+1yN算法框圖：x(1),H1對稱d(k)=-Hkgk||x(k+1)-構(gòu)造Hk的原則:從形式上模仿，造一個方向：H(k)應(yīng)滿足的條件：(1)滿足擬Newton條件：Δxk=Hk+1Δgk(2)H(k)為正定矩陣，這樣p(k)為下降方向；(3)由H(k)出發(fā)計算H(k+1)應(yīng)簡便:(4)算法具有二次收斂性：H(n+1)=

2f(x*)－1

.H(k+1)＝H(k)＋ΔH(k)記：Δg(k)=g(k+1)－g(k),Δx(k)=x(k+1)－x(k)校正矩陣尺度矩陣H(k)既近似2f(xk)－1

，計算又要方便！p(k)=－Hk

f(x(k))構(gòu)造Hk的原則:從形式上模仿，造一個方向：H(k)應(yīng)滿足的DFP算法：

Davidon(1959),FletcherandPowell(1963)，令ΔHk=αku(k)(u(k))T+βkv(k)(v(k))Tαk,βk是常數(shù)，u(k),v(k)是n維列向量。這樣定義的ΔHk是秩為2的對稱矩陣,所以稱為秩2校正。令

u(k)=Δxk

,v(k)=Hk

Δgk

,則由擬牛頓條件有

DFP算法：Davidon(1959),FletchDFP算法：1、上述算法具有三個性質(zhì)：(1)校正公式的分母總大于零,校正公式總有意義；(2)H(k)都是正定的，所以每次迭代方向都是下降方向；(3)對二次函數(shù)f(x)=c+bTx+0.5xTAx(A為正定矩陣)，迭代得到的搜索方向p(0),p(1),…,p(n－1)相互A共軛，所以DFP是一種共軛方向法；且H(n)=A－1

，說明H(k)逐次逼近A－1.DFP算法：1、上述算法具有三個性質(zhì)：(1)校正公式的分母2、DFP法的重新開始策略由于計算的舍入誤差及一維搜索精度不夠，會破壞H(k)的正定性，導(dǎo)致算法失效。（1）一維搜索后，如果f(x(k+1))f(x(k))，意味著p(k)不是下降方向，H(k)不是正定矩陣，則重新開始，重置H(k)=I；（2）每迭代n+1次后重新開始，令x(0)=x(n+1),H(0)=I2、DFP法的重新開始策略由于計算的舍入誤差及一維搜索精度不3、DFP法的算法開始給定x(0),

||g(k+1)||<

f0=f(x(0)),g(0)=f(x(0))x(k+1)=x(k)+tkp(k),其中tk為最優(yōu)步長fk+1=f(x(k+1)),g(k+1)=f(x(k+1))x(0)=x(k+1)f0=fk+1g(0)=g(k+1)是否y(k)=g(k+1)－g(k)s(k)=x(k+1)－x(k)x*=x(k+1)是結(jié)束k=n

否fk+1

fk否是H(0)=I，p(0)=－g(0),k=0p(k+1)=－H(k+1)g(k+1)k=k+1H(k+1)＝H(k)＋－s(k)s(k)Ts(k)Ty(k)H(k)y(k)Ty(k)TH(k)y(k)TH(k)y(k)3、DFP法的算法開始給定x(0),||g(k+1DFP算法收斂性分析定理4.12：若,則DFP方法構(gòu)造的矩陣Hi(i=1,2,…,n)為對稱正定矩陣。注：搜索方向dk=-Hk

gk一定是下降方向。參見課本P92的證明證明：數(shù)學(xué)歸納法（Schwartz不等式，正定矩陣的性質(zhì)，精確一維搜索的結(jié)果。）DFP算法收斂性分析定理4.12：若若目標(biāo)函數(shù)是正定二次函數(shù)，則DFP算法經(jīng)過有限步迭代必達(dá)到極小點，即具有二次收斂性。定理4.14：設(shè)用DFP算法求解下列問題其中Q為n階對稱正定矩陣。由DFP方法產(chǎn)生的搜索方向為，產(chǎn)生的矩陣為，則有如下結(jié)論成立。(1)

(2)

(3)

證明參見P93-P96頁

(4)

若目標(biāo)函數(shù)是正定二次函數(shù)，則DFP算法經(jīng)過有限步迭代必達(dá)到極2.若H1是單位向量，則所以DFP方法也是一種共軛梯度法。定理4.15

設(shè)f(x)存在連續(xù)一階偏導(dǎo)數(shù)，且函數(shù)為凸函數(shù)，且水平集有界，則由DFP法得到的點列有如下性質(zhì)1）為嚴(yán)格單調(diào)下降序列，且存在；2）的任意極限點都是f(x)的最優(yōu)解，且有:證明：參見P96的證明注：1.DFP方法也是一種共軛方向法。2.若H1是單位向量，則定理4.15BFGS方法——應(yīng)用最普遍的方法(一般函數(shù))由前面的推導(dǎo)，我們知道為了利用不包含二階導(dǎo)數(shù)的矩陣Hk+1取代▽2f(x(k))，該公式稱為另一種擬牛頓條件。由于上面的公式只需要交換就可以得到前面的擬牛頓條件。因此只需要在Hk的遞推公式中互換，并用Bk+1,Bk

分別取代Hk+1,Hk，就令

Bk+1滿足BFGS方法——應(yīng)用最普遍的方法(一般函數(shù))由前面的推導(dǎo)，我就得到Bk的遞推公式，所以關(guān)于Bk的修正公式為該公式稱為關(guān)于矩陣B的BFGS修正公式，有時也稱為DFP的對偶公式。設(shè)Bk+1可逆，則有所以滿足擬牛頓條件令就得到Bk的遞推公式，所以關(guān)于Bk的修正公式為該公式稱為關(guān)于對Bk+1兩邊求逆，得到這個重要公式是由Broyden,Fletcher,Goldfard和Shanno于1970年提出來的。它可以象DFP公式一樣使用，數(shù)值計算實例表明，它比DFP要好，目前得到廣泛的應(yīng)用。BFGS法有變尺度法的全部優(yōu)點，并且在一定條件下可以證明在BFGS法中使用前文中介紹的不精確一維搜索有全局收斂性。

對Bk+1兩邊求逆，得到這個重要公式是由Broyden,Flx(k+1)=x(k)+tkp(k)多變量最優(yōu)化迭代解法的一般迭代公式最優(yōu)步長可用一維搜索技術(shù)解決不同的搜索方向p(k),構(gòu)成不同的算法算法名稱搜索方向p(k)Powell共軛方向法共軛方向最速下降法p(k)=－f(x(k)

)Newton法p(k)=

－2f(x(k))－1f(x(k))Marquart法p(k)

＝－[2f(x(k))

+kI]－1f(x(k))F-R共軛梯度法p(0)=－f(x(0))p(k+1)=－f(x(k＋1))+kp(k)

小結(jié)DFP，BFGS法（擬Newton法）p(0)=－f(x(0))p(k+1)=－

H(k)

f(x(k))x(k+1)=x(k)+tkp(k)多變量方法的比較與選擇1、間接法：對簡單問題，求解必要條件或充分條件；2、迭代算法：零階法：只需計算函數(shù)值f(x)一階法：需計算一階導(dǎo)數(shù)▽f(x)二階法：需計算二階導(dǎo)數(shù)▽2f(x)直接法梯度法從收斂速度考慮：梯度法快于直接法Newton法擬Newton法(變尺度法)共軛梯度法Powell共軛方向法單純形法最速下降法方法的比較與選擇1、間接法：對簡單問題，求解必要條件或充分條作業(yè)：P99ch44.1-4,4.9-15,4.17-18,4.24,4.26作業(yè)：P99本章要點：最速下降法的基本思想及特點牛頓方向Newton法基本思想及特點共軛方向、共軛方向法的基本定理共軛梯度法基本思想擬Newton法的基本思想第四章無約束非線性問題的解法

本章要點：第四章無約束非線性問題的解法學(xué)習(xí)的重要性：1、直接用于無約束的實際問題；2、其基本思想和邏輯結(jié)構(gòu)可以推廣到約束問題；3、約束問題可以轉(zhuǎn)化成無約束問題求解。方法分類：1、間接法：對簡單問題，求解必要條件或充分條件；2、迭代算法：零階法：只需計算函數(shù)值f(x)一階法：需計算▽f(x)二階法：需計算▽2f(x)直接法梯度法學(xué)習(xí)的重要性：1、直接用于無約束的實際問題；2、其基本思想和

本章主要介紹無約束最優(yōu)化方法，它的應(yīng)用比較廣泛，理論比較成熟。另一方面，通?？梢园岩恍┘s束優(yōu)化問題轉(zhuǎn)化為無約束問題來處理，所以它是最優(yōu)化方法中的基本方法。

這些方法通常要用到函數(shù)的一階或二階導(dǎo)數(shù)。

在實際問題中，也常遇到函數(shù)的解析表達(dá)式比較復(fù)雜，有的甚至寫不出明顯的解析表達(dá)式，因而導(dǎo)數(shù)很難求出或無法求出，這時基于梯度的方法不能用，需要采取另一種所謂的直接法（或直接搜索法）。直接法是僅僅利用函數(shù)值的信息，去尋找最優(yōu)解的一類方法。在后面第九章有介紹?？紤]無約束優(yōu)化問題：本章主要介紹無約束最優(yōu)化方法，它的應(yīng)用比較廣泛，直接搜索法收斂速度一般比較慢，需要計算大量的函數(shù)值。梯度反映了函數(shù)值變化的規(guī)律，充分利用梯度信息構(gòu)造算法，能加速收斂。使用函數(shù)的梯度（一階導(dǎo)數(shù)）或Hesse矩陣（二階導(dǎo)數(shù)）的優(yōu)化算法統(tǒng)稱為梯度法。算法目標(biāo)：求出平穩(wěn)點（滿足f(x)=0的x*）。由于f(x)=0一般是非線性方程組，解析法往往行不通，所以梯度法通常是逐次逼近的迭代法。假定：

f(x)和2f(x)連續(xù)存在直接搜索法收斂速度一般比較慢，需要計算大量的函數(shù)值。梯度反映§4.1最速下降法(Cauchy法)（一）基本思想x(k+1)=x(k)+tkd(k)x(k)x*d(k)=－f(x(k)

)x(k+1)d(k+1)=－f(x(k+1)

)瞎子下山：由于他看不到哪里是山谷，不可能沿直接指向山谷的路線走，他只能在當(dāng)前位置上，靠手杖作局部探索，哪里最陡就往哪里前進(jìn)一步，然后在新的位置上再用手杖尋找最陡方向，再下降一步。這就是最速下降法的形象比喻。？多變量最優(yōu)化迭代解法的一般迭代公式：可用一維搜索技術(shù)解決關(guān)鍵是如何確定搜索方向d(k)最速下降法迭代公式

x(k+1)=x(k)

－tkf(x(k)