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

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

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

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

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

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

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

設，若為的局部極小點，且在內連續可微，則無約束優化的最優性條件----一階必要條件

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

設若在內二次連續可微，且正定，則為的嚴格局部極小點。

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

設是凸函數且在處連續可微，則為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對正定二次函數，用最速下降法產生的點列：偶數項點列均在一條直線上，奇數項點列也均在一條直線上，且都過最優點.

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

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

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

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

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

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

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

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

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

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

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

雖然后一初始點較前一初始點離最優點遠，但迭代中不出現鋸齒現象。

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

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

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

但

到底取多大，沒有統一的標準，

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

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

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

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

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

法求f的極小點，產生的序列為，對于有由于

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

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

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

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

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

（1）當時，等值線變為圓此時因而由上述定理知：

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

（3）當，