最優化理論

一維搜索:

1精確一維搜索

精確一維搜索可以分為三類：區間收縮法、函數逼近法（插值法）、

以及求根法。

區間收縮法：用某種分割技術縮小最優解所在的區間(稱為搜索

區間)。包括：黃金分割法、成功失敗法、斐波那契法、對分搜索法

以及三點等間隔搜索法等。

優化算法通常具有局部性質，通常的迭代需要在單峰區間進行操

作以保證算法收斂。確定初始區間的方法：進退法

①已知搜索起點和初始步長；②然后從起點開始以初始步長向前

試探，如果函數值變大，則改變步長方向；③如果函數值下降，則維

持原來的試探方向，并將步長加倍。

1.1黃金分割法：

黃金分割法是一種區間收縮方法(或分割方法)，其基本思想是通

過取試探點和進行函數值比較，使包含極小點的搜索區間不斷縮短以

逼近極小值點。具有對稱性以及保持縮減比原則。

優點：不要求函數可微，除過第一次外，每次迭代只需計算一個

函數值，計算量小，程序簡單；

缺點：收斂速度慢；

函數逼近法（插值法）：用比較簡單函數的極小值點近似代替原

函數的極小值點。從幾何上看是用比較簡單的曲線近似代替原的曲線，

用簡單曲線的極小值點代替原曲線的極小點。

1.2牛頓法：

將目標函數二階泰勒展開，略去高階項后近似的替代目標函數，

然后用二次函數的極小點作為目標函數的近似極小點。

牛頓法的優點是收斂速度快，缺點是需要計算二階導數，要求初

始點選的好，否則可能不收斂。

1.2拋物線法：

拋物線法的基本思想就是用二次函數拋物線來近似的代替目標

函數，并以它的極小點作為目標函數的近似極小點。在一定條件下，

1

拋物線法是超線性收斂的。

1.3三次插值法：

三次插值法是用兩點處的函數值和導數值來構造差值多項式，以

該曲線的極小點來逼近目標函數的極小點。一般來說，三次插值法比

拋物線法的收斂速度要快。

精確一維搜索的方法選擇：

1如目標函數能求二階導數：用Newton法，收斂快。

2如目標函數能求一階導數：

1如果導數容易求出，考慮用三次插值法，收斂較快；

2對分法、收斂速度慢，但可靠；

3只需計算函數值的方法：

1二次插值法, 收斂快，但對函數單峰依賴較強；

2黃金分割法收斂速度較慢，但實用性強，可靠；

4減少總體計算時間：非精確一維搜索方法更加有效。

2非精確一維搜索

精確搜索計算量較大，特別是當迭代點遠離最優解時，效率很低；

而且，很多最優化方法的收斂速度并不依賴于精確一維搜索的過程。

非精確的一維搜索：通過計算少量的函數值，得到一個可接受步

長，使得后續迭代點使目標函數要“充分”下降,達到一個滿意水平，

非精確一維搜索方法可大大節省計算量，且總體上有較快的收斂速度。

不用尋找單谷區間！

包括Armijo-Goldstein準則和Wolfe準則。Armijo-Goldstein 準則

可能將目標函數的極小點給排除在可接受區域外！！ Wolfe將準則更

新后可避免最優解被排除。

2

2無約束優化

2.1一維搜索

（精確一維搜索，非精確一維搜索）

2.2最速下降法

基本思想：以負梯度方向為下降方向，利用精確一維搜索得最佳

步長。

最速下降法中，利用精確一維搜索求最佳步長，使得相鄰兩次迭

代的搜索方向總是垂直的，使得逼近極小點過程是“之”字形，這樣

從任何一個初始點開始，都可以很快到達極小點附近，但是越靠近極

小點步長越小，移動越慢，導致最速下降法的收斂速度很慢。實際運

用中，在可行的計算時間內可能得不到需要的結果。

優缺點：

優點：1方法簡單，每迭代一次的工作量和存貯量小；2從一個

不好的初始點出發，也能保證算法的收斂性。

缺點：1在極小值點附近收斂得很慢；2梯度法的收斂速度與變

量的尺度關系很大；3梯度法對小的擾動是不穩定的，這樣就可能破

壞方法的收斂性。

2.3牛頓法

基本思想：將目標函數二階泰勒展開，略去高階項后近似的替代

目標函數，然后用二次函數的極小點作為目標函數的近似極小點。

優點：

1初始點離最優解很近時，算法收斂速度快；

2算法簡單，不需要進行一維搜索(確定步長=1)；

3正定二次函數，迭代一次就可得到最優解。

缺點：

1對多數算法不具有全局收斂性，對初值依賴；

2每次迭代都要計算Hes矩陣的逆，計算量大；

3海塞矩陣的逆可能不存在或者對應方程組奇異(或病態);

4海塞矩陣可能非正定，d可能不是下降方向，算法也可能收斂

于最大值點或者鞍點。

3

2.4阻尼牛頓法：

基本思想：阻尼牛頓法中下降方向仍為牛頓方向，但最佳步長通

過精確一維搜索得到。

若f(x)存在二階連續偏導數，函數的Hes矩陣正定，且水平集

有界，則阻尼Newton法或者在有限步迭代后終止，即具有二次終止

性。

2.5共軛梯度法

用迭代點處的負梯度向量為基礎產生一組共軛方向的方法叫做

共軛梯度法。

最速下降法計算簡單，但收斂速度慢，Newton法(阻尼)具有收斂

速度快的優點，但需要計算Hes矩陣的逆，計算量大。共軛梯度法

它比最速下降法的收斂速度要快得多，同時又避免了像牛頓法所要求

的海塞矩陣的計算，存貯和求逆。

共軛梯度法的特點：

1對凸函數全局收斂（下降算法）；

2計算簡單，不用求Hes矩陣或者逆矩陣，計算量小，存儲量

小，每步迭代只需存儲若干向量，適用于大規模問題；

3具有二次收斂性；

4共軛梯度法的收斂速率不壞于最速下降法。如果初始方向不用

負梯度方向，則其收斂速率是線性收斂的；

2.6變尺度法（擬牛頓法）

最速下降法計算簡單，但收斂速度慢，Newton法(阻尼)具有收斂

速度快的優點，但需要計算Hes矩陣的逆。上述兩種方法可用一個

統一的模型描述，為減小計算量，用尺度矩陣近似代替海塞矩陣的逆，

由此產生搜索方向的方法稱為變尺度法。

特點：

1若尺度矩陣正定，，則每一迭代步總使得函數值下降，即算法

是穩定的。

2易計算性，尺度矩陣在迭代中逐次生成，初始矩陣為任一正定

矩陣，修正矩陣選取的不同，對應著不同的變尺度法。包括對稱秩1

4

校正公式、DFP算法、BFGS算法以及布洛伊登族尺度法。

對稱秩1校正公式：

SR1校正公式的缺點是尺度矩陣的正定性不具有遺傳性質，從能

可能導致算法終止，即算法不穩定。SR1的優點是其對海塞矩陣的逆

的近似比BFGS法還好；算法具有二次終止性。

DFP算法：

若目標函數是正定二次函數，則DFP算法經過有限步迭代必達

到極小點，既具有二次收斂性。若 f (x)是可微的嚴格凸函數，則DFP

算法全局收斂。實際運算中，由于舍入誤差的存在可能影響算法的穩

定性，但BFGS算法受到的影響要小得多。

BFGS算法：

它比DFP的數值穩定性更好并且在一定條件下可以證明在

BFGS法中使用不精確一維搜索時有全局收斂性。

2.7直接搜索法

直接搜索法包括：模式搜索法、Powell法、和單純形法。

1模式搜索法

Hooke & Jeeves方法：

逼近極小點,算法從初始基點開始,包括兩種類型的移動，探測移

動和模式移動。

探測移動：依次沿n個坐標軸進行,用以確定新的基點和有利于函數

值下降的方向。

模式移動：沿相鄰兩個基點連線方向進行。

Ronbrock算法(轉軸法)：

算法每次迭代包括探測階段和構造搜索方向兩部分。

探測階段:從一點出發,依次沿n個單位正交方向進行探測移動,

一輪探測之后,再從第1個方向開始繼續探測.經過若干輪探測移動,完

成一個探測階段。

構造搜索方向：利用探測階段得到的結果構造一組新的正交方向,

并將其單位化稱之為轉軸。下次探測方向按照最新生成的正交方向進

5

行探測。

2 Powell方法

基本思想：Powell方法主要由基本搜索、加速搜索和調整搜索方

向三個部分組成。基本搜索包括從基點出發沿著已知的n個搜索方向

進行一維搜索，確定一個新基點；加速搜索是沿著相鄰的兩個基點的

連線方向進行一維搜索，使函數下降更快；最后用基點連線方向代替

已知的n個搜索方向之一，構造新的搜索方向組并進行下一步迭代。

與模式搜索法的異同：

Powell方法用一維搜索取代模式搜索中的試探方式；

Powell方法的加速搜索采用的方式與模式搜索法類似，僅在步長

的取法上有一定差異，Powell方法仍然采用一維搜索方法；

Powell方法產生新的迭代方向，而模式搜索法迭代方向保持不變

或者產生正交迭代方向，與之相比，Powell方法所產生的迭代方向為

共軛方向，具有二次收斂性。

Powell法存在的問題：

在迭代中的n個搜索方向有時會變成線性相關而不能形成共軛

方向。這時組不成n維空間，可能求不到極小點。

3單純形法

基本思想：單純形替換法不是利用搜索方向從一個點迭代到另一個更

優的點，而是從一個單純形迭代到另一個更優的單純形。在單純形替

換算法中，從一個單純形到另一個單純形的迭代主要通過反射、擴張、

收縮和縮邊這4個操作來實現。

2.8信賴域算法

信賴域方法是把最優化問題轉化為一系列相對簡單的局部尋優

問題。方法能夠對局部的所有方向進行“搜索”，進而同時確定“局

部最好”的前進方向及長度。接著用某一評價函數來決定是否接受該

位移以及確定下一次迭代的信賴域。如果試探步較好，下一步信賴域

擴大或保持不變，否則減小信賴域。在迭代過程中不斷利用二次函數

模型對目標函數進行逐步逼近。

6

信賴域算法特點：

1這種方法既具有牛頓法的快速局部收斂性，又具有理想的全局

收斂性;

2不要求目標函數的Hes陣是正定的;

3利用了二次模型來求修正步長，使得目標函數的下降比線性搜

索方法更有效。

1折線法：

折線法思想：用低維空間內滿足一定要求的折線，代替最優曲線。

單折線法：

連接Cauchy點和牛頓點，其連線與信賴域的邊界的交點即為子

模型的近似解。

雙折線法：

原理：若信賴域迭代產生的點一開始就偏向牛頓方向，能夠改善

算法性能。于是把Cauchy點和牛頓方向上的N?點連接起來，這條連

線與信賴域邊界的交點即為子模型的近似最優解。

2.9非線性最小二乘

非線性最小二乘法包括Gauss-Newton法Levenberg-Marquardt法。

Gauss-Newton法

基本思想：Gauss-Newton法也可以看成是對目標函數線性化得到的。

Gauss-Newton法的優缺點：

1對于不是很嚴重的大殘量問題，有較慢的收斂速度。對于殘量很大

的問題，算法不收斂。對于小殘量問題，具有較快的局部收斂速度。

對于零殘量問題，具有局部二階收斂速度；

2如果雅克比矩陣不滿秩，方法沒有定義；算法不一定總體收斂。

3對于線性最小二乘問題，一步達到極小值點。

Levenberg-Marquardt法：

Gauss-Newton法在迭代過程中要求雅克比矩陣列滿秩以保證搜

索方向為下降方向，限制了其應用。L-M法則通過優化模型來獲取下

7

降方向。

3約束優化

3.1罰函數法

借助罰函數將約束非線性規劃轉化為一系列無約束問題，通過求

解無約束問題來求解約束非線性規劃。

外點法：

對違反約束的點在目標函數中加入相應的懲罰，可行點不予懲罰，

這種方法的迭代點一般在可行域D的外部移動。

內點法：

對從內部企圖穿越可行域D邊界的點在目標函數中加入障礙，

距邊界越近，障礙越大，在邊界上給予無窮大的障礙，從而保證迭代

點一直在可行域內部移動。

1內點法要求迭代點在可行域內部移動，初始點必須是內點，可

行域的內部必須是非空的，內點法只能處理不等式約束。

2懲罰函數的有效區域是約束的可行域，目標函數在可行域內的

所有點都受到懲罰，越靠近邊界懲罰越多。

3不同的懲罰因子對應不同的懲罰函數，懲罰因子越小，懲罰函

數的極小點越接近于邊界處的最優點。

4當懲罰因子趨近與零時，懲罰函數的極小點就是原約束問題的

最優點。

混合法：

外點法適用于求解一般約束問題，且初始值任意選取但求解結果

常為不可行解，內點法適于解僅含不等式約束問題，并且每次迭代的

點都是可行點。但要求初始點為可行域的內點，需要浪費相當的工作

量，將外點法和內點法結合，兩種懲罰函數聯合使用。

外點罰函數的特點：

1初始點可以任選，對等式約束和不等式約束均可適用；

2初始罰因子要選擇得當，否則會影響迭代計算的正常進行；

3每個近似解往往不是可行解，這是某些實際問題所無法接受的；

8

4外點法中要求罰因子趨于無窮大，而罰因子太大將造成增廣目

標函數的Hes陣條件數越大，趨于病態，給無約束問題求解增加很

大困難，甚至無法求解。

5如果在可行域外目標函數f(x)的性質復雜或者沒有定義時，外

點法不適用了。

內點罰函數法的幾點說明：

1使用內點法時，初始點應選擇一個離約束邊界較遠的可行點。

如果太靠近某一約束邊界，求解無約束優化問題時可能會發生困難。

2懲罰因子的初值應適當，否則會影響迭代計算的正常進行。

3為求解約束優化問題，需要求解一系列的無約束優化問題，計

算量大，且罰因子的選取方法對收斂速度的影響比較大。并且罰因子

的增大（外點法）與縮小（內點法）使得問題的求解變得很困難。常

常會使增廣目標函數趨于病態。

3.2乘子法

1 Hestenes法

Hestenes乘子法相當于對拉格朗日函數進行外點懲罰。結論：將

等式約束優化問題轉化為增廣拉格朗日函數求解問題（無約束優化問

題），乘子法不需過分地增大懲罰因子，確實比外點法有效很多。

2 Powell法

3 Rockafellar法

Rockafellar在1973年將乘子法推廣到不等式約束優化問題，其

思想是引入松弛變量，將不等式約束轉化為等式約束。此乘子法比外

點法收斂速度快很多。

3.3二次逼近法

對于較為復雜的非線性問題，一種很自然的想法：將問題的約束

和目標函數通過泰勒展式線性化(二次規劃時，目標函數的拉格朗日

函數展開為二次逼近函數)。數值實驗表明，二次逼近法具有很好的

計算效率。

9

有效集法：

等式約束下的二次規劃問題有很多求解方法，如消去法、QR分

解法等。上述求解方程組對病態方程組求解會遇到一定困難。

有效集法：只要能夠找到最優解對應的有效集，就可以通過求解

等式約束下的二次規劃問題得到最優解。從二次規劃問題的一個子問

題出發，求出對應的有效集，然后按照使目標函數減少的原則，對有

效集不斷調整，直到迭代到最優解對應的有效集為止。

3.4可行方向法

基本思想：從可行點出發，沿著下降的可行方向進行搜索，求出

使目標函數值下降的新的可行點，直到滿足終止條件，得到最優解

x*。

可行方向法的核心是選擇可行下降搜索方向和確定搜索步長。搜

索方向的選擇方式不同就形成不同的可行方向法。如Frank Wolfe方

法、梯度投影法、既約梯度法。

梯度投影法：

基本思想: 當迭代點在可行域內部時，取該點處的負梯度方向為

可行下降方向；當迭代點在可行域邊界上時，取該點處負梯度方向在

可行域邊界上的投影產生一個可行下降方向．

目標函數的最速下降方向是負梯度方向．但是，在有約束情況下，

沿最速下降方向移動可能導致非可行點．對負梯度進行投影，使得目

標函數值不僅改進，同時又保持迭代點的可行性．

既約梯度法:

基本思想：借鑒求解線性規劃的單純形算法，選擇某些變量為基

變量，其它的作為非基變量，將基變量用非基變量表示，并從目標函

數中消去基變量，得到以非基變量為自變量的簡化的目標函數，進而

利用此函數的負梯度構造下降可行方向。

Frank Wolfe方法:

算法思想：在每次迭代中,將目標函數線性化，通過求解線性規

劃方法求得可行下降方向,并沿該方向在可行域內進行一維搜索。

10