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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當時，最小，最小值為，此時由可得

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

該方法直觀，簡單，計算方便，而且后來的一些新的有效的方法大多數(shù)是對它的改進，或受它的啟發(fā)而得到的。最速下降法(1)選定某一初始點，并令(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)解。最速下降法的收斂性分析

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

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

最速下降法在兩個相鄰點之間的搜索方向是正交的。最速下降法向極小點逼近是曲折前進的，這種現(xiàn)象稱為鋸齒現(xiàn)象。除特殊的目標函數(shù)和極特殊的初始點外，這種現(xiàn)象都會發(fā)生。令利用精確一維搜索，可得由此得出1.相鄰兩次迭代的方向互相垂直最速下降法的兩個特征注：在最速下降法中，利用精確一維搜索求最佳步長，導致相鄰兩次迭代的搜索方向總是垂直的，使得逼近極小點過程是“之”字形，

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

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

則分析：因為相鄰方向正交，t與k有關

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

儲量小，對初始點要求不嚴格。缺點：收斂速度并不快，因為最速下降方向僅僅是指某點

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

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

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

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

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

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

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

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

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

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

可使相鄰兩個迭代點處的梯度不正交，從而改變收斂性。

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

但

到底取多大，沒有統(tǒng)一的標準，

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）當，