最優(yōu)化理論與方法-電子科技大學(xué)

第三章最優(yōu)化理論與方法最優(yōu)化計算方法主要是研究在一定限制條件下，選取某種方案以達(dá)到最優(yōu)化目標(biāo)的一門學(xué)科。達(dá)到最優(yōu)目標(biāo)的方案，稱為最優(yōu)方案，搜索最優(yōu)方案的方法，稱為最優(yōu)化方法。這種方法的數(shù)學(xué)理論，稱為最優(yōu)化理論。實際上最優(yōu)化方法已廣泛應(yīng)用于空間技術(shù)、軍事科學(xué)、電子工程、通訊工程、自動控制、系統(tǒng)識別、資源分配、計算數(shù)學(xué)、經(jīng)濟(jì)管理等等領(lǐng)域。最優(yōu)化方法包括的內(nèi)容很廣泛，如線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、多目標(biāo)規(guī)劃、組合優(yōu)化等等。最優(yōu)化理論與方法3.1線性規(guī)劃問題的數(shù)學(xué)模型3.2二維線性規(guī)劃的圖解法3.3二維線性規(guī)劃的基本概念及解的性質(zhì)

3.4單純形法3.7一維搜索法3.8無約束最優(yōu)化方法§3.1線性規(guī)劃問題的數(shù)學(xué)模型一.最優(yōu)化問題舉例

例1（運輸問題）設(shè)有位于不同城市的m個電視機(jī)廠A1，A2，…，Am，其產(chǎn)量分別為a1，a2，…，am（臺），其產(chǎn)品供應(yīng)n個城市B1，B2，…，Bn。每個城市的需要量分別為b1，b2，…，bn（臺）。假定產(chǎn)需平衡，即?=miia1?=niib1=已知從Ai到Bj的運費單價為cij（元/臺）（i=1,2,…,m；j=1,2,…,n）。問由每個廠到每個城市的運輸量各為多少時，既能保證需要量，又能使總運費最少？

解設(shè)由Ai到Bj的運輸量為xij（臺）（i=1,2,…,m；j=1,2,…,n），則要求總運費

達(dá)到最小，其中要滿足的約束條件為：??==minjijijxc11綜上，可把所得到的線性規(guī)劃問題記為:???????????íì==3====????====,,,2,1;,,2,1,0,,,2,1,,,2,1,..,min1,111mjnixnjbxmiaxtsxcijmijijnjiijminjijij…………?=njijx1?=miijx1=ai，i=1,2,…,m；=bj，j=1,2,…,n例2(系統(tǒng)可靠性問題)在設(shè)計某些大型的系統(tǒng)工程時,常常要考慮它們的可靠性。設(shè)一個系統(tǒng)是由n個部件串聯(lián)而成。為提高系統(tǒng)的可靠性，每個部件都裝有備用件，一旦原部件出現(xiàn)故障，備用件就自動進(jìn)入系統(tǒng)。顯然,備用件越多系統(tǒng)可靠性越大，但費用也越高，重量也越大，這在實際上是不行的。假定當(dāng)部件k配置uk個備用件時，這個部件正常工作的概率為pk

(uk)，而每個備用件k的費用為ck,重量為ak。試在總費用不超過C，總重量不超過A的條件下決定各部件的備用件的數(shù)量，使得系統(tǒng)正常工作的概率最大。解

因為系統(tǒng)正常工作的概率是各部件正常工作的概率的乘積，所以問題歸納為uk

是正整數(shù)。?=nkkkup1)(max?=￡nkkkCucts1.?=￡nkkkAua1例3（非線性方程組的求解）解非線性方程組是相當(dāng)困難的一類問題，由于最優(yōu)化方法的發(fā)展，對解非線性方程組提供了一種有力的手段。解非線性方程組?????íì===0),,,(0),,,(0),,,(21212211nnnnxxxfxxxfxxxf…………………在方程組有解的情況下等價于下列函數(shù)的最小值點：),,,(),,,(min211221nniinxxxfxxxF?==……例4

合理下料問題某車間有長度為180cm的鋼管(數(shù)量充分多),今要將其截為三種不同長度,長度為70cm的管料100根,而52cm、35cm的管料分別不得少于150根和120根,問應(yīng)采取怎樣的截法,才能完成任務(wù),同時使剩下的余料最少？解所有可能的截法共有8種,如下表所示：截法一二三四五六七八需要量長度702111000010052021032101503510130235120余料56235246235選其中一種余料最少的截法,但不能完成任務(wù).所以我們必須同時采取若干種截法,配合起來,在完成任務(wù)的條件下,使總的余料最少.設(shè)采用第i種截法的鋼管數(shù)目為xi

(i=1,…,8),那么截出70cm的管料數(shù)目應(yīng)為(2x1

+x2

+x3+x4

)根,其總數(shù)應(yīng)為100,即2x1

+x2

+x3+x4

=100同理可得2x2

+x3

+x4+3x5

+2x6

+x7

≥150x1

+x3

+3x4+2x6

+3x7

+5x8

≥120由題意可知

xi

≥0

(i=1,…,8)

余料的總長度為于是上述下料問題的數(shù)學(xué)模型為i

說明：由于求變量x1，x2，…，xn使某函數(shù)f(x1，x2，…，xn)（也記為f(x))達(dá)到極大，等價于使-f(x)達(dá)到極小。所以上述例子均可歸結(jié)為函數(shù)的帶約束或不帶約束的極小化問題，簡稱最優(yōu)化問題，其中稱f(x)為目標(biāo)函數(shù)。二．最優(yōu)化問題的數(shù)學(xué)模型與分類1.根據(jù)問題不同特點分類

(1)無約束極小化問題求x=(x1，x2，…，xn)T

使函數(shù)f(x)

達(dá)到最小,記為)(minxfnRx?或min)(xf（2）約束極小化問題記為=3migtsfi,,2,1,0)(..)(minxx…h(huán)j(x)=0,j=1,2,…,n說明：若某些問題的約束條件出現(xiàn)h(x)≤0，則可令g(x)=-h(x)而將此約束轉(zhuǎn)化為g(x)≥0,所以模型中的不等號均假定為≥.注:∵h(yuǎn)(x)=0

h(x)≥0-h(x)≥0其中S={x|gi(x)≥0,i=1,…,m}稱為可行集或可行域，S中的點稱為可行點。所以上述(2)約束極小化問題也可表為：或)(minxfSx??íì=3migtsfi,…,2,1,0)(..)(minxx2.根據(jù)函數(shù)類型分類

根據(jù)目標(biāo)函數(shù)和約束函數(shù)是否是線性函數(shù)可分為三類，具體見下表。類目標(biāo)函數(shù)約束函數(shù)線性規(guī)劃線性線性二次規(guī)劃二次函數(shù)線性非線性規(guī)劃除上(1)

極大值問題極小化對maxf(x),

只要令g(x)=-f(x)

,

則極大值問題就轉(zhuǎn)化為求g(x)的極小值問題.

4.將一般的線性規(guī)劃問題轉(zhuǎn)化成標(biāo)準(zhǔn)形式的方法

3.線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式稱變量xn+p為松馳變量.

(3)

轉(zhuǎn)變“≥”約束為等式約束(2)

轉(zhuǎn)變“≤”約束為等式約束

引入xn+p

≥0

,使引入xn+q

≥0

,使稱變量xn+q為剩余變量.

標(biāo)準(zhǔn)形式要求

xi

≥0,模型中如果出現(xiàn)xi可任取值,則稱xi為自由變量,此時可作如下處理:

(4)消除自由變量

例5

將下面線性規(guī)劃化為標(biāo)準(zhǔn)形.

引入新變量,令即可.解極大問題極小化:

引入松馳變量

x4≥0,使.引入剩余變量x5≥0,使消除自由變量x3,

令則原規(guī)劃的標(biāo)準(zhǔn)形式為注:

標(biāo)準(zhǔn)形中還可要求bi

≥0

(i=1,…,m),若某個bi

≤0,則可在所在等式兩端同乘以(

1)即可.

5.線性規(guī)劃的標(biāo)準(zhǔn)形還可以寫成矩陣形式

令則線性規(guī)劃的標(biāo)準(zhǔn)形式又可寫成矩陣形式:

的矩陣形式為:

如例5，即規(guī)化:其中§3.2二維線性規(guī)劃的圖解法當(dāng)x=(x1,x2)

(即二維線性規(guī)劃)時,可行集R可用圖形表示出來,因而可用圖解法來求該線性規(guī)劃的解.對線性規(guī)劃設(shè)其可行集為R.例1

用圖解法求解解先繪出可行集,由x1

≥0,x2

≥0,可知可行集在第一象限內(nèi);因–x1

+2x2

≤4,可知可行集在以直線–x1

+2x2

=4為分界線,且含原點的半平面內(nèi);而3x1

+2x2

≤12是包含坐標(biāo)原點的、以直線3x1

+2x2

=12為分界線的半平面.這兩個半平面在第一象限的交集就是可行集,如下圖所示的陰影部分.

再繪出目標(biāo)函數(shù)的等值線.當(dāng)目標(biāo)函數(shù)值為z0時,其等值線為–x1

-2x2

=z0這是一條直線,當(dāng)

z0

取不同值時,可得到其他等值線.因具有相同的斜率,所以等值線是彼此平行的直線.例如,當(dāng)z0=0時,得一通過坐標(biāo)原點的等值線

–x1

-2x2

=0然后確定目標(biāo)函數(shù)的負(fù)梯度方向(這是函數(shù)值下降最快的方向):

如上圖中箭頭所指的方向.

最后沿(1,2)T方向,作目標(biāo)函數(shù)值的一系列等值線(一族平行線).由圖可知,沿目標(biāo)函數(shù)值下降方向的等值線在點x*=(2,3)與可行集R唯一相交;

若目標(biāo)函數(shù)值繼續(xù)下降,相應(yīng)的等值線與可行集將不再相交.故點x*=(2,3)為此線性規(guī)劃的唯一最小值點,相應(yīng)的最小值為

8.

例中最優(yōu)解是R的一個“頂點”.一般地,可證:(1)

若可行集R=

,則線性規(guī)劃無最優(yōu)解;例2

解線性規(guī)劃(2)

若線性規(guī)劃的最優(yōu)解存在,則必可在R的某個“頂點”處取得.(3)

若R的某兩個頂點是最優(yōu)解,則這兩個頂點所連接的線段上任一點都是最優(yōu)解.

解可行集如下圖所示的陰影部分.

繪出過原點的等值線;求出目標(biāo)函數(shù)的負(fù)梯度方向:

沿(-2,-2)T的方向作目標(biāo)函數(shù)的等值線,也即2x1

+2x2

=0的平行線,易見x*=(1,0)是此規(guī)劃的唯一最小值點,且最小值為2.說明:

將例2的min改為max,即min(-2x1

-2x2).此目標(biāo)函數(shù)的下降方向與例2的相反,由圖可知此線性規(guī)劃沒有最優(yōu)解.

例3

將例1的目標(biāo)函數(shù)改為f(x)=-3x1

-2x2,而約束條件不變,

即求解可行集如圖:f(x)=-3x1

-2x2

可行集的4個頂點為:(0,2),(0,0),(4,0),(2,3)相應(yīng)的函數(shù)值依次為:-4,0,-12,-12所以,目標(biāo)函數(shù)的最小值為-12,且點(2,3)與(4,0)之間的所有點都是該規(guī)劃的最優(yōu)解,該規(guī)劃有無窮多個解.

§3.3線性規(guī)劃的基本概念及解的性質(zhì)

其中A為m

n矩陣,設(shè)秩R(A)=m,則m≤n,用Pj表示A的第j列,則Ax=b可記為基:

若可逆,則稱B為該線性規(guī)劃的基.稱為基向量.稱

xji

為基變量.其余變量稱為非基變量.考慮線性規(guī)劃:(3.3.1)基本解:

設(shè)是式(3.3.1)的一個基,相應(yīng)的基變量為

則方程組BxB=b有唯一解:可行解:

滿足Ax=b,x≥0

的向量x稱為式(3.3.1)的可行解.

基本可行解:

若x既是可行解又是基本解,則稱x為式(3.3.1)的基本可行解.此時的B稱為可行基.因A為m

n矩陣，所以式(3.3.1)的不同基最多有Cnm個.即基本可行解的個數(shù)有限.令非基變量全部為0,得Ax=b的一組解:

稱此解為式(3.3.1)的基本解.(假定j1,…,jm=1,…,m)最優(yōu)解:

CTx取得的最小值的可行解x*,稱為式(3.3.1)的最優(yōu)解.

例1

求下列約束的所有基本可行解.

即

均為基

解

由于x1=-2<0,故x不是可行解,從而不是基本可行解.(2)

取B2為基,則x2,x3

為基變量.(3)

取B3為基,則x1,x3

為基變量.所以所有基本可行解為:x2,x3

(1)

取B1為基,則定義1

設(shè),若對,及,都有

,則稱D為凸集.規(guī)定空集

與單元集也是凸集.

說明:

(1)

凸集又等價為:若,且,都有,則D為凸集.(2)

從幾何來講,若集合D中任意兩點的連線仍屬于D,則D為凸集.定義2

設(shè)為一組非負(fù)實數(shù),且,則稱為x1,x2,…,xm

的一個凸組合.定理

為凸集的充要條件是D中任意有限個點的凸組合仍在D中.

定義3

設(shè),D是凸集,若x0

不能表示為D中其他任意兩個不同點的凸組合,則稱x0

是D的極點.

例

(1)

右圖中,x1,x2,x3,x4為凸集D的極點.(2)

下圖,圓周上每一點都是極點.(3)

開區(qū)間為凸集,其上任一點都可表示為兩個不同點的凸組合,故開區(qū)間上沒有極點.從以上理論可知:

求解線性規(guī)劃問題,其本質(zhì)上是找出可行集的極點.而極點與基本可行解一一對應(yīng),基本可行解最多Cnm個.從理論上說都可全部計算出來,通過比較各極點處目標(biāo)函數(shù)值的大小就可以得到最優(yōu)解.

定理

若線性規(guī)劃有最優(yōu)解,則必可在其可行集的頂點處取得.

推論線性規(guī)劃可行集R的點x是R的極點的充要條件是x為此線性規(guī)劃的基本可行解.所以x1=(0,1,1)T

和-5是最優(yōu)解.

解由例1知此線性規(guī)劃有兩個基本可行解:

代入目標(biāo)函數(shù)得例4

求線性規(guī)劃的最優(yōu)解基本思想：

從可行集的一個頂點出發(fā),沿目標(biāo)函數(shù)值下降的方向?qū)ふ蚁乱粋€頂點,而頂點的個數(shù)有限,所以若有解,則必可在有限步求得最優(yōu)解.§3.4單純形法一、對應(yīng)于B的單純形表設(shè)線性規(guī)劃問題為:設(shè)系數(shù)矩陣A的秩為m,B為m

m的線性規(guī)劃問題的一個基.不妨設(shè)相應(yīng)地其中,為對應(yīng)于B的基變量部分;為對應(yīng)于B的非基變量部分.此時判別定理對于基B,若,且則對應(yīng)于基B的基本解便是最優(yōu)解,稱為基本最優(yōu)解;這時基B稱為最優(yōu)基.注:

≤0與是等價的.此時目標(biāo)函數(shù)值為

cTx=

cBTxB=

cBTB-1b所以當(dāng)x為基本解時(有xN=0)有記:其中稱為檢驗數(shù).

對應(yīng)于基B的單純形表,記為T(B),

定義為說明

(1)如果所有,這時對應(yīng)于基B的基本解為基本可行解,基B為可行基.(2)

若所有

而且所有

,這時對應(yīng)于基B的基本解為基本最優(yōu)解,基B為最優(yōu)基.相應(yīng)的目標(biāo)函數(shù)值為最優(yōu)值.例1

線性規(guī)劃有三個基:因此對于基B1的單純形表T(B1)如下:說明:

(1)

因基變量值非負(fù),所以上述解是基本可行解.

(2)

由表可寫出用非基變量x3表示S和用x3表示基變量.

對應(yīng)于B1的基本解及相應(yīng)的目標(biāo)函數(shù)值為:x1=1,x2=1,x3=0;S

=3.S表目標(biāo)函數(shù)

x1x2x3S3002x11101x21012S=3-2x3,x1=1-x3,x2=1-2x3類似,得表T(B2):說明:

因基變量值非負(fù),檢驗數(shù)非正,所以上述解是最優(yōu)解(x1,x2,x3)=(1/2,0,1/2),S=2.

x1x2x3S20

10x11/21-1/20x31/201/21T(B3):x1x2x3S1

200x2

1

210x31101說明:

因基變量有負(fù)值-1,所以上述基本解不是可行解.二、換基迭代所謂換基迭代就是從一個基本可行解迭代到一個新的基本可行解的方法.

第一行中的第二個數(shù)起是檢驗數(shù),可用以判定基B對應(yīng)的基本可行解是否為最優(yōu)解.若

(1)所有檢驗數(shù)皆非正,則判定基B是最優(yōu)基,取最優(yōu)解,求解終止.

(2)

有某些檢驗數(shù)是正的,此時就要進(jìn)行換基迭代.

由運算可知,如果已知線性規(guī)劃問題的一個可行基B,我們可求得對應(yīng)于基B的單純形表,表中

第一列就是目標(biāo)函數(shù)值和基本解中基變量的值;一般地,如果對應(yīng)于可行基的單純形表(如下表)的檢驗數(shù)出現(xiàn)正數(shù),這時就不能判定B是否為最優(yōu)基,因而要進(jìn)行換基迭代.

換基迭代的步驟:

(1)求軸心項:

在所有的檢驗數(shù)b0j>0中,選最左邊的一個,設(shè)為b0s,其對應(yīng)的非基變量設(shè)為xs,對應(yīng)于向量用PS中正的各分量bis

分別去除對應(yīng)的bi0,取bi0/bis中最小者(若同時有幾個相同的最小者,則取其中對應(yīng)的基變量下標(biāo)最小者),設(shè)為br0/brs,則稱brs為軸心項,并將brs用□框住.

(2)

在基B中,調(diào)進(jìn)PS

(稱為進(jìn)基列),換出Pr

(稱為出基列),xs稱為進(jìn)基變量,xr稱為出基變量,得新基為使新表中brs=1,用原表中brs去除第r行各數(shù),得新表第r行的數(shù),即為使新表中bis=0（0≤i≠r≤m）,將在原表中第i行各數(shù)減去第r行相應(yīng)數(shù)的brj/brs,倍,得新表第i行的數(shù),即(3)

對基B的單純形表,進(jìn)行適當(dāng)?shù)淖儞Q,使PS各量變?yōu)閱挝幌蛄?分量brs取1,其他分量取0),便得新基的單純形表.

例如S表目標(biāo)函數(shù)

x1x2x3S3002x11101x21012

x1x2x3S3002x11101x31/201/21檢驗數(shù)為正Min{1/1,1/2}=1/2軸心項變?yōu)?(該行每元同除以2)x1x2x3S20

10x11/21-1/20x31/201/21變?yōu)?三、由一可行基開始,求解線性規(guī)劃的步驟1)作對應(yīng)于基B的單純形表T(B)

2)判別1.

如果所有檢驗數(shù)都非正,則基B對應(yīng)的基本可行解為最優(yōu)解.

已知一可行基

2.如果檢驗數(shù)中,有些為正數(shù),但其中某正數(shù)所對應(yīng)的列向量的所有分量都是非正數(shù),則問題無最優(yōu)解.

3.如果檢驗數(shù)中,有些為正數(shù),且這些正數(shù)的對應(yīng)的列向量中都有正分量,此時要進(jìn)行換基迭代.3)換基迭代注:

1.

若基B為單位矩陣I,則2.

若B=I,且cBT=0（如所有的基變量均為松馳變量），則

解引進(jìn)松馳變量,變化為標(biāo)準(zhǔn)形.

例2

用單純形法求解下列線性規(guī)劃此時-cT

=(2,5,0,0,0),bT

=(4,3,8)x1x2x3x4x5S

025000x3410100x4301010x5812001(1)

取基B為單位矩陣(P3,P4,P5

)得單純形表

(2)

判別數(shù)有正數(shù),正數(shù)中最左邊的為

2.(3)

因Min{4/1,8/1}=4,所以1為軸心項

.(4)

在基B1中調(diào)進(jìn)P1,換出P3,得新基(P1,P4,P5

)得單純形表

x1x2x3x4x5S

805

200x1410100x4301010x540

2

101(5)

判別數(shù)有正數(shù)5.(6)

因Min{3/1,4/2}=2,所以2為軸心項

.重復(fù)上面換基迭代步驟可得對應(yīng)于新基的單純形表

檢驗數(shù)有正數(shù)1/2,作換基迭代步驟,得新的單純形表

x1x2x3x4x5S

18001/20-5/2x1410100x41001/21-1/2x2201-1/201/2x1x2x3x4x5S

19000

1

2x12100

21x320012

1x2301010檢驗數(shù)全部小于等于零,得最優(yōu)解為去掉松馳變量的值,即得原問題的最優(yōu)解為:x1=2,x2=3相應(yīng)的原問題的目標(biāo)函數(shù)最大值為:

f(2,3)=19.例3

求解線性規(guī)劃解此時-cT

=(1,2,0,0,0),bT

=(4,3,8)(1)同上例一樣,取基B為單位矩陣(P3,P4,P5

)得單純形表:

換基迭代后,得新基(P1,P4,P5

)的單純形表:x1x2x3x4x5S

012000x34

1

0100x4301010x5812001x1x2x3x4x5S

402

100x1410000x4301010x540

2

101換基迭代后,得新基(P1,P4,P2

)的單純形表:x1x2x3x4x5S

80000

1x1410100x41011/21-1/2x2201-1/201/2

值得指出的是:

在上表中除基變量x1,x2,x4

對應(yīng)的檢驗數(shù)為零外,非基變量x3對應(yīng)的檢驗數(shù)也為零,可以把x3對應(yīng)列中b23=?作軸心項.在最優(yōu)基(P1,P4,P2

)中調(diào)進(jìn)P3

,調(diào)出P4

進(jìn)行換基迭代,得新的最優(yōu)基(P1,P3,P2

)對應(yīng)的單純形表:檢驗數(shù)全部小于等于零,得最優(yōu)解為:(x1,x2,x3,x4,x5)=(4,2,0,1,0),Smin

=-8因表中的檢驗數(shù)全非負(fù),所以(P1,P3,P2

)也為最優(yōu)基,對應(yīng)的基本最優(yōu)解為:所以,原問題的又一基本最優(yōu)解為:x1=2,x2=3;對應(yīng)的目標(biāo)函數(shù)最小值為:f(2,3)=-8.

x1x2x3x4x5S

80000

1x121-20

21x320212-1x230101

1綜上,得兩個最優(yōu)解:x1*=(4,2),x2*=(2,3).它們是可行集凸集的兩個頂點,故這兩個頂點的連線上的所有點都是該線性規(guī)劃的最優(yōu)解—最優(yōu)解有無窮多個,其表達(dá)式為

結(jié)論:

線性規(guī)劃問題的最優(yōu)基對應(yīng)的單純形表中,若非基變量對應(yīng)的檢驗數(shù)都是負(fù)數(shù),其基本最優(yōu)解是唯一的;若非基變量對應(yīng)的檢驗數(shù)中有零,這一問題的基本最優(yōu)解可能不止一個,一旦求得另一個最優(yōu)解,就可得到無窮多個最優(yōu)解.解例4

求解取基B為單位矩陣(P3,P4,P5

)得單純形表:

x1x2x3x4x5S

025000x34

10100x4301010x58

10001因檢驗數(shù)2>0,其對應(yīng)的列向量所以原規(guī)劃無最優(yōu)解.注:為避免迭代中的循環(huán),軸心基的選取應(yīng)遵循以下兩條原則:1)

對進(jìn)基列Ps在所有判別數(shù)為正的那些列中,以列標(biāo)最小,也就是最左邊的那一列作進(jìn)基列.2)

對軸心項若在進(jìn)基列Ps中有多個分量符合軸心項的條件,則取行標(biāo)最小的那一個作為軸心項.§3.7一維搜索法一、下降迭代算法及終止準(zhǔn)則下降迭代算法的基本思想:

選擇一個初始點x0

，逐次產(chǎn)生一系列點列x0,x1,x2,…，使

f(x0)＞f(x1)＞…＞f(xk)＞…并希望點列{xk}的極限就是f(x)的極小點x*。即問題為:基本步驟

(1)選初始點x0，令k=0。

(2)按某種規(guī)則確定一個方向pk，使f(x)

沿pk

方向函數(shù)值下降（稱為搜索方向）。

（3）從xk

出發(fā)以pk

為方向作射線xk+

pk（

≥0），（參數(shù)

稱為步長因子）。在此射線上求f(x)

的最小值。即求min03f(xk+adk)=f(xk

+akdk)=f(xk+1

)

a其中xk+1=xk+

kdk

說明：（*）式稱為終止準(zhǔn)則，終止準(zhǔn)則也可用下式(4)判別xk+1

是否為最優(yōu)解；若則xk+1為近似最優(yōu)解，迭代停止；否則令k﹕=k+1，轉(zhuǎn)（2）。其中ε1為預(yù)先給定的一個很小的正數(shù),▽f(xk+1)

為函數(shù)在點xk+1

的梯度.?f(xk+1)f(xk+1)-f(xk)＜ε1

或

＜ε1（*）或二、黃金分割法（0.618法）0.618法是求單峰函數(shù)的一種試探法，也是廣泛使用的方法之一。1.單峰函數(shù)定義

設(shè)f(x)是定義在[a,b]上的函數(shù)，若（i）存在x*∈[a,b]使minf(x)=f(x*)x∈[a,b]（ii）對任意的a≤x1<x2≤b，當(dāng)x2<x*時，f(x1)>f(x2)當(dāng)x1>x*時f(x1)<f(x2)，則稱f(x)為[a,b]上的單峰函數(shù)。例如：ax1x2

x*x1’x2’)(xf單峰函數(shù)ab)(xf不是單峰函數(shù)基本思想:

在搜索區(qū)間[a,b]內(nèi)適當(dāng)插入兩點t1和t2將其分成三段,通過比較這兩點的函數(shù)值后,由單峰函數(shù)的性質(zhì),可刪去最左或最右端的一段,這算一次迭代.然后在留下來的區(qū)間上再插入一點,重復(fù)上述過程,如此下去,可將區(qū)間無限縮小.2.黃金分割法說明:

(1)

黃金分割法中參數(shù)0.618是由對稱原則和等比收縮原則導(dǎo)出的,其中對稱原則是指選點x1和x2，使

[a,x1]的長=[x2,b]的長即使:x1-a=b-x2

x2=a+b-x1

（或x1=a+b-x2）即〝加兩頭減中間〞。等比收縮原則是指每次留下的區(qū)間長是上次留下的ω倍（ω即為0.618）且x1或x2是下次搜索的一個分點.

(2)

由等比收縮原則可得x1-a=l0(1-ω),l0為[a,b]的長.再由〝加兩頭減中間〞可得兩分點與端點間的關(guān)系式:x1=a+(1-ω)l0=a+(1-ω)(b-a)x2=a+

b-x1=a+ω(b-a)ω=0.618算法(0.618法

)

已知目標(biāo)函數(shù)f(x)，精度ε。(1)確定f(x)的搜索區(qū)間[a,b]—利用前一算法。(5)若y1≤y2，則置b:=x2，x2:=x1，y2:=y1

轉(zhuǎn)3）；否則置a:=x1，x1:=x2，計算x2=a+b-x1，y2=f(x2)，轉(zhuǎn)4）。(2)計算x2=a+0.618(b-a)，y2=

f(x2)。(3)計算x1=a+b-x2

，y1=f(x1)。(4)若|x1–x2|<ε，則停。取;否則轉(zhuǎn)5)。221*xxx+=§3.8無約束最優(yōu)化方法最速下降法1.最速下降方向

該方法在每次迭代中沿最速下降方向進(jìn)行搜索。那么什么方向是函數(shù),f(x)在點x∈Rn

處的最速下降方向呢？

分析：設(shè)f(x)在x處可微，由泰勒公式有)(δx+f=++)(xf)(xδgT)(δo其中g(shù)(x)=▽f(x)≠0，δ=(δ1,δ2,…,δn)T,,表示當(dāng)δ→0時，是比高階的無窮小。若忽略高階無窮小,上式等價于)(δo)(δo22221dd+…+dn

+=δδ再對上式右邊用Cauchy不等式可得)(δx+f)(xfδg(x)T-=δTg(x)≥-

)(xgδ)()(xxgg當(dāng)且僅當(dāng)δ=-時上式取等號。于是可見當(dāng)δ取負(fù)梯度方向時，f(x+δ)下降最快。這個方向稱為最速下降方向。)()(xxgg當(dāng)且僅當(dāng)δ=-時上式取等號。)(δx+f)(xf-≥-)(xgδ2.最速下降法問題：minf(x)，x∈Rn,本節(jié)的優(yōu)化問題均作此假定。計算步驟1）取初始點x0∈Rn