优化模型与LINDO_LINGO优化软件教程_来自清华大学数学科学系数学建模

第十二章非线性规划方法32020年1月7日非线性规划的一般模型；无约束线性规划的求解方法；带约束非线性规划的求解方法；非线性规划的软件求解方法；非线性规划的应用案例分析。一、非线性规划的一般模型42020年1月7日1.引例：股票的组合投资问题一个投资者拟选择Ａ，Ｂ，Ｃ三支业绩好的股票来进行长期组合投资．通过对这三支股票的市场分析和统计预测得到相关数据如下表1所示．52020年1月7日1.引例：股票的组合投资问题表1股票的相关数据表五年的协方差（％）股票名称五年期望收益率（％）ＡＢＣＡＢＣ9264411803611036120-30110-30140试从两个方面分别给出三支股票的投资比例：(1)问题的提出62020年1月7日(１)希望将投资组合中的股票收益的标准差降到最小，以降低投资风险，并希望五年后的期望收益率不少于65%．(２)希望在标准差最大不超过12%的情况下，获得最大的收益．1.引例：股票的组合投资问题(1)问题的提出72020年1月7日1.引例：股票的组合投资问题设123,,xxx分别表示Ａ，Ｂ，Ｃ三支股票的投资比例，其五年的期望收益率分别记为123,,rrr，即为随机变量．五年后投资组合的总收益率为112233Rxrxrxr，表1股票的相关数据表五年的协方差（％）股票名称五年期望收益率（％）ＡＢＣＡＢＣ9264411803611036120-30110-301402.模型的分析82020年1月7日1.引例：股票的组合投资问题2.模型的分析由概率统计的知识,投资组合的方差为222112233121213132323()()()()2(,)2(,)2(,),VarRxVarrxVarrxVarrxxCovrrxxCovrrxxCovrr根据表1中的数据计算得到222123121323()1801201407222060.VarRxxxxxxxxx投资组合的标准差为12222123121323[1801201407222060].Dxxxxxxxxx92020年1月7日问题(１)：根据投资者第(1)项要求，则问题的模型为12222123121323123123123min[1801201407222060];1,s.t.0.920.640.410.65,,,0.Dxxxxxxxxxxxxxxxxxx1.引例：股票的组合投资问题3.模型的建立102020年1月7日1.引例：股票的组合投资问题3.模型的建立根据投资者第（２）项要求，则问题的模型为12312312222123121323123max0.920.640.41;1,s.t.[1801201407222060]12,,,0.Rxxxxxxxxxxxxxxxxxx问题（２）：希望在标准差最大不超过12%的情况下，获得最大的收益．112020年1月7日二.非线性规划的数学模型1.非线性规划问题的一般模型如果问题的目标函数和约束条件中包含有非线性函数，则这样的规划问题称为非线性规划问题。非线性规划的一般模型为ljxxxgmixxxhxxxfnjnin,,2,1,0),,,(,,2,1,0),,,(),,,(min212121（1）122020年1月7日1.非线性规划问题的一般模型若nTnExxxX),,,(21,则模型(1)若目标函数为最大化问题，由)](min[)(maxXfXf，令)()(XfXF，则)(max)(minXfXF；(2)若约束条件为0)(Xgj，则0)(Xgj；(3）0)(0)(0)(XhXhXhiii且。一般模型形式：min()()0,1,2,,jfXgXjm（3）ljXgmiXhXfji,,2,1,0)(,,2,1,0)()(min（2）132020年1月7日（1）无约束的非线性规划当问题无约束条件时，则此问题称为无约束的非线性规划问题。0)(minXXfRX(4)二.非线性规划的数学模型2.非线性规划模型的几种特殊情况（2）二次规划如果目标函数是X的二次函数，约束条件都有是线性的，则称此规划为二次规划.nkjccxmibxaxxcxcXfkjjkjnjijijnjnkkjjknjjj,,2,1,,,0,,2,1,0)(min1111142020年1月7日二.非线性规划的数学模型2.非线性规划模型的几种特殊情况（3）凸规划当模型(3）中的目标函数)(Xf为凸函数，),,2,1)((mjXgj均为凹函数（即)(Xgj为凸函数），则这样的非线性规划称为凸规划。一般模型形式：min()()0,1,2,,jfXgXjm（3）152020年1月7日1.一般迭代法三、无约束非线性规划的解法对问题(4)，给出)(Xf的极小点的初始值)0(X，按某种规律计算出一系列的),2,1()(kXk，希望点列)(kX的极限*X就是)(Xf的一个极小点。0)(minXXfRX（4）??问题：如何来产生这个点列？即如何由一个解向量)(kX求出另一个新的向量解)1(kX？一般迭代法基本思想：1.一般迭代法162020年1月7日实际上：向量)1(kX总可以写成),2,1()()()1(kPXXkkkk其中)(kP为一个向量，k为一个实数，称为步长。实际中各种迭代法就在于寻求不同的k和)(kP，特别是方向)(kP的确定是问题的关键，称为搜索方向。选择k和)(kP的一般原则是使)()()()()1()0(kXfXfXf这种算法称为下降算法。最后检验)(kX是否收敛于最优解，即对0，是否有)()1(kXf决定迭代是否结束。172020年1月7日一维搜索法:沿着一系列的射线方向)(kP寻求极小化点列的方法.一维搜索法是对某一个确定方向)(kP来进行的.??问题:如何选择搜索方向)(kP呢？2.一维搜索法三、无约束非线性规划的解法对确定方向)(kP，在)0()()(kkPX上选取步长k使)()()()()(kkkkXfPXf，则可确定一个新的点)()()1(kkkkPXX，即为沿)()(kkPX求)(Xf的最小值问题。即等价于求)()()()(kkPXf在,|)()(kkPXXXL上极小点k。182020年1月7日2、一维搜索法选择下降速度最快的方向，可取)(Xf在)(kX点的方向导数最小的方向作为搜索方向，即令)()()(kkXfP，这就是梯度法，或最速下降法．(1)梯度法（最速下降法）共轭梯度法仅适用于正定二次函数的极小值问题：cXBAXXXfTT21)(min其中A为nn实对称正定阵，cEBXn,,为常数．(2)共轭梯度法192020年1月7日2、一维搜索法对于问题：cXBAXXXfTT21)(min当A为正定时，1A存在，于是有BAX1*为最优解．(3)牛顿（Newton）法(4)拟牛顿法）对于一般的二阶可微函数)(Xf，在)(kX点的局部有()()()()2()()()()()()1()()()2kkTkkTkkfXfXfXXXXXfXXX当黑塞矩阵)()(2kXf正定时，也可应用上面的牛顿法，这就是拟牛顿法，202020年1月7日2、一维搜索法3）计算)()1(1kkkXX，)()()()1(1kkkXfXf，1)(1)(11)(1111)()1(kkTkkTkkkkTkTkkkkHHHHH,)()1()1()1(kkkXfHP4）令;1kk返回2）．1）任取nEX)0(和)0(H（一般取IH)0(为单位阵），计算),()0()0()0(XfHP0k；(5)变尺度法2）若0)()(kXf，则停止计算，否则令)()()1(kkkkPXX，其中k为最佳步长，由)()(min)()()()(kkkkkPXfPXf确定；212020年1月7日1、非线性规划的可行方向法四、带约束非线性规划的解法mjXgXfj,,2,1,0)()(min（3）假设)(kX是问题（３）的一个可行解，但非最优解，为进一步寻找最优解在它的可行下降方向中选取其一个方向)(kD，并确定最佳步长k使,2,1,0,)()()()1()()()1(kXfXfRDXXkkkkkk反复进行这一过程，直到得到满足精度要求为止。即称为可行方向法．222020年1月7日2、非线性规划的制约函数法四、带约束非线性规划的解法基本思想：将求解非线性规划的问题转化为一系列无约极值问题来求解，故也称为序列无约束最小化方法．在无约束问题的求解中，对企图违反约束的那些点给出相应的惩罚约束，迫使这一系列的无约束问题的极小点不断地向可行域靠近(在可行外部)，或者一直在可行域内移动(在可行域内部)，直到收敛到原问题的最优解为止．制约函数分两类：惩罚函数和障碍函数。从方法上分为外点法(或外部惩罚函数法)和内点法(或内部惩罚函数法，即障碍函数法)．2、非线性规划的制约函数法232020年1月7日对于等式约束的问题：miXhXfi,,2,1,0)()(min（1）作辅助函数：mjjXhMXfMXP121)()(),(取M为充分大的正数，则问题（1）转化为求无约束问题),(min1MXPX的解的问题。（1）外点法（罚函数法）242020年1月7日对于不等式约束的问题：ljXgXfj,,2,1,0)()(min（2）同样可构造惩罚函数，即对充分大的M作：212)(,0min)(),(ljjXgMXfMXP则问题（2）可以转化为求),(min2MXPX的问题。（1）外点法（罚函数法）252020年1月7日（1）外点法（罚函数法）对于一般的问题ljXgmiXhXfji,,2,1,0)(,,2,1,0)()(min（3）对于充分大的M作辅助函数：)()(),(3XMPXfMXP其中2121)(,0)()(ljjmiiXgmimXhXP,则将问题（3）化为求解),(min3MXPX的问题。262020年1月7日选择惩罚因子M的一般策略:选取一个趋向无穷大的严格递增正数列}{kM，逐个求解)()(),(min3XPMXfMXPkkX即可得到一个极小点的序列}{*kX，在一定的条件下，这个序列收敛于原问题的最优解。这种方法又称为序列无约束极小化方法，简称为SUMT方法。（1）外点法（罚函数法）272020年1月7日内点法总是在可行域内进行的，并一直保持在可行域内进行搜索.这种方法只适用于只有不等式约束的问题：},,2,1,0)(|{)(minljXgXRXXfj作辅助函数（障碍函数）：)()(),(XrBXfrXQ其中)(XB是连续函数，)(XrB称为障碍项；r为充分小的正数，称之为障碍因子。2、非线性规划的制约函数法（2）内点法（障碍函数法）282020年1月7日（2）内点法（障碍函数法）作辅助函数（障碍函数）：)()(),(XrBXfrXQ其中)(XB是连续函数，)(XrB称为障碍项；r为充分小的正数，称之为障碍因子。注意到，当点X趋向于R的边界时，要)(XB趋向于正无穷大，则)(XB的最常用两种形式为ljjXgXB1)(1)(和ljjXgXB1)(log)(292020年1月7日由于)(XB的存在，在R的边界上形成了“围墙”，对迭代点的向外移动起到了阻挡作用，而越靠近边界阻力就越大。当点X趋向于R的边界时，则障碍函数),(rXQ趋向于正无穷大；否则，)(),(X