非線性規(guī)劃ppt課件

1、非線性規(guī)劃非線性規(guī)劃Non-linear ProgrammingNon-linear Programming1;非線性規(guī)劃非線性規(guī)劃v基本概念基本概念v凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃v一維搜索方法一維搜索方法v無約束最優(yōu)化方法無約束最優(yōu)化方法v約束最優(yōu)化方法約束最優(yōu)化方法2;基本概念基本概念v非線性規(guī)劃問題非線性規(guī)劃問題v非線性規(guī)劃方法概述非線性規(guī)劃方法概述3;非線性規(guī)劃問題非線性規(guī)劃問題例例1 曲線的最優(yōu)擬合問題曲線的最優(yōu)擬合問題已已知知某某物物體體的的溫溫度度 與與時(shí)時(shí)間間 t 之之間間有有如如 下下形形式式的的經(jīng)經(jīng)驗(yàn)驗(yàn)函函數(shù)數(shù)關(guān)關(guān)系系： tcetcc321 (*) 其其中中1c，2c，3c

2、是是待待定定參參數(shù)數(shù)?，F(xiàn)現(xiàn)通通過過測測 試試獲獲得得 n 組組 與與 t 之之間間的的實(shí)實(shí)驗(yàn)驗(yàn)數(shù)數(shù)據(jù)據(jù)),(iit ， i=1，2，,n。試試確確定定參參數(shù)數(shù)1c，2c，3c， 使使理理論論曲曲線線(*)盡盡可可能能地地與與 n 個(gè)個(gè)測測試試點(diǎn)點(diǎn) ),(iit 擬擬合合。 t n1i221)( min3 itciietcc 4;例例2 構(gòu)件容積問題構(gòu)件容積問題設(shè)計(jì)一個(gè)右圖所示的由圓錐和圓柱面 圍成的構(gòu)件，要求構(gòu)件的表面積為 S， 圓錐部分的高 h 和圓柱部分的高 x2之 比為 a。確定構(gòu)件尺寸，使其容積最 大。 x1x2x3 0, 0 2 .)3/1( max212121222211221xx

3、SxxxxaxxtsxxaV 5;數(shù)學(xué)規(guī)劃數(shù)學(xué)規(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 qjxhpixgRxXjin,.,1, 0)(,.,1, 0)(約束集或可行域約束集或可行域Xx MP的可行解或可行點(diǎn)的可行解或可行點(diǎn)6;向量化表示向量化表示當(dāng)當(dāng)p=0,q=0時(shí)，稱為時(shí)，稱為無約束非線性規(guī)無約束非線性規(guī)劃劃或者或者無約束最優(yōu)

4、化問題無約束最優(yōu)化問題。否則，稱為否則，稱為約束非線性規(guī)劃約束非線性規(guī)劃或者或者約束約束最優(yōu)化問題最優(yōu)化問題。7;最優(yōu)解和極小點(diǎn)最優(yōu)解和極小點(diǎn)定定義義 4.1.1 對(duì)對(duì)于于非非線線性性規(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)格格整整體體最

5、最優(yōu)優(yōu)值值或或嚴(yán)嚴(yán)格格整整體體極極小小值值。 8;非線性規(guī)劃方法概述非線性規(guī)劃方法概述定義定義 4.1.3 設(shè)設(shè)0,: pRpRxRRfnnn，若存在，若存在0 ，使，使 ), 0( ),()( txftpxf 則稱向量則稱向量 p 是函數(shù)是函數(shù) f(x)在點(diǎn)在點(diǎn)x處的處的下降方向下降方向。 不可行方向不可行方向9;非線性規(guī)劃基本迭代格式非線性規(guī)劃基本迭代格式第第 1 步步 選取初始點(diǎn)選取初始點(diǎn)0 x，k:=0; 第第 2 步步 構(gòu)造搜索方向構(gòu)造搜索方向kp； 第第 3 步步 根據(jù)根據(jù)kp，確定步長，確定步長kt； 第第 4 步步 令令kkkkptxx 1， 若若1 kx已滿足某種終止條件，停

6、止迭代，輸出已滿足某種終止條件，停止迭代，輸出 近似解近似解1 kx；否則令；否則令 k:=k+1，轉(zhuǎn)回第，轉(zhuǎn)回第 2 步。步。 迭代法的基本格式迭代法的基本格式10;常用停止規(guī)則常用停止規(guī)則11;凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃q凸函數(shù)及其性質(zhì)凸函數(shù)及其性質(zhì)q凸規(guī)劃及其性質(zhì)凸規(guī)劃及其性質(zhì)12;凸函數(shù)及其性質(zhì)凸函數(shù)及其性質(zhì)定義定義 4.2.1 設(shè)設(shè)nRS 是非空凸集，是非空凸集，RSf:，如果對(duì)任意的，如果對(duì)任意的)1 , 0( 有有 )()1()()1(2121xfxfxxf ，Sxx 21, 則稱則稱 f 是是 S 上的上的凸函數(shù)凸函數(shù)，或，或 f 在在 S 上是上是凸凸的。的。如果對(duì)于任意的

7、如果對(duì)于任意的)1 , 0( 有有 )()1()()1(2121xfxfxxf ，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)格格）凹凹的的。 13;(a) (a) 凸函數(shù)凸函數(shù) (b)(b)凹函數(shù)凹函數(shù)14;定定理理 4.2.2 設(shè)設(shè)nRS 是是非非空空凸凸集集，RRfn:是是凸凸函函數(shù)數(shù)，Rc ，則則集集合合 cxfSxcfHS )(),( 是是凸凸集集。 15;16;定理定

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

9、質(zhì) qjxhpixgtsxfji,.10,)( (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ī)劃。18;定理定理 4.2.5 對(duì)于非線性規(guī)劃對(duì)于非線性規(guī)劃(MP)，若，若pixgi,.,1),( 皆為皆為nR上的凸函數(shù)，上的凸函數(shù)，qjxhj,.,1),( 皆為線性函數(shù)，皆為線性函數(shù)， 并且并且 f 是是 X 上的凸函數(shù)，則上的凸函數(shù)，則(MP)是凸規(guī)劃。是

10、凸規(guī)劃。 定理定理 4.2.6 凸規(guī)劃的任一局部最優(yōu)解都是它凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。的整體最優(yōu)解。19; 例例 4.2.3 4.2.3 驗(yàn)證下列（驗(yàn)證下列（MPMP）是凸規(guī)劃）是凸規(guī)劃2221231231 31 21222112321233123min( , , ) 222.( )0( )216( )0f x x xxxxxxxxxxstg xxxxg xxxxg xxxx 20;一維搜索方法一維搜索方法目目標(biāo)標(biāo)函函數(shù)數(shù)為為單單變變量量的的非非線線性性 規(guī)規(guī)劃劃問問題題稱稱為為一一維維搜搜索索問問題題 (t) min)0(0 max ttt 其其中中Rt 。 精確一維搜索方法

11、精確一維搜索方法 0.618法法 Newton法法非精確一維搜索方法非精確一維搜索方法 Goldstein法法 Armijo法法21;0.618法（近似黃金分割法）法（近似黃金分割法）22; 例4.3.1 用0.618法求解 的單谷區(qū)間為0,3，30min ( )21tttt( ) t0.5解答解答23; 在在0.6180.618法中每次迭代搜索區(qū)間按常比例縮法中每次迭代搜索區(qū)間按常比例縮小，所以要使給定的單谷區(qū)間減少到所要小，所以要使給定的單谷區(qū)間減少到所要求的區(qū)間精度，需要的迭代次數(shù)是可以預(yù)求的區(qū)間精度，需要的迭代次數(shù)是可以預(yù)估的。另外若每次每次迭代按不同比例縮估的。另外若每次每次迭代按不

12、同比例縮小搜索區(qū)間，但仍要求每次迭代只計(jì)算一小搜索區(qū)間，但仍要求每次迭代只計(jì)算一個(gè)函數(shù)值，且希望在搜索點(diǎn)個(gè)數(shù)相同的情個(gè)函數(shù)值，且希望在搜索點(diǎn)個(gè)數(shù)相同的情況下使最終的搜索區(qū)間的長度最小，按此況下使最終的搜索區(qū)間的長度最小，按此要求設(shè)計(jì)的方法是要求設(shè)計(jì)的方法是FibonacciFibonacci法法24; NewtonNewton法思想法思想25;Newton法法)( mint 其中其中)(t 是二次可微的是二次可微的，且且0)( t 。 26; 從任意初始點(diǎn)開始的從任意初始點(diǎn)開始的NewtonNewton法產(chǎn)生的點(diǎn)列，法產(chǎn)生的點(diǎn)列，一般來說不一定收斂，即使收斂，其極限一般來說不一定收斂，即使收斂

13、，其極限點(diǎn)也不一定是點(diǎn)也不一定是 的極小點(diǎn)，只能保證它是的極小點(diǎn)，只能保證它是 的駐點(diǎn)。但當(dāng)初始點(diǎn)充分接近的駐點(diǎn)。但當(dāng)初始點(diǎn)充分接近 時(shí)，可時(shí)，可以證明以證明NewtonNewton法是收斂的。法是收斂的。 ( ) t( ) t*t27;abcd)0( )(ty ty)0()0( tmy)0()0(1 tmy)0()0(2 Goldstein法法28;29;Goldstein法步驟法步驟30; 例例4.3.3 4.3.3 用用GoldsteinGoldstein法求解法求解 取取30min( )21tttt0122,0.2,0.7,2tmm解答解答31;Armijo法法)0( )(ty tmy

14、)0()0( ktkMt取取定定Mm 10，用用一一下下兩兩個(gè)個(gè)式式子子限限定定kt不不太太大大也也不不太太小?。?)0()0()( kkmtt )0()0()( kkmMtMt 32;無約束最優(yōu)化方法無約束最優(yōu)化方法v無約束問題的最優(yōu)性條件無約束問題的最優(yōu)性條件v最速下降法最速下降法v共軛方向法共軛方向法)( minxf (UMP) 其其中中nTnRxxx ),.,(1，RRfn: 33;無約束問題的最優(yōu)化條件無約束問題的最優(yōu)化條件定理定理 4.4.1 設(shè)設(shè)RRfn:在點(diǎn)在點(diǎn)nRx 處可微。處可微。若存在若存在nRp ，使，使 0)( pxfT 則向量則向量 p 是是 f 在點(diǎn)在點(diǎn)x處的下降

15、方向。處的下降方向。 定理定理 4.4.2 設(shè)設(shè)RRfn:在點(diǎn)在點(diǎn)nRx 處可微。若處可微。若*x是是(UMP)的局部的局部最優(yōu)解，則最優(yōu)解，則 0)(* xf 定定理理 4.4.3 設(shè)設(shè)RRfn:在在點(diǎn)點(diǎn)nRx 處處的的 Hesse 矩矩陣陣)(*2xf 存存在在。若若 0)(* xf，并并且且)(*2xf 正正定定 則則*x是是(UMP)的的局局部部最最優(yōu)優(yōu)解解。 定定理理 4.4.4 設(shè)設(shè)RRfn:，nRx *，f 是是nR上上得得可可微微凸凸函函數(shù)數(shù)。若若有有 0)(* xf 則則*x是是(UMP)的的整整體體最最優(yōu)優(yōu)解解。 34;最速下降法最速下降法設(shè)（設(shè)（NMP）問題中的目標(biāo)函數(shù)）

16、問題中的目標(biāo)函數(shù)RRfn:一階連續(xù)可微一階連續(xù)可微 35;36;第第 1 步步 選取初始點(diǎn)選取初始點(diǎn)0 x，給定終止誤差，給定終止誤差0 ，令，令0: k； 第第 2 步步 計(jì)算計(jì)算)(kxf ，若，若 )(kxf，停止迭代，輸出，停止迭代，輸出kx。否則進(jìn)行第否則進(jìn)行第 3 步；步； 第第 3 步步 取取)(kkxfp 第第 4 步步 進(jìn)行一維搜索，求進(jìn)行一維搜索，求kt，使得，使得)(min)(0kktkkktpxfptxf 令令kkkkptxx 1，1: kk，轉(zhuǎn)第，轉(zhuǎn)第 2 步。步。 37;解答解答38; 隨著迭代次數(shù)的增加，收斂速度越來越慢隨著迭代次數(shù)的增加，收斂速度越來越慢 最速下

17、降法的相鄰兩個(gè)搜索方向是彼此正最速下降法的相鄰兩個(gè)搜索方向是彼此正交的交的 具有全局收斂性具有全局收斂性39;解答解答40; 隨著迭代次數(shù)的增加，收斂速度越來越慢隨著迭代次數(shù)的增加，收斂速度越來越慢 最速下降法的相鄰兩個(gè)搜索方向是彼此正最速下降法的相鄰兩個(gè)搜索方向是彼此正交的交的 具有全局收斂性具有全局收斂性41; 共軛方向法共軛方向法42;43; F-R法步驟44;解答解答45; F-R法具有二次終止性。對(duì)一般可微函數(shù)的法具有二次終止性。對(duì)一般可微函數(shù)的無約束優(yōu)化問題，當(dāng)函數(shù)滿足一定的條件無約束優(yōu)化問題，當(dāng)函數(shù)滿足一定的條件時(shí)，可以證明時(shí)，可以證明F-RF-R方法具有全局收斂性其收方法具有全

18、局收斂性其收斂速度比最速下降法快斂速度比最速下降法快 F-R法強(qiáng)烈依賴于一位搜索的精確性法強(qiáng)烈依賴于一位搜索的精確性46;約束最優(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)47;約束最優(yōu)化問題的最優(yōu)化條件約束最優(yōu)化問題的最優(yōu)化條件 qjxhpixgRxXjin,.,1, 0)(,.,1, 0)(, 0)( |)(*IixgixIi Xx * Jjx

19、hqJj , 0)(,.,2 , 1*，即，即令令定理定理 4.5.1 設(shè)設(shè)RRfn:和和)(,:*xIiRRgni 在點(diǎn)在點(diǎn)*x處可微，處可微， )(,*xIIigi 在點(diǎn)在點(diǎn)*x處連續(xù)，處連續(xù)，JjRRhnj ,:在點(diǎn)在點(diǎn)*x處連續(xù)處連續(xù) 可微，并且各可微，并且各JjxhxIixgji ),( ),( ),(*線性無關(guān)。線性無關(guān)。若若 *x是是(MP)的局部最優(yōu)解，則存在兩組實(shí)數(shù)的局部最優(yōu)解，則存在兩組實(shí)數(shù))(,*xIii 和和Jjj ,* ， 使得使得 )( , 00)()()(*)(*xIixhxgxfiJjjjxIiii K-T條件條件48;定定理理 4.5.2 對(duì)對(duì)于于(MP)問問

20、題題，若若JjhIigfji , , ,在在點(diǎn)點(diǎn)*x處處連連續(xù)續(xù)可可微微， 可可行行點(diǎn)點(diǎn)*x滿滿足足(MP)的的 K-T 條條件件，且且)(, ,*xIigfi 是是凸凸函函數(shù)數(shù)，Jjhj , 是是線線性性函函數(shù)數(shù)，則則*x是是(MP)的的整整體體最最優(yōu)優(yōu)解解。 49;簡約梯度法簡約梯度法 0 .)( minxbAxtsxf 其中，RRfRxnn: , ，mArnm )(，mRb (4.5.12)定理定理 4.5.3 對(duì)于非線性規(guī)劃問題對(duì)于非線性規(guī)劃問題(4.5.12)，設(shè)，設(shè) f 是可微函數(shù)，是可微函數(shù)，lkXx ，并且有分解，并且有分解 kNkBkxxx，0 kBx。若。若 kNkBkpp

21、p由下式確定由下式確定， kNkkkBkBkikikikikikikNpNBpIirrxrrpp1 0 0 ,: (*) 則則 （1） 當(dāng)當(dāng)0 kp時(shí)，時(shí)，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 , | xbAxRxXnl50;Wolfe法步驟法步驟51;懲罰函數(shù)法懲罰函數(shù)法思想思想：利用問題中的約束函數(shù)做出適當(dāng)?shù)膸в袇?shù)的懲：利用問題中的約束函數(shù)做出適當(dāng)?shù)膸в袇?shù)的懲罰函數(shù)，然后在原來的目標(biāo)函數(shù)上加上懲罰函數(shù)構(gòu)造出罰函數(shù)，然后在原來的目標(biāo)函數(shù)上加上懲罰函數(shù)構(gòu)

22、造出帶參數(shù)的增廣目標(biāo)函數(shù)，把帶參數(shù)的增廣目標(biāo)函數(shù)，把(MP)問題的求解轉(zhuǎn)換為求解問題的求解轉(zhuǎn)換為求解一系列無約束非線性規(guī)劃問題。一系列無約束非線性規(guī)劃問題。罰函數(shù)法罰函數(shù)法障礙函數(shù)法障礙函數(shù)法52;罰函數(shù)法罰函數(shù)法 qjxhpixgtsxfji,.,1, 0)( ,.,1, 0)( .)( min qjxhpixgRxXjin,.,1, 0)(,.,1, 0)(設(shè)法適當(dāng)?shù)丶哟蟛豢尚悬c(diǎn)處對(duì)應(yīng)的目標(biāo)函數(shù)值，使設(shè)法適當(dāng)?shù)丶哟蟛豢尚悬c(diǎn)處對(duì)應(yīng)的目標(biāo)函數(shù)值，使不可行點(diǎn)不能成為相應(yīng)無約束極小化問題的最優(yōu)解。不可行點(diǎn)不能成為相應(yīng)無約束極小化問題的最優(yōu)解。 qjjpiicxhcxgcxp1212)(2)0),(

23、max()(罰函數(shù)罰函數(shù))( minxFc)()()(xpxfxFcc 53;實(shí)際應(yīng)用中，選取一個(gè)實(shí)際應(yīng)用中，選取一個(gè)遞增且趨于無窮的正罰遞增且趨于無窮的正罰函數(shù)參數(shù)列函數(shù)參數(shù)列 qjjkpiikcxhcxgcxpk1212)(2)0),(max()(其中其中*)()()( minxpxfxFkkcc *54;罰函數(shù)法計(jì)算步驟罰函數(shù)法計(jì)算步驟第第 1 步步 選取初始點(diǎn)選取初始點(diǎn)0 x，罰參數(shù)列，罰參數(shù)列,.)2 , 1( kck， 給出檢驗(yàn)終止條件的誤差給出檢驗(yàn)終止條件的誤差0 ，令令 k:=1； 第第 2 步步 按按(*)構(gòu)造函數(shù)構(gòu)造函數(shù))(xpkc，再按，再按(*)構(gòu)造構(gòu)造(MP) 的增廣目標(biāo)函數(shù)，即的增廣目標(biāo)函數(shù)，即)()()(xpxfxFkkcc 第第 3 步步 選用某種無約束最優(yōu)化方法，以選用某種無約束最優(yōu)