第二節(jié) 優(yōu)化基礎(chǔ)

一、最優(yōu)化

（一）最優(yōu)化問題

在現(xiàn)實社會中，人們經(jīng)常遇到這樣一類問題：判別在一個問題的眾多解決方案中什么樣的方案最佳，以及如何找出最佳方案。例如，在資源分配中，如何分配有限資源，使得分配方案既能滿足各方面的需求，又能獲得好的經(jīng)濟(jì)效益；在工程設(shè)計中，如何選擇設(shè)計參數(shù)，使得設(shè)計方案既能滿足設(shè)計要求，又能降低成本等。這類問題就是在一定的限制條件下使得所關(guān)心的指標(biāo)達(dá)到最優(yōu)。最優(yōu)化就是為解決這類問題提供理論基礎(chǔ)和求解方法的一門數(shù)學(xué)學(xué)科。

在量化求解實際最優(yōu)化問題時，首先要把實際問題轉(zhuǎn)化為數(shù)學(xué)問題，建立數(shù)學(xué)模型。最優(yōu)化數(shù)學(xué)模型主要包括三個要素：決策變量和參數(shù)、約束或限制條件、目標(biāo)函數(shù)。

連續(xù)變量優(yōu)化模型的數(shù)學(xué)模型一般形式可以寫為：

式中，x=(x1,x2,…,xn)T∈Rn，x即是n維向量，是指需要確定的未知數(shù)，在實際問題中也常常把變量x1,x2,…,xn叫決策變量；f(x)，hi(x)(i=1,2,…,m)，gj(x)(j=1,2,…,p)為x的函數(shù)，s.t.為英文“subject to”的縮寫，表示“受限制于”。

求極小值的函數(shù)f(x)稱為目標(biāo)函數(shù)，是要求達(dá)到極小的目標(biāo)的衡量。hi(x)(i=1,2,…,m)，和gj(x)(j=1,2,…,p)稱為約束函數(shù)，其中hi(x)=0稱為等式約束，而gj(x)≥0稱為不等式約束。

對于求目標(biāo)函數(shù)極大值的問題，由于max f(x)與min[-f(x)]的最優(yōu)解相同，因而可轉(zhuǎn)化為目標(biāo)函數(shù)的相反數(shù)求解極小值：min[-f(x)]。

滿足約束條件式（2-35）和式（2-36）的x稱為可行解，由全體可行解構(gòu)成的集合稱為可行域，記為D，即

對一般模型（P），最優(yōu)解具有如下定義：

定義2-1 若存在x?∈D，使得x≠x?對任意x∈D，均有f（x?）≤f（x），則稱x?為最優(yōu)化問題（P）的整體最優(yōu)解。

定義2-2 若存在x?∈D，使得對任意x∈D，均有f（x?）＜f（x），則稱x?為最優(yōu)化問題（P）的嚴(yán)格整體最優(yōu)解。

定義2-3 若存在x?∈D及x?的一個鄰域Nε（x?），使得對任意x∈D∩Nε（x?），均有f（x?）≤f（x），則稱x?為最優(yōu)化問題（P）的局部最優(yōu)解，其中，ε＞0}。

定義2-4 若存在x?∈D及x?的一個鄰域Nε（x?），使得對任意x∈D∩Nε（x?），x≠x?，均有f（x?）＜f（x），則稱x?為最優(yōu)化問題（P）的嚴(yán)格局部最優(yōu)解。

根據(jù)數(shù)學(xué)模型中有無約束函數(shù)分類，最優(yōu)化問題可分為有約束的最優(yōu)化問題和無約束的最優(yōu)化問題。在數(shù)學(xué)模型中m=0，p=0時，即不存在約束的最優(yōu)化問題稱為無約束最優(yōu)化問題，否則稱為約束最優(yōu)化問題。

（二）凸集

凸集和凸函數(shù)在最優(yōu)化的理論中十分重要，稱為凸優(yōu)化。

凸優(yōu)化具有良好的性質(zhì)，比如局部最優(yōu)解是全局最優(yōu)解；凸優(yōu)化問題是多項式時間可解問題，如線性規(guī)劃問題。此外，很多非凸優(yōu)化或NP-Hard問題也可以使用對偶、松弛（擴(kuò)大可行域，去掉部分約束條件）方法轉(zhuǎn)化成凸優(yōu)化問題，在SVM算法中，為了對目標(biāo)函數(shù)進(jìn)行優(yōu)化，就使用了拉格朗日乘子法、對偶問題、引入松弛因子等。

因此，本節(jié)主要介紹凸集的相關(guān)定義和性質(zhì)。

1.凸集

定義2-5 設(shè)集合D?Rn，若對于任一點x，y∈D及實數(shù)α∈[0，1]，都有：

則稱集合D為凸集。

凸集的直觀幾何表示如圖2-1所示：左側(cè)為凸集，右側(cè)為非凸集，因為右邊的集合中任意兩點x和y連線之間的點有時不屬于該集合。

凸集具有如下性質(zhì)（設(shè)Di?Rn，i=1，2，…，k）：

1）設(shè)D1,D2,…,Dk是凸集，則它們的交D=D1∩D2∩…∩Dk是凸集；

2）設(shè)D是凸集，β為一實數(shù)，則集合βD={y|y=βx,x∈D}是凸集；

3）設(shè)D1,D2是凸集，則D1與D2的和D1+D2={y|y=x+z,x∈D1,z∈D2}是凸集。

2.凸組合

定義2-6 設(shè)xi∈Rn，i=1，2，…，k，實數(shù)λi≥0，，則稱為x1，x2，…，xk的凸組合。

由凸集的定義知，凸集中任意兩點的凸組合屬于凸集。

3.極點

定義2-7 設(shè)D是凸集，若D中的點x不能稱為D中任何線段上的內(nèi)點，則稱x為凸集D的極點。

極點的直觀幾何表示如圖2-2所示。

（三）凸函數(shù)

明確凸集的概念后，可以進(jìn)一步介紹凸函數(shù)的定義和性質(zhì)。凸函數(shù)具有很好的極值特性，這使它在非線性規(guī)劃中占有重要的地位。凹函數(shù)與凸函數(shù)相似，凸函數(shù)具有全局極小值，凹函數(shù)具有全局極大值，兩者之間可以很方便地進(jìn)行轉(zhuǎn)換。

1.凸函數(shù)

定義2-8 設(shè)函數(shù)f（x）定義在凸集D?Rn上。若對于任意的x，y∈D及任意實數(shù)α∈[0，1]，都有

則稱f(x)為凸集D上的凸函數(shù)。

對于一元凸函數(shù)，其幾何表現(xiàn)如圖2-3所示。

在曲線上任取兩點，之間的弦位于弧之上。

2.嚴(yán)格凸函數(shù)

定義2-9 設(shè)函數(shù)f（x）定義在凸集D?Rn上。若對于任意的x，y∈D，x≠y，及任意實數(shù)α∈（0，1），都有

則稱f(x)為凸集D上的嚴(yán)格凸函數(shù)。

3.凸函數(shù)的性質(zhì)

1）設(shè)f（x）是凸集D?Rn上的凸函數(shù)，實數(shù)k≥0，則kf（x）也是D上的凸函數(shù)；

2）設(shè)f1（x），f2（x）是凸集D?Rn上的凸函數(shù)，實數(shù)λ≥0，μ≥0，則λf1（x）+μf2（x）也是D上的凸函數(shù)；

3）設(shè)f（x）是凸集D?Rn上的凸函數(shù)，β為實數(shù)，則水平集s(f,β)={x|x∈D，f（x）≤β}是凸集；

4）f（x）是凸集D?Rn上的凹函數(shù)的充分必要條件是[-f（x）]是凸集D?Rn上的凸函數(shù)。

4.凸函數(shù)的判斷

判斷一個函數(shù)是否為凸函數(shù)，最基本的方法是使用其定義。但對于可微函數(shù)，下面介紹的兩個判定定理可能更為有效。

定理2-1（一階判別定理） 設(shè)在凸集D?Rn上f（x）可微，則f（x）在D上為凸函數(shù)的一階充分必要條件是對任意的x，y∈D，有

定理2-2（二階判別定理） 設(shè)在開凸集D?Rn內(nèi)f（x）二階可微，則

1）f（x）為凸集D內(nèi)的凸函數(shù)的二階充分必要條件為在D內(nèi)任何一點x處，f（x）的二階偏導(dǎo)數(shù)組成的矩陣即黑塞矩陣?2f(x)為半正定矩陣。

2）若在D內(nèi)?2f(x)為正定矩陣，則f（x）在凸集D內(nèi)為嚴(yán)格凸函數(shù)。

5.常用凸函數(shù)判斷方法

下面給出一些常用的快速判別凹、凸函數(shù)的方法：

1）指數(shù)函數(shù)是凸函數(shù)；

2）對數(shù)函數(shù)是凹函數(shù)，負(fù)對數(shù)函數(shù)是凸函數(shù)；

3）對一個凸函數(shù)進(jìn)行仿射變換，可以理解為線性變換，結(jié)果仍為凸函數(shù)；

4）二次函數(shù)是凸函數(shù)（二次項系數(shù)為正）；

5）正態(tài)分布（又稱高斯分布）函數(shù)是凹函數(shù)；

6）常見的范數(shù)函數(shù)是凸函數(shù)；

7）多個凸函數(shù)線性加權(quán)，如果權(quán)值大于等于零，那么整個加權(quán)結(jié)果函數(shù)為凸函數(shù)。

二、無約束最優(yōu)化問題

這里討論無約束最優(yōu)化問題的數(shù)學(xué)模型

求解無約束最優(yōu)化問題（P）的基本方法是給定一個初始點x0，依次產(chǎn)生一個點列x1，x2，…，xk，…，記為{xk}，使得或者某個xk恰好是問題的一個最優(yōu)解，或者該點列{xk}收斂到問題的一個最優(yōu)解x?，這就是迭代算法。

在迭代算法中由點xk迭代到xk+1時，要求f(xk+1)≤f(xk)，稱這種算法為下降算法，點列{xk}的產(chǎn)生，通常由兩步完成。首先在xk點處求一個方向pk，使得f(x)沿方向pk移動時函數(shù)值有所下降，一般稱這個方向為下降方向或搜索方向。然后以xk為出發(fā)點，以pk為方向做射線xk+αpk，其中α>0，在此射線上求一點xk+1=xk+αkpk，使得f(xk+1)<f(xk)，其中αk稱為步長。

下降法如算法2-1所示：

對于迭代算法，我們還要給出某種終止準(zhǔn)則。當(dāng)某次迭代滿足終止準(zhǔn)則時，就停止計算，而以這次迭代所得到的點xk或xk+1為最優(yōu)解x?的近似解，常用的終止準(zhǔn)則有以下幾種。

1）‖xk+1-xk‖＜ε或；

2）|f（xk+1）-f（xk）|＜ε或；

3）‖?f（xk）‖=‖gk‖＜ε；

4）上述三種終止準(zhǔn)則的組合。

其中，ε>0是預(yù)先給定的適當(dāng)小的實數(shù)。

下面介紹幾種常用的優(yōu)化算法。

（1）一維搜索。

最優(yōu)化問題有明顯的幾何意義，往往可以用圖解法獲得最優(yōu)解。一維搜索又稱一維優(yōu)化，是指求解一維目標(biāo)函數(shù)的最優(yōu)解的過程，已知xk，并且求出了xk處的下降方向pk，從xk出發(fā)，沿方向pk求目標(biāo)函數(shù)的最優(yōu)解，即求解問題

或者

稱為一維搜索，設(shè)其最優(yōu)解為αk，于是得到一個新點

所以一維搜索是求解一元函數(shù)φ(α)的最優(yōu)化問題（也叫一維最優(yōu)化問題）。我們把此問題仍表示為

（2）最速下降法。

對于無約束最優(yōu)化問題考慮下降算法，最速下降法是其他許多算法的基礎(chǔ)，它的計算過程就是沿梯度下降的方向求解極小值。在多元函數(shù)f(x)中，由泰勒公式有

由于

式中，θ為p與-g(x)的夾角。當(dāng)θ=0°時，cos θ=1，因此，負(fù)梯度方向使目標(biāo)函數(shù)f(x)下降最快，稱為最速下降方向。

最速下降法如算法2-2所示：

（3）牛頓法。

最速下降法的本質(zhì)是用線性函數(shù)去近似目標(biāo)函數(shù)，可以考慮對目標(biāo)函數(shù)的高階逼近得到快速算法，牛頓法就是通過用二次模型近似目標(biāo)函數(shù)得到的。假設(shè)f（x）是二階連續(xù)可微函數(shù)，設(shè)xk為f（x）的極小點x?的一個近似，將f（x）在xk附近做泰勒展開，有

式中，fk=f（xk），gk=g（xk），Gk=G（xk），若Gk正定，則qk（x）有唯一極小點，將它取為x?的下一次近似xk+1。由一階必要條件可知，xk+1應(yīng)滿足

即

令xk+1=xk+pk，其中pk稱為牛頓方向，應(yīng)滿足

上述方程組稱為牛頓方程，也可以從中解出pk并代入迭代公式，得到

即稱為牛頓迭代公式。

根據(jù)上面推導(dǎo)，牛頓法如算法2-3所示：

（4）共軛梯度法。

牛頓法每步計算量很大，因此放松要求，認(rèn)為經(jīng)過有限次迭代就可得到正定二次函數(shù)極小點的算法是比較有效的。共軛梯度法的基本思想是在共軛方向法和最速下降法之間建立某種聯(lián)系，以求得到一個既有效又有較好收斂性的算法。

對正定二次函數(shù)，由初始下降方向取為

確定共軛方向，并且采用精確一維搜索得到的共軛梯度法，在m(m≤n)次迭代后可求得二次函數(shù)的極小點，并且對所有i∈{1,2,…,m}，有

然后通過設(shè)法消去表達(dá)式中的G，使算法便于推廣到一般的目標(biāo)函數(shù)。

（5）擬牛頓法。

擬牛頓法不需要二階導(dǎo)數(shù)的信息，有時比牛頓法更為有效。擬牛頓法是一類使每步迭代計算量少而又保持超線性收斂的牛頓型迭代法，條件類似于牛頓法，給出以下迭代公式：

其中，αk為迭代步長。若令，則上式為牛頓迭代公式。擬牛頓法就是利用目標(biāo)函數(shù)值和一階導(dǎo)數(shù)的信息，構(gòu)造合適的Hk來逼近，使得既不需要計算，算法又收斂得快。為此，Hk的選取應(yīng)滿足以下的條件：

1）Hk是對稱正定矩陣。顯然，當(dāng)Hk是對稱正定矩陣時，若gk≠0，則

從而pk=-Hkgk為下降方向。

2）Hk+1由Hk經(jīng)簡單形式修正而得Hk+1=Hk+Ek，其中，Ek稱為修正矩陣，此式稱為修正公式。

我們希望經(jīng)過對任意初始矩陣H0的逐步修正能得到的一個好的逼近。令

由泰勒公式，有

當(dāng)Gk+1非奇異時，有，對于二次函數(shù)，該式為等式。

因為目標(biāo)函數(shù)在極小點附近的性態(tài)與二次函數(shù)近似，所以一個合理的想法就是，如果使Hk+1滿足

那么Hk+1就可以較好地近似。上式稱為擬牛頓方程，如果修正公式滿足擬牛頓方程，則相應(yīng)算法稱為擬牛頓法。顯然Hk+1yk=sk中有(n2+n)/2個未知數(shù)，n個方程，所以一般有無窮多個解，故由擬牛頓方程確定的是一族算法，稱為擬牛頓法。

三、約束最優(yōu)化問題

在解決實際問題時，經(jīng)常會遇到約束最優(yōu)化問題，這類優(yōu)化問題要比無約束最優(yōu)化問題困難得多，也復(fù)雜得多。而由于約束最優(yōu)化問題的應(yīng)用極其廣泛，所以人們一直在努力尋找它的求解方法，目前已出現(xiàn)很多種有效的求解方法。

本節(jié)主要研究一般性的約束最優(yōu)化問題：

的計算方法。

其中，問題（P1）的可行域為D={x|ci（x）=0,i=1,2,…,l,ci(x)≥0,i=l+1,l+2,…,m}。

（一）約束優(yōu)化問題的最優(yōu)性條件

約束優(yōu)化問題的最優(yōu)性條件是指最優(yōu)化問題的目標(biāo)函數(shù)與約束函數(shù)在最優(yōu)解處應(yīng)滿足的充分條件、必要條件和充要條件，是最優(yōu)化理論的重要組成部分，對最優(yōu)化算法的構(gòu)造及算法的理論分析都是至關(guān)重要的。

對一般性優(yōu)化問題（P1），可給出部分庫恩-塔克必要定理的內(nèi)容：

定理2-3（庫恩-塔克必要條件） 若

1）x?為局部最優(yōu)解，其有效集I?={i|ci（x?）=0,i∈I}；

2）f（x），ci（x）(i=1,2,…,m)在點x?可微；

3）對所有i∈E∪I?，?ci（x?）線性無關(guān)，則存在向量使得

通常稱式（2-69）為庫恩-塔克條件或KT條件，滿足式（2-69）的點x?稱為KT點。

m+n維函數(shù)

稱為問題（P1）的拉格朗日函數(shù)，于是式（2-69）中的即為?xL（x?，λ?）=0，其中λ?稱為拉格朗日乘子向量，矩陣

稱為拉格朗日函數(shù)在處的黑塞矩陣，記為ω?，即。

定理2-4（二階充分條件） 設(shè)f（x）和ci（x）(i∈E∪I)是二階連續(xù)可微函數(shù)，若存在x?∈Rn，x?為一般約束優(yōu)化問題（P1）的可行點，且滿足：

1）為KT對，且嚴(yán)格互補(bǔ)松弛條件成立；

2）對子空間中的任意d≠0，有dTω?d＞0，則x?為問題（P1）的嚴(yán)格局部最優(yōu)解。

（二）罰函數(shù)法與乘子法

目前已有許多種求解無約束最優(yōu)化問題的有效的算法，所以一種自然的想法就是設(shè)法將約束問題的求解轉(zhuǎn)化為無約束問題的求解。具體說就是根據(jù)約束的特點，構(gòu)造某種“懲罰”函數(shù)，然后把它加到目標(biāo)函數(shù)中，將約束問題的求解轉(zhuǎn)化為一系列無約束問題的求解。這種“懲罰”策略將使得一系列無約束問題的極小點或者無限地靠近可行域，或者一直保持在可行域內(nèi)移動，直至迭代點列收斂到原約束問題的最優(yōu)解。這類算法主要有三種：外罰函數(shù)法、內(nèi)罰函數(shù)法和乘子法。

1.外罰函數(shù)法

外罰函數(shù)法的懲罰策略是對于在無約束問題的求解過程中企圖違反約束的那些迭代點給予很大的目標(biāo)函數(shù)值，迫使這一系列無約束問題的極小點（迭代點）無限向容許集靠近。

對一般約束最優(yōu)化問題

可行域為D={x|ci(x)=0,i=1,2,…,l,ci(x)≥0,i=l+1,l+2,…,m}；

構(gòu)造如下罰函數(shù)：

其中

顯然有

函數(shù)p（x,σ）稱為約束問題（P1）的增廣目標(biāo)函數(shù)，稱為問題的罰函數(shù)，參數(shù)σ>0稱為罰因子。

于是求解約束問題（P1）就轉(zhuǎn)化為求增廣目標(biāo)函數(shù)p（x,σ）的系列無約束極小min p（x,σk），即求解

其中 {σk}為正的數(shù)列，且σk→+∞。

那么如何通過來求解約束最優(yōu)化問題（P1）呢？首先給出一個定理：

定理2-5 對于某個給定σk，若是無約束問題的極小點，則是約束問題（P1）的極小點的充要條件是是約束問題（P1）的可行點。

證明：

1）必要性：因為極小點必定是可行點，所以必要性顯然成立。

2）充分性：設(shè)，這里的D是約束問題（P1）的可行域，那么對于?x∈D，總有：

所以是約束問題（P1）的極小點。

定理2-5說明，若由無約束問題解出的極小點是約束問題（P1）的可行點，那就是約束問題（P1）的極小點。此時只需求解一次無約束問題即可，但在實際中，這種情況很少發(fā)生，即一般不屬于可行域D，那么這時求得的一定不是約束問題（P1）的極小點，需要再進(jìn)一步增大σk，重新求解無約束問題，新的極小點會進(jìn)一步向可行域靠近，也就是進(jìn)一步向式（2-69）的極小點靠近。

構(gòu)建外罰函數(shù)法的求解算法如算法2-4所示：

對已知一般性約束優(yōu)化問題（P1）：

2.內(nèi)罰函數(shù)法

為使迭代點總是可行點，使迭代點始終保持在可行域內(nèi)移動，可以使用這樣的“懲罰”策略，即在可行域的邊界上豎起一道趨向于無窮大的“圍墻”，把迭代點擋在可行域內(nèi)，直到收斂到約束問題的極小點。不過這種策略只適用于不等式約束問題，并且要求可行域內(nèi)點集非空，否則每個可行點都是邊界點，都加上無窮大的懲罰，懲罰方法也就失去了意義。

對不等式約束問題

當(dāng)x從可行域D={x∈Rn|ci(x)≥0,i=1,2,…,m}的內(nèi)部趨近于邊界時，則至少有一個ci(x)趨于零，因此，可構(gòu)造如下增廣目標(biāo)函數(shù)：

其中或稱為內(nèi)罰函數(shù)或障礙函數(shù)，參數(shù)r>0仍稱為罰因子，我們?nèi)≌臄?shù)列{rk}且rk→0，則求解不等式約束優(yōu)化問題轉(zhuǎn)化為求解系列無約束問題，即

這種從可行域內(nèi)部逼近最優(yōu)解的方法稱為內(nèi)罰函數(shù)法或SUMT內(nèi)點法。

內(nèi)罰函數(shù)法的算法如下：

已知不等式約束問題，且其可行域的內(nèi)點集D0≠?，取控制誤差ε＞0和罰因子的縮小系數(shù)0＜c＜1（比如可取ε=10-4，c=0.1）。

求解算法如算法2-5所示：

無約束優(yōu)化問題的解法目前已有許多很有效的算法，所以在求解約束優(yōu)化問題時，技術(shù)人員一般樂于采用罰函數(shù)法。內(nèi)點法適合解僅含不等式的約束問題，且每次迭代的點都是可行點，但要求初始點為可行域的內(nèi)點需耗費大量工作量，且不能處理等式約束。外點法能夠解決一般約束優(yōu)化問題，欲使無約束問題的解接近于原約束問題的解，應(yīng)選取很大的σ，但為減輕求解無約束問題的困難，又應(yīng)選取較小的σ，否則增廣目標(biāo)函數(shù)趨于病態(tài)。這些是罰函數(shù)法的固有弱點，限制其應(yīng)用。

3.乘子法

罰函數(shù)法雖然易于操作，但是也存在缺點，比如由罰因子σk→∞（或rk→0）引起的增廣目標(biāo)函數(shù)病態(tài)性質(zhì)。那么能否克服這個缺點呢？回答是肯定的。將拉格朗日函數(shù)與外罰函數(shù)結(jié)合起來，函數(shù)稱為增廣拉格朗日函數(shù)，通過求解增廣拉格朗日函數(shù)的系列無約束問題的解來獲得原約束問題的解，可以克服上述缺點，這就是下面要介紹的乘子法。

一般性約束問題（P1）的乘子法：

對一般約束優(yōu)化問題（P1）：

有增廣拉格朗日函數(shù)為

乘子的修正公式為：

令，則終止準(zhǔn)則為ψk≤ε。

據(jù)此，Rockafellar在PH算法的基礎(chǔ)上提出了一般約束問題的乘子——PHR算法，如算法2-6所示：

（三）可行方向法

可行方向法是一類直接求解約束優(yōu)化問題的重要方法，這類方法的基本思想為：從給定的一個可行點xk出發(fā)，在可行域內(nèi)沿一個可行下降方向pk進(jìn)行搜索，求出使目標(biāo)函數(shù)值下降的新可行點xk+1=xk+αkpk，如果xk+1仍不是問題的最優(yōu)解，則可重復(fù)上述步驟，直到得到最優(yōu)解為止。選擇可行方向pk的策略不同，則形成不同的方法，此處不做過多介紹。

（四）投影梯度法

投影梯度法就是利用投影矩陣來產(chǎn)生可行下降方向的方法。它是從一個基本可行解開始，由約束條件確定出凸約束集邊界上梯度的投影，以便求出下次的搜索方向和步長，每次搜索后都要進(jìn)行檢驗，直到滿足精度要求為止。

定義2-10 設(shè)n階方陣p滿足p=pT且pp=p，則稱p為投影矩陣。

投影梯度法的算法如算法2-7所示：

（五）簡約梯度法——RG法

簡約梯度法的基本思想是利用線性約束條件，將問題的某些變量用一組獨立變量表示，來降低問題的維數(shù)，利用簡約梯度構(gòu)造下降可行方向進(jìn)行線性搜索，逐步逼近問題的最優(yōu)解，如算法2-8所示：