二次规划求解方法探讨

二次规划求解方法探讨李骥昭1刘义山2(1.平顶山工业职业技术学院文化教育部1河南平顶山467001;2.平顶山工业职业技术学院文化教育部2河南平顶山467001)摘要：文章推广与应用了二次非线性规划模型的基础理论及算法。在线性规划模型中，活动对目标函数的贡献与活动水平成比例关系，因而目标函数是决策变量的线性函数，而在实际问题中，往往遇到活动对目标函数的贡献与活动水平不成比例关系的情形，即目标函数不是决策变量的线性函数，而是二次非线性函数，我们可以利用K-T条件并转化为等价求解相应的线性规划问题。经过分析可以得到结论，目标函数变成了线性函数，但约束函数中有一个非线性函数，这时问题仍然是非线性的。应用Excel规划求解工具解这个模型后我们知道如果投资者愿意承担多一点的风险，就可以获得更大的收益。关键词：非线性规划，线性规划，目标函数，决策变量，模型中图分类：O226文献标识：A0引言非线性规划是运筹学的一个重要分支，它在管理科学、系统控制等诸多领域有广泛应用。非线性规划的任一算法都不能仅仅考察可行域极点的目标函数值来寻优。非线性规划的最优点可能在其可行域的任一点达到，即最优解可能在极点，或边介点或内点达到。在非线性规划问题中，其变量取值受到多个约束条件的限制，对其求解，一方面要使目标函数每次选代要逐次下降，且还要保持解的可行性。这就给寻找最优解带来更大的困难。为使求解能较顺利进行，一般采用将约束条件转化为无约束条件，化为较简单问题来处理[1]。1预备知识1.1相关概念,相关定理若0x使得00xgj则称此约束条件是0x的不起作用约束；起作用约束：若0x使得00xgj，则称此约束条件是0x的起作用约束[2]。可行方向：若0,,,,2,10|00njEPLjxgxRx的实数，使得0,0，均有RPx0，则称方向P是0x的一个可行方向；当PJjPxgTj,00必为0x的一个可行方向；下降方向：若0,00nEPRx使得0,0均有00xfPxf，则称P为0x的一个下降方向。当PPxgTj00必为0x的下降方向；可行下降方向：若Rx0又00PxgTj且,00JjPxgTj则称P是0x的可行下降方向[3]相关定理，若*x是非线性规划的一个局部极小点，目标函数xf在*x可微，且Jjxgj在*x处可微，又Jjxgj处连续，则在*x点不存在可行下降方向，则不存在P同时满足0*PxfT且.00JjPxgTj1.1.1K-T条件若非线性规划有极小点*x，且*x点与各起作用约束的梯度线性无关，则存在**2*1*,,,Lrrr使下述条件成立[4]：LjrLjxgrxgrxfjjjjLjj,,2,10,,2,100****1**或可改写为：若*x是非线性规划的极小点，且*x点所起作用的约束梯度mixhi,,2,1*和Jjxgj*线性无关，则存在向量**2*1*,,,m和**2*1*,,,Lrrr使得下述条件成立[5]LjrLjxgrxgrxhxfjjjjLjjimji,,2,10,,2,100****1**1**1.1.2例如利用K-T条件求解0x2xxx1xxfmin221221可以把上式改写成以下形式1,0xg1,1xg1,2x2xf0xxg02xxxgx1xxfminT2T11T22211221因为K-T条件如下2,1j0r2,1j0xgr0xgrxf*j*j*j*j21j*j*则有0r0r0xr02xxr0010r11r12x2*2*1*2*2*2*1*1*2*1*1即）（rrxrxxrrrrx10000201022*2*1*2*2*2*1*1*2*1*1*1考虑下面几种情况：.0r2r，2x2x02xx0r0x0r0r,0r)1*1*1*1*1*2*1*1*2*2*2*1矛盾与得代入因为由上式知因为由上式知因为.0r1r)1(0r0r,0r)2*1*1*2*2*1矛盾与式知由因为.）1（0rr)3*2*1式的条件不满足.1x.1r)1(，0r，0r0x）1（0r0r,0r)4*1*2*2*1*2*2*2*1得代入把得代入因为0min01,2,2101*21211221*xf，，x。，xxgxxxgxxxf。TK，，xTT此时解是全局最优因此为规划所以该非线性规问题凸均为凸函数由条件满足所以2二次规划求解方法2.1二次规划转化问题探讨目标函数为二次函数，约束均用线性形式给出的非线性规划问题称为二次规划，二次规划求解方法较多，下面介绍利用K-T条件并转化为等价求解相应的线性规划问题的方法[6,7]。设二次规划问题00..21minXbAXtsXCCXxxfTT（2）其中nCCxxxxijTn为,,,,21维正定或半正定矩阵。mxnijTmaAbbb1。式（2）等价表述为njXmibXaXCXXCxfjijnjijnjjjkjnjnkjk,,2,10,,2,1021min1111其中，nkCCkjjk,,2,1,。因为njnjnnnjnjnjjjnjCCCXXXCCCCCCCCCxf11111111令njxxgjj,,2,1,0njjxgj,,2,1010行第令njbXaXxgijnjijinin,,2,1,01inijiinaaaxg1据K-T条件011xgrxgrxfinmiinjnjj有mnmjmmninijiinnjnnjnjnjnnnjnjnjjjnjaaaraaaraaarrrrCCCXXXCCCCCCCCC1111111111111111100010001整理得njrarCXCmiinijjjnkkjk,,2,1011又mnnnjxgrjj,,1,,,2,1,0*有mnnnjrxjj,,1,,,2,1,0mnnnjrxjj,,1,,,2,1,0,0求)3(,,1,,2,100,,1,,2,10,,2,10,,2,1111mnnjrxmnnjrxmibXXanjCrraXCjjjjiinjniijjjinmiijnkkjk所得解为原二次规划的解.为了求解(3)，可引进辅助规划如下njjyY1min)4(,,1,,2,10,,2,10,,1,,2,10,0,,2,10,,2,1sgn111mnnjrxnjymnnjrxmibxxanjCyCXCrrajjjjjiinjnjijjjjknkjkmijinij若求得最优解。xxxyyyrrrxxxnnmnmn]98[**2*121**2*1**2*1,,,0,,0,0,,,,,,,,优解为原二次规划问题的最则2.2股票投资问题一个投资者考虑将其资金投入到三支股票中去，这三支股票是：河南科技、北方通讯、南方交通。通过市场分析和统计预测，他整理出有关数据，如表所示表1三支股票五年的收益率和和五年的协方差股票名称五年期望收益率（%）五年协方差（%平方）河南科技北方通讯南方交通河南科技北方通讯南方交通9264411803611036120-30110-30140这个投资者想要将投资组合中股票收益的标准差最小化以降低投资风险，并希望五年后的期望收益率要达到65%以上。下面我们来分析一下这个问题。设H、N、S分别表示投资者将其资金投入到河南科技、北方通讯、南方交通三支股票中的比例，那么这个问题可以描述为：最小标准差满足如下约束：1）比例：H+N+S=1.02）目标收益:0.92H+0.64N+0.41S≥0.653）非负约束:H,N,S≥0目标是将标准差最小化,再加上三个约束条件,第一个约束是指投资者所投资的各个股票的比例之和必须是1；第二个约束是指这个投资组合五年的投资收益率至少要有65%；第三个约束是指对每支股票的投资比例不可能是负数。下面我们将这个模型未完成的部分也就是目标函数分析一下，以便完成这个模型。令随机变量SNH、R、RR分别为河南科技、北方通讯、南方交通三支股票五年的投资收益率，那么投资组合在五年期的收益率R为SNHSRNRHRR我们应用上面这一等式来求投资组合的方差，可得SNSHNHSNHRRNSCovRRHSCovRRHNCovRVarSRVarNRVarHRVar,2,2,2222将表中的数据代入此式得方差=NSHSHNSNH6022072140120180222所以投资组合的标准差为：标准差=NSHSHNSNH6022072140120180222将这一表达式代入前面的模型中，得到此问题完整的数学模型为NSHSHNSNH6022072140120180min2220,,65.041.064.092.00.1..SNHSNHSNHts注意这个问题的约束是三个决策变量的线性函数，而且目标函数则是非线性的，我们可以用Excel规划求解来解这个模型。求解后得到计算结果是：购买河南科技23.51%、北方通讯52.22%、南方交通24.27%，标准差是8.04%。从另一方面考虑，投资者可能想使收益最大化，而让表示风险的标准差的大小作为约束，比如说，让标准差最大不超过12%，那么最优化问题变为SNH41.064.092.0max0,,1260220721401201800.1..222SNHNSHSHNSNHSNHts这时,目标函数变成了线性函数，但约束函数中有一个非线性函数，这时问题仍然是非线性的。应用Excel规划求解工具解这个模型后我们知道如果投资者愿意承担多一点的风险，就可以获得更大的收益，根据结果可知，投资者将其85.93%的资金投入到河南科技中、将14.07%的资金投入到北方通讯中、不购买南方交通的股票，可在一定风险下获得最大收益率，最大收益率为88.06%.3结束语经过分析可以得到结论，对于非线性规划问题,其变量取值受到多个约束条件的限制,对其求解,一方面要使目标函数每次选代要逐次下降，且还要保持解的可行性。这就给寻