第07章無約束問題

在科學(xué)管理和其他領(lǐng)域中，很多實(shí)際問題可以歸結(jié)為線性規(guī)劃問題，其目標(biāo)函數(shù)和約束條件都是自變量的一次函數(shù)。但是，還有另外一些問題，其目標(biāo)函數(shù)和(或)約束條件很難用線性函數(shù)來表達(dá)。如果目標(biāo)函數(shù)或約束條件中含有非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題。解這種問題要用非線性規(guī)劃的方法以。由于很多實(shí)際問題要求進(jìn)一步精確化以及電子計(jì)算機(jī)的發(fā)展，使非線性規(guī)劃在近幾十年來得以快速發(fā)展。目前，它已成為運(yùn)籌學(xué)的重要分支之一，并在最優(yōu)設(shè)計(jì)、管理科學(xué)、系統(tǒng)控制等許多領(lǐng)域得到越來越廣泛的應(yīng)用。02二月2023非線性規(guī)劃

一般來說，由于非線性函數(shù)的復(fù)雜性，解非線性規(guī)劃問題要比解線性規(guī)劃問題困難得多。而且，也水像線性規(guī)劃有單純形法等通用方法，非線性規(guī)劃目前沒有適于各種問題的一般算法，各個(gè)方法都有自己特定的適用范圍。這是需要人們更深入地進(jìn)行研究的一個(gè)領(lǐng)域。

為了敘述方便，用大寫字母代表n維歐氏空間中的向量(點(diǎn))，而以相應(yīng)的小字字母代表該向量的分量(點(diǎn)的坐標(biāo))。此外，所用到的向量，均規(guī)定為列向量。02二月2023非線性規(guī)劃第七章無約束問題OperationalResearch(OR)東北農(nóng)業(yè)大學(xué)工程學(xué)院王吉權(quán)7.1基本概念7.2一維搜索7.3無約束極值問題的解法02二月20234第七章非線性規(guī)劃1.問題的提出

讓我們先看兩個(gè)例子。

例1某公司經(jīng)營(yíng)兩種產(chǎn)品，第一種產(chǎn)品每件售價(jià)30元，第二種產(chǎn)品每件售價(jià)450元。根據(jù)統(tǒng)計(jì)，售出一件第一種產(chǎn)品所需要的服務(wù)時(shí)間平均為0.5小時(shí)，第二種產(chǎn)品是(2+0.25x2)小時(shí)，其中x2是第二種產(chǎn)品的售出數(shù)量。已知該公司在這段時(shí)間內(nèi)的總服務(wù)時(shí)間為800小時(shí)，試決定使其營(yíng)業(yè)額最大的營(yíng)業(yè)計(jì)劃。02二月202357.1基本概念7.1.1引言

設(shè)該公司計(jì)劃經(jīng)營(yíng)第一種產(chǎn)品x1件，第二種產(chǎn)品x2件。根據(jù)題意，其營(yíng)業(yè)額為f(X)=30x1+450x2

由于服務(wù)時(shí)間的限制，該計(jì)劃必須滿足0.5x1+(2+0.25x2)x2800此外，這個(gè)問題還應(yīng)滿足x10,x20

如此，得到這個(gè)瓿的數(shù)學(xué)模型如下：02二月202367.1基本概念7.1.1引言例2為了進(jìn)行多屬性問題(假設(shè)有n個(gè)屬性)的綜合評(píng)價(jià)，就需要確定每個(gè)屬性的相對(duì)重性，即求它們的權(quán)重。為此將各屬性的重要性(對(duì)評(píng)價(jià)者或決策者而言)進(jìn)行兩兩比較從而得出如處判斷矩陣02二月202377.1基本概念7.1.1引言其中，元素aij是第i個(gè)屬性的重要性與第j個(gè)屬性的重要性之比。

現(xiàn)需從判斷矩陣求出各屬性的權(quán)重wi(i=1,2,…,n)。為了使求出的權(quán)向量W=(w1,w2,…,wn)T在最小二乘意義上能最好的反映判斷矩陣的估計(jì)，由aijwi/wj，可得02二月202387.1基本概念7.1.1引言

例1的目標(biāo)函數(shù)為自變量的線性函數(shù)，但其第一個(gè)約束條件卻是自變量的二次函數(shù)。因而它是非線性規(guī)劃問題。例2的目標(biāo)函數(shù)是自變量的非線性函數(shù)，所以它也是非線性規(guī)劃問題。02二月202397.1基本概念7.1.1引言非線性規(guī)劃數(shù)學(xué)模型的一般形式是：其中，X=(x1,x2,…,xn)T是n維歐氏空間En中的點(diǎn)(向量)，f(X)為目標(biāo)函數(shù)，hi(X)0，gj(X)0為約束條件。02二月202310(7-1)2.非線性規(guī)劃問題的數(shù)學(xué)模型(7-2)(7-3)7.1基本概念7.1.1引言

由于maxf(X)=-min[-f(X)]，當(dāng)需使目標(biāo)函數(shù)極大化時(shí)，只需使其負(fù)值極小化即可。因而僅考慮目標(biāo)函數(shù)極小化，這無損于一般性。

若某約束條件是“”不等式時(shí)，僅需用“-1”乘該約束的兩端，始可將這個(gè)約束變?yōu)椤啊钡男问健?/p>

由于等式約束hi(X)=0等價(jià)于下述兩個(gè)不等式約束：02二月2023117.1基本概念7.1.1引言因而，也可將非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式02二月202312(7-4)(7-5)7.1基本概念7.1.1引言

圖示法可以給人以直觀概念，當(dāng)只有兩個(gè)自變量時(shí)，非線性規(guī)劃問題也可像線性規(guī)劃那樣用圖法來表示(如圖7-1所示)。

考慮非線性規(guī)劃問題02二月2023132.非線性規(guī)劃問題的圖示(7-6)(7-7)7.1基本概念7.1.1引言圖7-102二月202314x1x26320236ABCDf(X)=2f(X)=47.1基本概念7.1.1引言若令其目標(biāo)函數(shù)f(X)=c其中，c為某一常數(shù)，則(7-8)式代表目標(biāo)函數(shù)值等于c的點(diǎn)的集合，它一般為一條曲線或一張曲面，通常稱其為等值線或等值面。對(duì)于這個(gè)例子來說，若令目標(biāo)函數(shù)(7-6)式分別等于2和4，就得到相應(yīng)的兩條圓形等值線(圖7-1)。由圖可見，等值線f(X)=2和約束條件直線AB相切，切點(diǎn)D即為此問題的最優(yōu)解：x1*=x3*=3，其目標(biāo)函數(shù)值f(X*)=2。02二月202315(7-8)7.1基本概念7.1.1引言

在這個(gè)例子中，約束條件(6-7)式對(duì)最優(yōu)解是有影響的。

現(xiàn)若以h(X)=x1+x2-60代替約束條件(7-7)式，則非線性規(guī)劃問題(7-6)式、(7-9)式的最優(yōu)解是x1=x2=2，即圖6-1中的C點(diǎn)(這時(shí)f(X)=0)。由于最優(yōu)點(diǎn)位于可行域的內(nèi)部，故對(duì)這個(gè)問題的最優(yōu)解來說，約束(7-9)式事實(shí)上是不起作用的。在求這個(gè)問題的最優(yōu)解時(shí)，可不考慮約束條件(7-9)式，就相漢于沒有這個(gè)約束一樣。02二月202316(7-9)7.1基本概念7.1.1引言

在高等數(shù)學(xué)課程中，已學(xué)過一元函數(shù)和多元函數(shù)的極值問題，現(xiàn)僅扼要說明如下。1.局部極值和全局極值

由于線性規(guī)劃的目標(biāo)函數(shù)為線性函數(shù)，可行域?yàn)橥辜蚨蟪龅淖顑?yōu)解就是在整個(gè)可行域的全局最優(yōu)解。非線性規(guī)劃則不然，有時(shí)求出的某個(gè)解雖是一部分可行域中的極值點(diǎn)，但卻并不一定是整個(gè)可行域上的全局最優(yōu)解。02二月2023177.1基本概念7.1.2極值問題

設(shè)f(X)為定義在n維歐氏空間En的某一區(qū)域R上的n元實(shí)函數(shù)，其中X=(x1,x2,…,xn)T。對(duì)于X*R，如果存在某個(gè)>0，使所有與X*的距離小于的XR(即XR且||X-X*||<)均滿足不等式f(X)f(X*)，則稱X*為f(X)在R上的局部極小點(diǎn)(或相對(duì)極小點(diǎn))，f(X*)為局部極小值。若對(duì)于所有XX*且與X*的距離小于的XR，f(X)>f(X*)，則稱X*為f(X)在R上的嚴(yán)格局部極小點(diǎn)，f(X*)為嚴(yán)格局部極小值。02二月2023187.1基本概念7.1.2極值問題

若點(diǎn)X*R，而對(duì)于所有XR都有f(X)f(X*)，則稱X*為f(X)在R上的全局極小點(diǎn)，f(X*)為全局極小值。若對(duì)于所有XR且XX*，都有f(X)>f(X*)，則稱X*為f(X)在R上的嚴(yán)格全局極小點(diǎn)，f(X*)為嚴(yán)格全局極小值。

如將上述不等式反向，即可得到相應(yīng)的極大點(diǎn)和極大值的定義。

下面僅就極小點(diǎn)及極小值加以說明，而且主要研究局部極小。02二月2023197.1基本概念7.1.2極值問題

2.極值點(diǎn)存在的條件

現(xiàn)說明極值點(diǎn)存在的必要條件和充分條件。

定理1(必要條件)：設(shè)R是n維歐氏空間En上的某一開集，f(X)在R上有一階連續(xù)偏導(dǎo)數(shù)，且在點(diǎn)X*R取得局部極值，則必有或f(X*)=0上式中02二月202320(7-10)(7-11)(7-12)7.1基本概念7.1.2極值問題為函數(shù)f(X)在X*處的梯度。由數(shù)學(xué)分析知道，f(X)的方向?yàn)閒(X)的等值面(等值線)的法線(在X處）方向，沿這個(gè)方向函數(shù)值增加最快。

滿足式(7-10)或式(7-11)的點(diǎn)稱為平穩(wěn)點(diǎn)或駐點(diǎn)，在區(qū)域內(nèi)部，極值點(diǎn)必為平穩(wěn)點(diǎn)，但平穩(wěn)點(diǎn)不一定是極值點(diǎn)。02二月2023217.1基本概念7.1.2極值問題

定理2(充分條件)設(shè)R是n維歐氏空間En上的某一開集，f(X)在R上有二階連續(xù)偏導(dǎo)數(shù)，X*R，若f(X*)=0，且對(duì)任何非零向量ZEn有ZTH(X*)Z>0則X*為f(X)的嚴(yán)格局部極小點(diǎn)

此處H(X*)為f(X)在點(diǎn)X*處的海賽(Hesse)矩陣：

02二月202322(7-13)(7-14)7.1基本概念7.1.2極值問題

需要指出，定理2中的充分條件(7-13)式并不是必要的?？梢耘e出這樣的例子：X*是f(X)的極小點(diǎn)，但卻不滿足條件(7-13)式。例如f(X)=x*，它的極小點(diǎn)是x*=0，但f’’(x*)=0，這不滿足(7-13)式。

二次型是X=(x1,x2,…,xn)T的二次齊次函數(shù)，它在研究非線性最優(yōu)化中具有重要作用。現(xiàn)考慮二次型ZTHZ。若對(duì)于任意Z0(即Z的元素不全為0)，二次型ZTHZ的值總是正的，即ZTHZ>0，則稱該二次型是正定的；若對(duì)于任意Z0總有ZTHZ0，則稱其為半正定；若對(duì)于任意Z0總有ZTHZ<0，則稱其為負(fù)定；若對(duì)于任意02二月2023237.1基本概念7.1.2極值問題Z0總有ZTHZ0，則稱其為半負(fù)定。如果對(duì)某些Z0總有ZTHZ>0，而對(duì)另一些Z0總有ZTHZ<0，即它既非正定，也非負(fù)定，則稱其為不定的。由線性代數(shù)知道，二次型ZTHZ為正定的充要條件，是它的矩陣H的左上角各階主子式都大于0；而它為負(fù)定的充要條件，是它的矩陣H的左上角各階主子式依次負(fù)正相同。

現(xiàn)以hij表示矩陣H的元素，上述條件為，當(dāng)二次型正定時(shí)：02二月2023247.1基本概念7.1.2極值問題當(dāng)二次型負(fù)定時(shí)：二次型ZTHZ為正定、負(fù)定或不定時(shí)，其對(duì)稱矩陣H分別稱為正的、負(fù)定的或不定的。定理2中的條件(7-13)式，就等于是說其海賽矩陣在X*處正定。02二月2023257.1基本概念7.1.2極值問題

凸集、凸函數(shù)以及凸函數(shù)的極值的性質(zhì)，是研究非線性規(guī)劃問題所不可缺少的內(nèi)容。凸集的概念在講線性規(guī)劃時(shí)已作過說明，因而這里簡(jiǎn)要說明凸函數(shù)的有關(guān)問題。1.什么是凸函數(shù)和凹函數(shù)

設(shè)f(X)為定義在n維歐氏空間En中某個(gè)凸集R上的函數(shù)，若對(duì)任何實(shí)數(shù)(0<<1)以及R中的任意兩點(diǎn)X(1)和X(2)，恒有f(X(1)+(1-)X(2))f(X(1))

+(1-)f(X(2))則稱f(X)為定義在R上的凸函數(shù)。02二月2023267.1基本概念7.1.3凸函數(shù)和凹函數(shù)(7-15)若對(duì)任意實(shí)數(shù)(0<<1)和X(1)X(2)R恒有f(X(1)+(1-)X(2))<f(X(1))

+(1-)f(X(2))則稱f(X)為定義在R上的嚴(yán)格凸函數(shù)。

將(6-15)式和(6-16)式中的不等號(hào)反向，即可得到凹函數(shù)和嚴(yán)格凹函數(shù)的定義。顯然，若函數(shù)f(X)是凸函數(shù)(嚴(yán)格凸函數(shù))，則-f(X)一定是凹函數(shù)(嚴(yán)格凹函數(shù))。

凸函數(shù)和凹函數(shù)的幾何意義十分明顯，若函數(shù)圖形上任兩點(diǎn)的聯(lián)線處處都不在這個(gè)函數(shù)圖形的下方，它當(dāng)然是下凸的(圖7-2(a))。凹函數(shù)則是下凹的(上凸的)(圖7-2(b)).線性函數(shù)即可看作凸函數(shù)，也可看作凹函數(shù)。02二月202327(7-16)7.1基本概念7.1.3凸函數(shù)和凹函數(shù)圖7-202二月202328f(x)Ox(1)x(2)x(1)+(1-)x(2)xf(x(1)+(1-)x(2))f(x(1))+(1-)f(x(2))f(x)Ox(1)x(2)x(1)+(1-)x(2)xf(x(1)+(1-)x(2))f(x(1))+(1-)f(x(2))圖7-2(a)凸函數(shù)

圖7-2(b)凹函數(shù)7.1基本概念7.1.3凸函數(shù)和凹函數(shù)圖7-202二月202329第一節(jié)基本概念1.3凸函數(shù)和凹函數(shù)f(x)Ox(1)x(2)xf(x(2))f(x(1))圖7-2(c)非凸、非凹函數(shù)

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

凸函數(shù)具有如下性質(zhì)：性質(zhì)1設(shè)f(X)為定義在R上的也是凸函數(shù)，則對(duì)任意實(shí)數(shù)0，函數(shù)也是f(X)定義在R上的凸函數(shù)。

性質(zhì)2設(shè)f1(X)和f2(X)為定義的凸集R上的兩個(gè)凸函數(shù)，則其和f(X)=f1(X)+f2(X)仍為定義在R上的凸函數(shù)。

因?yàn)閒1(X)和f2(X)都是定義在R上的凸函數(shù)，故對(duì)R上的任兩點(diǎn)X(1)和X(2)以及任意實(shí)數(shù)(0<<1)恒有f1(X(1)+(1-)X(2))f1(X(1))

+(1-)f1(X(2))f2(X(1)+(1-)X(2))f2(X(1))

+(1-)f2(X(2))02二月2023307.1基本概念7.1.3凸函數(shù)和凹函數(shù)將上述兩端分別相加得f(X(1)+(1-)X(2))f(X(1))

+(1-)f(X(2))故f(X)也是R上的凸函數(shù)。

由以上兩個(gè)性質(zhì)立刻推得：有限個(gè)凸函數(shù)的非負(fù)線性組合1f1(X)+2f2(X)+…+mfm(X)i0,i=1,2,…,m仍為凸函數(shù)。02二月2023317.1基本概念7.1.3凸函數(shù)和凹函數(shù)

性質(zhì)3設(shè)f(X)為定義在凸集R上的凸函數(shù)，則對(duì)任一實(shí)數(shù)，集合S={X|XR,f(X)}是凸集(S稱為水平集)。

證明：

任取X(1)S和X(2)S，則有f(X(1))，f(X(2))。

由于R為凸集，幫對(duì)任意實(shí)數(shù)(0<<1)，X(1)+(1-)X(2)R，又因?yàn)閒(X)為凸函數(shù)，故f(X(1)+(1-)X(2))f(X(1))

+(1-)f(X(2))這就表明點(diǎn)X(1)+(1-)X(2)S，于是，S為凸集。02二月202332(7-17)7.1基本概念7.1.3凸函數(shù)和凹函數(shù)

3.函數(shù)凸性的判定

現(xiàn)在來研究怎樣判斷一個(gè)函數(shù)是凸函數(shù)，當(dāng)然可以直接依據(jù)定義去判斷。對(duì)于可微凸函數(shù)，也可利用下述兩個(gè)判別定理。

定理3(一階條件)設(shè)R為n維歐氏空間En上的某一開集，f(X)在R上有一階連續(xù)偏導(dǎo)數(shù)，則f(X)為R上的凸函數(shù)的充要條件是，對(duì)任意兩個(gè)不同點(diǎn)X(1)R和X(2)R，恒有

f(X(2))f(X(1))

+f(X(1))(X(2)-X(1))02二月202333(7-18)7.1基本概念7.1.3凸函數(shù)和凹函數(shù)

證明必要性：

設(shè)f(X)為R上的凸函數(shù)，則對(duì)任何(0<<1)有f(X(2)+(1-)X(1))f(X(2))

+(1-)f(X(1))于是

令+0，上式左端的極限為f(X(1))T(X(2)-X(1))即

f(X(2))f(X(1))

+f(X(1))(X(2)-X(1))02二月2023347.1基本概念7.1.3凸函數(shù)和凹函數(shù)

充分性：任取X(1)R及X(2)R，現(xiàn)令X=X(1)+(1-)X(2)，0<<1分別以X(1)和X(2)為式(7-18)中的X(2)，以X為式(7-18)中的X(1)，則

f(X(1))f(X)

+f(X)(X(1)-X)f(X(2))f(X)

+f(X)(X(2)-X)用乘上面的第一式，用(1-)乘上面的第二式，然后兩端相加02二月2023357.1基本概念7.1.3凸函數(shù)和凹函數(shù)f(X(1))+(1-)f(X(2))f(X)+f(X)T[X(1)-X+(1-)(X(2)-X)]=f(X)=f(X(1)+(1-)X(2))從而可知f(X)為R上的凸函數(shù)。

若式(7-18)為平橋不等式，它就是嚴(yán)格凸函數(shù)的充要條件。

凸函數(shù)的定義式(7-15)，本質(zhì)上是說凸函數(shù)上兩點(diǎn)間的線性插值不低于這個(gè)函數(shù)的值；而定理3則是說，基于某點(diǎn)導(dǎo)數(shù)的線性近似不高于這個(gè)函數(shù)的值(圖7-3)。02二月2023367.1基本概念7.1.3凸函數(shù)和凹函數(shù)圖7-302二月202337f(X)OX(1)Xf(X(1))+f(X(1))(X-X(1))7.1基本概念7.1.3凸函數(shù)和凹函數(shù)

定理4(二階條件)設(shè)R為n維歐氏空間En上的某一開集，f(X)在R上有二階連續(xù)偏導(dǎo)數(shù)，則f(X)為R上的凸函數(shù)的充要條件是，f(X)的海賽矩陣H(X)在R上處處半正定。

證明先證明必要性。

設(shè)f(X)為R上的凸函數(shù)。任取XR和ZEn，現(xiàn)證ZTH(X)Z0

因R為開集，故存在，使當(dāng)時(shí)，有X+ZR。由定理3可得f(X+Z)f(X)+f(X)TZ02二月2023387.1基本概念7.1.3凸函數(shù)和凹函數(shù)再由泰勒公式f(X+Z)f(X)+f(X)TZ+0.52ZTH(X)Z+o(2)其中由以上兩式得0.52ZTH(X)Z+o(2)0從而0.5ZTH(X)Z+o(2)/20令0，則得ZTH(X)Z0

02二月2023397.1基本概念7.1.3凸函數(shù)和凹函數(shù)即H(X)為半正定矩陣。下面證明充分性。設(shè)對(duì)任意XR，H(X)為半正定矩陣，任取，由泰勒公式，有其中(0,1)。

因R為凸集，。再由假設(shè)知為半正定，從而由定理3，f(X)為R上的凸函數(shù)。02二月2023407.1基本概念7.1.3凸函數(shù)和凹函數(shù)若對(duì)一切XR，f(X)的海賽矩陣都是正定的，則f(X)是R上的嚴(yán)格凸函數(shù)。

對(duì)于凹函數(shù)可以得到和上述類似的結(jié)果。

例3試證明f(X)=-x12-x22為凹函數(shù)。

證明首先由定義證明f1(x1)=-x12為凹函數(shù)。

任意指定兩點(diǎn)a1和a2，看下述各式是否成立？-[a1+(1-)a2]2(-a12)+(1-)(-a22)或a12(-2)-2a1a2(-2)+a22(-2)0或(-2)(a1-a2)2002二月2023417.1基本概念7.1.3凸函數(shù)和凹函數(shù)由于0<<1，故-2>0。顯然，不管a1和a2取什么值，總有(-2)(a1-a2)20成立，從而證明f1(x1)=-x12為凹函數(shù)。用同樣的方法可以證明f2(x2)=-x22也是凹函數(shù)。根據(jù)性質(zhì)2，f(X)=-x12-x22為凹函數(shù)。

再用定理3證明。任意選取一點(diǎn)X(1)=(a1,b1)T，第二點(diǎn)X(2)=(a2,b2)T。如此f(X(1))=-a12-b12

f(X(2))=-a22-b22

f(X)=(-2x1,-2x2)Tf(X(1))=(-2a1,-2b1)T現(xiàn)看下述各式是否成立？02二月2023427.1基本概念7.1.3凸函數(shù)和凹函數(shù)或-a22-b22-a12-b12-2a1(a2-a1)-2b1(b2-b1)或-(a22-2a1a2+a12)-(b22-2b1b2+b12)0或-(a2-a1)2-(b2-b1)20不管a1、a2、b1和b2取什么值，上式均成立，從而得證。02二月2023437.1基本概念7.1.3凸函數(shù)和凹函數(shù)

下面用定理4證明。由于其海賽矩陣處處負(fù)定，故f(X)為(嚴(yán)格)凹函數(shù)。02二月2023447.1基本概念7.1.3凸函數(shù)和凹函數(shù)

前已指出，函數(shù)的局部極值并不一定等于它的最小值，前者只不過反映了函數(shù)的局部性質(zhì)。而最優(yōu)化的目的，往往是要求函數(shù)在整個(gè)域中的最小值(或最大值)和最小點(diǎn)(或最大點(diǎn))。為此，必須將所得的全部極小值進(jìn)行比較(有時(shí)尚需考慮邊界值)，以便從中選出最小者。然而，對(duì)于定義在凸集上的凸函數(shù)來說，則用不著進(jìn)行這種麻煩的工作，它的極小值就等于其最小值。

定理5若f(X)為定義在凸集R上的凸函數(shù)，則它的任一極小點(diǎn)就是它在R上的最小點(diǎn)(全局極小點(diǎn))，而且它的極小點(diǎn)形成一個(gè)凸集。02二月2023457.1基本概念7.1.3凸函數(shù)和凹函數(shù)

證明設(shè)X*是一個(gè)局部極小點(diǎn)，則對(duì)于充分小的鄰域N(X*)中的一切X，均有f(X)f(X*)

令Y是R中的任一點(diǎn)，對(duì)于充分小的，0<<1，就有((1-)X*+Y)N(X*)從而f((1-)X*+Y)f(X*)由于f(X)為凸函數(shù)，故(1-)f(X*)+f(Y)f((1-)X*+Y)02二月2023467.1基本概念7.1.3凸函數(shù)和凹函數(shù)

將上述兩個(gè)不等式相加，移項(xiàng)后除以，得到f(X)f(X*)這就是說，X*是全局極小點(diǎn)。

由性質(zhì)3，所有極小點(diǎn)的集合形與一個(gè)凸集。

定理6

設(shè)是定義在凸集R上的可微凸函數(shù)，若存在點(diǎn)X*R，使得對(duì)于所有的XR有f(X*)T(X-X*)0則X*是f(X)在R上的最小點(diǎn)(全局極小點(diǎn))。02二月2023477.1基本概念7.1.3凸函數(shù)和凹函數(shù)

證明：由定理3f(X)f(X*)+f(X*)T(X-X*)如此，對(duì)所有X*R有f(X)f(X*)

一種極為重要的情形是，當(dāng)點(diǎn)X*是R的內(nèi)點(diǎn)時(shí)，這時(shí)式(7-19)對(duì)任意X-X*都成立，這就意味著可將式(7-19)改為f(X*)=0

以上兩個(gè)定理說明，定義在凸集上的凸函數(shù)的平穩(wěn)點(diǎn)，就是其全局極小點(diǎn)。全局極小點(diǎn)并不一定是唯一的，02二月2023487.1基本概念7.1.3凸函數(shù)和凹函數(shù)但若為平橋凸函數(shù)，則其全局極小點(diǎn)就是唯物主義一的了。02二月2023497.1基本概念7.1.3凸函數(shù)和凹函數(shù)現(xiàn)在再回到非線性規(guī)劃式(7-1)～(7-3)。和線性規(guī)劃類似，把滿足約束條件式(7-2)和式(7-3)的點(diǎn)稱做可行點(diǎn)(可行解)，所有可行點(diǎn)的集合稱做可行域。若某個(gè)可行解使目標(biāo)函數(shù)式(7-1)為最小，就稱它為最優(yōu)解。

考慮非線性規(guī)劃02二月2023507.1基本概念7.1.4凸規(guī)則假定其中f(X)為凸函數(shù)，gj(X)(j=1,2,…,l)為凹函數(shù)(或者說-gj(X)為凸函數(shù))，就樣的非線性規(guī)劃稱為凸規(guī)劃。可以證明，上述凸規(guī)劃的可行域?yàn)橥辜?，其局部最?yōu)解即為全局最優(yōu)解，而且其最優(yōu)解的集合形成一個(gè)凸集。當(dāng)凸規(guī)劃的目標(biāo)函數(shù)f(X)為嚴(yán)格凸函數(shù)時(shí)，其最優(yōu)解必定唯一(假定最優(yōu)解存在)。由此可見，凸規(guī)劃是一類比較簡(jiǎn)單而又具有重要理論意義的非線性規(guī)劃。

由于線性函數(shù)即可視為凸函數(shù)，又可視為凹函數(shù)，故線性規(guī)劃也屬于凸規(guī)劃。02二月2023517.1基本概念7.1.4凸規(guī)則

例4試分析非線性規(guī)劃minf(X)=x12+x22-4x1+4

解：f(X)和g2(X)的海賽矩陣的行列式分別是02二月2023527.1基本概念7.1.4凸規(guī)則

知f(X)為嚴(yán)格凸函數(shù)，g2(X)為凹函數(shù)。由于其他約束條件均為線性函數(shù)，所以這是一個(gè)凸規(guī)劃問題(見圖7-4)。C點(diǎn)為其最優(yōu)點(diǎn)：X*=(0.58,1.34)T，目標(biāo)函數(shù)的最優(yōu)值為f(X*)=3.8。02二月2023537.1基本概念7.1.4凸規(guī)則圖7-402二月2023547.1基本概念7.1.4凸規(guī)則1234-112.2546.25RCg1(X)=0g2(X)=0x2x10目標(biāo)函數(shù)等值線

為了求某可微函數(shù)(假定無約束)的最優(yōu)解，根據(jù)前面的敘述，可如下進(jìn)行：令該函數(shù)的梯度等于0，由此求得平穩(wěn)點(diǎn)；然后用充分條件進(jìn)行判別，求出所要的解。對(duì)某些較簡(jiǎn)單的函數(shù)，這樣做有時(shí)是可行的；但對(duì)一般n元函數(shù)f(X)來說，由條件f(X)=0得到的常是一個(gè)非線性方程組，解它相當(dāng)困難。對(duì)于不可微函數(shù)，當(dāng)然談不上使用這樣的方法。為此，常直接使用迭代法。02二月2023557.1基本概念7.1.5下降迭代算法

迭代法的基本思想是：為了求函數(shù)f(X)的最優(yōu)解，首先給定一個(gè)初始估計(jì)X(0)，然后按某種規(guī)則(即算法)找出比X(0)更好的解X(1)(對(duì)極小化問題，f(X(1))<f(X(0))；對(duì)極大化問題f(X(1)>f(X(0)))，再按此種規(guī)則找出比X(1)更好的解X(2)……。如此即可得到一個(gè)解的序列{X(k)}。若這個(gè)解序列有極限X*，即則稱它收斂于X*。02二月2023567.1基本概念7.1.5下降迭代算法

若這算法是有效的，那么它所產(chǎn)生的解的序列將收斂于該問題的最優(yōu)解。不過，由于計(jì)算機(jī)只能進(jìn)行有限次迭代，一般說很難得到準(zhǔn)確解，而保能得到近似解。當(dāng)滿足所要求的精度時(shí)，即可停止迭代。

若由某算法所產(chǎn)生的解的序列{X(k)}使目標(biāo)函數(shù)f(X(k))逐步減少，就稱這算法為下降算法。“下降”的要求比較容易實(shí)現(xiàn)，它包含了很多種具體算法。顯然，求解極小化問題應(yīng)采用下降算法。

現(xiàn)假定已迭代到點(diǎn)X(k)，見圖7-5。02二月2023577.1基本概念7.1.5下降迭代算法圖7-502二月2023587.1基本概念7.1.5下降迭代算法X*101520P(k)X(k)kP(k)X(k+1)若從X(k)出發(fā)沿任何方向移動(dòng)都不能使目標(biāo)函數(shù)值下降，則X(k)是一局部極小點(diǎn)，迭代停止。若從X(k)出發(fā)至少存在一個(gè)方向可使目標(biāo)函數(shù)值有所下降，則可選定能使目標(biāo)函數(shù)值下降的某方向P(k)，沿這個(gè)方向邁進(jìn)適當(dāng)?shù)囊徊剑玫较乱粋€(gè)迭代點(diǎn)X(k+1)，并使f(X(k))<f(X(k+1))。這相當(dāng)于在射線

X=X(k)+P(k)

上選定新點(diǎn)X(k+1)=X(k)+kP(k)

其中，

P(k)稱為搜索方向；k稱為步長(zhǎng)或步長(zhǎng)因子。下降迭代算法的可總結(jié)如下：(1)選定某一初始點(diǎn)X(0)，并令k:=0；(2)確定搜索方向P(k)；(3)從X(k)出發(fā)，沿方向P(k)求步長(zhǎng)k，以產(chǎn)生下一個(gè)迭代點(diǎn)X(k+1)；02二月2023597.1基本概念7.1.5下降迭代算法

(4)檢查得到的新點(diǎn)X(k+1)是否為極小點(diǎn)或近似極小點(diǎn)。若是，則停止迭代。否則，令k:=k+1，轉(zhuǎn)回(2)繼續(xù)進(jìn)行迭代。

在以上步驟中，選取搜索方向P(k)是最關(guān)鍵的一步，有關(guān)各種算法的區(qū)分，主要在于確定搜索方向的方法不同。

確定步長(zhǎng)k可選用不同的方法。最簡(jiǎn)單的一種是令它等于某一常數(shù)(例如k=1)，這樣做計(jì)算簡(jiǎn)便，但不能保證使目標(biāo)函數(shù)值下降。第二種稱為可接受點(diǎn)算法，只要能目標(biāo)函數(shù)值下降，可任意選取步長(zhǎng)k。第三種方法02二月2023607.1基本概念7.1.5下降迭代算法是基于沿搜索方向使目標(biāo)函數(shù)值下降最多，即沿射線X=X(k)+P(k)求目標(biāo)函數(shù)f(X)的極小(注意，這里是指無約束問題)k：minf(X(k)+P(k))由于這項(xiàng)工作是求以為變量的一元函數(shù)f(X(k)+P(k))的極小點(diǎn)k，故常稱這一過程為(最優(yōu))一維搜索或線性搜索，這樣確定的步長(zhǎng)為最佳步長(zhǎng)。

一維搜索有個(gè)十分重要的性質(zhì)：在搜索方向上所得最優(yōu)點(diǎn)處目標(biāo)函數(shù)的梯度和該搜索方向正交。02二月2023617.1基本概念7.1.5下降迭代算法

定理7

設(shè)目標(biāo)函數(shù)f(X)具有一階連續(xù)偏導(dǎo)數(shù)，X(k+1)按下述規(guī)則產(chǎn)生k：minf(X(k)+P(k))X(k+1)=X(k)+kP(k)則有f(X(k+1))TP(k)=0

證明構(gòu)造函數(shù)()=f(X(k)+P(k))，則得即k為()的極小點(diǎn)。此外’()=f(X(k)+P(k))TP(k)。02二月2023627.1基本概念7.1.5下降迭代算法(7-21)

由’()|

=

k=0，可得f(X(k)+kP(k))TP(k)=f(X(k+1))TP(k)定理得證。

式(7-21)的幾何意義見下圖。02二月2023637.1基本概念7.1.5下降迭代算法X(k)X(k+1)f(X)=f(X(k+1))P(k)f(X(k+1))3020

對(duì)一個(gè)好的算法，不僅要求它產(chǎn)生的點(diǎn)列能收斂到問題的最優(yōu)解，還要求具有較快的收斂速度。設(shè)序列{X(k)}收斂于X*，若存在與迭代次數(shù)k無關(guān)的數(shù)0<<和1，使k從某個(gè)k0>0開始都有||X(k+1)-X(k)||||X(k)–X*||成立，就稱{X(k)}收斂的階為，或{X(k)}階收斂。

當(dāng)=2時(shí)，稱為二階收斂，也可說{X(k)}具有二階斂速。

當(dāng)1<<2時(shí)，稱超線性收斂。

當(dāng)=1，且0<<1時(shí)，稱線性收斂或一階收斂。02二月2023647.1基本概念7.1.5下降迭代算法(7-22)

一般來講，線性收斂的斂速是比較慳慢的，二階收斂是很快的，超級(jí)性收斂介于以上兩者之間。若一個(gè)算法具有超線性或更高的收斂速度，就認(rèn)為它是一個(gè)很好的算法。

因?yàn)檎嬲淖顑?yōu)解事先并不知道，為決定什么暑假停止計(jì)算，只能根據(jù)相繼兩次迭代的結(jié)果。常用的終止計(jì)算準(zhǔn)則有以下幾種。(1)根據(jù)相繼兩次迭代的絕對(duì)誤差||X(k+1)-X(k)||<1|f(X(k+1))-f(X(k))|<202二月2023657.1基本概念7.1.5下降迭代算法(7-23)(7-24)

(2)根據(jù)相繼兩次迭代的相對(duì)誤差這時(shí)要求分母不等于和不接近于0.(3)根據(jù)目標(biāo)函數(shù)梯度的模足夠小||f(X(k))||<5其中，1,2,3,4,5為事先給定的足夠小的正數(shù)。02二月2023667.1基本概念7.1.5下降迭代算法(7-27)(7-26)(7-25)

前已述及，當(dāng)用上述迭代法求函數(shù)的極小點(diǎn)時(shí)，常常要用到一維搜索，即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)。一維搜索的方法很多，常用的有：(1)試探法(“成功—失敗”法，斐波那契法，0.618法等)；(2)插值法(拋物線插值法，三次插值法等)；(3)微積分中的求根法(切線法，二分法等)。

限于篇幅，以下僅介紹斐波那契法和0.618法。02二月2023677.2一維搜索

設(shè)y=f(t)是敬意[a,b]上的下單峰函數(shù)(圖7-7)，在此敬意內(nèi)它有唯一極小點(diǎn)t*。若在此敬意內(nèi)任取兩點(diǎn)a1和b1，a1<b1，并計(jì)算函數(shù)值f(a1)和f(b1)，可能出現(xiàn)以下兩種情形：02二月2023687.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)f(t)f(t)f(t)f(t)ttOat*a1b1bOat*a1b1b(a)(b)圖7-7

(1)f(a1)<f(b1)(圖7-7(a))，這時(shí)極小點(diǎn)t*必在區(qū)間[a,b1]內(nèi)。(2)f(a1)f(b1)(圖7-7(b))，這時(shí)極小點(diǎn)t*必在區(qū)間[a1,b]內(nèi)。02二月2023697.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)02二月2023f(t)f(t)f(t)f(t)ttOat*a1b1bOat*a1b1b(a)(b)圖7-7

這說明，只要在區(qū)間[a,b]內(nèi)取兩個(gè)不同點(diǎn)，并算出它們的函數(shù)值加以比較，就可以把搜索區(qū)間[a,b]縮小成[a,b1]或[a1,b](縮小后的區(qū)間仍需包含極小點(diǎn))?，F(xiàn)在如果要繼續(xù)縮小搜索區(qū)間[a,b1](或[a1,b])，就只需在上述區(qū)間內(nèi)再取一點(diǎn)算出其函數(shù)值，并與f(a1)或f(b1)加以比較即可。只要縮小后的區(qū)間包含極小點(diǎn)t*，則區(qū)間縮小得越小，就越接近于函數(shù)的極小點(diǎn)，但計(jì)算函數(shù)值的次數(shù)也就越多。這就說明區(qū)間的縮短率和函數(shù)值的計(jì)算次數(shù)有關(guān)?，F(xiàn)在要問，計(jì)算函數(shù)值n次，能氫包含有極小點(diǎn)的區(qū)間縮小到什么程度呢?02二月2023707.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)

或者用Fn表示計(jì)算n個(gè)函數(shù)值能縮短為單位區(qū)間的最大原區(qū)間長(zhǎng)度，顯然F0=F1=1其原因是，只有當(dāng)原區(qū)間長(zhǎng)度本來就是一個(gè)單位長(zhǎng)度時(shí)才不必計(jì)算函數(shù)值；此外，只計(jì)算一次函數(shù)值無法將區(qū)間縮短，故只有區(qū)間長(zhǎng)度本來就是單位區(qū)間時(shí)才行。

現(xiàn)考慮計(jì)算函數(shù)值兩次的情形，今后我們把計(jì)算函數(shù)值的點(diǎn)稱做試算點(diǎn)或試點(diǎn)。02二月2023717.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)(7-28)

在區(qū)間[a,b]內(nèi)取兩個(gè)不同點(diǎn)a1和b1(圖7-8(a))，計(jì)算其函數(shù)值以縮短區(qū)間，縮短后的區(qū)間為[a,b1]或[a1,b]。顯然，這兩個(gè)區(qū)間長(zhǎng)度之和必大于[a,b]的長(zhǎng)度，也就是說，計(jì)算兩次函數(shù)值一般無法把長(zhǎng)度大于兩個(gè)單位的區(qū)間縮成單位區(qū)間。但是，對(duì)于長(zhǎng)度為兩個(gè)單位的區(qū)間，可以如圖7-8(b)那樣選取試點(diǎn)a1和b1，圖中為任意小的正數(shù)，縮短后的區(qū)間長(zhǎng)度為1+。由于可任意選取，故縮短后的區(qū)間長(zhǎng)度接近于一個(gè)單位長(zhǎng)度。由此可得F2=2。02二月2023727.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)

根據(jù)同樣的分析(見圖7-9)可得02二月2023737.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)a1b1aaa1b1bb1201-1+(a)(b)圖7-802二月2023747.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)2/3圖7-91/3①②③n=33/52/5①②③n=41/5④5/83/8①②③n=52/8④1/8⑤F3=3,F4=5,F3=8,┅序列{Fn}可寫成一個(gè)遞推公式Fn=Fn-1

+Fn-2

n2利用式(7-29)，可依次算出各Fn的值，見表7-1。這些Fn就是通常所說的斐波那切契數(shù)。表7-102二月2023757.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)n0123456789101112Fn

1123581321345589144233(7-29)

由以上討論可知，計(jì)算n次函數(shù)值所能獲得的最大縮短率(縮短后的區(qū)間長(zhǎng)度與原區(qū)間長(zhǎng)度之比)為1/Fn。例如F10=10946，所以計(jì)算20個(gè)函數(shù)值即可把原長(zhǎng)度為L(zhǎng)的區(qū)間縮短為L(zhǎng)/10496=0.00009L的區(qū)間?，F(xiàn)在，要想計(jì)算n個(gè)函數(shù)值，而把區(qū)間[a0,b0]的長(zhǎng)度縮短為原來長(zhǎng)度的倍，即縮短后的區(qū)間長(zhǎng)度為bn-1-an-1(b0-a0)則只要n足夠大，能使下式成立即可Fn1/02二月2023767.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)(7-30)其中，為一個(gè)正小數(shù)，稱為區(qū)間縮短的相對(duì)精度。有時(shí)給出區(qū)間縮短的絕對(duì)精度，即要求bn-1-an-1顯然，上述相對(duì)精度和絕對(duì)精度之間有如下關(guān)系=(b0-a0)

用這個(gè)方法縮短區(qū)間的步驟如下：(1)確定試點(diǎn)的個(gè)數(shù)n。根據(jù)相對(duì)精度，即可用式(7-30)算出Fn，然后由表7-1確定最小的n。(2)選取前兩個(gè)試點(diǎn)的位置。02二月2023777.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)(7-31)(7-32)

由式(7-29)可知第一次縮短時(shí)的兩個(gè)試點(diǎn)位置分別是(見圖7-10)：02二月2023787.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)a0b0t1t1'Fn-2Fn-1Fn-2Fn-1Fn-3Fn圖7-10

它們?cè)趨^(qū)間內(nèi)的位置是對(duì)稱的。(3)計(jì)算函數(shù)值f(t1)和f(t1’)，并比較它們的大小。

若f(t1)<f(t1’)，則取a1=a0

b1=t1’

t2’=t1并令02二月2023797.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)(7-33)

否則，取a1=t1

b1=b0

t2=t1’并令(4)計(jì)算f(t2)和f(t2’)(其中的一個(gè)已經(jīng)算出)，如第3步那樣一步步迭代。計(jì)算試點(diǎn)的一般公式為02二月2023807.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)其中，k=1,2,…,n-1。

(5)當(dāng)進(jìn)行至k=n-1時(shí)tn-1=t’n-1=0.5(an-2+bn-2)這就無法借比較函數(shù)值f(tn-1)和f(t’n-1)的大小來確定最終區(qū)間，為此，取02二月2023817.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)(7-34)其中為任意小的數(shù)。在tn-1和t’n-1這兩點(diǎn)中，以函數(shù)值較小者為近似極小點(diǎn)，相應(yīng)的函數(shù)值為近似極小值，并得最終區(qū)間[an-2,t’n-1]或[tn-1,bn-2]。

由上述分析可知，斐波那契法使用對(duì)稱搜索的方法，逐步縮短所考察的區(qū)間，它能以晝少的函數(shù)求值次數(shù)，達(dá)到預(yù)定的某一縮短率。02二月2023827.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)(7-35)

例5試用斐波那契法求函數(shù)f(t)=t2-t+2的近似極小點(diǎn)和極小值，要求縮短后的區(qū)間長(zhǎng)度不大于區(qū)間[-1,3]的0.08倍。

解：容易驗(yàn)證，在此區(qū)間上函數(shù)f(t)=t2-t+2為嚴(yán)格凸函數(shù)。為了進(jìn)行比較，我們給出其精確解是：t*=0.5，f(t*)=1.75。

已知=0.08，F(xiàn)n1/=1/0.08=12.5

查表7-1，n=6，a0=-1,b0=3t1=b0+F5(a0-b0)/F6=3+8(-1-3)/13=0.538t1’=a0+F5(b0-a0)/F6=-1+8(3-(-1))/13=1.46202二月2023837.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)f(t1)=0.5382-0.538+2=1.751f(t1’)=1.4622-1.462+2=2.675由于f(t1)<f(t1’)，故取a1=-1,b1=1.462,t2’=0.538t2=b1+F4(a1-b1)/F5=1.462+5(-1-1.462)/8=-0.077f(t2)=(-0.077)2-(-0.077)+2=2.083由于f(t2)>f(t2’)=1.751，故取a2=-0.077,b2=1.462,t3=0.538t3’=a2+F3(b2-a2)/F4=-0.077+3(1.462+0.077)/5=0.846f(t3’)=0.8462-0.846+2=1.870由于f(t3’)>f(t3)=1.751，故取a3=-0.077,b3=0.846,t4’=0.53802二月2023847.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)t4=b3+F2(a3-b3)/F3=0.846+2(-0.077-0.846)/3=0.231f(t4)=0.2312-0.231+2=1.822由于f(t4)>f(t4’)=1.751，故取a4=0.231,b4=0.846,t5=0.538?，F(xiàn)令=0.01，則t5’=a4+(0.5+)(b4-a4)=0.231+(0.5+0.01)(0.846-0.231)=0.545f(t5’)=0.5452-0.545+2=1.752>f(t5)=1.751故取a5=0.231,b5=0.545。由于f(t5)=1.751<f(t5’)=1.752，所以以t5為近似極小點(diǎn)，近似極小值為1.751。02二月2023857.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)

縮短后的區(qū)間長(zhǎng)度為0.545-0.231=0.314，0.314/4=0.0785<0.08，其整個(gè)計(jì)算過程示于圖7-11中。02二月2023867.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)圖7-1102二月2023877.2一維搜索7.2.1斐波那契(Fibonacci)法(分?jǐn)?shù)法)a0b0a4b4t5t5'a3b3t4t4'a2b2t3t3'a1b1t2t2'a0b0-10123t1't1①②③⑤⑥④

由上節(jié)的論述可知，當(dāng)用斐波那契法以n個(gè)試點(diǎn)來縮短某一縮短某一區(qū)間時(shí)，區(qū)間長(zhǎng)度的第一次縮短率為Fn-1/Fn，其后各次分別為Fn-2/Fn-1,Fn-3/Fn-2,…,F1/F2現(xiàn)將以上數(shù)列分為奇數(shù)項(xiàng)F2k-1/F2k和偶數(shù)項(xiàng)F2k/F2k+1，可以證明，這兩個(gè)數(shù)列收斂于同一個(gè)極限。

設(shè)當(dāng)k時(shí)F2k-1/F2k

F2k/F2k+1由于02二月2023887.2一維搜索7.2.20.618法(黃金分割法)

故當(dāng)k時(shí)同理可證將式(7-35)代入式(7-37)得即02二月2023897.2一維搜索7.2.20.618法(黃金分割法)(7-36)(7-37)

從而可得

若把式(7-37)代入式(7-36)，則得將式(7-35)代入式(7-37)得2++1=0故有02二月2023907.2一維搜索7.2.20.618法(黃金分割法)(7-38)

現(xiàn)用不變的區(qū)間縮短率0.618，代替斐波那契法每次不同的縮短率，就得到了黃金分割法(0.618法)。這個(gè)方法可以看成是斐波那契法的近似，實(shí)現(xiàn)起來比較容易，效果也相當(dāng)好，因而易于為人們所接受。

當(dāng)用0.618法時(shí)，計(jì)算n個(gè)試點(diǎn)的函數(shù)值可以把原區(qū)間[a0,b0]連續(xù)縮短n-1次，因?yàn)槊看蔚目s短率均為，故最后的區(qū)間長(zhǎng)度為(a0-b0)

n-1這就是說，當(dāng)已知縮短的相對(duì)精度為時(shí)，可用下式計(jì)算試點(diǎn)個(gè)數(shù)n02二月2023917.2一維搜索7.2.20.618法(黃金分割法)

n-1

當(dāng)然，也可以不預(yù)先計(jì)算試點(diǎn)的數(shù)目n，而在計(jì)算過程中逐次加以判斷，看是否已滿足了提出的精度要求。0.618法是一種等速對(duì)稱進(jìn)行的試探的方法，每次的試點(diǎn)均取在區(qū)間長(zhǎng)度的0.618倍和0.382倍處。02二月2023927.2一維搜索7.2.20.618法(黃金分割法)(7-39)對(duì)于無約束極值問題的解法，這種問題可表述為minf(X),XEn前面曾指出，在求解上述問題時(shí)常使用迭代法，迭代法可大體分為兩大類。一類要用到函數(shù)的一階層數(shù)和(或)二階層數(shù)，由于用到了函數(shù)的解析性質(zhì)，故稱為解法法；另一類在迭代過程中僅用到函數(shù)值，而不要求函數(shù)的解析性質(zhì)，這類方法稱為直接法。一般來說，直接法的收斂速度較慢，只是在變量較少時(shí)才適用。但是直接法的迭代簡(jiǎn)單，特別是當(dāng)目標(biāo)函數(shù)的解析表達(dá)式十分復(fù)雜，甚至寫不出具體表達(dá)式時(shí)，它們的導(dǎo)數(shù)很難求得，或者根本不存在。這時(shí)解析法就無能為力了。02二月2023937.3無約束極值問題的解法(7-40)在求解無約束極值問題的解析法中，梯度法是最為古老但又十分基本的一種數(shù)值方法。它的迭代過程簡(jiǎn)單，使用方便宜，而且又是理解某些其他最優(yōu)化方法的基礎(chǔ)，所以我們先來說明這一方法。1.梯度法的基本原理

假定無約束極值問題式(7-40)中的目標(biāo)函數(shù)f(X)有一階連續(xù)偏導(dǎo)數(shù)，具有極小點(diǎn)X*。以X(k)表示極小點(diǎn)的第k次近似，為了求其第k+1次近似點(diǎn)X(k+1)，我們?cè)赬(k)點(diǎn)沿方向P(k)作射線X=X(k)+P(k)(0)02二月2023947.3無約束極值問題的解法7.3.1梯度法(最速下降法)現(xiàn)將f(X)在X(k)點(diǎn)處展成泰勒級(jí)數(shù)f(X)=f(X(k)+P(k))=f(X(k))+f(X(k))TP(k)+o()其中對(duì)于充分小的，只要f(X(k))TP(k)<0即可保證f(X(k)+P(k))<f(X(k))。這時(shí)若取X(k+1)=X(k)+P(k)就能使目標(biāo)函數(shù)值得到改善。02二月2023957.3無約束極值問題的解法7.3.1梯度法(最速下降法)(7-41)現(xiàn)考查不同方向P(k)。假定P(k)的模一定(且不為0)，并設(shè)f(X(k))0(否則，X(k)是平穩(wěn)點(diǎn))，使式(7-41)成立的P(k)有無限多個(gè)。為了使目標(biāo)函數(shù)值能得到盡量大的改善，必須尋求使f(X(k))TP(k)取最小值的P(k)。由線性代數(shù)學(xué)知道f(X(k))TP(k)=||f(X(k))||||P(k)||cos式中為向量f(X(k))與P(k)的夾角。當(dāng)P(k)與f(X(k))反向時(shí)，=1800，cos=-1。這時(shí)式(7-41)成立，而且其左端取最小值。我們稱方向P(k)=-f(X(k))02二月2023967.3無約束極值問題的解法7.3.1梯度法(最速下降法)(7-42)為負(fù)梯度方向，它是使函數(shù)值下降最快的方向(在X(k)的某一小范圍內(nèi))。

為了得到下一個(gè)近似極小點(diǎn)，在選定了搜索方向之后，還要確定步長(zhǎng)。當(dāng)采用可接受點(diǎn)算法時(shí)，就是取某一進(jìn)行試算，看是否滿足不等式f(X(k)-P(k))<f(X(k))若上述不等式成立，就可以迭代下去。否則，縮小使?jié)M足不等式式(7-43)。由于采用負(fù)梯度方向，滿足式(7-43)的總是存在的。02二月2023977.3無約束極值問題的解法7.3.1梯度法(最速下降法)(7-43)另一種方法是通過在負(fù)梯度方向的一維搜索，來確定使f(X)最小的k，這種梯度法就是所謂最速下降法。2.計(jì)算步驟

現(xiàn)將用梯度法解無約束極值問題的步驟簡(jiǎn)要總結(jié)如下：(1)給定初始近似點(diǎn)X(0)及精度>0，若||f(X(0))||2，則X(0)即為近似極小點(diǎn)。(2)若||f(X(0))||2>，求步長(zhǎng)0

，并計(jì)算X(1)=X(0)-0f(X(0))02二月2023987.3無約束極值問題的解法7.3.1梯度法(最速下降法)求步長(zhǎng)可用一維搜索法、微分法或計(jì)劃處法。若求最佳步長(zhǎng)，則應(yīng)使用前兩種方法。(3)一般地，設(shè)已迭代到點(diǎn)X(k)，若||f(X(0))||2，則X(k)即為所求的近似解；若||f(X(0))||2>，則求步長(zhǎng)k，并確定下一個(gè)近似點(diǎn)X(k+1)=X(k)-kf(X(k))如此繼續(xù)，直至達(dá)到要求的精度為止。

若f(X)具有二階連續(xù)偏導(dǎo)數(shù)，在X(k)作f(X(k)-f(X(k)))的泰勒展開02二月2023997.3無約束極值問題的解法7.3.1梯度法(最速下降法)(7-44)f(X(k)-f(X(k)))f(X(k))-f(X(k))Tf(X(k))+0.5f(X(k))TH(X(k))f(X(k))則對(duì)求導(dǎo)并令其層數(shù)等于零，則得近似最佳步長(zhǎng)

可見近似最佳步長(zhǎng)不僅與梯度有關(guān)，而且與海賽矩陣H也有關(guān)系，計(jì)算起來比較麻煩。

確定步長(zhǎng)k也可不用式(7-45)，而采用任一種一維搜索法(例如0.618法等)。

若將搜索方向P(k)的模規(guī)格化為1，在這種情況下02二月20231007.3無約束極值問題的解法7.3.1梯度法(最速下降法)(7-45)同時(shí)，式(7-45)變?yōu)?/p>

例6式用梯度法求f(X)=(x1-1