二次規(guī)劃求解方法探討

1、二次規(guī)劃求解方法探討李驥昭 1劉義山 2(1.平頂山工業(yè)職業(yè)技術(shù)學(xué)院文化教育部1河南平頂山 467001;2.平頂山工業(yè)職業(yè)技術(shù)學(xué)院文化教育部2河南平頂山 467001)摘要： 文章推廣與應(yīng)用了二次非線性規(guī)劃模型的基礎(chǔ)理論及算法。在線性規(guī)劃模型中，活動對目標(biāo)函數(shù)的貢獻與活動水平成比例關(guān)系，因而目標(biāo)函數(shù)是決策變量的線性函數(shù)，而在實際問題中，往往遇到活動對目標(biāo)函數(shù)的貢獻與活動水平不成比例關(guān)系的情形，即目標(biāo)函數(shù)不是決策變量的線性函數(shù)，而是二次非線性函數(shù)，我們可以利用K-T 條件并轉(zhuǎn)化為等價求解相應(yīng)的線性規(guī)劃問題。經(jīng)過分析可以得到結(jié)論，目標(biāo)函數(shù)變成了線性函數(shù)，但約束函數(shù)中有一個非線性函數(shù)，這時問題仍然

2、是非線性的。應(yīng)用Excel 規(guī)劃求解工具解這個模型后我們知道如果投資者愿意承擔(dān)多一點的風(fēng)險，就可以獲得更大的收益。關(guān)鍵詞： 非線性規(guī)劃，線性規(guī)劃，目標(biāo)函數(shù)，決策變量，模型中圖分類： O226文獻標(biāo)識： A0 引言非線性規(guī)劃是運籌學(xué)的一個重要分支，它在管理科學(xué)、系統(tǒng)控制等諸多領(lǐng)域有廣泛應(yīng)用。非線性規(guī)劃的任一算法都不能僅僅考察可行域極點的目標(biāo)函數(shù)值來尋優(yōu)。非線性規(guī)劃的最優(yōu)點可能在其可行域的任一點達到，即最優(yōu)解可能在極點，或邊介點或內(nèi)點達到。在非線性規(guī)劃問題中，其變量取值受到多個約束條件的限制，對其求解，一方面要使目標(biāo)函數(shù)每次選代要逐次下降，且還要保持解的可行性。這就給尋找最優(yōu)解帶來更大的困難。為使

3、求解能較順利進行，一般采用將約束條件轉(zhuǎn)化為無約束條件，化為較簡單問題來處理 1 。1 預(yù)備知識1.1相關(guān)概念 , 相關(guān)定理若 x 0 使得 g j x 00 則稱此約束條件是x0 的不起作用約束； 起作用約束： 若 x0使得 g jx 00 ，則稱此約束條件是x 0的起作用約束 2 ?？尚蟹较颍喝?x 0Rx | g jx0j 1,2,L, PE n ,00 的實數(shù)，使得0,0 ，均有 x 0P R ，則稱方向P 是 x0 的一個可行方向；當(dāng)g j x 0T P0jJ , P 必為 x0 的一個可行方向；下降方向： 若 x0RPE n ,00 使得0, 0 均有 f x0Pfx0，則稱 P 為

4、 x0的一 個 下 降 方 向 。 當(dāng) g jx0 T P0P 必 為 x0 的 下 降 方 向 ； 可 行 下 降 方 向 ： 若 x0R又g jx0 TP 0且g j x0 TP0jJ ,則稱 P 是 x0 的可行下降方向 3相關(guān)定理，若 x*是非線性規(guī)劃的一個局部極小點，目標(biāo)函數(shù)fx 在 x* 可微，且 g j x jJ 在 x* 處可微，又 g j x jJ處連續(xù)，則在x*點不存在可行下降方向，則不存在P 同時滿足f x*TP0且g jx0 TP 0jJ.1.1.1K-T條件x*，且 x*若非線性規(guī)劃有極小點點與各起作用約束的梯度線性無關(guān)，則存在r1,r2 ,rL 使下Lr j *f

5、x*g j x*0j1述條件成立4 ： r j*g j x*0j1,2, Lr j*0j1,2, L或可改寫為：若 x*是 非 線 性 規(guī) 劃 的 極 小 點 ， 且 x*點所起作用的約束梯度g j x*jJ線性無關(guān)，則存在向量*1*, 2* , , m* 和 *r1* , r2* ,m*L*f x*g jx*0ihi xr jj 1j1r j*g jx*0j1,2, Lr j*0j1,2, L1.1.2例如利用 K-T條件求解min fxx 11 2x 2x1x 22x 20可以把上式改寫成以下形式min f xx 11 2x 2g1 xx1x 22 0因 為 f x T2x1 2 ,1g1

6、 x Tg2xx 20K-T條件如下2f x *rj *g j x*0j 1rj* g j x *0j1,2rj*0j1,2hi x * i1,2, m和,r L * 使得下述條件成立51, 1g2 x T0 ,12x1*2*1*001r11r210則有r1*x1*x*22 0r2* x *20r1*0r2*02x1*r1*20r1*r2*10即r1*x1*x2*2 0（1）r2* x2*0r1*0 r2*0考慮下面幾種情況：1) r1*0 , r2*0因 為r2*0 由上式知 x *20因為r1*0 由上式 知 x1*x*22 0x1*2因為x1*2，代入得 r1*2與 r1*0矛盾.2)r

7、1*0 ,r2*0因為r2*0由(1)式知r1*1與r1*0矛盾.3)r1*r2*0不滿足（1）式的條件 .*0因為*0代入得*04) r10 , r2r2（1） x 2把r1*0，r2*0，代入 (1)得 r2*1.x1*1.所以x*1，0T滿足條件。由f x22, g1x x1 x2 2,，K Tx1 1x2g1xx均為凸函 數(shù)，所 以該非 線性規(guī)問 題為凸規(guī) 劃。因此x*， T是全局最優(yōu)21 0解，此時0min f x2 二次規(guī)劃求解方法2.1二次規(guī)劃轉(zhuǎn)化問題探討目標(biāo)函數(shù)為二次函數(shù)，約束均用線性形式給出的非線性規(guī)劃問題稱為二次規(guī)劃，二次規(guī)劃求解方法較多，下面介紹利用K-T 條件并轉(zhuǎn)化為等

8、價求解相應(yīng)的線性規(guī)劃問題的方法6,7 。設(shè)二次規(guī)劃問題min f x1xTCXCT X2（ 2）AXb0s.t.0X其中 x x1 , x2 , xnT ,CCij 為n 維正定或半正定矩陣。 b b1 bmT Aaij mxn。式（ 2）等價表述為min fx1nnC jkX j X knX j2 j 1C jk 1j1naijX j bi0i1,2, mj 1X j0j1,2, nC11C1 jC1nX 1C1其中， C jkCkj ,k1,2,n 。因為f xC j1C jjC jnX jC jC n1C njC nnX nC n0令g j xx j0, j1,2, ng j x1第 j

9、 行j1,2,n0n令gn i xXn iaij X jbi0, j1,2, nj 1ai1g n ixaijain據(jù) K-T 條件nmf xr j g j xrn i gn i x 0j 1i 1有C11C1 jC1nX 1C1100C j1C jjC jnX jC jr1 0r j1rn 0Cn1CnjCnnX nCn001a11ai1am1rn 1a1 jrn i aijrn m amja1nainamn整理得nmC jk X kC j r jaij rn i0j 1,2, ,nk 1i 1又r j * g j x0,j1,2, n, n1, nm有x j r j0,j1,2, n, n

10、1, nmx j0,r j0,j1,2, n, n1, nm求nmC jkX kaij rn ir jC jj1,2, ,nk 1i1naijX jX n ibi0i1,2, mi 1x j r j0j1,2,n1, nmx j0r j 0j1,2, n1, nm所得解為原二次規(guī)劃的解.為了求解 (3)，可引進輔助規(guī)劃如下nminYyjj1mnaij rnir jC jk X k sgn C j y jC jj 1,2, , ni1k1naij xjxnibi 0i1,2,mj1x j0,r j0j1,2,n1,y j0j1,2, nx j r j0j1,2, n1,若求得最優(yōu)解x1* , x

11、2* , xn m* , r1* , r2* , , rn m* , y1 0, y2 0, , yn 0則 x1* , x2* , xn * 為 原二 次 規(guī) 劃 問 題的優(yōu)最解 8 9。(3),nm(4), nm2.2 股票投資問題一個投資者考慮將其資金投入到三支股票中去，這三支股票是：河南科技、北方通訊、南方交通。通過市場分析和統(tǒng)計預(yù)測，他整理出有關(guān)數(shù)據(jù)，如表所示表 1三支股票五年的收益率和和五年的協(xié)方差股票名稱五年期望收益率（ %）五年協(xié)方差（ %平方）河南科技北方通訊南方交通河南科技9218036110北方通訊6436120-30南方交通41110-30140這個投資者想要將投資組合

12、中股票收益的標(biāo)準差最小化以降低投資風(fēng)險，并希望五年后的期望收益率要達到 65%以上。下面我們來分析一下這個問題。設(shè) H、 N、 S 分別表示投資者將其資金投入到河南科技、北方通訊、南方交通三支股票中的比例，那么這個問題可以描述為：最小標(biāo)準差滿足如下約束：1） 比例： H+N+S=1.02） 目標(biāo)收益 :0.92H+0.64N+0.41S 0.653） 非負約束 :H,N,S 0目標(biāo)是將標(biāo)準差最小化,再加上三個約束條件,第一個約束是指投資者所投資的各個股票的比例之和必須是1；第二個約束是指這個投資組合五年的投資收益率至少要有65%；第三個約束是指對每支股票的投資比例不可能是負數(shù)。下面我們將這個模

13、型未完成的部分也就是目標(biāo)函數(shù)分析一下，以便完成這個模型。令隨機變量R 、R、R 分別為河南科技、北方通訊、南方交通三支股票五年的投資收益率，那么投資組合在五年期HNS的收益率 R 為RHRHNRNSRS我們應(yīng)用上面這一等式來求投資組合的方差，可得Var R H 2Var RHN 2Var RN S2Var RS2HNCov RH , RN2HSCov RH , RS2NSCov RN , RS將表中的數(shù)據(jù)代入此式得方差 =180H 2120N 2140S272HN220HS 60NS所以投資組合的標(biāo)準差為：標(biāo)準差 =180H 2120N 2140S272HN220HS60NS將這一表達式代入前

14、面的模型中，得到此問題完整的數(shù)學(xué)模型為min180H 2120N 2140S272HN220HS60NSHNS1.0s.t. 0.92H0.64N0.41S0.65H ,N,S0注意這個問題的約束是三個決策變量的線性函數(shù)，而且目標(biāo)函數(shù)則是非線性的，我們可以用劃求解來解這個模型。求解后得到計算結(jié)果是：購買河南科技23.51% 、北方通訊52.22% 、南方交通標(biāo)準差是8.04%。從另一方面考慮，投資者可能想使收益最大化，而讓表示風(fēng)險的標(biāo)準差的大小作為約束，比如說，讓標(biāo)準差最大不超過12%，那么最優(yōu)化問題變?yōu)镋xcel 規(guī)24.27% ，max 0.92 H0.64N0.41SHNS1.0s.t.

15、180H 2H,N,S120N02140S272 HN220HS60NS12這時 ,目標(biāo)函數(shù)變成了線性函數(shù)，但約束函數(shù)中有一個非線性函數(shù)，這時問題仍然是非線性的。應(yīng)用 Excel 規(guī)劃求解工具解這個模型后我們知道如果投資者愿意承擔(dān)多一點的風(fēng)險，就可以獲得更大的收益，根據(jù)結(jié)果可知，投資者將其85.93%的資金投入到河南科技中、將14.07%的資金投入到北方通訊中、不購買南方交通的股票，可在一定風(fēng)險下獲得最大收益率，最大收益率為88.06%.3 結(jié)束語經(jīng)過分析可以得到結(jié)論，對于非線性規(guī)劃問題,其變量取值受到多個約束條件的限制,對其求解 ,一方面要使目標(biāo)函數(shù)每次選代要逐次下降，且還要保持解的可行性。

16、這就給尋找最優(yōu)解帶來更大的困難。為使求解能順利進行，一般采用約束條件轉(zhuǎn)化為無約束條件，化為較簡單問題來處理。參考文獻 :1 張維迎 . 博弈論與信息經(jīng)濟學(xué) .上海 :上海人民出版社 ,1996.2 鄧成梁 .運籌學(xué)的原理和方法 .武漢 : 華中理工大學(xué)出版社 ,19963 謝識予 .經(jīng)濟博弈論 .上海 :復(fù)旦大學(xué)出版社 ,20024 韓伯棠 .管理運籌學(xué) .北京 :清華大學(xué)出版社,20005 施錫銓 .博弈論 .上海 :上海財經(jīng)大學(xué)出版社 ,2002.6王周宏，王能超， 鐘毅芳 . 求解一般半正定二次規(guī)劃的數(shù)值穩(wěn)定方法J. 華中科技大學(xué)學(xué)報：自然科學(xué)版， 2002，24（ 4）：203-205

17、.7滕召波，張世永，陳華富，何光中 . 非線性規(guī)劃一般約束條件的SQP 方法 J. 電子科技大學(xué)學(xué)報， 2001 ，35（ 1）： 123-126.8劉綱，黃宗明 . 一種基于動態(tài)序列二次規(guī)劃的模型修正修正方法J. 重慶大學(xué)學(xué)報， 2008， 31（ 1）：107-109.9李輝，丁樺 . 結(jié)構(gòu)動力模型修正方法研究進展J. 力學(xué)進展， 2005， 35（ 2）： 170-180.Quadratic programming solution method is discussedLiJiZhao 1 LiuYiShan 2(1. Pingdingshan industry vocational

18、college culture ministry of education 1 henan pingdingshan; 4670012. Pingdingshan industry vocational college culture ministry of education 2 henan pingdingshan 467001)Abstract: the article's purpose is to make the two times the basic theory of nonlinear programming model and algorithm are popul

19、arized and applied. In linear programming model, the activities of the objective function and activity level of contribution proportional relation, thus the objective function is the decisionvariables linear function, and in the actual problem, often meet activities on the objective function of thecontribution and activity level disproportionate to the circumstances of the relationship, that is, t