非線性規(guī)劃

如果目的函數(shù)或約束條件中具有一種或各種是變量非線性函數(shù)，咱們稱此類規(guī)劃問(wèn)題為非

線性規(guī)劃（nonlinearprogramming,可簡(jiǎn)記為NP）。

普通地，解非線性規(guī)劃問(wèn)題要比解線性規(guī)劃問(wèn)題困難多，由「它不像解線性規(guī)劃問(wèn)題有單純

形法這一通用辦法，非線性規(guī)劃當(dāng)前還沒(méi)有適合于各種問(wèn)題普通算法，各個(gè)辦法均有自己特

定應(yīng)用范疇.

非線性規(guī)劃基本概念和基本原理

第一節(jié)非線性規(guī)劃數(shù)學(xué)模型

例：某金屬制品廠要加工一批容積為1米3長(zhǎng)方形容器，按規(guī)格規(guī)定，上下底材料為

25元/m2,側(cè)面材料為40元/m2,試擬定長(zhǎng)、寬、高尺寸，使這個(gè)容器成本最低。

設(shè)容器長(zhǎng)為以寬為瓦則高為跖

依照題意得：

min/（M，x,）=50XR2+80]―-—（x（+x2）]

x^x2>0

例：某公司經(jīng)營(yíng)兩種設(shè)備，笫一種設(shè)備每件售價(jià)30元，第二種設(shè)備每件售價(jià)為4S0元，依照

記錄，售出一件第一種設(shè)備所需營(yíng)業(yè)時(shí)間平均為0.5小時(shí)，第二種設(shè)備為B時(shí),其中團(tuán)是第二

種設(shè)備售出數(shù)量，已知該公司在這段時(shí)間內(nèi)總營(yíng)業(yè)時(shí)間為800小時(shí)，試決定使其營(yíng)業(yè)額最大

營(yíng)業(yè)籌劃。

解：設(shè)該公司籌劃經(jīng)營(yíng)第一種設(shè)備為2件，第二種設(shè)備為13件，依照題總得：

maxf（JV]yx2）=30為+450x2

?0.5x,4-（2-1-0.25X2）X2<800

X1,x2>0

由這兩個(gè)例子可以看出，這兩個(gè)例子在高等數(shù)學(xué)中代表了兩類不同類型極值問(wèn)題。例1

是無(wú)條件極值：例2是有條件極值。

如果令U是n維空間13上點(diǎn)，則普設(shè)非線性數(shù)學(xué)模型為:

min

//；（/）=0,i=1,2,…，m

gjW20,J=1,2,…，/

13為目的函數(shù)，E為約束條件，X為自變量。若某個(gè)約束條件是13不等式，不等式兩邊乘以

“-1”。

第二節(jié)極值問(wèn)題

設(shè)團(tuán)是定義在n維歐式空間空間團(tuán)上某?區(qū)域13上n元函數(shù)，其中巴

對(duì)于團(tuán)如果存在某一種。使得所有與B距離不大于03,（即13）,均滿足區(qū)則稱0為用在目

上局部極小點(diǎn)。田為局部極小值。

若所日田，HM有近則稱（3為（3在（3上嚴(yán)格局部極小點(diǎn)。13為嚴(yán)格局部極小信。

若點(diǎn)瓦對(duì)于所有13,均滿足團(tuán)，則稱U為13在團(tuán)上全局極小點(diǎn)。團(tuán)為全局極小值。

若對(duì)于所有國(guó)且回，均有氏則稱3為由在圖上嚴(yán)格全局極小點(diǎn)。（3為嚴(yán)格全局極小值。

如果將上述不等式反向，即可得到局部極大值與全局極大值定義。

定理1:極值必要條件

設(shè)（3是定義在自上某一區(qū)域用上函數(shù),（3是團(tuán)內(nèi)一點(diǎn)，若自在回處可微且獲得局部極值，則必有巧或圓,

上式點(diǎn)稱為駐點(diǎn)，或平穩(wěn)點(diǎn)。即在區(qū)域內(nèi)部，極點(diǎn)必是駐點(diǎn).（3稱為3在點(diǎn)X處梯度。但反過(guò)

米，駐點(diǎn)不一定是極值點(diǎn)。如點(diǎn)（0,0）母國(guó)數(shù)13狂點(diǎn)，但不是極值點(diǎn)。

定理2:極值充要條件

設(shè)團(tuán)是定義在B上某一區(qū)喇上函數(shù),且在圖上二次持續(xù)可微，團(tuán)是團(tuán)內(nèi)一點(diǎn)，若ta在它處滿足團(tuán)

且對(duì)任意非零向量Y,有色則稱（3在點(diǎn)目處獲得嚴(yán)格局部極小值。這里同是用在點(diǎn)21處海賽矩陣。

若回則（3在點(diǎn)13處獲得嚴(yán)格局部極大值。

山定理2看出，駐點(diǎn)處海賽矩陣13是正定矩陣時(shí)，函數(shù)團(tuán)在點(diǎn)回處獲得極小值。駐點(diǎn)處海賽矩

陣13是負(fù)定矩陣時(shí)，函數(shù)（3在點(diǎn)團(tuán)處獲得極大值。

定理3:設(shè)0是定義在13上函數(shù)，且在點(diǎn)0處存在二階持續(xù)偏導(dǎo)數(shù)，若團(tuán)是團(tuán)局部極小點(diǎn)，則（3,且

圖半正定。

需要指出是，定理2不是必要條件，定理3不是充分條件。

例：對(duì)于無(wú)約束問(wèn)題

minf(X)=x：+=()；+xQ

解：由于0

令（3,得駐點(diǎn)0,

12x；+4君8萬(wàn)典

并且〃CO=

8X}X24*：+12^2

_o0

因此//（/）=

_00

日不是正定矩陣，但用在點(diǎn)13處獲得最小值，即由為住嚴(yán)格局部極小點(diǎn)。

解：由于（3

令包，得伺

02020

//(/),//（A）,〃(元)

2X2-20-202

__90-_20

〃（K）=,//a,,）=

L0-2jLC2]

13是不定，因而13不是極值點(diǎn)；13是負(fù)定，故G3是極大點(diǎn)。團(tuán)是正定，故團(tuán)是嚴(yán)格極小點(diǎn)。

例：minf{X}=）；一

解：由于ffl,

令0,得用

〃⑴=〃⑴=12。

06*2）[00

日是半正定矩陣，但在13任意團(tuán)鄰域13內(nèi)，總可以取到團(tuán)，使得（3,即（3不是局部極小點(diǎn)。

例：minf（X）=-x1-x}-

33

解：由于團(tuán)

令ffl,得團(tuán)

0],〃(見(jiàn))=\2O-

//(T)=:?

0-2]LO2

:

//(i3)=[■O-

02.

13是不定，因而13不是極值點(diǎn);

13是負(fù)定，故(3是極大點(diǎn)。團(tuán)是正定，故13是嚴(yán)格極小點(diǎn)。

非線性規(guī)劃圖解問(wèn)題

圖解法可以給人以直觀概念，當(dāng)只仃兩個(gè)白變量時(shí)，非線性規(guī)劃也像線性規(guī)劃同樣，可以運(yùn)

用圖解法。

例：用圖解法求解非線性規(guī)劃。

[minf[X}=(X,-2)2+(x,-I)2

例：＜

為+蒞-5=0

若令目的函數(shù)瓦C為某一常數(shù)。則圖就代表一條曲線，稱為等位線或等高線。等值線田與直線

AB相切，切點(diǎn)為我

例：用圖解法求解非線性規(guī)劃。

2

minf(X)=(4-2尸+(x2-I)

天十々-5A0

x2>0

解：畫(huà)出目的函數(shù)等值線

0,它表達(dá)一族中心在（2,1）上同心圓。

畫(huà)出約束區(qū)域：先畫(huà)13,這是一條拋物線，再畫(huà)不等式瓦但所代表約束區(qū)域。則拋物線孤AB

CD為約束集。由動(dòng)點(diǎn)A出發(fā)拋物線ABCD移動(dòng)時(shí)，弧AB段，目的函數(shù)值下降，在BC

段函數(shù)值上升，弧CD段，目的函數(shù)值下降，并且在D點(diǎn)是可行域上使目的函數(shù)值最小點(diǎn)，

它是全局最長(zhǎng)處。其坐標(biāo)由約束方程組可得.最長(zhǎng)處（4,1）,最優(yōu)值機(jī)

第三節(jié)凸函數(shù)及其性質(zhì)

一、凸函數(shù)

凸集、凸函數(shù)是研究非線性規(guī)劃問(wèn)題所不可缺少內(nèi)容，關(guān)于凸集概念參見(jiàn)我性規(guī)劃某些,

這里重要簡(jiǎn)介凸函數(shù)概念。

定義：設(shè)例是定義在n維歐式空間空何田中某個(gè)凸集團(tuán)上函數(shù)，若對(duì)任意一種實(shí)數(shù)期以及圖中任

意兩點(diǎn)（3和（3,恒有13,

則稱rco是定義在凸集c上凸函數(shù)。

若對(duì)任意一種實(shí)數(shù)團(tuán)以及樂(lè)幽,恒有12,則稱B是定義在凸集13上嚴(yán)格凸函數(shù)。

若上述不等式反向，稱團(tuán)分別為0上凹函數(shù)及嚴(yán)格凹函數(shù)。

下面給出凸函數(shù)與凹函數(shù)幾何意義

即函數(shù)圖形上任意兩點(diǎn)連線處處不在這個(gè)函數(shù)圖形下方，稱它為凸函數(shù)，下凸。

線性函數(shù)既是凸函數(shù)，乂是凹函數(shù)。

下面簡(jiǎn)介凸函數(shù)性質(zhì)。

性質(zhì)I:設(shè)例是凸集用上凸函數(shù),況且用則:在

性質(zhì)2：設(shè)仍是凸集13上兩個(gè)凸函數(shù)，姐和函數(shù)的仍是由上凸函數(shù)。

性質(zhì)3：設(shè)田是凸集目上凸函數(shù)，對(duì)任意實(shí)數(shù)團(tuán)13仍是凸集田上凸函數(shù)。

由性質(zhì)2、性質(zhì)3可得：

凸集B上有限個(gè)凸函數(shù)團(tuán)正系數(shù)線性組合瓦仍是凸集團(tuán)上凸函數(shù)。

性質(zhì)4:設(shè)團(tuán)是定義在凸集圖上凸函數(shù)，則對(duì)每一種實(shí)數(shù)圖，集合回是凸集。集合田稱為實(shí)數(shù)13水

平集。

值得注意是，性質(zhì)4逆命題不成立。

例：當(dāng)團(tuán)時(shí)，團(tuán)是13上嚴(yán)格凹出數(shù)，而不是凸函數(shù)。

但對(duì)于一切瓦水平集13是凸集.

下面簡(jiǎn)介凸函數(shù)鑒定辦法。

定理：設(shè)（2是凸集（3上具備一階持續(xù)偏導(dǎo)數(shù)，則同是目上凸函數(shù)回對(duì)于任意兩點(diǎn)（3,必有目

不等式是嚴(yán)格不等式時(shí)，即得嚴(yán)格凸函數(shù)充要條件。

即一種可微函數(shù)時(shí)凸函數(shù)O函數(shù)圖形上任意一點(diǎn)處切平面位于?曲面下方。

定理：設(shè)團(tuán)是凸第13上具備二階持續(xù)偏導(dǎo)數(shù)，則13是13上凸函數(shù)U海賽矩陣13時(shí)整個(gè)團(tuán)上是半正

定。

喇賽矩陣用是正定，則仍是嚴(yán)格凸函數(shù),反之不成立。

凹函數(shù)和上面成果類似，在此就不重且。

例：設(shè)團(tuán)，其中回是n階對(duì)稱矩陣,則

（1），是一"上凸函數(shù)O0為半正定矩陣。

（2）F是""上嚴(yán)格凸函數(shù)O0為正定矩陣。

證：二次函數(shù)閉在團(tuán)上具備二階持續(xù)偏導(dǎo)數(shù)，且

13由定理知，（1）成立。

卜面證（2）:由于團(tuán)是閉上嚴(yán)格凸函數(shù)，當(dāng)且僅當(dāng)

0,任意①

即等價(jià)干￡（「）＞f（X）+（OX+bY（Y—才）.X.YeR\XY.

由于13是二次函數(shù),13為對(duì)稱矩陣，因此上式等價(jià)于

13即故（3為正定矩陣。

例：證明（3為凹函數(shù)

證：

2222

df?dfodfdf.

ex：84333月

故EE為負(fù)定矩陣，故團(tuán)為嚴(yán)格凹函數(shù)。

咱們懂得，普通來(lái)說(shuō)，函數(shù)局部極值并?定就是全局極值，而解非線性翅劃時(shí)，所求地

優(yōu)解必要是目的函數(shù)在某個(gè)可行域上所有極值。但對(duì)于一類所給凸規(guī)劃來(lái)比下面將看到,

其局部最優(yōu)解必然是全局最優(yōu)解。

定理：設(shè)團(tuán)是凸集團(tuán)上一種凸函數(shù)，則使得團(tuán)獲得極小值點(diǎn)集必是一種凸集，并HJ3任一局部極

小值也是它在（3上全局極小值。

該定理闡明，對(duì)于凸集上凸函數(shù)，所有極小點(diǎn)位于批準(zhǔn)凸集中，即所有極小點(diǎn)集合形成?種

凸集，并且局部極小值也是全局極小值.

定理：設(shè)圖是凸集團(tuán)上一階可微凸函數(shù)，點(diǎn)此且為田內(nèi)點(diǎn)，則同為B在同上全局極小點(diǎn)用對(duì)于所有

國(guó)有同

由定理可知，當(dāng)團(tuán)為13內(nèi)點(diǎn)時(shí)，上式對(duì)于任意（3都成立，即它意味著回，也就是，對(duì)于凸集

上凸函數(shù)，駐點(diǎn)就是全局極小點(diǎn)。

當(dāng)前咱們回到非線性規(guī)劃中：

非線性規(guī)劃數(shù)學(xué)模型為:

minf〈X)(1)

力,(￥)=0,i=1,2,???,Z7⑵

g,Cr)>0,j=1,2,...,/(3)

它與線性規(guī)劃類似，把滿足約束條件（2〉、（3）點(diǎn)稱為可行點(diǎn)（可行解）。

所有可行解集合稱為可行域。若某個(gè)可行解使目的函數(shù)（1）值最小，就稱它為最優(yōu)解。

下面咱們考慮一種比較特殊非線性規(guī)劃：

minf{X}

n=M兄CONO,j=1,2,-,/}

其中,例是凸函數(shù),13為凹函數(shù)5為凹函數(shù)），這樣非線性規(guī)劃稱為凸規(guī)劃?？梢宰C明，凸劃可

行域是凸集。

由此可知，凸規(guī)劃局部最優(yōu)解就曷它個(gè)局最優(yōu)解。因而，凸規(guī)劃是一種較簡(jiǎn)樸非線性規(guī)劃。

例：求解依線性規(guī)劃

min/(/)=-2*+1

S(才)=一1；+4^(+-5>0

s衣&(*)=-V)-2x2+4>0

xv/之0

解:曬塞矩陣為:

82f(X)d2fW'8?當(dāng)(4)求孤了)

肅dxxdx2-2O"Ox；己丫0丫2[-20

〃⑴=1—，6（才）828(才)32?⑴一|00

才/(4)d2f(X}_02_

dxdxdx"2

21血百ax2_

由于B為正定矩陣，故13為嚴(yán)格凸函數(shù)：B為半定矩陣，所覺(jué)得為凹函數(shù)，B為線性函數(shù)，可以看

作凹函數(shù)。

因此，該非線性規(guī)劃為凸規(guī)劃。

如圖所示，圖中A點(diǎn)為最長(zhǎng)處比目的函數(shù)最優(yōu)侑為心

第四節(jié)下降迭代算法

對(duì)于求可微函數(shù)最優(yōu)解，從理論上講，咱們是?方面令函數(shù)梯度等于零（0）,求得駐點(diǎn),

然后運(yùn)用充分條件進(jìn)行鑒別，求最優(yōu)新。

但在實(shí)際中，對(duì)于普通n元函數(shù)目來(lái)說(shuō)，由于團(tuán)得到經(jīng)常是一種非線性方程組，求它解相

稱困難。此外諸多實(shí)際問(wèn)題目的函數(shù)對(duì)各自變最偏導(dǎo)數(shù)不存在，從而無(wú)法運(yùn)用上面所說(shuō)求它

駐點(diǎn)，因而這時(shí)經(jīng)常使用迭代法。

所謂迭代法，就是從已知點(diǎn)用出發(fā)，按照某種規(guī)則（即算法），求出比田更好解瓦（若極小化問(wèn)

題，叫再按照此規(guī)則求出比國(guó)更好點(diǎn)畫(huà)…如此重復(fù)這個(gè)過(guò)程，便產(chǎn)生一種點(diǎn)列瓦在一定條

件下，下降迭代算法產(chǎn)牛?點(diǎn)列收斂于原問(wèn)題解。即團(tuán)颯

稱該點(diǎn)列卜叫收斂于工

由于算法產(chǎn)生點(diǎn)列使目的函數(shù)值逐漸減小，稱這--算法為下降算法。

收斂速度

設(shè)算法產(chǎn)生點(diǎn)列，剛攵斂到解團(tuán)且團(tuán),團(tuán)，若存在（3,及一種與迭代次數(shù)k無(wú)關(guān)常數(shù)由，使

1.線性收斂：當(dāng)團(tuán)，（3時(shí)稱為線性收斂速度。

2.超線性收斂：當(dāng)0,0,或0,0IM,稱為超線性收斂速度

3.二階收斂：當(dāng)G）,k充分大時(shí)有目

普通地以為，具備超線性收斂或二階收斂速度算法是比較迅速算法。但是應(yīng)當(dāng)結(jié)識(shí)到,

對(duì)任意一種算法，收斂性和收斂速度理論成果并不保證算法在實(shí)際應(yīng)用（執(zhí)行）時(shí)一定有好

實(shí)際計(jì)算效果。一方面，由「這些理論成果白身不能保證算法一定行好侍性；另一方面是它

們忽視了計(jì)算過(guò)程中十分重要舍入誤笄影響。

對(duì)于?不同問(wèn)題，要依照詳細(xì)狀況來(lái)選取算法，由丁?咱們事先并不懂得最優(yōu)解，迭代到什么時(shí)

候停止呢？慣用準(zhǔn)則是：

（1）|片旬-卜￡、,『（M，】））_￡（『*））］<Q

卜-r（/u））||

-/

⑶|"（心））|</

迭代中咱們從?點(diǎn)出發(fā)沿卜降可行方向找?種新、性質(zhì)有所改進(jìn)點(diǎn)。

△下降方向：

設(shè)回，若存在0,使同則稱（3為12點(diǎn)下降方向。

△可行方向：設(shè)瓦若存在瓦使團(tuán)稱團(tuán)為田點(diǎn)可行方向。

同步滿足上述兩個(gè)性質(zhì)方向稱下降可行方向。

4.1慣用搜索算法構(gòu)造

在以上迭代過(guò)程中，選用搜索方向以是最核心一步，計(jì)算各種算法區(qū)別，重要在于擬定

搜索方向辦法不同。

擬定步長(zhǎng)算法也向諸各種，步氏送定是由使目的附數(shù)值沿搜索方向下降最多根據(jù)，即沿

射線13求￡極小。

即選用回使團(tuán)由于這?工作是求覺(jué)得13變0?元函數(shù)13極小點(diǎn)13,故稱為一維搜索或線性搜

索。由此擬定步氏為最佳步長(zhǎng)。

一維搜索有一種重要性質(zhì)：在搜索方向上所獲得最長(zhǎng)處處梯度和該方向正交。

即=0,

表述為定理如下:

定理：設(shè)目的函數(shù)（3具備一階持續(xù)偏導(dǎo)數(shù)，回按下述產(chǎn)生:

f（M）+4/力=+2*））｝

￥（&.1）=一+"幻

則有

由于函數(shù)團(tuán)在某點(diǎn)梯度和該點(diǎn)等值面切線正交，on個(gè)人一維搜索方向和其上最長(zhǎng)處處等

值面相切。

第五節(jié)一維搜索

定理：設(shè)(3在13上單峰,13。那么

1°若13,則團(tuán),團(tuán)；如左下圖

2°若瓦則回團(tuán)：如右下圖

一、分?jǐn)?shù)法(斐波那鍥法)

分?jǐn)?shù)法是尋找單峰函數(shù)極小點(diǎn)-一種辦法。

設(shè)團(tuán)在區(qū)間13上只有一種極值點(diǎn)團(tuán)則對(duì)區(qū)間團(tuán)內(nèi)任意兩點(diǎn)回國(guó)并計(jì)算心貝!必有下列兩種

狀況之一：

(1)0,此時(shí)必有此

(2)0,此時(shí)必有此

通過(guò)上面討論，咱們懂得，只要在區(qū)間￡3內(nèi)取兩個(gè)不同點(diǎn)，并算出這兩點(diǎn)函數(shù)值，加以比較,

就能把搜索區(qū)向0縮小成團(tuán)或巳。

如果繼續(xù)縮社區(qū)間閉或同就需要在區(qū)間閉或片內(nèi)取一點(diǎn)團(tuán)，并計(jì)算出Pi值，并與目比較。

若團(tuán)則田:

a,則a.

這樣如此繼續(xù)卜.去，就能越來(lái)越精準(zhǔn)地預(yù)計(jì)出以位置,固然，如果無(wú)限地搜索卜.去，可以

精準(zhǔn)地求出極小點(diǎn)機(jī)但實(shí)際計(jì)算時(shí)只能使g包括在某個(gè)社區(qū)間內(nèi)，且此時(shí)社區(qū)間長(zhǎng)度不超過(guò)

某一給定精度就可以了。如通過(guò)n次搜索后來(lái)，已知（2位于區(qū)間田中，且13,其中回是事先給定

精度，這時(shí)區(qū)間團(tuán)中點(diǎn)都可以作為13近似點(diǎn).

因而，當(dāng)前咱們關(guān)懷是：進(jìn)行n次搜索后，能把區(qū)間團(tuán)縮小到什么限度？或者說(shuō)，計(jì)算

n次函數(shù)值后來(lái)能把多長(zhǎng)區(qū)間縮小成K度為1區(qū)間？

用13表達(dá)計(jì)算n個(gè)函數(shù)值能縮短為單位區(qū)間最大原區(qū)間氏度，顯然有國(guó)

這是由于至少要計(jì)算兩次函數(shù)值才干縮短區(qū)間，只計(jì)算零次或一次函數(shù)值是不能縮短

區(qū)間長(zhǎng)度，故只有區(qū)間長(zhǎng)度自身等于1時(shí)才行。

現(xiàn)考慮計(jì)算函數(shù)值兩次情形：咱（把計(jì)算函數(shù)值點(diǎn)稱為試算點(diǎn)或試點(diǎn)。

在區(qū)間（3內(nèi)任取兩點(diǎn)13,計(jì)算函數(shù)值以縮短區(qū)間，縮短后區(qū)間為B或13,顯然，這兩個(gè)區(qū)間長(zhǎng)度

之和必不不大于ta區(qū)間長(zhǎng)度。也就是說(shuō)計(jì)算兩次函數(shù)值普通無(wú)法把長(zhǎng)度不不大于2區(qū)間縮

短成單位區(qū)間，但是對(duì)于長(zhǎng)度為2區(qū)詞，可以用如圖辦法選用試點(diǎn)瓦圖中13為任意小正數(shù),

縮短后區(qū)間長(zhǎng)度我1+田，故縮短后區(qū)間長(zhǎng)度近似等于1。由此得：

F?=2

依照同樣辦法，可行

握=3,居=5,片=8,片=13,???

序列（3遞推公式為:13

運(yùn)用公式可計(jì)算出（3值如下:

n012345678910II

1123581321345589144

這里人就是普通所說(shuō)裴波那鍥數(shù)。

由以上討論知，計(jì)算n次函數(shù)值所能獲得最大縮短率（縮短后長(zhǎng)度與原區(qū)間長(zhǎng)度比）為

(3。

如團(tuán)，即計(jì)算20個(gè)函數(shù)值可以把原區(qū)間長(zhǎng)度為L(zhǎng)區(qū)間縮短為B區(qū)間長(zhǎng)度。

當(dāng)前對(duì)于尋找近似極小點(diǎn)來(lái)說(shuō)，如果但愿誤差不超過(guò)區(qū)只需將原區(qū)間團(tuán)縮短為包括極小點(diǎn)向

區(qū)間長(zhǎng)度不竭過(guò)13區(qū)間就叮以了。這時(shí)計(jì)算函數(shù)值次數(shù)n只要滿足：

0即可。rr時(shí)給出區(qū)間縮短絕對(duì)精度。規(guī)定。

分?jǐn)?shù)法求近似極小點(diǎn)環(huán)節(jié)

(1)給出精度瓦求出使團(tuán)最小整數(shù)n,

由團(tuán)定出兩個(gè)試點(diǎn)0,出

(2)計(jì)算例與13:

若同取(3

并令0,13。

若團(tuán)，取團(tuán)，

并令3,團(tuán)。

(3)計(jì)算一比較它們大小。辦法同(2)o

(4)當(dāng)?shù)?<=91時(shí)，

Xn-l=Xn-\~(練-2+4-2)/2

這時(shí)無(wú)法比較函數(shù)值例與圓來(lái)擬定最后區(qū)間比為此取

Xn.\=(*+%)/2

*

X-I=4-2+(限2_*)*(1/2+￡)

其中回是一種很小正數(shù)，這樣就可以比較圖與例值以擬定最后區(qū)間團(tuán)，在田與6中其函數(shù)值較

小者為近似極小點(diǎn)，相應(yīng)函數(shù)值為近似極小值。

例：試用分?jǐn)?shù)發(fā)，求函數(shù)團(tuán)在區(qū)間13上近似極小點(diǎn)和近似極小值，并規(guī)定誤差不超過(guò)0.2。

解：不難驗(yàn)證,團(tuán)在區(qū)間團(tuán)上是僅有唯一收小點(diǎn)單峰函數(shù)，極小點(diǎn)為團(tuán)，極小值團(tuán)。下面運(yùn)用分?jǐn)?shù)

法求解。

已知GJ,故n=7,又知G,GJ

，取百=—2,b]-0.4762,

*2=4+3-可)4/8=-1.0476

*；=3=-0.4762

f(x2)=1.0499,f(^)=0.7504](*2)>fix?

取團(tuán)，這樣始終下去，最后可得：

由于瓦因而取團(tuán)取(3為近似極小點(diǎn)，近似極小值以

二、0.618法(黃金分割法)

由上節(jié)討論知，用分?jǐn)?shù)法以n個(gè)試點(diǎn)來(lái)縮短某一區(qū)間時(shí)，區(qū)間長(zhǎng)度第一次能短率為虱其

后各次分別為:便,圖，…，瓦現(xiàn)將以上數(shù)列分為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)，可以證明，這兩個(gè)數(shù)量收斂

于同一種極限：

7+V5=0.6180339887118948

2

以不變區(qū)間縮短率0.618代替分?jǐn)?shù)法每次不同縮短率，就得到黃金分割法(0.518法工它可

以當(dāng)作是分?jǐn)?shù)法近似，實(shí)現(xiàn)起來(lái)比較容易，效果也好。

詳細(xì)算法如下：

例：為了提高某種化工產(chǎn)品質(zhì)量指標(biāo)，需要在制作過(guò)程中加入某種原料，已知其最佳加入量

在1000克到克之間某?點(diǎn)，當(dāng)前通過(guò)實(shí)臉辦法找到該點(diǎn)。

按0.618法來(lái)獲取該點(diǎn)。

先做第一次實(shí)驗(yàn)，其加入量為:1000+0.382(-1000)=1382g：

再做第二次實(shí)驗(yàn)，加入成為：1000+0.618(—1000)=1618g：

(I)(2)

1OOO13822000

比較這兩次實(shí)險(xiǎn)成果。

如果第⑵點(diǎn)較第⑴點(diǎn)效果好，則去掉1000至1382這段，然后在留下一段中再找出第⑵點(diǎn)對(duì)

稱點(diǎn)，做第三次實(shí)驗(yàn)，其加入量為1382+0.618(—1382)=1764g,

再比較第一次與第三次實(shí)驗(yàn)成果。

<^>17C4

<!><2>?'

IOOO13H22000

如果依然是第⑵點(diǎn)較第(3)點(diǎn)效果好，則去掉1764至這一段，然后在留下一段中再找出

第⑷點(diǎn)對(duì)稱點(diǎn)，做第四次實(shí)驗(yàn)，其加入量為1382+0.618(1764-1382)=1528g：

O

<■><-?>

I4MM>."N，―門(mén)上2O??<?

如果依然是第⑷點(diǎn)較第⑵點(diǎn)效果好，則去掉1618至1764這一段，對(duì)留下1382至1618這一

段中繼續(xù)實(shí)驗(yàn)卜去就能找到最長(zhǎng)處，這樣可以用至少實(shí)驗(yàn)次數(shù)找到最佳加入量。

例：川黃金分割法求函數(shù)

山)=卜/2，%-2

[-x+3,x>2

在區(qū)間(3上極大點(diǎn)，規(guī)定縮短后長(zhǎng)度不不不大于原區(qū)間長(zhǎng)度15%。

解：已知⑸則

X、=0.382(3-0)=1.146,x\=0.618((3-0)=1.854,

F(S)=0.573,F(*；)=0.927

由于胤故原區(qū)間縮短匆3,令瓦瓦故原區(qū)間縮短為團(tuán)。

令此故原區(qū)間縮短為田，

令㈣(2,故原區(qū)間縮短為&

由于g,以達(dá)到精度規(guī)定，停止迭代，得近似極大點(diǎn)和極大值團(tuán)，此題精準(zhǔn)最優(yōu)解為巴

三、牛頓法（Newton）（切線法〉

上面咱們所討論辦法，只是對(duì)?某些點(diǎn)函數(shù)值大小進(jìn)行比較，而函數(shù)自身并沒(méi)有得到充分

運(yùn)用，至于函數(shù)某些解析性質(zhì)，更是宅無(wú)運(yùn)用，下面簡(jiǎn)介牛頓法當(dāng)函數(shù)性質(zhì)具備較好解析性

質(zhì)時(shí)，計(jì)算效果要比分?jǐn)?shù)法、0.618法更好。

當(dāng)前仍設(shè)13在［3上僅有一種極小點(diǎn)單峰函數(shù)，且具備二階導(dǎo)數(shù)。

咱們懂得，如果函數(shù)13在處取極小值，則必It助因而求此函數(shù)極小點(diǎn)，只需求山羽在團(tuán)內(nèi)零點(diǎn)

即可。

對(duì)團(tuán)在團(tuán)點(diǎn)展開(kāi)：

4'）=4J*4）1{xjxxj/2\o（xxj

取二次式（略去高階項(xiàng)）：

團(tuán)，用團(tuán)作為?近似。

一方面求制導(dǎo)數(shù)，并令其等于零。

/（*）=尸（乙）+尸（*/*一相）=0,

得a,?。?為新迭代點(diǎn)。

以上過(guò)程即Newton法。

特點(diǎn)：二階、局部收斂。（算法框怦見(jiàn)下頁(yè)）

、a"on法算法框圖

當(dāng)團(tuán)在團(tuán)上僅有三階導(dǎo)數(shù),團(tuán)，以及必，則切線法產(chǎn)生點(diǎn)列收斂到g在團(tuán)中唯一極小點(diǎn)。

當(dāng)團(tuán)是具備極小點(diǎn)二次函數(shù)時(shí)，牛頓法可以?步達(dá)到極小點(diǎn)。

當(dāng)13三階導(dǎo)數(shù)在團(tuán)內(nèi)不不大于零時(shí)，迭代初始點(diǎn)田應(yīng)在b端點(diǎn)附近，田三階導(dǎo)數(shù)在司內(nèi)不大于零時(shí),

迭代初始點(diǎn)13應(yīng)在a端點(diǎn)附近。

例：求minf(x}=tan-1tdt

解:0,0

迭代公式:0

取團(tuán)算成果：

Axk夕dJ?/r（xA）

110.7854

2

2-O.57GH-0.4187

1.3258

30.1169-0.1164

1.0137

4>0.001095-0.001Q9S

xs?x，=0

取(3計(jì)算成果如卜.:

A

1.1071

2-3.5357-1.2952

13.50

313.95不收斂?

例：用牛頓法求13在區(qū)間團(tuán)上極小點(diǎn)。

解：由于瓦由此可知，在團(tuán)上瓦而在團(tuán)上有唯一極小點(diǎn)跖

下面用牛頓法來(lái)求。

2(3初始點(diǎn)選在接近5一端，取初始點(diǎn)瓦并取精度13。

EL計(jì)算血胤計(jì)算電血

計(jì)算

0,0,停止迭代。

取x*=3.0001,f(**)=3.0000009?

四、拋物線法(插值法)：

1.插值法概念

假定咱們給定問(wèn)題是在某一擬定區(qū)間內(nèi)謀求函數(shù)極小點(diǎn)位置，但是沒(méi)有函數(shù)表達(dá)式，只有若

干實(shí)瞬點(diǎn)處困數(shù)值。咱們可以依照這些函數(shù)值，構(gòu)成一種與原目的函數(shù)相接近低次插值多項(xiàng)

式，用該多項(xiàng)式最優(yōu)解作為原函數(shù)最優(yōu)解近似解，這種辦法是用低次插值多項(xiàng)式逐漸遇近原

目的函數(shù)極小點(diǎn)近似求解辦法，稱為播值辦法或函數(shù)逼近法。

上面牛頓法需要計(jì)算臥-階導(dǎo)數(shù)、二階導(dǎo)數(shù)，“物很豆雜時(shí)，計(jì)算起來(lái)相稱困濰。拋物線法是

一種多項(xiàng)式逼近，即用一種二次多項(xiàng)式13來(lái)逼近所給函數(shù)瓦并用13極小點(diǎn)來(lái)近似13極小點(diǎn)，在

整個(gè)計(jì)算過(guò)程中，只需要計(jì)算(3值。其基本思想就是用二次三項(xiàng)式來(lái)逼近目的函數(shù)。

2.插值法與出探法區(qū)別

實(shí)驗(yàn)點(diǎn)位置擬定辦法不同。在試探法中實(shí)臉點(diǎn)位置是由某種給定規(guī)律擬定，并未考慮函數(shù)值

分布。例如：黃金分割法是按照等比例0.618縮短率擬定。而在插值法中，實(shí)驗(yàn)點(diǎn)位置是按

函數(shù)值近似分布極小點(diǎn)擬定。試探法僅僅運(yùn)用/實(shí)驗(yàn)點(diǎn)函數(shù)值進(jìn)行大小比較，而插值法還要

運(yùn)用函數(shù)值自身。因此，當(dāng)函數(shù)具備較好解析性質(zhì)時(shí)，插值辦法比試探辦法效果更好。

3.二次插值法概念

運(yùn)用原目的函數(shù)上三個(gè)插值點(diǎn)，構(gòu)成一種二次插值多項(xiàng)式，用該多項(xiàng)式最優(yōu)的作為原函數(shù)最

優(yōu)解近似解，逐漸逼近原目的函數(shù)極小點(diǎn)，稱為二次插值辦法或拋物線法。

4.二次插值函數(shù)構(gòu)成

設(shè)一維目的函數(shù)搜索區(qū)間為⑼取三點(diǎn)0,其中回取區(qū)間端點(diǎn)，即

a<—*1，/—6

而且為區(qū)間內(nèi)一種點(diǎn)，開(kāi)始可以取區(qū)間中點(diǎn)，即

=0.5（$

x2十公）

計(jì)算函數(shù)值/；=

過(guò)函數(shù)曲線上三點(diǎn)團(tuán)作二次插值多項(xiàng)式團(tuán)，滿足條件

夕（巧）=力*:+屈勺+J=f\

■尸（*2）=力?。?歐2+6=6

P,s）=力/2+/3+G=6

解方程組，得待定系數(shù)ABC分別為

（巧一+（*3-+（*1—巧）/

（a-&）（4-Vj）

x2）（x2-

（考-考）44-（Xj-4」+（xf-*；）/；

15=----------:-----------:-------------------------------

（X,-X.,）（x2-X3）（*3-*1）

（*3-X2）X2X3/J-（*]-*3）*1*34+（*2—尸1）*]*24

（*3-3）

（占-X2）（々-/）

于是函數(shù)國(guó)就是一種擬定二次多項(xiàng)式，稱二次插值函數(shù)，如圖所示，虛線某些即為二次插值

函數(shù)