工程優(yōu)化第4章-2

最優(yōu)性條件最速下降法牛頓法及其阻尼牛頓法共軛方向法共軛梯度法變尺度法（DFP算法和BFGS算法）第4章無約束最優(yōu)化方法無約束最優(yōu)化問題：從而得到第k+1次迭代點(diǎn)，即步長由精確一維搜索得到。最速下降法負(fù)梯度方向假設(shè)f連續(xù)可微，最速下降法向極小點(diǎn)逼近是曲折前進(jìn)的，這種現(xiàn)象稱為鋸齒現(xiàn)象。除特殊的目標(biāo)函數(shù)和極特殊的初始點(diǎn)外，這種現(xiàn)象都會發(fā)生。1.相鄰兩次迭代的方向互相垂直最速下降法的兩個(gè)特征注：在最速下降法中，利用精確一維搜索求最佳步長，導(dǎo)致相鄰兩次迭代的搜索方向總是垂直的，使得逼近極小點(diǎn)過程是“之”字形，

這樣從任何一個(gè)初始點(diǎn)開始，都可以很快到達(dá)極小點(diǎn)附近，但是越靠近極小點(diǎn)步長越小，移動越慢，導(dǎo)致最速下降法的收斂速度很慢。實(shí)際運(yùn)用中，在可行的計(jì)算時(shí)間內(nèi)得不到需要的結(jié)果。最速下降法收斂速度慢最速下降法的兩個(gè)特征對正定二次函數(shù)，用最速下降法產(chǎn)生的點(diǎn)列：偶數(shù)項(xiàng)點(diǎn)列均在一條直線上，奇數(shù)項(xiàng)點(diǎn)列也均在一條直線上，且都過最優(yōu)點(diǎn).最速下降法的兩個(gè)特征

優(yōu)點(diǎn)：理論明確，程序簡單，每次的計(jì)算量小，所需的存

儲量小，對初始點(diǎn)要求不嚴(yán)格。缺點(diǎn)：收斂速度并不快，因?yàn)樽钏傧陆捣较騼H僅是指某點(diǎn)

的一個(gè)局部性質(zhì)。最速下降法相鄰兩次搜索方向的正交性，決定了迭代全

過程的搜索路線呈鋸齒狀，遠(yuǎn)快近慢。最速下降法的優(yōu)缺點(diǎn)Newton法

前面介紹精確一維搜索時(shí)介紹了牛頓法，即用目標(biāo)函數(shù)的二次泰勒多項(xiàng)式近似代替函數(shù)本身，用二次多項(xiàng)式的極小點(diǎn)近似函數(shù)的極小點(diǎn)。這種方法可以推廣到多維的情形。牛頓法是求解無約束極小化問題的最古老的算法之一，現(xiàn)在已經(jīng)發(fā)展成一類算法-----Newton型方法。Newton法一維優(yōu)化的Newton迭代公式多維優(yōu)化的Newton迭代公式

算法的基本思路：考慮從到的迭代過程，在點(diǎn)處對函數(shù)Tayloy展開：Newton法令

，有略去高階項(xiàng)若Hesse矩陣正定，則存在，由此求出二次函數(shù)的極小點(diǎn)為：以此作為極小點(diǎn)的一個(gè)新的近似。此公式即為多元函數(shù)求極值的Newton迭代公式。Newton法步驟1.

選定初始點(diǎn),計(jì)算已知目標(biāo)函數(shù),給定誤差限.步驟2.

如果，算法停止，，否則轉(zhuǎn)步驟3。步驟3.

計(jì)算搜索方向Newton法的計(jì)算步驟步驟4.

令，轉(zhuǎn)步驟2.

步長取常數(shù)1牛頓方向步驟1.

選定初始點(diǎn),計(jì)算步驟2.

如果，算法停止，，否則轉(zhuǎn)步驟3。步驟3.

計(jì)算搜索方向Newton法的計(jì)算步驟步驟4.

令，轉(zhuǎn)步驟2.

步驟3中的搜索方向，可以通過方程組求解，這樣可以減少計(jì)算工作量，且解線性方程組已有標(biāo)準(zhǔn)程序。x1,ε>0,k=1▽2f(xk)d=-▽f(xk)

得dk,xk+1=xk+dk||▽f(xk+1)||<ε?STOP.xk+1駐點(diǎn)YesNok=k+1注：若▽2f(xk)非正定時(shí)進(jìn)行相應(yīng)處理Newton法框圖計(jì)算解：取初始點(diǎn)代入Newton迭代公式，此即為問題的最優(yōu)點(diǎn)例：用Newton法求的極小點(diǎn)。一步即達(dá)到最優(yōu)解Newton法----算例設(shè)其中f(x)的極小點(diǎn)即是正定二次函數(shù)等值面的中心，下面用Newton法求解f(x)的極小點(diǎn)。一步即達(dá)到最優(yōu)解

當(dāng)f(x)為正定二次函數(shù)時(shí)，用Newton法從任意初始點(diǎn)可一步迭代達(dá)到最優(yōu)解。

當(dāng)f(x)為正定二次函數(shù)時(shí)，用Newton法從任意初始點(diǎn)可一步迭代達(dá)到最優(yōu)解。二次收斂性

從任意初始點(diǎn)出發(fā)，經(jīng)有限次迭代總可以達(dá)到正定二次函數(shù)的極小點(diǎn)，稱這樣的算法具有二次收斂性。Newton法具有二次收斂性

牛頓法比最速下降法收斂快。

當(dāng)初始點(diǎn)靠近極小點(diǎn)時(shí)，Newton法的收斂速度很快。

當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時(shí)，Newton法可能不收斂，甚至連下降性都保證不了。

Newton法：局部二次收斂Newton法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：當(dāng)初始點(diǎn)離最優(yōu)解很近時(shí)，算法收斂速度快；

算法簡單，不需要進(jìn)行一維搜索；

對正定二次函數(shù)，迭代一次就可得到最優(yōu)解。Newton法的優(yōu)缺點(diǎn)缺點(diǎn)：(1)對多數(shù)算法不具有全局收斂性：

(2)每次迭代都要計(jì)算Hesse矩陣，計(jì)算量大；

(3)每次迭代都要計(jì)算或者求解方程組可能不存在；

方程組是奇異的，病態(tài)的；非正定，

(4)收斂于鞍點(diǎn)或極大點(diǎn)的可能性并不小。當(dāng)Hesse矩陣正定時(shí)，從而可能不是下降方向。Newton法的改進(jìn)Newton法的缺點(diǎn)和優(yōu)點(diǎn)都很突出，本身并不實(shí)用；Newton法的改進(jìn)方法是求解無約束優(yōu)化問題的有效方法之一。

保留Newton法的優(yōu)點(diǎn)，克服部分缺點(diǎn)。針對Newton法的缺點(diǎn)(1)對多數(shù)算法不具有全局收斂性：

和(4)收斂于鞍點(diǎn)或極大點(diǎn)的可能性并不小，步長不取固定值1，而是采用精確一維搜索找最佳步長，這就是阻尼Newton法。怎么改進(jìn)呢？在Newton迭代公式中,

加入精確一維搜索：求得最佳步長

,得到下個(gè)迭代點(diǎn)

這樣修正之后通?？筛倪M(jìn)Newton法的缺點(diǎn)(1)和(4)。Newton法的改進(jìn)----阻尼Newton法每次迭代目標(biāo)函數(shù)值一定有所下降缺點(diǎn)(1)對多數(shù)算法不具有全局收斂性：

(4)收斂于鞍點(diǎn)或極大點(diǎn)的可能性并不小；設(shè)f(x)存在連續(xù)二階偏導(dǎo)數(shù)，函數(shù)的Hesse矩陣正定，且水平集有界，則阻尼Newton法或者在有限步迭代后終止；或者得到的無窮點(diǎn)列有如下性質(zhì)：(1)為嚴(yán)格單調(diào)下降序列；(2)有唯一聚點(diǎn)，它是f(x)的最小點(diǎn)。Newton法的改進(jìn)----阻尼Newton法特點(diǎn)：可改善局部收斂性。收斂性定理：例：用阻尼牛頓法求解下列無約束優(yōu)化問題，已知解故計(jì)算令得此即為問題的最優(yōu)點(diǎn)一步即達(dá)到最優(yōu)解Newton法的進(jìn)一步修正

阻尼Newton法改進(jìn)了Newton法，但還是存在缺點(diǎn):

(2)每次迭代都要計(jì)算Hesse矩陣，計(jì)算量大；

(3)可能不存在，即使存在，也未必正定，因而牛

頓方向不一定是下降方向。牛頓法還有其他的修改方式。缺點(diǎn)（3）的改進(jìn)方法之一：

當(dāng)dk為函數(shù)上升方向時(shí)，可向其負(fù)方向搜索，

但可能出現(xiàn)±dk

均非下降方向的情況。為減小工作量，取m（正整數(shù)），使每m次迭代使用同一個(gè)Hesse陣，迭代公式變?yōu)椋?/p>

Newton法的改進(jìn)---針對缺點(diǎn)(2)每次計(jì)算Hesse矩陣特點(diǎn)：收斂速度隨m的增大而下降。

m=1時(shí)即Newton法，m→∞即線性收斂。(2)Goldstein-Price方法(G-P法)：取采用下列非精確一維搜索（Armijo-Goldstein準(zhǔn)則）：求，使

Newton法的改進(jìn)---針對缺點(diǎn)(3)非正定和奇異的情況其中特點(diǎn)：在一定條件下，G-P法全局收斂。但當(dāng)

非正定情況較多時(shí)，收斂速度降為接近線性。(3)Levenberg-Marguardt法（L-M法）：主要思想：找到盡可能小的

使

正定。用

取代

進(jìn)行迭代，其中I為單位矩陣。特點(diǎn)：全局二階收斂。Newton法的改進(jìn)---針對缺點(diǎn)(3)非正定的情況作業(yè)：

P994.2，4.3

最速下降法，計(jì)算步驟簡單，但收斂速度慢。共軛方向法計(jì)算效果好，應(yīng)用廣泛；共軛方向法和共軛梯度法這就是要討論的共軛方向法和共軛梯度法。Newton法和阻尼Newton法都有一個(gè)優(yōu)點(diǎn)：收斂速度快，但需要計(jì)算Hesse矩陣和Hesse矩陣的逆矩陣，計(jì)算量和存儲量都很大。

需要尋找一種好的算法，這種算法能夠兼有這兩種方法的優(yōu)點(diǎn)，又能克服它們的缺點(diǎn)，即收斂速度快同時(shí)計(jì)算簡單。函數(shù)的系數(shù)矩陣有關(guān)的共軛方向。共軛梯度法是最著名的共軛方向法，其搜索方向是與正定二次

設(shè)是對稱正定矩陣，如果則稱向量p和q是A共軛的(或稱為A正交)。

如果對有限個(gè)向量，有共軛方向法---共軛方向及其性質(zhì)若

則p與q是正交的。定義1

定義2

則稱這個(gè)向量組是A-共軛(或A正交)向量組，也稱它們是一組A共軛方向。共軛是正交的推廣共軛向量組是正交向量組的推廣。假設(shè)f(x)是n元正定二次函數(shù)對二維情況（n=2）任選取初始點(diǎn)x1沿某個(gè)下降方向d1作精確一維搜索，得共軛方向法---共軛方向及其性質(zhì)如果按最速下降法，選取

如果希望下次迭代就得到最優(yōu)解，α1d1x1x2x*11α2d2d2由精確一維搜索的性質(zhì)，可知共軛方向法---共軛方向及其性質(zhì)則將發(fā)生鋸齒現(xiàn)象。共軛方向法---共軛方向及其性質(zhì)

如果能夠選定這樣的搜索方向，那么對于二元二次函數(shù)只需依次沿搜索方向d

1,d

2兩進(jìn)行次精確一維搜索就可以求到極小點(diǎn)x*，即x*是f(x)的極小點(diǎn)，故x*是f(x)的駐點(diǎn)，將等式兩邊同時(shí)左乘得：

兩次迭代要得到二元二次函數(shù)的極小點(diǎn)，d1必須滿足的條件是：搜索方向d1和d2是A共軛的。即d1是某個(gè)下降方向性質(zhì)2

若Rn中的非零向量p1,p2,…,pm是A共軛向量組，則這m

個(gè)向量是線性無關(guān)的。性質(zhì)3

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

性質(zhì)4

設(shè)n元函數(shù)f(x)=1/2xTAx+bTx+c,A=AT正定，又設(shè)n維非零向量組p1,p2,…,pn是A共軛向量組，從任意點(diǎn)x1出發(fā)，依次以p1,p2,…,pn

為搜索方向進(jìn)行精確一維搜索，則

(1)▽f(xk+1)與p1,p2,…,pk(k=1,2,…,n)正交；

(2)最多n次迭代必達(dá)到二次函數(shù)f(x)的極小點(diǎn)。

性質(zhì)1

在n維空間中與n個(gè)線性無關(guān)的向量都正交的一定是零向量。

共軛方向法---共軛方向的性質(zhì)因?yàn)楣曹椃较蚍?--共軛方向及其性質(zhì)存在一組實(shí)數(shù)證明：假設(shè)線性無關(guān)，向量與正交，證線性無關(guān)，所以可作為空間中的一組基，故可由線性表出，即故性質(zhì)1

在n維空間中與n個(gè)線性無關(guān)的向量都正交的一定是零向量。

因?yàn)楣曹椃较蚍?--共軛方向及其性質(zhì)因?yàn)锳正定，證明：假設(shè)要證線性無關(guān),是A共軛向量組，兩邊同乘得證。性質(zhì)2

若Rn中的非零向量p1,p2,…,pm是A共軛向量組，則這m

個(gè)向量是線性無關(guān)的。只需證明所以故共軛方向法---共軛方向及其性質(zhì)證明：利用性質(zhì)2即可。性質(zhì)2

若Rn中的非零向量p1,p2,…,pm是A共軛向量組，則這m

個(gè)向量是線性無關(guān)的。性質(zhì)3

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

Rn中線性無關(guān)的非零向量最多有n個(gè)。性質(zhì)4

設(shè)n元函數(shù)f(x)=1/2xTAx+bTx+c,A=AT正定，又設(shè)n維非零向量組p1,p2,…,pn是A共軛向量組，從任意點(diǎn)x1出發(fā)，依次以p1,p2,…,pn

為搜索方向進(jìn)行精確一維搜索，則

(1)▽f(xk+1)與p1,p2,…,pk(k=1,2,…,n)正交；

(2)最多n次迭代必達(dá)到二次函數(shù)f(x)的極小點(diǎn)。

共軛方向法---共軛方向的性質(zhì)性質(zhì)4中(1)▽f(xk+1)與p1,p2,…,pk(k=1,2,…,n)正交；

是按照精確一維搜索得到的，所以有共軛方向法---共軛方向及其性質(zhì)下證證明：共軛方向法---共軛方向及其性質(zhì)P1,P2,…,

Pn