非線性規(guī)劃的基本概念

1、第五講第五講 非線性規(guī)劃的基本概念非線性規(guī)劃的基本概念l 非非線性規(guī)劃問題線性規(guī)劃問題l 非非線性規(guī)劃數(shù)學模型線性規(guī)劃數(shù)學模型l 非線性規(guī)劃的圖解法非線性規(guī)劃的圖解法l 梯度、梯度、Hesse矩陣、矩陣、Jacobi陣陣l 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃l 解非線性規(guī)劃方法概述解非線性規(guī)劃方法概述l 一維最優(yōu)化一維最優(yōu)化 在科學管理和其他領域中，大量應用問題可以歸結為線性規(guī)在科學管理和其他領域中，大量應用問題可以歸結為線性規(guī)劃問題，但是，也有另外許多問題，其目標函數(shù)和（或）約束條劃問題，但是，也有另外許多問題，其目標函數(shù)和（或）約束條件很難用線性函數(shù)表達。如果目標函數(shù)和（或）約束條件中包含件很難

2、用線性函數(shù)表達。如果目標函數(shù)和（或）約束條件中包含有自變量的非線性函數(shù)，則這樣的規(guī)劃問題就屬于非線性規(guī)劃。有自變量的非線性函數(shù)，則這樣的規(guī)劃問題就屬于非線性規(guī)劃。 非線性規(guī)劃是運籌學的重要分支之一。最近非線性規(guī)劃是運籌學的重要分支之一。最近3030多年來發(fā)展很多年來發(fā)展很快，不斷提出各種算法，而其應用范圍也越來越廣泛。比如在各快，不斷提出各種算法，而其應用范圍也越來越廣泛。比如在各種預報、管理科學、最優(yōu)設計、質量控制、系統(tǒng)控制等領域得到種預報、管理科學、最優(yōu)設計、質量控制、系統(tǒng)控制等領域得到廣泛且不短深入的應用。廣泛且不短深入的應用。 一般來說，求解非線性規(guī)劃問題比線性規(guī)劃問題困難得多。一般來

3、說，求解非線性規(guī)劃問題比線性規(guī)劃問題困難得多。而且，也不象線性規(guī)劃那樣有單純形法這一通用的方法。非線性而且，也不象線性規(guī)劃那樣有單純形法這一通用的方法。非線性規(guī)劃的各種算法大都有自己特定的使用范圍，都有一定的局限性。規(guī)劃的各種算法大都有自己特定的使用范圍，都有一定的局限性。到目前為止還沒有到目前為止還沒有適合于各種問題的一般算法適合于各種問題的一般算法，這是需要深入研，這是需要深入研究的一個領域。我們只是對一些模型及應用作簡單介紹。究的一個領域。我們只是對一些模型及應用作簡單介紹。1 1非線性規(guī)劃問題舉例非線性規(guī)劃問題舉例例一：選例一：選址問題址問題設有設有 個市場，第個市場，第 個市場位置為

4、個市場位置為 ，它對某種貨物的需要，它對某種貨物的需要量為量為 ?，F(xiàn)計劃建立。現(xiàn)計劃建立 個倉庫，第個倉庫，第 個倉庫的存儲個倉庫的存儲容量為容量為 試確定倉庫的位置，使各倉庫對各市場的試確定倉庫的位置，使各倉庫對各市場的運輸量與路程乘積之和為最小。運輸量與路程乘積之和為最小。設第設第 個倉庫的位置為個倉庫的位置為 第第 個倉庫到第個倉庫到第 個市場的貨物供應量為個市場的貨物供應量為 則第則第 個個倉庫到第倉庫到第 個市場的距離為個市場的距離為jn),(jjqp), 2 , 1(njbj mi)., 2 , 1(miai i, 2 , 1),(miyxii ij)., 2 , 1, 2 , 1

5、(njmizij ij,)()(22jijiijqypxd ,)()(min221111jijiminjijijminjijqypxzdz 目標函數(shù)為目標函數(shù)為約束條件為約束條件為 （1 1）每個倉庫向各市場提供的貨物量之和不能超過它的）每個倉庫向各市場提供的貨物量之和不能超過它的存儲容量。存儲容量。miazinjij, 2 , 1,1 njbzjmiij, 2 , 1,1 （2）每個市場從各倉庫得到的貨物量之和應等于它的）每個市場從各倉庫得到的貨物量之和應等于它的需要量。需要量。（3）運輸量不能為負數(shù)）運輸量不能為負數(shù)njmizij, 2 , 1, 2 , 1, 0 例例2. 木木梁設計問題

6、梁設計問題 把圓形木材加工成矩形橫截面的木梁，要求木梁高度把圓形木材加工成矩形橫截面的木梁，要求木梁高度不超過不超過 ，橫截面的慣性矩（高度的平方，橫截面的慣性矩（高度的平方 寬度）不小寬度）不小于于 ，而且高度介于寬度與，而且高度介于寬度與4倍寬度之間。問如何確定木倍寬度之間。問如何確定木梁尺寸可使木梁成本最小梁尺寸可使木梁成本最小.H W2x1x設矩形橫截面的高度為設矩形橫截面的高度為 ， 寬度寬度為為 ，則圓形木材的半徑，則圓形木材的半徑1x2x222122 xxr,44min22212 xxrs 目標函數(shù)為目標函數(shù)為約束條件為約束條件為 )( . 0,4 4( W)( )(212121

7、2211高度與寬度非負高度與寬度非負倍寬度之間）倍寬度之間）高度介于寬度與高度介于寬度與慣性矩不小于慣性矩不小于高度不小于高度不小于 xxxxxxWxxHHx（1）數(shù)學規(guī)劃模型的一般形式：）數(shù)學規(guī)劃模型的一般形式：其中其中, 簡記為簡記為MP(Mathematical Programming) 2 2 非線性規(guī)劃問題的數(shù)學模型非線性規(guī)劃問題的數(shù)學模型 qjxhpixgxfii, 1 , 0)( , 1 , 0)( s.t.)( min的實值函數(shù)，的實值函數(shù)，為為xxhxgxfxxxxjiTn)(),(),(,),(21 （2）簡記形式：）簡記形式：Tpxgxgxg)(,),()(1 Tqxhx

8、hxh)(,),()(1 引入引入向量函數(shù)向量函數(shù)符號：符號： qjxhpixgtsxfii, 1 , 0)( , 1 , 0)( .)( min 0)( 0)( .)( minxhxgtsxfXxxf )(min qjxhpixgRxXiin, 1, 0)(, 1, 0)(（3）數(shù)學規(guī)劃問題的分類：）數(shù)學規(guī)劃問題的分類： 0)( 0)( s.t.)( minxhxgxf若若 為線性函數(shù)，即為為線性函數(shù)，即為線性規(guī)劃線性規(guī)劃(LP)；若若 至少一個為非線性至少一個為非線性, 即為即為非線性規(guī)劃非線性規(guī)劃(NLP)；對于非線性規(guī)劃，對于非線性規(guī)劃，若沒有若沒有 ,即即X=Rn,稱為稱為 無約束非

9、線性規(guī)劃無約束非線性規(guī)劃或或無約束最優(yōu)化問題無約束最優(yōu)化問題；否則稱為否則稱為約束非線性規(guī)劃或約束最優(yōu)化問題約束非線性規(guī)劃或約束最優(yōu)化問題。)(),(),(xhxgxfji)(),(),(xhxgxfji)(),(xhxgji（4）可行域和可行解：）可行域和可行解： qjxhpixgRxXiin, 1, 0)(, 1, 0)(稱稱為為MP問題的問題的約束集約束集或或可行域可行域。若若x在在X內(nèi)，稱內(nèi)，稱x為為MP的的可行解可行解或者或者可行點可行點。 qjxhpixgtsxfii, 1 , 0)( , 1 , 0)( .)( min（5）最優(yōu)解和極小點）最優(yōu)解和極小點對于非線性規(guī)劃（對于非線性

10、規(guī)劃（MP），），若若 ，并且有，并且有Xx *Xxxfxf ),()(*極極小小值值。）的的整整體體最最優(yōu)優(yōu)值值或或整整體體是是（稱稱MP)(*xf如果有如果有*, ),()(xxXxxfxf 嚴嚴格格整整體體極極小小點點，）的的嚴嚴格格整整體體最最優(yōu)優(yōu)解解或或是是（稱稱MP*x嚴嚴格格整整體體極極小小值值。）的的嚴嚴格格整整體體最最優(yōu)優(yōu)值值或或是是（稱稱MP)(*xf定義定義:極極小小點點，）的的整整體體最最優(yōu)優(yōu)解解或或整整體體是是（則則稱稱MP*x 使使的的鄰鄰域域并并且且存存在在若若）對對于于非非線線性性規(guī)規(guī)劃劃（ )( ,MP* xxRxxNxXxnXxNxxfxf)()()(* ，

11、極極小小值值）的的局局部部最最優(yōu)優(yōu)值值或或局局部部是是（稱稱MP)(*xf如果有如果有* ,)()()(xxXxNxxfxf ，定義定義嚴嚴格格局局部部極極小小點點）的的嚴嚴格格局局部部最最優(yōu)優(yōu)解解或或是是（稱稱MP*x嚴嚴格格局局部部極極小小值值。）的的嚴嚴格格局局部部最最優(yōu)優(yōu)值值或或是是（MP)(*xf則稱則稱 x* 是是(MP)的的局部最優(yōu)解或或局部極小解, 例1： 用圖解法求解 min f(x)=(x12)2 +(x22)2 s.t. h(x)= x1 + x2 - 6 = 0 x1x20662233最優(yōu)解 x* = ( 3，3 )T可行解 x = ( 1.5，4.5 )T最優(yōu)級解即為

12、最小圓的半徑：最優(yōu)級解即為最小圓的半徑：f(x)=(x12)2 +(x22)2 = 23 非線性規(guī)劃問題的圖解法 對二維最優(yōu)化問題，總可以用圖解法求解，而對三維或高維問題，對二維最優(yōu)化問題，總可以用圖解法求解，而對三維或高維問題，已不便在平面上作圖，此法失效。已不便在平面上作圖，此法失效。x1x206622D可行域最優(yōu)解最優(yōu)解 x x* * = = ( 2( 2，2 )2 )T T 例2： 用圖解法求解 min f(x)=(x1 - 2)2 +(x2 - 2)2 s.t. h(x)= x1 + x2 - 6 03 3 非線性規(guī)劃問題的圖解法非線性規(guī)劃問題的圖解法最優(yōu)級解即為最小圓的半徑：最優(yōu)級

13、解即為最小圓的半徑：f f( (x x)=()=(x x1 1 - 2) - 2)2 2 +( +(x x2 2 - 2) - 2)2 2 = 0 = 0 解：先畫出等式約束曲線 的圖形拋物線， 0,0505.12)(min212122212221xxxxxxxtsxxxf052221 xxxx1x2123456135 例3：用圖解法求解 再畫出不等式約束區(qū)域， 最后畫出目標函數(shù)等值線， 所以 最優(yōu)解最優(yōu)解 x*=(4,1), 最優(yōu)值最優(yōu)值 min f(x)=4.4 梯度、Hesse矩陣、Jacobi陣一般形式:矩陣形式:二次型:矩陣A的正定性: 正定、半正定、負定、不定。其中AAT。二次型的

14、正定性: 正定、半正定、負定、不定。 cxbxxgxxxfiniininjjiijn 1112121, cxbAxxxfTT 21 AxxxfT21 定義：f(x) 是定義在是定義在En上的可微函數(shù)。上的可微函數(shù)。f(x) 的的n個偏導數(shù)個偏導數(shù)為分量的向量稱為為分量的向量稱為f(x) 的的梯度梯度. Tnxxfxxfxxfxf ,)(21 性質：設f(x) 在定義域內(nèi)有連續(xù)偏導數(shù)，即有連續(xù)梯度，則梯度有以下兩個重要性質： 性質一 函數(shù)在某點的梯度不為零，則該梯度方向必與過該點的等值面垂直; 性質二 梯度方向是函數(shù)具有最大變化率的方向（負梯度方向也叫最速下降方向）。解： 由于,46211xxx

15、f 102121 xxxfxfxfP例：試求目標函數(shù) 在點 x =0,1T 處的最速下降方向，并求沿這個方向移動一個單位長度后新點的目標函數(shù)值。 2221212143,xxxxxxf 則函數(shù)在 x =0,1T 處的最速下降方向是21224xxxf 24244610212121xxxxxx這個方向上的單位向量是： 551552242422xfxfe解： 由于例：試求目標函數(shù) 在點x =0,1T 處的最速下降方向，并求沿這個方向移動一個單位長度后新點的目標函數(shù)值。 2221212143,xxxxxxf 新點是： 551552242422xfxfe 5511552551552101exx 52526

16、|4312221211 xxxxxxf函數(shù)值： 幾個常用的梯度公式幾個常用的梯度公式： AxxfAxxxfAxxfxxxfbxfxbxfCxfCxfTTT2 .0 . 0,.1 則則對對稱稱矩矩陣陣。則則則則即即則則常常數(shù)數(shù) 22221222222212121222122nxxfnxxxfnxxxfxnxxfxxfxxxfxnxxfxxxfxxfxfxf多元函數(shù) f(x) 關于x的二階導數(shù)，稱為 f(x)的Hesse矩陣.當f(x)的所有二階偏導數(shù)連續(xù)時,即 ijjixxxfxxxf 22Hesse矩陣是對稱的.時，時， ; 0)(,)(2 xfbxfxbxfT );()(,)(

17、212單位陣單位陣IxfxxfxxxfT .)(,)(,212AxfAxxfAAxxxfT 對對稱稱幾個常用Hessian公式： 向量變量值函數(shù)： nmmmnnxxgxxgxxgxxgxxgxxgxxgxxgxxgxg0201002202102012011010向量值函數(shù)g(x)在點 x0處的Jacobi矩陣Tnxgxgxgxg)(,),(),()(21 向量變量值函數(shù)的導數(shù)：Tnxxxx),(21 (1)凸函數(shù)：凸函數(shù)：）有）有，（若對若對是非空凸集，是非空凸集，設設10,:1 RSfRSn定義定義上上是是凸凸的的。在在上上的的凸凸函函數(shù)數(shù)，或或是是則則稱稱SSff上上是是嚴嚴格格凸凸的的。

18、在在上上的的嚴嚴格格凸凸函函數(shù)數(shù)，或或是是則則稱稱SSff凹凹的的。嚴嚴格格上上是是在在或或凹凹函函數(shù)數(shù)嚴嚴格格上上的的是是凸凸函函數(shù)數(shù)，稱稱嚴嚴格格上上的的是是若若)(S,)(S)(Sfff 5 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃Sxxxfxfxxf 212121,),()1()()1( Sxxxfxfxxf 212121,),()1()()1( 若若即是凸的也是凹的。即是凸的也是凹的。其中其中例例1,)( RRxxxfnT 是凸函數(shù)是凸函數(shù)其中其中例例nRxxxf |)( 例：正定二次函數(shù)例：正定二次函數(shù),21)(cxbAxxxfTT 其中其中A是正定矩陣，是正定矩陣，f(x)是凸函數(shù)。是凸函數(shù)

19、。是非空凸集是非空凸集設設nRS 性質性質1:上的凸函數(shù)；上的凸函數(shù)；是是，則，則上的凸函數(shù)，上的凸函數(shù)，是是若若S0S)1(ff 上上的的凸凸函函數(shù)數(shù)。是是上上的的凸凸函函數(shù)數(shù)是是若若S,S,)2(2121ffff （2）凸函數(shù)的性質）凸函數(shù)的性質性質性質2:則集合則集合是凸函數(shù)是凸函數(shù)是非空凸集是非空凸集設設,1RcfRSn cxfSxcfHS )(|),(是凸集。是凸集。證明證明:略略.則則可可微微：是是非非空空開開凸凸集集，設設,S1RSfRn 上上的的凸凸函函數(shù)數(shù)是是）（S1fSxxxfxfxxxfT 2112121,),()()()(處處的的梯梯度度。是是函函數(shù)數(shù)在在點點）（其其中

20、中11111)(,)()(xxxfxxfxfTn 定理定理1：（一階條件）：（一階條件）上上的的嚴嚴格格凸凸函函數(shù)數(shù)是是）（S2f212112121, ),()()()(xxSxxxfxfxxxfT n=1時幾何意義：可微函數(shù)是凸的等價于切線不在函數(shù)圖像時幾何意義：可微函數(shù)是凸的等價于切線不在函數(shù)圖像上方。上方。 （3） 凸函數(shù)的判定凸函數(shù)的判定逆命題不成立）逆命題不成立）上的嚴格凸函數(shù)（此時上的嚴格凸函數(shù)（此時是是上是正定矩陣時上是正定矩陣時在在當當上是半正定的。上是半正定的。在在上的凸函數(shù)上的凸函數(shù)是是則則二階連續(xù)可導二階連續(xù)可導是非空開凸集是非空開凸集設設,)(S)( ,:,S221Sf

21、SxfxfSfRSfRn nnnnxxxfxxxfxxxfxxxfxfxf)(.)(.)(.)()(Hesse)(2121211222矩陣，矩陣，為為其中其中定理定理2：（二階條件）：（二階條件） , 1 0 , 1 0 . miniqjxh pixgtsxfj）（）（）（4）凸規(guī)劃的定義及其性質：）凸規(guī)劃的定義及其性質： , 1 0 , 1 0 qjxhpixgRxXjin）（）（簡簡稱稱凸凸規(guī)規(guī)劃劃。凸凸規(guī)規(guī)劃劃為為非非線線性性稱稱上上的的凸凸函函數(shù)數(shù)是是是是凸凸集集若若,MP,)(SfX凸規(guī)劃定義：凸規(guī)劃定義：定理定理是凸規(guī)劃。是凸規(guī)劃。上的凸函數(shù)，則上的凸函數(shù)，則是是并且并且皆為線性函

22、數(shù)，皆為線性函數(shù)，上的凸函數(shù)上的凸函數(shù)皆為皆為若若）（）（）（對于非線性規(guī)劃對于非線性規(guī)劃)( MP)(,)(g , 1 0 , 1 0 s.t. min,(MP) iXfxhRxqjxh pixgxfjnij 凸規(guī)劃性質凸規(guī)劃性質：定理定理凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。凸規(guī)劃是以后重點討論的一類非線性規(guī)劃凸規(guī)劃是以后重點討論的一類非線性規(guī)劃凸函數(shù)凸函數(shù)線性函數(shù)線性函數(shù)（1）微分學方法的局限性：）微分學方法的局限性：實際的問題中，函數(shù)可能是不連續(xù)或者不可微的。需要解復雜的方程組，而方程組到目前仍沒有有效的算法。實際的問題可能含有不等式約束，

23、微分學方法不易處理。6 6 非線性規(guī)劃方法概述非線性規(guī)劃方法概述（2）數(shù)值方法的基本思路：迭代給定初始點x0根據(jù)x0,依次迭代產(chǎn)生點列xkxk的最后一點為最優(yōu)解xk有限xk無限xk收斂于最優(yōu)解迭代格式迭代格式xkxk+1kx kkkxxx 1pkkkkptx kkkxxx 1稱稱pk為第為第k輪輪搜索方向搜索方向，tk為第為第k輪沿輪沿pk方向的方向的步長步長。產(chǎn)生產(chǎn)生tk和和pk的不同方法，形成了不同的算法。的不同方法，形成了不同的算法。，使，使若存在若存在設設0, 0,:1 pRpRxRRfnnn), 0( ),()( txftpxf處處的的下下降降方方向向。在在點點是是函函數(shù)數(shù)則則稱稱向

24、向量量xxfp)(處處下下降降最最快快的的方方向向。在在就就是是可可導導，則則在在若若xxfxfxxf)()(-)( 定義定義：特殊搜索方向：特殊搜索方向下降方向下降方向，使得，使得若存在若存在設設0t, 0, pRpXxRXnnXtpx 的的可可行行方方向向。關關于于處處是是點點則則稱稱向向量量Xxp定義：定義：特殊搜索方向特殊搜索方向下降方向下降方向解非線性規(guī)劃問題，關鍵在于解非線性規(guī)劃問題，關鍵在于找到某個方向，使得在此方向找到某個方向，使得在此方向上，目標函數(shù)得到下降，同時上，目標函數(shù)得到下降，同時還是可行方向。還是可行方向。這樣的方向稱為這樣的方向稱為可行下降方向?？尚邢陆捣较?。定義

25、：算法收斂、下降迭代算法定義：算法收斂、下降迭代算法集合集合S上的迭代算法：上的迭代算法：（1）初始點）初始點0 x；（2）按照某種搜索方向）按照某種搜索方向pk產(chǎn)生下一個迭代點產(chǎn)生下一個迭代點.1kkkkpxx （i）如果點列如果點列kx收斂于最優(yōu)解收斂于最優(yōu)解*x，則稱此，則稱此算法收斂算法收斂。（ii）如果如果 )()()(10kxfxfxf，則稱此算法為，則稱此算法為下降迭代算法下降迭代算法。.0 x.1x.2x（3）下降迭代算法步驟）下降迭代算法步驟（1）給出初始點）給出初始點0 x，令，令0 k；（2）按照某種規(guī)則確定下降搜索方向）按照某種規(guī)則確定下降搜索方向kd；（3）按照某種規(guī)

26、則確定搜索步長）按照某種規(guī)則確定搜索步長k ，使得，使得)()(kkkkxfdxf ；（4）令）令 kkkkdxx 1，1: kk；（5）判斷）判斷kx是否滿足是否滿足停止條件停止條件。是則停止，否則轉第。是則停止，否則轉第2步。步。搜索步長確定方法：搜索步長確定方法：)(min)(kkkkkdxfdxf 稱稱0)( kTkkkddxf k 為為最優(yōu)步長最優(yōu)步長，且有對，且有對 k的梯度的梯度（4） 終止條件終止條件)(31 kkkkxxxx )(41 kkkkxfxfxfxf11 kkxx21)()( kkxfxf（5）常用的收斂性判別準則）常用的收斂性判別準則:（）點收斂準則（）點收斂準則

27、: :( (可取可取Rn中任一種模中任一種模) )。 ) 1()(kkxx（）目標函數(shù)值準則：（）目標函數(shù)值準則：（絕對差）。（絕對差）。 )()() 1()(kkffxx（）目標函數(shù)值準則：（）目標函數(shù)值準則：（相對差）。（相對差）。 )()()()() 1()(kkkfffxxx取其中之一取其中之一,也可同時取也可同時取(1)與與(2);(1)與與(3);或或(1),(2)和和(3)等。等。（6）算法的收斂速度）算法的收斂速度則稱則稱 的收斂階為的收斂階為 。設算法所得的點列為設算法所得的點列為kx，如果，如果,|*1 xxxxkk.0, kx1.線性收斂（當線性收斂（當k充分大時）：充分

28、大時）： 2.超線性收斂：超線性收斂：3.二階收斂：二階收斂： （*）式中）式中 =2時成立。時成立。1|*)(*)1( xxxxkk0|lim*)(*)1( xxxxkkk 單變量單變量( (一維一維) )最優(yōu)化最優(yōu)化l 一維最優(yōu)化問題一維最優(yōu)化問題l 進退法進退法l 黃金分割法黃金分割法l 拋物線搜索法拋物線搜索法l 三次插值法三次插值法下降迭代算法下降迭代算法中最優(yōu)步長的確定中最優(yōu)步長的確定)(min)(kkkkkdxfdxf .kxkd.k 一維最優(yōu)化問題：一維最優(yōu)化問題：)(minxfRxts .解析的方法解析的方法（極值點的必要條件）極值點的必要條件）0)( xf一、一維最優(yōu)化問題

29、一、一維最優(yōu)化問題1. 單峰函數(shù)單峰函數(shù)定義定義：設：設)(xf是區(qū)間是區(qū)間,ba上的一元函數(shù)，上的一元函數(shù)，x是是)(xf在在,ba上的極小點，且對任意的上的極小點，且對任意的, ,2121xxbaxx 有有（a）當當xx 2時，時，; )()(21xfxf （b）當當時，時，xx 1. )()(21xfxf a.b.x.1x2x則稱則稱 是單峰函數(shù)。是單峰函數(shù)。)(xf.性質性質：通過計算區(qū)間：通過計算區(qū)間 a, b 內(nèi)兩個不同點的函數(shù)值，就可內(nèi)兩個不同點的函數(shù)值，就可以確定一個包含極小點的子區(qū)間。以確定一個包含極小點的子區(qū)間。定理定理 設設是區(qū)間是區(qū)間,ba上的一元函數(shù)，上的一元函數(shù)，x

30、是是)(xf在在,ba上的極小點。任取點上的極小點。任取點)(xf, ,badc 則有則有（1）如果）如果)()(dfcf ，則，則; ,bcx （2）如果）如果, )()(dfcf 則則。,dax a.b.x.cd2 搜索法求解：搜索法求解：)(min0 xx )(minmax0 xxx 或或基本過程：基本過程：給出給出a,b,使得使得x*在在a,b中。中。a,b稱為稱為搜索區(qū)間搜索區(qū)間。迭代縮短迭代縮短a,b的長度。的長度。當當a,b的長度小于某個預設的值，或者導數(shù)的絕的長度小于某個預設的值，或者導數(shù)的絕對值小于某個預設的正數(shù)，則迭代終止。對值小于某個預設的正數(shù)，則迭代終止。二進退法二進退

31、法思想思想從一點出發(fā)從一點出發(fā),按一定的步長按一定的步長, 試圖確定出函數(shù)值呈現(xiàn)試圖確定出函數(shù)值呈現(xiàn)“高高 - 低低 - 高高”的三點。一個方向不成功，就退回來，再沿相反方的三點。一個方向不成功，就退回來，再沿相反方向尋找。向尋找。進退法的計算步驟進退法的計算步驟,. 1)0(Rx 給給定定初初始始點點, 00 h初初始始步步長長,0hh 令令,)0()1(xx ),()1(xf計算計算. 0 k并令并令,. 2)1()4(hxx 令令),()4(xf計算計算. 1: kk令令),()(. 3)1()4(xfxf 若若，則轉則轉 45.否則，轉否則，轉,. 4)1()2(xx 令令,)4()1

32、(xx ),()()1()2(xfxf ),()()4()1(xfxf . 2,2:轉轉令令hh 如何確定包含極小點的一個區(qū)間？如何確定包含極小點的一個區(qū)間？, 1. 5 k若若；則轉則轉 6. 7否則，轉否則，轉,:. 6hh 令令,)4()2(xx ),()()4()2(xfxf . 2轉轉,. 7)2(3)xx 令令,)1()2(xx ,)4()1(xx 停停止止計計算算。例：例：)0(x)1(xhxx )1()4()2(x)1(x)4(x)3(x)2(x)1(x)0(x)1(x)4(xhh :)1(x)2(x)4(x)3(x)2(x)1(x。即即為為包包含含極極小小點點的的區(qū)區(qū)間間或或

33、區(qū)區(qū)間間,)1()3()3()1(xxxx,)1()3(xx：極小點區(qū)間極小點區(qū)間,)3()1(xx極小點區(qū)間：極小點區(qū)間：假定：已經(jīng)確定了單峰區(qū)間假定：已經(jīng)確定了單峰區(qū)間a,b)(min0 xx )(minmax0 xxx )(minxbxa )(1x)(2xx)(1t )(2t xx1x2ababx12新搜索區(qū)間為新搜索區(qū)間為a,x2新搜索區(qū)間為新搜索區(qū)間為x1,b三三. 黃金分割法（黃金分割法（0.618法）法）區(qū)間縮小比例的確定：區(qū)間縮小比例的確定：區(qū)間縮短比例為區(qū)間縮短比例為(x2-a)/(b-a)縮短比例為縮短比例為(b-x1)/(b-a)縮短比例縮短比例 滿足：滿足：每次插入搜索

34、點使得兩個區(qū)間每次插入搜索點使得兩個區(qū)間a,x2和和x1,b相等；相等；每次迭代都以相等的比例縮小區(qū)間。每次迭代都以相等的比例縮小區(qū)間。618. 0215 縮短比例縮短比例0.618法法)(1x)(2x)(1x)(2xx1x2ababx1x2黃金分割法的計算公式的推導：黃金分割法的計算公式的推導：上單峰，上單峰，在在設設,)(11baxf.,11bax 極小點極小點假設進行假設進行次迭代前次迭代前第第 k,kkbax ,kkkkba 取取規(guī)定規(guī)定.kk , )()(kkff 和和計計算算分兩種情況：分兩種情況：, )()(. 1kkff 若若,1kka 則令則令;1kkbb , )()(. 2

35、kkff 若若,1kkaa 則令則令.1kkb ？與與如何確定如何確定kk kkkkab . 1比率相同，即比率相同，即每次迭代區(qū)間長度縮短每次迭代區(qū)間長度縮短. 2)0()(11 kkkkabab)1()2(）可得：）可得：）與（）與（由式（由式（21 )()(1(kkkkkkkkabaaba )3()4(件：件：要求其滿足以下兩個條要求其滿足以下兩個條kakbk ku？取值的確定取值的確定 通過確定通過確定 的取值，使上一次迭代剩余的迭代點恰與下一次的取值，使上一次迭代剩余的迭代點恰與下一次迭代的一個迭代點重合，從而減少算法的計算量。迭代的一個迭代點重合，從而減少算法的計算量。 , )()

36、()1(kkuffk 次迭代時有次迭代時有設在第設在第則有則有。,11kkkkuaba ,111k kuk 次迭代時選取次迭代時選取在第在第）有）有則由（則由（4)(1111 kkkkabau )(2kkkaba 。不必重新計算不必重新計算因此因此則則，如果令如果令112,1 kkkuu 618. 021512 。次迭代時有次迭代時有若在第若在第)()()2(kkuffk 同理可得。同理可得。3. 0.618法的算法步驟：法的算法步驟：0.,. 111 精度要求精度要求給定初始區(qū)間給定初始區(qū)間ba. 1: k令令),(382. 01111aba 令令),(618. 01111aba ).()(

37、11 ff與與并計算并計算,. 2 kkab若若停止，停止，.2kkabx 且且否則，否則，；時，轉時，轉當當3)()(kkff . 4)()(時，轉時，轉當當kkff ,. 31kka 令令,1kkbb ,1kk ),(618. 01111 kkkkaba ),(1 kf 計算計算。轉轉 2,. 41kkaa 令令,1kkb ,1kk ),(382. 01111 kkkkaba ),(1 kf 計算計算, 1: kk令令。轉轉 2, 1: kk令令確定確定a,b,計算探索點計算探索點x1=a+0.382(b-a)x2=a+0.618(b-a)()(21xx是是否否ax2是是停止，輸出停止，輸

38、出x1否否以以a,x2為新的搜索區(qū)間為新的搜索區(qū)間1xb是是停止，輸出停止，輸出x2否否以以x1,b為新的搜索區(qū)間為新的搜索區(qū)間3. 0.618法的算法框圖：法的算法框圖：黃金分割法的迭代效果：黃金分割法的迭代效果：第第 k 次后迭代后所得區(qū)間長度為初始區(qū)間長度的次后迭代后所得區(qū)間長度為初始區(qū)間長度的。倍倍k)215( 其它的試探點算法：其它的試探點算法：Fibonacci算法。算法。例例：5 . 0,3 , 0 12)(min 30精度精度其中單谷區(qū)間其中單谷區(qū)間求解求解 tttt 解：解：t1t2)(1t )(2t 30t 1、第一輪：、第一輪：t1=1.146, t2=1.8546648

39、. 3)(,2131. 0)(21 tt t200.52、第二輪：、第二輪：t2=1.146, t1=0.7082131. 0)(0611. 0)(21 tt t20=1.1460.53、第三輪：、第三輪：t1=0.438, t2=0.7082082. 0)(0611. 0)(12 tt b -t1=1.146-0.4380.51.8540t t2t11.1460 tt2t14、第四輪：、第四輪：t2=0.876=(1.146-0.438), t1=0.7080798. 0)(0611. 0)(21 tt b-t1=1.146-0.7080，求目標函數(shù)值的計算次，求目標函數(shù)值的計算次數(shù)數(shù) n，

40、使，使置辨別常數(shù)置辨別常數(shù)0。計算試探點。計算試探點 計算函數(shù)值和計算函數(shù)值和 。置。置k =1。（2） 若若 ，則轉（，則轉（3）；）； 若若 ，則轉（，則轉（4）。）。,11ba / )(11abFn 11 和和 ,1111111211abFFaabFFannnn )()(11 ff和和)()(k ffk )()(k ffk （3） （5） 置置k= k+1，轉（，轉（2）。）。)5(),( ,(6);, 2(2.7) )b(,11111,111轉轉計算函數(shù)值計算函數(shù)值否則否則則轉則轉若若計算試探點：計算試探點：令令 kkkkkkkkkkkfnkaabba )5(),( ,(6);, 2(

41、2.8) )b( ,111111,111轉轉計算函數(shù)值計算函數(shù)值否則否則則轉則轉若若：計算計算令令 kkkkkkkkkkkkfnkaabaa （4） b, b, .b,),()( ;b,),()( )()(,1111。的的長長度度不不超超過過且且，停停止止計計算算，極極小小點點含含于于則則令令若若則則令令若若，和和計計算算函函數(shù)數(shù)值值令令 nnnnnnnnnnnnnnnnnnnnnnaaaaffbaffff （6） 思想思想在極小點附近，用二次三項式在極小點附近，用二次三項式),()(xfx 逼近目標函數(shù)逼近目標函數(shù) 處有相同的函數(shù)值，處有相同的函數(shù)值，在三點在三點與與令令)3()2()1()

42、()(xxxxfx 并并假假設設).()(),()()3()2()2()1(xfxfxfxf )1(x)2(x)3(x)(xf)(x x*x四四. 拋物線（二次）插值拋物線（二次）插值即即“兩頭大中間小兩頭大中間小”,)(2cxbxax 設設)()()1(2)1()1()1(xfcxbxax )()()2(2)2()2()2(xfcxbxax )()()3(2)3()3()3(xfcxbxax .)(cbx和和的系數(shù)的系數(shù)近函數(shù)近函數(shù)解上述方程組，可得逼解上述方程組，可得逼 的極小點，的極小點，再求函數(shù)再求函數(shù))(x 令令cxbx2)( , 0 解得解得cbx2 如何計算函數(shù)如何計算函數(shù)?)(

43、x 。的極小點的估計值的極小點的估計值作為作為以以)(xfx )()()()()()(2)()()()()()()3()2()1()2()1()3()1()3()2()3()2()1()2()1()3()1()3()2(222222xfxxxfxxxfxxxfxxxfxxxfxx 令令x=33221123322221111111121fxfxfxxfxfxf 拋物線插值算法步驟：拋物線插值算法步驟：, ,)1()3()1(xx給定初始區(qū)間給定初始區(qū)間).()(),()()3()2()2()1(xfxfxfxf 設設。給定精度給定精度。令令 )1()0(1:xxk 。令令。設設3,2,1, )(

44、)()()2()()(2 ixfxcxbxaxii 解出解出。的極小點的極小點解出解出。系數(shù)系數(shù)cbxxcbak2)(,)( 及其及其的函數(shù)值最小的三個點的函數(shù)值最小的三個點中選擇中選擇和和從從)(,)3()()3()2()1(xfxxxxk。）轉（轉（。令令。重新標記為重新標記為左、右兩點，左、右兩點，21:,)3()2()1( kkxxx）。）。否則轉（否則轉（，則算法停止則算法停止若若3,| )()(|)1()( kkxfxf思路：思路：,0)()()()1()2()1()2()1( xfxxxxxf且有且有，的函數(shù)值的函數(shù)值、在點在點已知已知利用這兩點的函數(shù)值利用這兩點的函數(shù)值的極小點

45、。的極小點。內(nèi)存在內(nèi)存在（則區(qū)間則區(qū)間)(),.0)()2()1()2(xfxxxf 在在這這兩兩點點有有相相同同的的函函使使它它與與項項式式和和導導數(shù)數(shù)構構造造一一個個三三次次多多)(, )(xfx 的極小點。的極小點。的極小點近似的極小點近似并用并用逼近逼近用用數(shù)值和導數(shù)，數(shù)值和導數(shù)，)()(, )()(xfxxfx )1(x)2(x)(xf)(x *xx五五. 三次插值法三次插值法設設)1()()()()()1(2)1(3)1(dxxcxxbxxax 令令 )()()()()()()()()2()2()1()1()2()2()1()1(xfxxfxxfxxfx 則有則有 )()(2)(3

46、)()()()()()()2()1()2(2)1()2()1()2()1()2(2)1()2(3)1()2()1(xfcxxbxxaxfcxfdxxcxxbxxaxfd)2(。從而確定函數(shù)從而確定函數(shù)，的值的值求解方程組得出系數(shù)求解方程組得出系數(shù))(,xdcba 的方法：的方法：確定函數(shù)確定函數(shù))(x 求解滿足求解滿足 0)(0)(xx 的極小點的極小點 令令0)(2)(3)()1(2)1( cxxbxxax )3(。bxxax2)(6)()1( 而而解方程（解方程（3），有兩種情況：），有兩種情況：解得解得時，時，當當0. 1 a)4(2)1(bcxx 由（由（2）可知）可知。)1()2()

47、2()1(, 0)(,0)(xxxfxfc 。所以所以0 b的極小點。的極小點。是是即即因此因此)(,02)(xxbx 。x解得解得時，時，當當0. 2 aaacbbxx332)1( )5(acbbaacbbax322336)(22 此時有此時有式中應取式中應取則在則在為使為使)5(,0)( x aacbbxx332)1( acbbc32 )6(式可知式可知由由時，時，而當而當)6(0 a式式所所以以，)6(2)1(bcxx 一表達式。一表達式。兩種情況下極小點的統(tǒng)兩種情況下極小點的統(tǒng)、是是21極小點的計算公式：極小點的計算公式：令令)7()()( 3)1()2()1()2(xxxfxfs )

48、8()()()2()1(xfxfst )9()()()2()1(22xfxftw )10()2)()()(1)()1()2()2()1()2()1(wxfxfwtxfxxxx 則有則有算法步驟：算法步驟：要求要求計算計算給定初始點給定初始點, )(, )(, )(, )(,. 1)2()1()2()1()2()1(xfxfxfxfxx 。滿足條件：滿足條件：0)(,0)(,)2()1()1()2( xfxfxx。給定允許誤差給定允許誤差0,0 。和和、計算計算、按照公式按照公式xwts)10()9()8()7(. 2。否則，轉否則，轉；則停止計算，得到點則停止計算，得到點，若若4|. 3)1()2(xxx 。停止計算，得到點停止計算，得到點，若若。計算計算xxfxfxf | )(|)(, )(. 4。轉轉。則令則令，若若2)()(, )()(,0)()1()1()1(xfxfxf