運(yùn)籌學(xué)第4章非線性規(guī)劃

1、第第1頁頁運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外第第4 4章章 非線性規(guī)劃非線性規(guī)劃Non-linear ProgrammingNon-linear Programming第第2頁頁v4.1 4.1 基本概念基本概念v4.2 4.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃v4.3 4.3 一維搜索方法一維搜索方法v4.4 4.4 無約束最優(yōu)化方法無約束最優(yōu)化方法v4.5 4.5 約束最優(yōu)化方法約束最優(yōu)化方法第第4章章 非線性規(guī)劃非線性規(guī)劃第第3頁頁1. 非非線線性性規(guī)規(guī)劃劃問問題題例例4.1.1 曲線的最優(yōu)擬合問題曲線的最優(yōu)擬合問題已知某物體的溫度已知某物體的溫度 與時間與

2、時間 t 之間有如之間有如 下形式的經(jīng)驗函數(shù)關(guān)系：下形式的經(jīng)驗函數(shù)關(guān)系： tcetcc321 (*) 其中其中1c，2c，3c是待定參數(shù)。是待定參數(shù)?，F(xiàn)通過測現(xiàn)通過測 試獲得試獲得 n 組組 與與 t 之間的實驗數(shù)據(jù)之間的實驗數(shù)據(jù)),(iit ， i=1，2，,n。試確定參數(shù)試確定參數(shù)1c，2c，3c， 使理論曲線使理論曲線(*)盡可能地與盡可能地與 n 個測試點(diǎn)個測試點(diǎn) ),(iit 擬合。擬合。 t n1i221)( min3 itciietcc 4.1 基本概念基本概念第第4頁頁例例2 構(gòu)件容積問題構(gòu)件容積問題設(shè)計一個右圖所示的由圓錐和圓柱面 圍成的構(gòu)件，要求構(gòu)件的表面積為S， 圓錐部分

3、的高h(yuǎn)和圓柱部分的高x2之 比為a。確定構(gòu)件尺寸，使其容積最 大。 x1x2x3 0, 0 2 . .) 3/1 ( max212121222211221xxSxxxxaxxtsxxaV 4.1 基本概念基本概念1. 非非線線性性規(guī)規(guī)劃劃問問題題第第5頁頁數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃設(shè)設(shè)nTnRxxx ),.,(1，RRqjxhpixgxfnji:,.,1),(;,.,1),();( , 如如下下的的數(shù)數(shù)學(xué)學(xué)模模型型稱稱為為數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃(Mathematical Programming, MP)： qjxhpixgtsxfji,.,1, 0)( ,.,1, 0)( .)( min qjxhpixgRx

4、Xjin,.,1, 0)(,.,1, 0)(約束集或可行域約束集或可行域MP中目標(biāo)函數(shù)和約束函數(shù)中至少有一個不是中目標(biāo)函數(shù)和約束函數(shù)中至少有一個不是x的的線性函數(shù)，稱線性函數(shù)，稱(MP)為非線性規(guī)劃為非線性規(guī)劃4.1 基本概念基本概念Xx MP的可行解或可行點(diǎn)的可行解或可行點(diǎn)第第6頁頁向向量量化化表表示示當(dāng)當(dāng)p=0,q=0時，稱為時，稱為無約束非線性規(guī)劃無約束非線性規(guī)劃或者或者無約無約束最優(yōu)化問題束最優(yōu)化問題。否則，稱為否則，稱為約束非線性規(guī)劃約束非線性規(guī)劃或者或者約束最優(yōu)化問約束最優(yōu)化問題題。4.1 基本概念基本概念第第7頁頁最最優(yōu)優(yōu)解解和和極極小小點(diǎn)點(diǎn)定定義義4.1.1 對對于于非非線線性

5、性規(guī)規(guī)劃劃(MP)，若若Xx *，并并且且有有 X ),()(* xxfxf 則則稱稱*x是是(MP)的的整整體體最最優(yōu)優(yōu)解解或或整整體體極極小小點(diǎn)點(diǎn)，稱稱)(*xf是是 (MP)的的整整體體最最優(yōu)優(yōu)值值或或整整體體極極小小值值。如如果果有有 * ),()(xxX,xxfxf 則則稱稱*x是是(MP)的的嚴(yán)嚴(yán)格格整整體體最最優(yōu)優(yōu)解解或或嚴(yán)嚴(yán)格格整整體體極極小小點(diǎn)點(diǎn)，稱稱 )(*xf是是(MP)的的嚴(yán)嚴(yán)格格整整體體最最優(yōu)優(yōu)值值或或嚴(yán)嚴(yán)格格整整體體極極小小值值。 4.1 基本概念基本概念第第8頁頁最最優(yōu)優(yōu)解解和和極極小小點(diǎn)點(diǎn)定定義義 4.1.2 對對于于非非線線性性規(guī)規(guī)劃劃(MP)，若若Xx *，

6、并并且且存存在在*x的的一一個個 領(lǐng)領(lǐng)域域 ), 0( )(*RxxRxxNn ，使使 XxNxxfxf)( ),()(* ， 則則稱稱*x是是(MP)的的局局部部最最優(yōu)優(yōu)解解或或局局部部極極小小點(diǎn)點(diǎn)，稱稱)(*xf是是(MP)的的局局部部 最最優(yōu)優(yōu)值值或或局局部部極極小小點(diǎn)點(diǎn)。如如果果有有 * ,)( ),()(xxXxNxxfxf ， 則則稱稱*x是是(MP)的的嚴(yán)嚴(yán)格格局局部部最最優(yōu)優(yōu)解解或或嚴(yán)嚴(yán)格格局局部部極極小小點(diǎn)點(diǎn)，稱稱)(*xf是是(MP) 的的嚴(yán)嚴(yán)格格局局部部最最優(yōu)優(yōu)值值或或嚴(yán)嚴(yán)格格局局部部極極小小點(diǎn)點(diǎn)。 4.1 基本概念基本概念第第9頁頁求解。似于線性規(guī)劃的圖解法單的非線性規(guī)

7、劃可用類和約束條件較簡數(shù)對于二維空間中目標(biāo)函)(xf例：例：2221)2()2()(minxxxf06)(. .21xxxhts*2*13xx2, 0)(0)(*2*1xxxhxh則換為如非線性規(guī)劃的圖解法2)(xf1x2x4)(xf226363cDAB第第10頁頁2. 非線性規(guī)劃方法概述：非線性規(guī)劃方法概述：4.1 基本概念基本概念第第11頁頁線搜索框架下的迭代算法第第12頁頁基基本本迭迭代代格格式式4.1 基本概念基本概念第第 1步步 選取初始點(diǎn)選取初始點(diǎn)0 x，k:=0; 第第 2步步 構(gòu)造搜索方向構(gòu)造搜索方向kp； 第第 3步步 根據(jù)根據(jù)kp，確定步長，確定步長kt； 第第 4步步 令

8、令kkkkptxx 1， 若若1 kx已滿足某種終止條件，停止迭代，輸出已滿足某種終止條件，停止迭代，輸出 近似解近似解1 kx；否則令；否則令k:=k+1，轉(zhuǎn)回第，轉(zhuǎn)回第2步。步。 第第13頁頁4.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃1. 凸函數(shù)的定義凸函數(shù)的定義定義定義 4.2.1 設(shè)設(shè)nRS 是非空凸集，是非空凸集，RSf:，如果對任意的，如果對任意的)1 , 0( 有有 )()1()()1(2121xfxfxxf ，Sxx 21, 則稱則稱 f 是是 S 上的上的凸函數(shù)凸函數(shù)，或，或 f 在在 S 上是上是凸凸的。的。如果對于任意的如果對于任意的)1 , 0( 有有 )()1()()1(2

9、121xfxfxxf ，21xx 則稱則稱 f 是是 S 上的上的嚴(yán)格凸函數(shù)嚴(yán)格凸函數(shù)，或或 f 在在 S 上是上是嚴(yán)格凸嚴(yán)格凸的。的。 若若-f是是S上上的的（嚴(yán)嚴(yán)格格）凸凸函函數(shù)數(shù)，則則稱稱f是是S上上的的（嚴(yán)嚴(yán)格格）凹凹函函數(shù)數(shù)， 或或f在在S上上是是（嚴(yán)嚴(yán)格格）凹凹的的。 第第14頁頁(a) 凸函數(shù)凸函數(shù) (b)凹函數(shù)凹函數(shù)4.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃第第15頁頁定定理理 4.2.2 設(shè)設(shè)nRS 是是非非空空凸凸集集，RRfn:是是凸凸函函數(shù)數(shù)，Rc ，則則集集合合 cxfSxcfHS )(),( 是是凸凸集集。 4.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃2. 凸函數(shù)的一些基本性質(zhì)凸

10、函數(shù)的一些基本性質(zhì)注：一般來說上述定理的逆是不成立的。注：一般來說上述定理的逆是不成立的。第第16頁頁定定理理 4.2.3 設(shè)設(shè)nRS 是是非非空空開開凸凸集集，RSf:可可微微，則則 （1） f 是是 S 上上的的凸凸函函數(shù)數(shù)的的充充要要條條件件是是 )()()()(12121xfxfxxxfT ， Sxx 21, 其其中中Tnxxfxxfxf)(,.,)()(1111 是是函函數(shù)數(shù) f 在在點(diǎn)點(diǎn)1x處處的的一一階階 導(dǎo)導(dǎo)數(shù)數(shù)或或梯梯度度。 （2） f 是是 S 上上的的嚴(yán)嚴(yán)格格凸凸函函數(shù)數(shù)的的充充要要條條件件是是 )()()()(12121xfxfxxxfT ， 2121, xxSxx 4

11、.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃2. 凸函數(shù)的一些基本性質(zhì)凸函數(shù)的一些基本性質(zhì)第第17頁頁定定 理理 4.2.4 設(shè)設(shè)nRS 是是 非非 空空 開開 凸凸 集集 ，RSf:二二 階階 連連 續(xù)續(xù) 可可 導(dǎo)導(dǎo) ， 則則 f 是是S 上上 的的 凸凸 函函 數(shù)數(shù) 的的 充充 要要 條條 件件 是是 f 的的 Hesse 矩矩 陣陣)(2xf 在在 S 上上 是是 半半 正正 定定 的的。 當(dāng)當(dāng))(2xf 在在 S 上上 是是 正正 定定 矩矩 陣陣 時時 ， f 是是 S 上上 的的 嚴(yán)嚴(yán) 格格 凸凸 函函 數(shù)數(shù) 。（ 注注 意意 ： 該該 逆逆 命命 題題 不不 成成 立立 。 ） 22221

12、222222122122122122)()()(.)(.)()()(.)()()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf 4.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃2. 凸函數(shù)的一些基本性質(zhì)凸函數(shù)的一些基本性質(zhì)第第18頁頁,. 1對稱件：矩陣的正定等定義及條HEHnn正定。稱如HxHxxT, 0, 0) 1 (0 所有主子式正定H半正定。稱如HxHxxT, 0)2(0, 0)3(xHxxT負(fù)定：如負(fù)定H各階主子式負(fù)正負(fù)正相間（第一個為負(fù)）0 所有順序主子式0 所有主子式半正定H第第19頁頁3.凸凸規(guī)規(guī)劃劃的的定定義義 qjxhpixgtsxfji,.10,)

13、( (MP) ,.,1, 0)( .)( min qjxhpixgRxXjin,.,1, 0)(,.,1, 0)(約束集如果如果(MP)的約束集的約束集X是凸集，目標(biāo)函數(shù)是凸集，目標(biāo)函數(shù)f是是X上的上的凸函數(shù)，則凸函數(shù)，則(MP)叫做叫做非線性凸規(guī)劃非線性凸規(guī)劃，或簡稱為，或簡稱為凸凸規(guī)劃規(guī)劃。4.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃第第20頁頁定定理理 4.2.5 對對于于非非線線性性規(guī)規(guī)劃劃(MP)，若若pixgi,.,1),( 皆皆為為nR上上的的凸凸函函數(shù)數(shù)，qjxhj,.,1),( 皆皆為為線線性性函函數(shù)數(shù)， 并并且且f是是X上上的的凸凸函函數(shù)數(shù)，則則(MP)是是凸凸規(guī)規(guī)劃劃。 定理定理

14、 4.2.6 凸規(guī)劃的任一局部最優(yōu)解都是它的凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。整體最優(yōu)解。4.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃4.凸規(guī)劃的性質(zhì)：凸規(guī)劃的性質(zhì)：第第21頁頁本節(jié)練習(xí)本節(jié)練習(xí) 1. 驗證 )(P44min12221xxx02. .221 xxts1210 xx ）半正定）為凸規(guī)劃（用xH(第第22頁頁4.3 一維搜索方法一維搜索方法精確一維搜索方法：精確一維搜索方法： 0.618法法， Newton法法非精確一維搜索方法：非精確一維搜索方法： Goldstein法法， Armijo法法第第23頁頁1. 0.618法（近似黃金分割法）法（近似黃金分割法）4.3 一維搜索方法一

15、維搜索方法第第24頁頁2. Newton法法4.3 一維搜索方法一維搜索方法第第 1 步步 給定初始點(diǎn)給定初始點(diǎn)1t ，0 e e，1: k； 第第 2 步步 如果如果e e )(kt，停止迭代，輸出，停止迭代，輸出kt 。 否則，當(dāng)否則，當(dāng)0)( kt 時，停止，時，停止， 解題失??；解題失??；當(dāng)當(dāng)0)( kt 時，轉(zhuǎn)下一步；時，轉(zhuǎn)下一步； 第第 3 步步 計算計算)()(1kkkktttt ，如果，如果e e kktt1，停止迭代，輸出，停止迭代，輸出1 kt。 否則否則1: kk， 轉(zhuǎn)第轉(zhuǎn)第2 步。步。 第第25頁頁abcd)0( )(ty ty)0()0( tmy)0()0(1 tmy

16、)0()0(2 3. Goldstein法法4.3 一維搜索方法一維搜索方法第第26頁頁Goldstein法步驟法步驟:4.3 一維搜索方法一維搜索方法第第27頁頁4. Armijo法法tmy)0()0( )0( )(ty ktkMt4.3 一維搜索方法一維搜索方法取定取定Mm 10，用一下兩個式子限定，用一下兩個式子限定kt 不太大也不太?。翰惶笠膊惶。?)0()0()( kkmtt )0()0()( kkmMtMt 第第28頁頁4.4 無約束最優(yōu)化方法無約束最優(yōu)化方法v無約束問題的最優(yōu)性條件無約束問題的最優(yōu)性條件v最速下降法最速下降法v共軛方向法共軛方向法第第29頁頁1、無約束問題的最

17、優(yōu)化條件、無約束問題的最優(yōu)化條件4.4 無約束最優(yōu)化方法無約束最優(yōu)化方法第第30頁頁4.4 無約束最優(yōu)化方法無約束最優(yōu)化方法1、無約束問題的最優(yōu)化條件、無約束問題的最優(yōu)化條件第第31頁頁2. 最速下降法（又稱梯度法）最速下降法（又稱梯度法）4.4 無約束最優(yōu)化方法無約束最優(yōu)化方法第第32頁頁4.4 無約束最優(yōu)化方法無約束最優(yōu)化方法最速下降法的計算步驟：最速下降法的計算步驟：第第33頁頁3. 共軛方向法共軛方向法4.4 無約束最優(yōu)化方法無約束最優(yōu)化方法第第34頁頁4.4 無約束最優(yōu)化方法無約束最優(yōu)化方法3. 共軛方向法共軛方向法第第35頁頁F-R法步驟法步驟4.4 無約束最優(yōu)化方法無約束最優(yōu)化方

18、法第第36頁頁4.5 約束最優(yōu)化方法約束最優(yōu)化方法v約束最優(yōu)化問題的最優(yōu)化條件約束最優(yōu)化問題的最優(yōu)化條件v簡約梯度法簡約梯度法v懲罰函數(shù)法懲罰函數(shù)法qjRRhpiRRgRRfRxnjninn,.,1 :,.,1 ,: : , 其中其中 ,.,1 0)( 1 0)( .)( minqjxh,.,pixgtsxfji(MP)第第37頁頁1. 約束最優(yōu)化問題的最優(yōu)化條件約束最優(yōu)化問題的最優(yōu)化條件qjxhpixgRxXjin,.,1,0)(,.,1,0)(MP)問題的可行區(qū)域為設(shè), 0)( |)(*IixgixIi積極約束的下標(biāo)集：JjxhqJXxj ,0)(,2, 1, *，即滿足令對4.5 約束最

19、優(yōu)化方法約束最優(yōu)化方法第第38頁頁Kuhn-Tucker條件（條件（K-T條件）：條件）：4.5 約束最優(yōu)化方法約束最優(yōu)化方法注：凡是滿足注：凡是滿足K-T條件的點(diǎn)叫條件的點(diǎn)叫K-T點(diǎn)點(diǎn)第第39頁頁4.5 約束最優(yōu)化方法約束最優(yōu)化方法第第40頁頁簡約梯度法簡約梯度法 0 .)( minxbAxtsxf 其中，RRfRxnn: , ，mArnm )(，mRb (4.5.12)定理定理 4.5.3 對于非線性規(guī)劃問題對于非線性規(guī)劃問題(4.5.12)，設(shè)，設(shè) f 是可微函數(shù)，是可微函數(shù)，lkXx ，并且有分解，并且有分解 kNkBkxxx，0 kBx。若。若 kNkBkppp由下式確定由下式確定，

20、 kNkkkBkBkikikikikikikNpNBpIirrxrrpp1 0 0 ,: (*) 則則 （1） 當(dāng)當(dāng)0 kp時，時，kp是是 f 在點(diǎn)在點(diǎn)kx處關(guān)于處關(guān)于lX的可行下降方向；的可行下降方向； （2） 0 kp的充要條件是的充要條件是kx是問題是問題(4.5.12)的的 K-T 點(diǎn)。點(diǎn)。 0 , | xbAxRxXnl第第41頁頁Wolfe法步驟法步驟第第 1步步 選選取取初初始始可可行行點(diǎn)點(diǎn)lXx 0，給給定定終終止止誤誤差差0 e e，令令 k:=0; 第第 2步步 設(shè)設(shè)kBI是是kx的的 m個個最最大大分分量量的的下下標(biāo)標(biāo)集集，對對矩矩陣陣 A進(jìn)進(jìn)行行相相應(yīng)應(yīng)分分解解 ),

21、(kkNBA 第第 3步步 計計算算 )()()(kNkBkxfxfxf，然然后后，計計算算簡簡約約梯梯度度 )()()(1kNkBTkkkNxfxfNBr 記記kNr的的第第)(kBIii 個個分分量量為為kir； 第第 4步步 按按(*)式式構(gòu)構(gòu)造造可可行行下下降降方方向向kp。若若e e kp，停停止止迭迭代代，輸輸出出kx； 否否則則進(jìn)進(jìn)行行第第 5步步； 第第 5步步 進(jìn)進(jìn)行行有有效效一一維維搜搜索索，求求解解 )(minmax0kktttpxfk 得得到到最最優(yōu)優(yōu)解解kt，其其中中 00 0min0 1maxkkkikikinikkppppxpt或或者者， 令令kkkkptxx 1

22、，k:=k+1，轉(zhuǎn)轉(zhuǎn)第第 2步步 第第42頁頁懲罰函數(shù)法懲罰函數(shù)法思想思想：利用問題中的約束函數(shù)做出適當(dāng)?shù)膸в校豪脝栴}中的約束函數(shù)做出適當(dāng)?shù)膸в袇?shù)的懲罰函數(shù)，然后在原來的目標(biāo)函數(shù)上加參數(shù)的懲罰函數(shù)，然后在原來的目標(biāo)函數(shù)上加上懲罰函數(shù)構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把上懲罰函數(shù)構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把(MP)問題的求解轉(zhuǎn)換為求解一系列無約束非線問題的求解轉(zhuǎn)換為求解一系列無約束非線性規(guī)劃問題。性規(guī)劃問題。罰函數(shù)法罰函數(shù)法障礙函數(shù)法障礙函數(shù)法第第43頁頁罰函數(shù)法罰函數(shù)法 qjxhpixgtsxfji,.,1, 0)( ,.,1, 0)( .)( min qjxhpixgRxXjin,.,1,

23、0)(,.,1, 0)(設(shè)法適當(dāng)?shù)丶哟蟛豢尚悬c(diǎn)處對應(yīng)的目標(biāo)設(shè)法適當(dāng)?shù)丶哟蟛豢尚悬c(diǎn)處對應(yīng)的目標(biāo)函數(shù)值，使不可行點(diǎn)不能成為相應(yīng)無約函數(shù)值，使不可行點(diǎn)不能成為相應(yīng)無約束極小化問題的最優(yōu)解。束極小化問題的最優(yōu)解。 qjjpiicxhcxgcxp1212)(2)0),(max()(罰函數(shù)罰函數(shù))( minxFc)()()(xpxfxFcc第第44頁頁實際應(yīng)用中，選取一個實際應(yīng)用中，選取一個遞增且趨于無窮的正罰遞增且趨于無窮的正罰函數(shù)參數(shù)列函數(shù)參數(shù)列 qjjkpiikcxhcxgcxpk1212)(2)0),(max()(其中其中*)()()( minxpxfxFkkcc *罰函數(shù)法罰函數(shù)法第第45頁頁罰函數(shù)法計算步驟罰函數(shù)法計算步驟第第 1 步步 選取初始點(diǎn)選取初始點(diǎn)0 x，罰參數(shù)列，罰參數(shù)列,.)2 , 1( kck， 給出檢驗終止條件的誤差給出檢驗終止條件的誤差0 e e，令令 k:=1； 第第 2 步步 按按(*)構(gòu)造函數(shù)構(gòu)造函數(shù))(xpkc，再按，再按(*)構(gòu)造構(gòu)造(MP) 的增廣目標(biāo)函數(shù)，即的增廣目標(biāo)函數(shù)，即)()()(xpxfxFkkcc 第第 3