非線性規劃 講義大綱 : 1.非線性規劃的定義和相關概念 . 2.常用的求解非線性規劃的方法 . 3.MATLAB求解 非線性規劃及例題 . 4.lingo求解 非線性規劃及例題 . 5.練習 . 非現性規劃的基本概念 定義 如果目標函數或約束條件中至少有一個是非線性函數時的最優化問題就叫做非線性規劃問題 一般形式 : （ 1） 其中 ， 是定義在 En 上的實值函數，簡記 : Xfm in .,.,2,1 0m;1 , 2 , . . . , 0. ljXhiXgtsji nTn ExxxX , 21 ji hgf ,1nj1ni1n E :h ,E :g ,E : EEEf 其它情況 : 求目標函數的最大值或約束條件為小于等于零的情況，都可通過取其相反數化為上述一般形式 定義 1 把滿足問題（ 1）中條件的解 稱為 可行解 （或可行點 ），所有可行點的集合稱為 可行集 （或 可行域 ）記為 D即 問題 (1)可簡記為 nji EXXhXgXD ,0,0|)( nEX XfDX min定義 2 對于問題 (1)，設 ，若存在 ,使得對一切 ，且 ，都有 ，則稱 X*是 f(X)在 D上的局部極小值點 （ 局部最優解 ） 特別地當 時， 若 則稱 X*是f(X)在 D上的 嚴格局部極小值點（嚴格局部最優解） DX * 0DX *XX*XX XfXf * XfXf *定義 3 對于問題 (1),設 ,對任意的 ,都有 則稱 X*是 f(X)在 D上的 全局極小值點 （ 全局最優解 ） 特別地當 時，若 ，則稱 X*是 f(X)在 D上的 嚴格全局極小值點（ 嚴格全局最優解 ） DX * DX XfXf *XX XfXf *返回 非線性規劃的基本解法 SUTM外點法 SUTM內點法（障礙罰函數法） 1、罰函數法 2、 近似規劃法 返回 罰函數法 罰函數法 基本思想是通過構造罰函數把約束問題轉化為一系列無約束最優化問題，進而用無約束最優化方法去求解這類方法稱為 序列無約束最小化方法 (Sequential Unconstrained Minization Technique) 簡稱為 SUMT法 其一為 SUMT外點法 ，其二為 SUMT內點法 )2( ,0m i n,1212 ljjmii XhMXgMXfMXT可設： )3( ,m i n 1 MXTnEX ）轉化為無約束問題：將問題（其中 T(X,M)稱為 罰函數 ， M稱為 罰因子 ， 帶 M的項稱為 罰項 ， 這里的罰函數只對不滿足約束條件的點實行懲罰：當 時，滿足各 ，故罰項 =0，不受懲罰當 時，必有 的約束條件，故罰項 0，要受懲罰 XD 0,0 XhXg ii DX 00 XhXg ii 或SUTM外點法 )1( ., . . . ,2,1 0m;1 , 2 , . . . , 0. m i n ljXhiXgtsXfji對一般的非線性規劃： 罰函數法的 缺點 是：每個近似最優解 Xk往往不是容許解，而只能近似滿足約束，在實際問題中這種結果可能不能使用；在解一系列無約束問題中，計算量太大，特別是隨著 Mk的增大，可能導致錯誤 1、 任意給定初始點 X0，取 M11，給定允許誤差 ，令 k=1； 2、 求無約束極值問題 的最優解，設為 Xk=X(Mk)，即 ； 3、 若存在 ，使 ，則取 MkM( )令 k=k+1返回（ 2），否則，停止迭代得最優解 . 計算時也可將收斂性判別準則 改為 . 0 MXTnEX ,min ),(,m i n kkEXMXTMXTn mii 1 ki Xg 10, 1 MM k 0,0m i n12 mii XgMkXX * ki XgSUTM外點法 (罰函數法 )的 迭代步驟 例題 .min x2 s.t. x=1 顯然本問題的最優解為 x*=1 用 SMT外點法 : T(x,M)=x2+Mmin(0,x-1)2 = 求 minT(x,M).本題可由 T(x,M)=2x+2M(x-1)=0,解得 : x=M/(1+M),M趨于無窮 . 可知 x從小于 1趨于 1,罰函數從外部趨于最優解 . 2221x x Xx M x x X 當當 )1(, . . . ,2,10.m i n i mXgtsXfi考慮問題： 所有嚴格內點的集合。是可行域中，設集合 00 ,2,1,0| DmiXgXD i 11111, , l n ( , ) ( )1l n mmiii immiii iI X r I X r f X r g X I X r f X rgXr g X r rgX 構 造 障 礙 函 數： 或其 中 稱 或 為 障 礙 項 ， 為 障 礙 因 子 ）（得值問題：）就轉化為求一系列極這樣問題（kkkDXrXrXI ,m i n10SUTM內點法（ 障礙函數法 ） 內點法的迭代步驟 (1) 給定允許誤差 0 ，取 10,01 r ； ( 2 ) 求 出 約 束 集 合 D 的 一 個 內 點 00 DX ，令 1k ；( 3 ) 以 01 DX k 為 初 始 點 ， 求 解 kDXrXI ,m i n0， 其 中0DX 的 最 優 解 ， 設 為 0DrXX kk ；( 4 ) 檢 驗 是 否 滿 足 mikiXgr1ln 或 miikXgr11，滿足 ， 停 止 迭 代 ，kXX *；否則取kkrr 1，令 1 kk ，返回 (3 ）例題 .min x2 s.t. x=1 顯然本問題的最優解為 x*=1 用 SMT內點法 : 罰函數 I(x,rk)=x2 rkln(x-1),求其最值 . 可見 ,x從大于 1趨于 1. , 2 0111, 0 , 12kkkkrI x r xxrx r x 解 得 令 得 近似規劃法的基本思想 ： 將問題 (3)中的目標函數 和約束條件 近似為線性函數，并對變量的取值范圍加以限制，從而得到一個近似線性規劃問題，再用單純形法求解之，把其符合原始條件的最優解作為 (3)的解的近似 Xf ),1( 0 m ) ;1 ,. .,( 0 ljXhiXg ji 近似規劃法 每得到一個近似解后，都從這點出發，重復以上步驟 這樣，通過求解一系列線性規劃問題，產生一個由線性規劃最優解組成的序列，經驗表明，這樣的序列往往收斂于非線性規劃問題的解。 近似規劃法的 算法步驟如下 ( 2 ) 在點kX 處 ， 將 Xf ， XhXgji, 按 泰 勒 級 數 展 開 并取 一 階 近 似 ， 得 到 近 似 線 性 規 劃 問 題 ： kTkkXXXfXfXf m i n miXXXgXgXgkTkikii,1 0 lXXXhXhXhkTkjkjj,1j 0 ；( 1 ) 給定初始可行點 112111 , nxxxX ，步長限制 njj ,11 ，步長縮小系數 1,0 ，允許誤差 ，令 k = 1 ； 5) 判 斷 精 度 ：若 njkj ,1 ，則 點1kX為 近 似 最 優 解 ；否則，令 njkjkj ,1 1 ， k = k + 1 ， 返 回 步 驟 ( 2 ) ( 3 ) 在 上 述 近 似 線 性 規 劃 問 題 的 基 礎 上 增 加 一 組 限 制 步 長 的 線性 約 束 條 件 因 為 線 性 近 似 通 常 只 在 展 開 點 附 近 近 似 程 度 較高 ，故 需 要 對 變 量 的 取 值 范 圍 加 以 限 制 ，所 增 加 的 約 束 條 件 是 ： njxxkjkjj,1 求 解 該 線 性 規 劃 問 題 ， 得 到 最 優 解1kX ；( 4 ) 檢驗 1kX 點 對 原 約 束 是 否 可 行 。 若 1kX 對 原 約 束 可 行 ，則轉步驟 ( 5 ) ；否 則 ，縮 小 步 長 限 制 ，令 njkjkj ,1 ，返回步驟 ( 3 ) ， 重 解 當 前 的 線 性 規 劃 問 題 ；返回 例題 1、用近似規劃法求解下列問題。 12221 1 2222 1 2121m i n 2 1. . 2 5 0700 5 , 0 1 03 , 2 . 5 , 2 , 1 , 0 . 5TTf x x xs t g x x xg x x xxx 1初 始 點 ： x解：第一次迭代：在點 x1處將 g1(x), g2(x)線性化。 1 1 11 1 11212369 . 7 52 . 554 0 . 2 5 6 5 0 2TTg x g x g x x xxxxx 1 1 12 2 21212364 . 7 52 . 559 . 2 5 6 5 0 3TTg x g x g x x xxxxx 步長限制： 111122, 2 3 2 1 51 2 . 5 1 1 . 5 3 . 5 4x x x xxx 即2 114 , 36 2 0Tx 解（ 1）（ 2）（ 3）（ 4），得 ， 檢驗，可得 x2不滿足原始約束。 第二次迭代，減少 2111221 , 0 . 51 3 1 2 450 . 5 2 . 5 0 . 5 2 3Txxxx 解（ 1,2,3,5)，得 x2=(4,3)T,f(x2)= -11.所以 x2為最小值點 . 用 MATLAB軟件求解 ,其 輸入格式 如下 : 1. x=quadprog(H,C,A,b); 2. x=quadprog(H,C,A,b,Aeq,beq); 3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6. x,fval=quaprog(.); 7. x,fval,exitflag=quaprog(.); 8. x,fval,exitflag,output=quaprog(.); 1、二次規劃 標準型為： M i n Z = 21XTH X + cTX s . t . A X =0時，返回不超過 x的最大整數；當 x=100; x1*r21+x2*r22+x3*r23=100; x1*r31+x2*r32+x3*r33=100; x1*r41+x2*r42+x3*r43=70; x1+x2+x3=105; x1+x2+x3=5.9; 2.9*r12+2.1*r22+1.5*r32+1.8*r42=5.9; 2.9*r13+2.1*r23+1.5*r33+1.8*r43=5.9; 2.9*r11+2.1*r21+1.5*r31+1.8*r41=x2;x2=x3; gin(x1);gin(x2);gin(x3); gin(r11);gin(r21);gin(r31);gin(r41); gin(r12);gin(r22);gin(r32);gin(r42); gin(r13);gin(r23);gin(r33);gin(r43); end 運行結果如下： Feasible solution found at iteration: 26565 Model Title: 鋼管下料； Variable Value X1 72.00000 R11 1.000000 X2 29.00000 R12 0.000000 X3 14.00000 R13 2.000000 R21 1.000000 R22 1.000000 R23 0.000000 R31 0.000000 R32 3.000000 R33 1.000000 R41 1.000000 R42 0.000000 R43 0.000000 Lingo源程序二 model: Title 鋼管下料 - 最小化鋼管根數的 LINGO模型 ; SETS: NEEDS/1.4/:LENGTH,NUM; ! 定義基本集合 NEEDS及其屬性 LENGTH,NUM; CUTS/1.3/:X; ! 定義基本集合 CUTS及其屬性 X; PATTERNS(NEEDS,CUTS):R; ! 定義派生集合 PATTERNS（這是一個稠密集合）及其屬性 R; ENDSETS DATA: LENGTH=2.9 2.1 1.5 1.8; NUM=100 100 100 70; CAPACITY=7.4; ENDDATA min=SUM(CUTS(I): X(I) ); !目標函數 ; Lingo源程序二 FOR(NEEDS(I): SUM(CUTS(J): X(J)*R(I,J) ) NUM(I) ); !滿足需求約束 ; FOR(CUTS(J): SUM(NEEDS(I): LENGTH(I)*R(I,J) ) CAPACITY -MIN(NEEDS(I):LENGTH(I) ); !合理切割模式約束 ; SUM(CUTS(I): X(I) ) 105; SUM(CUTS(I): X(I) ) X(I+1) ); !人為增加約束 ; FOR(CUTS(J): GIN(X(J) ) ; FOR(PATTERNS(I,J): GIN(R(I,J) ); end 運行結果如下： Local optimal solution found at iteration: 64408 Objective value: 113.0000 Model Title: 鋼管下料 - 最小化鋼管根數的 LINGO模型 Variable Value Reduced Cost CAPACITY 7.400000 0.000000 LENGTH( 1) 2.900000 0.000000 LENGTH( 2) 2.100000 0.000000 LENGTH( 3) 1.500000 0.000000 LENGTH( 4) 1.800000 0.000000 NUM( 1) 100.0000 0.000000 NUM( 2) 100.0000 0.000000 NUM( 3) 100.0000 0.000000 NUM( 4) 70.00000 0.000000 X( 1) 50.00000 1.000000 X( 2) 37.00000 1.000000 X( 3) 26.00000 1.000000 運行結果如下： R( 1, 1) 1.000000 0.000000 R( 1, 2) 0.000000 0.000000 R