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

最優(yōu)性條件最速下降法牛頓法及其阻尼牛頓法共軛方向法共軛梯度法變尺度法（DFP算法和BFGS算法）第4章無約束最優(yōu)化方法

求解（1），就是找中的一點(diǎn)，使對均有，稱為(1)的全局極小點(diǎn)。

無約束最優(yōu)化問題：求解(1)的計(jì)算方法稱為無約束最優(yōu)化方法。

無約束最優(yōu)化方法應(yīng)用廣泛，理論也比較成熟；可將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來處理；最優(yōu)化方法中的基本方法---無約束優(yōu)化方法：利用函數(shù)的一階或二階導(dǎo)數(shù)的方法收斂速度快，需要計(jì)算梯度或者Hesse矩陣：僅利用函數(shù)值的信息，尋找最優(yōu)解不涉及導(dǎo)數(shù)，適用性強(qiáng)，但收斂速度慢可求得目標(biāo)函數(shù)的梯度時(shí)使用解析法在不可能求得目標(biāo)函數(shù)的梯度或偏導(dǎo)數(shù)時(shí)使用直接法本章介紹解析法最優(yōu)性條件(OptimalityConditions)

所謂最優(yōu)性條件，是指最優(yōu)化問題的最優(yōu)解所要滿足的必要條件或充分條件。

這些條件對于最優(yōu)化算法的建立和最優(yōu)化理論的推導(dǎo)都是至關(guān)重要的。

解析法要用到目標(biāo)函數(shù)的梯度或者Hesse矩陣，容易想到利用一階必要條件將無約束優(yōu)化問題轉(zhuǎn)化成一個(gè)梯度為0確定的方程組。這里用到的一階必要條件就是最優(yōu)性條件。定理(一階必要條件)

設(shè)，若為的局部極小點(diǎn)，且在內(nèi)連續(xù)可微，則無約束優(yōu)化的最優(yōu)性條件----一階必要條件

若為的局部極小點(diǎn)，且在內(nèi)二次連續(xù)可微，則半正定。無約束優(yōu)化的最優(yōu)性條件----二階必要條件定理（二階必要條件）定理(二階充分條件)

設(shè)若在內(nèi)二次連續(xù)可微，且正定，則為的嚴(yán)格局部極小點(diǎn)。

如果負(fù)定，則為的嚴(yán)格局部極大點(diǎn)。無約束優(yōu)化的最優(yōu)性條件----二階充分條件定理(一階充要條件)

設(shè)是凸函數(shù)且在處連續(xù)可微，則為

的全局極小點(diǎn)的充要條件是無約束優(yōu)化的最優(yōu)性條件----凸優(yōu)化的一階條件定理(一階必要條件)

設(shè)是嚴(yán)格凸函數(shù)且在處連續(xù)可微，若則為的唯一全局極小點(diǎn)。例：利用最優(yōu)性條件求解下列問題：解：令即：得到駐點(diǎn)：無約束優(yōu)化的最優(yōu)性條件利用二階條件判斷駐點(diǎn)是否是極小點(diǎn)利用一階條件求駐點(diǎn)函數(shù)的Hesse陣：在點(diǎn)處的Hesse陣依次為：無約束優(yōu)化的最優(yōu)性條件利用二階條件判斷駐點(diǎn)是否是極小點(diǎn)的行列式小于0；無約束優(yōu)化的最優(yōu)性條件是正定矩陣；是負(fù)定矩陣；是鞍點(diǎn)；是極小點(diǎn)；是極大點(diǎn)。對某些較簡單的函數(shù)，這樣做有時(shí)是可行的；但對一般n元函數(shù)f(x)來說，由條件

得到的是一個(gè)非線性方程組，解它相當(dāng)困難。為此，常直接使用迭代法。(1)選定某一初始點(diǎn)，并令(2)確定搜索方向(3)從出發(fā)，沿方向求步長，以產(chǎn)生下一個(gè)迭代點(diǎn)(4)檢查得到的新點(diǎn)是否為極小點(diǎn)或近似極小點(diǎn)。，轉(zhuǎn)(2)繼續(xù)進(jìn)行迭代。

在以上步驟中，步長的選取可采用精確一維搜索或非精確一維搜索，下降方向的選取正是下面要介紹的，不同的下降方向，得到不同的算法。若是，則停止迭代。線搜索迭代法的步驟否則，令從而得到第k+1次迭代點(diǎn)，即步長由精確一維搜索得到。最速下降法負(fù)梯度方向這是函數(shù)值減少最快的方向假設(shè)f連續(xù)可微，最速下降法負(fù)梯度方向是函數(shù)值減少最快的方向？令是單位長度的向量，

P是什么方向時(shí)，函數(shù)值下降最快？也就是p是什么方向時(shí)，取得最小值？

當(dāng)時(shí)，最小，最小值為，此時(shí)由可得

最速下降法是求多元函數(shù)極值的最古老的數(shù)值算法，早在1847年法國數(shù)學(xué)家Cauchy提出該算法，后來Curry作了進(jìn)一步的研究。

該方法直觀，簡單，計(jì)算方便，而且后來的一些新的有效的方法大多數(shù)是對它的改進(jìn)，或受它的啟發(fā)而得到的。最速下降法(1)選定某一初始點(diǎn)，并令(2)若，否則轉(zhuǎn)（3）；

由精確一維搜索確定最佳步長，最速下降法的迭代格式(3)令轉(zhuǎn)（2）。算法框圖x1,ε>0,k=1||▽f(xk)

||<ε?Yesstop.xk–解Nodk=－▽f(xk

)解minf(xk+λdk)s.t.λ>0得xk+1=xk+λkdkk=k+1最速下降法框圖

例利用最速下降法求解令解：函數(shù)的梯度為第1次迭代：取得令得第2次迭代：令得第3次迭代：繼續(xù)迭代可得到函數(shù)的近似最優(yōu)解。最速下降法的收斂性分析

設(shè)f(x)連續(xù)可微，且水平集有界，則最速下降法或者在有限迭代步后終止；或者得到點(diǎn)列，它的任何聚點(diǎn)都是f(x)的駐點(diǎn)。

在收斂定理的假設(shè)下，若f(x)為凸函數(shù)，則最速下降法或在有限迭代步后達(dá)到最小點(diǎn)；或得到點(diǎn)列，它的任何聚點(diǎn)都是f(x)的全局最小點(diǎn)。收斂性定理：推論：

最速下降法在兩個(gè)相鄰點(diǎn)之間的搜索方向是正交的。最速下降法向極小點(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è)特征

對正定二次函數(shù)，用最速下降法產(chǎn)生的點(diǎn)列：偶數(shù)項(xiàng)點(diǎn)列均在一條直線上，奇數(shù)項(xiàng)點(diǎn)列也均在一條直線上，且都過最優(yōu)點(diǎn).

則分析：因?yàn)橄噜彿较蛘唬瑃與k有關(guān)

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

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

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

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

最速下降法不是好的實(shí)用算法，但是一些有效算法

是通過對它的改進(jìn)或利用它與其他收斂快的算法結(jié)合而得到的，因此它是無約束優(yōu)化的基本方法之一。

為了清除最速下降法中兩個(gè)搜索方向正交的不良后果，提出了許多改進(jìn)的方法，如：(1)選擇不同初始點(diǎn)

例令最速下降法的改進(jìn)取初始點(diǎn)第1次迭代得然后再從開始新的迭代，經(jīng)過10次迭代，得最優(yōu)解

計(jì)算中可以發(fā)現(xiàn)，開始幾次迭代，步長比較大，函數(shù)值下降將較快，但當(dāng)接近最優(yōu)點(diǎn)時(shí)，步長很小，目標(biāo)函數(shù)值下降很慢。如果不取初點(diǎn)為而取一步就得到了極小點(diǎn)。

可見：造成鋸齒現(xiàn)象與初始點(diǎn)的選擇有關(guān)，但怎樣選一個(gè)初始點(diǎn)也是一件困難的事。第1次迭代

雖然后一初始點(diǎn)較前一初始點(diǎn)離最優(yōu)點(diǎn)遠(yuǎn)，但迭代中不出現(xiàn)鋸齒現(xiàn)象。

采用非精確一維搜索求步長,

可使相鄰兩個(gè)迭代點(diǎn)處的梯度不正交，從而改變收斂性。

對于最速下降法，有時(shí)為了減少計(jì)算工作量，采用固定步長，稱為固定步長最速下降法。

但

到底取多大，沒有統(tǒng)一的標(biāo)準(zhǔn)，

取小了，收斂太慢，而取大了，又會漏掉極小點(diǎn)。（2）采用不精確的一維搜索：最速下降法的改進(jìn)（3）采用加速梯度法：

由于最速下降法在極小點(diǎn)附近成“鋸齒”狀，因此下降過程中的搜索方向可取

下兩步繼續(xù)用最速下降方向即負(fù)梯度方向。

Shah等人于1964年提出了一種“平行切線法”（簡記為PARTAN法），又稱加速梯度法。最速下降法的改進(jìn)負(fù)梯度方向和結(jié)合這兩種方向交替使用，效用要比最速下降法好的多。

用于二次函數(shù)時(shí)的收斂速度分析定理：設(shè)二次函數(shù) A對稱正定，分別為其最小和最大特征值，從任意初點(diǎn)出發(fā)，用最速下降

法求f的極小點(diǎn)，產(chǎn)生的序列為，對于有由于

而函數(shù)的極小點(diǎn)恰好是。故最速下降法對于二次函數(shù)關(guān)于任意初始點(diǎn)均收斂，且是線性收斂。

下面說明最速下降法收斂性的幾何意義。

考慮A為正三角矩陣時(shí)的二次函數(shù)函數(shù)的等值線為其中

用于二次函數(shù)時(shí)的收斂速度分析改寫為：

這是以和為半軸的橢圓從下面的分析可見兩個(gè)特征值的相對大小決定最速下降法的收斂性。

（1）當(dāng)時(shí)，等值線變?yōu)閳A此時(shí)因而由上述定理知：

即只需迭代一步就到了極小點(diǎn)，這表明最速下降法用于等值線為圓的目標(biāo)函數(shù)時(shí)，只需迭代一步就到了極小點(diǎn)。

（3）當(dāng)，