試驗(yàn)優(yōu)化設(shè)計(jì)-數(shù)學(xué)建模非線性規(guī)劃6ppt課件

1、 第六章第六章 一般的非線性規(guī)劃問題一般的非線性規(guī)劃問題6.1 問題概論問題概論（模型）（模型） min f (x) s .t ( )0,1,.,( )0,1,.,ijg ximh xjn （一些基本定義）（一些基本定義） 梯度梯度 Hesse矩陣矩陣 Jaccobi矩陣矩陣 1( )(,.,)Tndfdff xdxdx ( )Hx 1111nmmnffff 1( )TTnfF xf 定義6.2.1 整體全局最優(yōu)解 定義6.2.2 局部最優(yōu)解 （已有算法基本都是求局部最優(yōu)解的） 6.3 凸集與凸函數(shù)定義6.3.1 凸集定義6.3.2 （嚴(yán)格凸函數(shù) 稱定義在凸集K上的實(shí)值函數(shù)f (x)為凸函數(shù)，

2、假設(shè) 定義6.3.3 凹函數(shù)1201xxK ，及，有： 1212(1)()(1) ()fxxf xf x定義定義6.3.4 凸規(guī)劃圖集上凸函數(shù)的極小化問題）凸規(guī)劃圖集上凸函數(shù)的極小化問題）定理定理6.3.1 設(shè)設(shè) 、 均為凸集，那么均為凸集，那么 也是凸也是凸集集 ，對任意實(shí)數(shù)，對任意實(shí)數(shù)， 是凸集。是凸集。 （證明）（推廣）（證明）（推廣）定理定理6.3.2 有限個(gè)凸集的交集必是凸集有限個(gè)凸集的交集必是凸集定理定理6.3.3 （分離定理（分離定理K為閉凸集，為閉凸集， 那么那么 定理定理6.3.4 （支撐超平面定理）（支撐超平面定理）1K1K12KKyK0min/TTpp yp x xK ，

3、2K 定理6.3.5 假設(shè) 均為凸集K上的凸函數(shù)，那么 也是K上的凸函數(shù)。 （請證明）定理6.3.6 設(shè)f (x)是凸集K上的凸函數(shù)，那么 實(shí)數(shù)C，水平集 必為凸集。定理6.3.7 若f (x) 在開集K 中可微，則f 是K上的嚴(yán)格凸函數(shù)當(dāng)且僅當(dāng) 1( )( )rf xf x，0i=1,ir，（）1()riiifx/( )xkf xC ,( )( )( ) ()Tx yKf xf yf xxy均有證明充分性） 任取 ，記由條件， （必要性） 0,1, x yK(1) ,zzxyK則( )( )( ) ()( ) (1)( ) ()TTf xf zf zx zf zf zx y ( )( )(

4、) ()( )( ) ()TTf yf zf zyzf zf zxy 1-()(1)()()(1)()fxfyfzfxyfx第 一 式 乘 以， 第 二 式 乘 以 （） ， 相 加 得故為 凸 函 數(shù),(0 ,1),()(1)()(1)()()()()(1)()()()xyKfxfxyfxfyfyfxfyfxyfyfxfy由凸 ， 可 得故令此即需證。假設(shè) f (x) 兩階可微，則有以下的定理：定理6.3.8 設(shè)f (x)在開凸集K中二階連續(xù)可微，f 為凸函數(shù)的充要條件為：證明：（充分性）0 ,( ) ()( )( )Tf xxyf xf y得:,( )xK f xx n在 處的Hesse矩

5、陣H(x)在R 中半正定，即( )0Ty H x y ,nxKyR ,( )x yKf x由的二階可微性得1( )( )( ) ()()()()2TTf xf yf yxyxyH yxyxy此處從而， (必要性) 任取將 在 x 處展開 ： (0,1),()KyxyK因?yàn)?為凸集，故有()H yxy( )( )( ) ()nTRf xf yf yxy在中半正定，故：,nxK zRxzK因?yàn)镵是開集，故存在0,使當(dāng)(0, )時(shí)， ()f xz22()( )( )( )()2TTf xzf xf xzz H x zo 令 得定理1.3.9 證明 22( )( )( )()2TTf xf xzz H

6、 x zo 0( )0Tz H x z ( ),( )nf xxK HesseRf x 在開凸集中二階連續(xù)可微，若矩陣在上正定，則是嚴(yán)格凸函數(shù)。,x yK xy由假設(shè)1( )( )( ) ()()()()2( )( ) ()TTTf xf yf yxyxyH yxyxyf yf yxy此即說明f 是嚴(yán)格凸函數(shù)。定理6.3.10證明 當(dāng) 充分小時(shí) 在 的鄰域中，從而導(dǎo)出矛盾，證畢 ( )( )f xKf xK是凸集 上的凸函數(shù)，則在 中的任一局部最優(yōu)解都是它的整體最優(yōu)解。*,( )( )xxRf xf x 是一局部最優(yōu)解但非整體最優(yōu)解，則使*0 1( )(1)( )(1) ()()f xfxxf

7、 xf xf x（ ， ），由于是凸函數(shù)，可得：*(1)xx*x無約束極小化問題 （模型） min s .t （6.4.1)定理6.4.1 （一階必要條件假設(shè) 是可微函數(shù)， 是問題6.4.1)的一個(gè)局部最小點(diǎn)的必要條件為： （無約束極小化問題求解等價(jià)于方程組求解）定理6.4.2 （二階必要條件設(shè) 為 中的二階連續(xù)可微函數(shù)，假如 是 的一個(gè)局部極小點(diǎn)，那么 ()nfxxR( )f x*x*()0,1,phxpt( )0f x 21mintpphx( )f x( )f xnR*x*()0()0Tfxy H xy證明：由定理6.4.1， 。對任意的由于 是局部極小點(diǎn)，故對于充分小的 必有此式成立必須

8、有 ，證畢。*()0f x,nyR根據(jù)泰勒公式有2*2()()()()2Tf xyf xy H xyo*()()f xf xy*x*()0Ty H xy 定理6.4.3 （二階充分條件設(shè) 兩階可微，假設(shè) 滿足則點(diǎn) 的一個(gè)嚴(yán)格局部極小點(diǎn)，這里 是 的兩階Hesse矩陣定理6.4.4兩階充分條件設(shè) 兩階連續(xù)可微，假設(shè) 滿足 證明：任取顯然， 由假設(shè)， ，由 的任意性， 是 ( )f xx()0()0,0Tnf xy F xyyRy 且( )xf x是( )F x( )f x( )f xx()0,()f xxVx且存在 的一個(gè)鄰域，使得( )0,Ty H x y ,()nyRxVx 有( )xf x

9、則 必為的局部極小點(diǎn)。1(),( )()()()()2TxVxf xf xxxH xxxxx由()()xxxVx( )()f xf xxx( )f x 的局部極小點(diǎn)，證畢。定理6.4.5證畢 ( )( )nf xRf x若是上的凸函數(shù)，則的任意局部極小點(diǎn)均為整體最小解: ( ),( )()() ()0,( )nTxf xxRf xf xf xxxxf x 證 設(shè) 是的任意局部極小點(diǎn)，由凸函數(shù)性質(zhì)此即說明是的整體極小點(diǎn)。具有等式與不等式約束的極小化問題 (NP) min s .t 定義 6.4.1 設(shè)x是滿足(NP)約束條件的點(diǎn)，記 稱I 為x處不等式約束中的積極約束的下標(biāo)集合 定義6.4.2

10、（積極約束） 稱約束為x處的積極約束定義6.4.3 （正則點(diǎn)若向量組線性無關(guān)，則稱x為約束條件的一個(gè)正則點(diǎn)。( )f x( )0( )0g xh x( )( )0,1,iI xi gxim( )0,( );( )0,1,ipg xiI x hxpt ( )0,( );( )0,1,ipg xiI xhxpt 定理6.4.5 （Kuhn-Tucker條件設(shè) 是(NP)的局部極小點(diǎn)且 其中 x1)( ,)TnxuuuT1n 是約束的正則點(diǎn)，則必存在乘子矢量 （ ， ，和 0,xu使得 和 滿足11( )( )( )0mtiippipf xg xuhx( )0,1,0,1,( )0,1,( )0,1

11、,iiiipg ximimg ximhxpt例 求下面問題的 K-T 點(diǎn) min s .t 解：本問題的 K-T條件為2212126618xxxx124xx120,0 xx11221311221321212312260260(4)00,04,0,0 xxxxxxxxx x ；（1）假設(shè) （舍去）假設(shè) （舍去）（2） （舍去）（3） 10,x 則上述條件化為1213212322123662(4)0,004;,0 xxxx 231402x 2120406x 212006x 1200,xxKT且 條件化為故有 求得 23112111032(2)026xx11222xx(2,2)Tx迭代算法 記滿足要

12、求的點(diǎn)集為 （如 K-T 點(diǎn)集，最優(yōu)解集等）。算法一般采用迭代方法，即：任給一個(gè)初始點(diǎn)步1步2 定義1.5.1 （全局收斂性設(shè)A是求解問題的一個(gè)算法，若對任意初始點(diǎn) 在用算法A進(jìn)行迭代時(shí)，或能在有限步求得最優(yōu)解，或求得一無窮點(diǎn)列 ，該點(diǎn)列的任意聚點(diǎn)均為需求的點(diǎn)。1()kkkxxA x若停 ； 否則,求一改進(jìn)點(diǎn) 0,: 0 xk 令:1,1kk返回步0 x,1,kxk 例1 求解問題 min s .t 算法 迭代點(diǎn)列例2 求解 min 算法 1nxx 1( )(1)2A xx111111111(1)122222kkkkxx0 x,x xE1(1),12( )1,12xxA xxx當(dāng)當(dāng)?shù)c(diǎn)列 假

13、設(shè) 假設(shè)定義 6.5.1 （閉映射設(shè)X何Y分別是兩個(gè)非空閉集，A是從X到Y(jié)的一個(gè)點(diǎn)到集的映射，即對任意 有 設(shè) ，且 假設(shè) （例1種的映射是閉的，而例2中的映射則是非閉的） 顯然，例2的最優(yōu)解為 取算法A為X到X的一個(gè)映射：定理6.5.1 若對任意取定的 ：（1） （2存在 ， （3算法 A 在 外是閉的則算法 A 必定是全局收斂的。（證明從略）0011,2kkxxx則 011kxx 則xX( )A xY ,kkxXyY(),kkyA xk,( )kkxx yyyA x則必有0,0 x 記011,1,1(1),(1)2kxxAA但注01,: 0,()kkkxX kxxA x若則取 0,kxXAx由算法 求得的點(diǎn)列滿足 kx是列緊的( ),( ),( )( )f xxyA xf yf x若有,( ),( )( )xyA xf yf x若有收斂速度定義6.5.2 設(shè)實(shí)數(shù)列 除有限個(gè) 外 除有限個(gè) 外 其他 被稱為商收斂因子定理1.5.2 僅有以下三種情況之一發(fā)生： （1） （2） （3） ， ,0,krrp 令10( )limkpkkrrQ prrkrkrkrrkrr( )Q p( )0Q p ( )Q p ( )Q p ( )0Q p 000,pp