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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上二次規(guī)劃求解方法探討 李驥昭1 劉義山2(1.平頂山工業(yè)職業(yè)技術(shù)學(xué)院文化教育部1 河南 平頂山 ; 2.平頂山工業(yè)職業(yè)技術(shù)學(xué)院文化教育部2 河南 平頂山 )摘要：文章推廣與應(yīng)用了二次非線性規(guī)劃模型的基礎(chǔ)理論及算法。在線性規(guī)劃模型中，活動對目標(biāo)函數(shù)的貢獻(xiàn)與活動水平成比例關(guān)系，因而目標(biāo)函數(shù)是決策變量的線性函數(shù)，而在實際問題中，往往遇到活動對目標(biāo)函數(shù)的貢獻(xiàn)與活動水平不成比例關(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 文獻(xiàn)標(biāo)識：A0 引言非線性規(guī)劃是運籌學(xué)的一個重要分支，它在管理科學(xué)、系統(tǒng)控制等諸多領(lǐng)域有廣泛應(yīng)用。非線性規(guī)劃的任一算法都不能僅僅考察可行域極點的目標(biāo)函數(shù)值來尋優(yōu)。非線性規(guī)劃的最優(yōu)點可能在其可行域的任一點達(dá)到，即最優(yōu)解可能在極點，或邊介點或內(nèi)點達(dá)到。在非線性規(guī)劃問題中，其變量取值受到多個約束條件的限制，對其求解，一方面要使目標(biāo)函數(shù)每次選代要逐次下降，且還要保持解的可行性。這就給尋找最優(yōu)解帶來更大的困難。為

3、使求解能較順利進行，一般采用將約束條件轉(zhuǎn)化為無約束條件，化為較簡單問題來處理1。1 預(yù)備知識1.1 相關(guān)概念,相關(guān)定理若使得則稱此約束條件是的不起作用約束；起作用約束：若使得，則稱此約束條件是的起作用約束2?？尚蟹较颍喝舻膶崝?shù)，使得，均有，則稱方向P是的一個可行方向；當(dāng)必為的一個可行方向；下降方向：若使得均有，則稱P為的一個下降方向。當(dāng)必為的下降方向；可行下降方向：若又且則稱P是的可行下降方向3相關(guān)定理，若是非線性規(guī)劃的一個局部極小點，目標(biāo)函數(shù)在可微，且在處可微，又處連續(xù)，則在點不存在可行下降方向，則不存在P同時滿足且1.1.1 K-T 條件若非線性規(guī)劃有極小點，且點與各起作用約束的梯度線性無

4、關(guān)，則存在使下述條件成立4：或可改寫為：若是非線性規(guī)劃的極小點，且點所起作用的約束梯度和線性無關(guān)，則存在向量和使得下述條件成立51.1.2 例如利用K-T 條件求解可以把上式改寫成以下形式K-T 條件如下則有 即 考慮下面幾種情況：2 二次規(guī)劃求解方法2.1 二次規(guī)劃轉(zhuǎn)化問題探討目標(biāo)函數(shù)為二次函數(shù)，約束均用線性形式給出的非線性規(guī)劃問題稱為二次規(guī)劃，二次規(guī)劃求解方法較多，下面介紹利用K-T條件并轉(zhuǎn)化為等價求解相應(yīng)的線性規(guī)劃問題的方法6,7。設(shè)二次規(guī)劃問題 （2） 其中維正定或半正定矩陣。式（2）等價表述為 其中，。因為令 令 據(jù)K-T條件 有整理得又有求所得解為原二次規(guī)劃的解.為了求解(3)，可

5、引進輔助規(guī)劃如下若求得最優(yōu)解2.2股票投資問題一個投資者考慮將其資金投入到三支股票中去，這三支股票是：河南科技、北方通訊、南方交通。通過市場分析和統(tǒng)計預(yù)測，他整理出有關(guān)數(shù)據(jù)，如表所示 表1 三支股票五年的收益率和和五年的協(xié)方差 股票名稱五年期望收益率（%） 五年協(xié)方差（%平方）河南科技北方通訊南方交通河南科技北方通訊南方交通9264411803611036120-30110-30140這個投資者想要將投資組合中股票收益的標(biāo)準(zhǔn)差最小化以降低投資風(fēng)險，并希望五年后的期望收益率要達(dá)到65%以上。下面我們來分析一下這個問題。設(shè)H、N、S分別表示投資者將其資金投入到河南科技、北方通訊、南方交通三支股票中

6、的比例，那么這個問題可以描述為：最小標(biāo)準(zhǔn)差滿足如下約束：1） 比例：H+N+S=1.02） 目標(biāo)收益:0.92H+0.64N+0.41S0.653） 非負(fù)約束:H,N,S0目標(biāo)是將標(biāo)準(zhǔn)差最小化,再加上三個約束條件,第一個約束是指投資者所投資的各個股票的比例之和必須是1；第二個約束是指這個投資組合五年的投資收益率至少要有65%；第三個約束是指對每支股票的投資比例不可能是負(fù)數(shù)。下面我們將這個模型未完成的部分也就是目標(biāo)函數(shù)分析一下，以便完成這個模型。令隨機變量分別為河南科技、北方通訊、南方交通三支股票五年的投資收益率，那么投資組合在五年期的收益率R為 我們應(yīng)用上面這一等式來求投資組合的方差，可得將表

7、中的數(shù)據(jù)代入此式得方差=所以投資組合的標(biāo)準(zhǔn)差為：標(biāo)準(zhǔn)差=將這一表達(dá)式代入前面的模型中，得到此問題完整的數(shù)學(xué)模型為注意這個問題的約束是三個決策變量的線性函數(shù)，而且目標(biāo)函數(shù)則是非線性的，我們可以用Excel規(guī)劃求解來解這個模型。求解后得到計算結(jié)果是：購買河南科技23.51%、北方通訊52.22%、南方交通24.27%，標(biāo)準(zhǔn)差是8.04%。從另一方面考慮，投資者可能想使收益最大化，而讓表示風(fēng)險的標(biāo)準(zhǔn)差的大小作為約束，比如說，讓標(biāo)準(zhǔn)差最大不超過12%，那么最優(yōu)化問題變?yōu)?這時,目標(biāo)函數(shù)變成了線性函數(shù)，但約束函數(shù)中有一個非線性函數(shù)，這時問題仍然是非線性的。應(yīng)用Excel規(guī)劃求解工具解這個模型后我們知道如

8、果投資者愿意承擔(dān)多一點的風(fēng)險，就可以獲得更大的收益，根據(jù)結(jié)果可知，投資者將其85.93%的資金投入到河南科技中、將14.07%的資金投入到北方通訊中、不購買南方交通的股票，可在一定風(fēng)險下獲得最大收益率，最大收益率為88.06%.3 結(jié)束語 經(jīng)過分析可以得到結(jié)論，對于非線性規(guī)劃問題,其變量取值受到多個約束條件的限制,對其求解,一方面要使目標(biāo)函數(shù)每次選代要逐次下降，且還要保持解的可行性。這就給尋找最優(yōu)解帶來更大的困難。為使求解能順利進行，一般采用約束條件轉(zhuǎn)化為無約束條件，化為較簡單問題來處理。參考文獻(xiàn): 1 張維迎. 博弈論與信息經(jīng)濟學(xué).上海:上海人民出版社,1996.2 鄧成梁.運籌學(xué)的原理和方

9、法.武漢:華中理工大學(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.7 滕召波，張世永，陳華富，何光中. 非線性規(guī)劃一般約束條件的SQP方法J. 電子科技大學(xué)學(xué)報，2001，35（1）：123-126.8 劉綱，黃宗明. 一種基于動態(tài)序列二次規(guī)劃的模型修正修正方法J. 重慶大學(xué)學(xué)報，2008，31（1）：107-109.9

10、李輝，丁樺. 結(jié)構(gòu)動力模型修正方法研究進展J. 力學(xué)進展，2005，35（2）：170-180.Quadratic programming solution method is discussedLiJiZhao 1 LiuYiShan 2(1. Pingdingshan industry vocational college culture ministry of education 1 henan pingdingshan; 2. Pingdingshan industry vocational college culture ministry of education 2 henan p

11、ingdingshan )Abstract: the articles purpose is to make the two times the basic theory of nonlinear programming model and algorithm are popularized and applied. In linear programming model, the activities of the objective function and activity level of contribution proportional relation, thus the obj

12、ective function is the decision variables linear function, and in the actual problem, often meet activities on the objective function of the contribution and activity level disproportionate to the circumstances of the relationship, that is, the objective function is not the decision variables linear

13、 function, but second nonlinear function, we can use K-T conditions and translated into equivalent to solve the corresponding linear programming problem. After analysis can come to the conclusion, the objective function into linear function, but constraint function has a nonlinear function, and then problems still is non-linear. Application programming solver tool Excel solution this mod