二次规划求解方法探讨

1、二次规划求解方法探讨李骥昭 1刘义山 2(1.平顶山工业职业技术学院文化教育部1河南平顶山 467001;2.平顶山工业职业技术学院文化教育部2河南平顶山 467001)摘要： 文章推广与应用了二次非线性规划模型的基础理论及算法。在线性规划模型中，活动对目标函数的贡献与活动水平成比例关系，因而目标函数是决策变量的线性函数，而在实际问题中，往往遇到活动对目标函数的贡献与活动水平不成比例关系的情形，即目标函数不是决策变量的线性函数，而是二次非线性函数，我们可以利用K-T 条件并转化为等价求解相应的线性规划问题。经过分析可以得到结论，目标函数变成了线性函数，但约束函数中有一个非线性函数，这时问题仍然

2、是非线性的。应用Excel 规划求解工具解这个模型后我们知道如果投资者愿意承担多一点的风险，就可以获得更大的收益。关键词： 非线性规划，线性规划，目标函数，决策变量，模型中图分类： O226文献标识： A0 引言非线性规划是运筹学的一个重要分支，它在管理科学、系统控制等诸多领域有广泛应用。非线性规划的任一算法都不能仅仅考察可行域极点的目标函数值来寻优。非线性规划的最优点可能在其可行域的任一点达到，即最优解可能在极点，或边介点或内点达到。在非线性规划问题中，其变量取值受到多个约束条件的限制，对其求解，一方面要使目标函数每次选代要逐次下降，且还要保持解的可行性。这就给寻找最优解带来更大的困难。为使

3、求解能较顺利进行，一般采用将约束条件转化为无约束条件，化为较简单问题来处理 1 。1 预备知识1.1相关概念 , 相关定理若 x 0 使得 g j x 00 则称此约束条件是x0 的不起作用约束； 起作用约束： 若 x0使得 g jx 00 ，则称此约束条件是x 0的起作用约束 2 。可行方向：若 x 0Rx | g jx0j 1,2,L, PE n ,00 的实数，使得0,0 ，均有 x 0P R ，则称方向P 是 x0 的一个可行方向；当g j x 0T P0jJ , P 必为 x0 的一个可行方向；下降方向： 若 x0RPE n ,00 使得0, 0 均有 f x0Pfx0，则称 P 为

4、 x0的一 个 下 降 方 向 。 当 g jx0 T P0P 必 为 x0 的 下 降 方 向 ； 可 行 下 降 方 向 ： 若 x0R又g jx0 TP 0且g j x0 TP0jJ ,则称 P 是 x0 的可行下降方向 3相关定理，若 x*是非线性规划的一个局部极小点，目标函数fx 在 x* 可微，且 g j x jJ 在 x* 处可微，又 g j x jJ处连续，则在x*点不存在可行下降方向，则不存在P 同时满足f x*TP0且g jx0 TP 0jJ.1.1.1K-T条件x*，且 x*若非线性规划有极小点点与各起作用约束的梯度线性无关，则存在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*是 非 线 性 规 划 的 极 小 点 ， 且 x*点所起作用的约束梯度g j x*jJ线性无关，则存在向量*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均为凸函 数，所 以该非 线性规问 题为凸规 划。因此x*， T是全局最优21 0解，此时0min f x2 二次规划求解方法2.1二次规划转化问题探讨目标函数为二次函数，约束均用线性形式给出的非线性规划问题称为二次规划，二次规划求解方法较多，下面介绍利用K-T 条件并转化为等

8、价求解相应的线性规划问题的方法6,7 。设二次规划问题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据 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所得解为原二次规划的解.为了求解 (3)，可引进辅助规划如下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,若求得最优解x1* , x

11、2* , xn m* , r1* , r2* , , rn m* , y1 0, y2 0, , yn 0则 x1* , x2* , xn * 为 原二 次 规 划 问 题的优最解 8 9。(3),nm(4), nm2.2 股票投资问题一个投资者考虑将其资金投入到三支股票中去，这三支股票是：河南科技、北方通讯、南方交通。通过市场分析和统计预测，他整理出有关数据，如表所示表 1三支股票五年的收益率和和五年的协方差股票名称五年期望收益率（ %）五年协方差（ %平方）河南科技北方通讯南方交通河南科技9218036110北方通讯6436120-30南方交通41110-30140这个投资者想要将投资组合

12、中股票收益的标准差最小化以降低投资风险，并希望五年后的期望收益率要达到 65%以上。下面我们来分析一下这个问题。设 H、 N、 S 分别表示投资者将其资金投入到河南科技、北方通讯、南方交通三支股票中的比例，那么这个问题可以描述为：最小标准差满足如下约束：1） 比例： H+N+S=1.02） 目标收益 :0.92H+0.64N+0.41S 0.653） 非负约束 :H,N,S 0目标是将标准差最小化,再加上三个约束条件,第一个约束是指投资者所投资的各个股票的比例之和必须是1；第二个约束是指这个投资组合五年的投资收益率至少要有65%；第三个约束是指对每支股票的投资比例不可能是负数。下面我们将这个模

13、型未完成的部分也就是目标函数分析一下，以便完成这个模型。令随机变量R 、R、R 分别为河南科技、北方通讯、南方交通三支股票五年的投资收益率，那么投资组合在五年期HNS的收益率 R 为RHRHNRNSRS我们应用上面这一等式来求投资组合的方差，可得Var R H 2Var RHN 2Var RN S2Var RS2HNCov RH , RN2HSCov RH , RS2NSCov RN , RS将表中的数据代入此式得方差 =180H 2120N 2140S272HN220HS 60NS所以投资组合的标准差为：标准差 =180H 2120N 2140S272HN220HS60NS将这一表达式代入前

14、面的模型中，得到此问题完整的数学模型为min180H 2120N 2140S272HN220HS60NSHNS1.0s.t. 0.92H0.64N0.41S0.65H ,N,S0注意这个问题的约束是三个决策变量的线性函数，而且目标函数则是非线性的，我们可以用划求解来解这个模型。求解后得到计算结果是：购买河南科技23.51% 、北方通讯52.22% 、南方交通标准差是8.04%。从另一方面考虑，投资者可能想使收益最大化，而让表示风险的标准差的大小作为约束，比如说，让标准差最大不超过12%，那么最优化问题变为Excel 规24.27% ，max 0.92 H0.64N0.41SHNS1.0s.t.

15、180H 2H,N,S120N02140S272 HN220HS60NS12这时 ,目标函数变成了线性函数，但约束函数中有一个非线性函数，这时问题仍然是非线性的。应用 Excel 规划求解工具解这个模型后我们知道如果投资者愿意承担多一点的风险，就可以获得更大的收益，根据结果可知，投资者将其85.93%的资金投入到河南科技中、将14.07%的资金投入到北方通讯中、不购买南方交通的股票，可在一定风险下获得最大收益率，最大收益率为88.06%.3 结束语经过分析可以得到结论，对于非线性规划问题,其变量取值受到多个约束条件的限制,对其求解 ,一方面要使目标函数每次选代要逐次下降，且还要保持解的可行性。

16、这就给寻找最优解带来更大的困难。为使求解能顺利进行，一般采用约束条件转化为无约束条件，化为较简单问题来处理。参考文献 :1 张维迎 . 博弈论与信息经济学 .上海 :上海人民出版社 ,1996.2 邓成梁 .运筹学的原理和方法 .武汉 : 华中理工大学出版社 ,19963 谢识予 .经济博弈论 .上海 :复旦大学出版社 ,20024 韩伯棠 .管理运筹学 .北京 :清华大学出版社,20005 施锡铨 .博弈论 .上海 :上海财经大学出版社 ,2002.6王周宏，王能超， 钟毅芳 . 求解一般半正定二次规划的数值稳定方法J. 华中科技大学学报：自然科学版， 2002，24（ 4）：203-205

17、.7滕召波，张世永，陈华富，何光中 . 非线性规划一般约束条件的SQP 方法 J. 电子科技大学学报， 2001 ，35（ 1）： 123-126.8刘纲，黄宗明 . 一种基于动态序列二次规划的模型修正修正方法J. 重庆大学学报， 2008， 31（ 1）：107-109.9李辉，丁桦 . 结构动力模型修正方法研究进展J. 力学进展， 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