运筹学非线性规划

第三章非线性规划请回顾线性规划:,其目标与约束函数均为线性的。线性规划具有相对完美的理论与方法，应用也很广泛，但它终究不能穷尽各种优化问题，因为世界是非线性的。非线性规划（NonlinearProgramming）研究具有非线性构成函数的优化问题，是运筹学中相对活跃的重要研究分支。0..XbAXtsCXMaxz第一节基本概念一、非线性规划问题与模型1.问题⑴生产计划问题max()()()()0..()0ijfxxPxxCxgxsthxx:产量;P(x):价格;C(x)成本⑵投资决策问题1111::::::max()..0jjjijnnnjjijjijnjjjjxjPjBjijfxxxxPxBstx第种股票的购买量；第种股票的价格总资金；第种股票的每股平均收益风险系数；第种与第种股票收益的协方差2.模型1nnmin()()0,1,,()..()0,1,,[,,]{|()0,()0}min()DNLPDRNLPDRNLPijTnnijXDfXhXimNLPstgXjlXxxDXRhXgXNLPfX其中记则（）也可以表示为其中称为（）的约束集或可行域。当＝时，（）称做无约束极值问题；当时，（）称做约束极值问题。二、模型的解及相关概念1.可行解与最优解★可行解：约束集D中的X。★最优解：如果有，对于任意的，都有，则称为（NLP）的最优解，也称为全局最小值点。*XDXD*()()fXfX*X★局部最优解：如果对于，使得在的邻域中的任意都有，则称为（NLP）的局部最优解，也称为局部最小值点。0XD0XXD0()()fXfX00(,){|}BXXXX0X例1：考虑非线性问题221212min()(2)(2)..6fXxxstxx2x1x6633如果约束改为呢？126xx2.梯度、海塞阵与泰勒公式★梯度00000001()()()()()()()[]TnfXXfXXfXXfXfXfXfXxx若在的邻域内有连续一阶偏导数，则称在点对n个变元的偏导数组成的向量为在的梯度，记为，即＝，，00()XfXX几何意义：梯度是过点且与在的切平面垂直的向量，梯度向量的方向是函数值在该点增加最快的方向。★海塞阵00000000110012222222()()()()()()[]()()()()ijnnnnnfXXfXXnfXXfXHXHXxxfXfXxxxfXfXxxx若在的邻域内有连续二阶偏导数，则称在点对个变元两两组合的二阶偏导数组成的矩阵为在的海赛阵，记为，即=★泰勒公式000000002022000()()()()()1()()()2()()TTfXXfXXfXfXfXXXXXHXXXoXXoXXXXXX若在的邻域内有连续二阶偏导数，则可写出在点的（二阶）泰勒展开式：＝（－）－其中：是当时的高阶无穷小。例2：写出在点的二阶泰勒展开式212()3sinfXxx0[0,0]TX12002()[6()[01cos],]6060(),()0sin00TTfXxfXxHXHXx解:2111222()0[01601][]()002xxfXxxoXxx20212()()3()fXfXxoXXx如果忽略了在，则点的近似表达式为+3.极值的条件对于无约束极值问题，可以利用微积分的知识给出局部极值点的条件。将n(n1)元函数与一元函数的极值条件加以对比并归纳如下：()fX()fx00()Xx或是极小点()fx一元函数()fXn元函数0'()0fx0()0fX00'()0,''()0fxfx且00()0()0fXHX且充分条件必要条件0()0HX注：表示海赛阵正定。如果一个方阵的各阶主子式均大于零，则可以判定该方阵是正定的。例3：求的极小值点221122()228420fXxxxx解12120()[()0][4844][21]TTTfffXxxfXXxx＝＝，解得驻点令0040(),()004HXHXX又故是极小值点。4.凸规划★凸函数：f(X)是定义在凸集D上且满足对任意有下式成立的函数：1212()((1))(1)()fXfXXfX12,,XXD[0,1]若不等式中严格不等号成立，则称f(X)为严格凸函数注：判断一个可导函数f(X)是否是凸函数的方法一元函数f(x)：二阶导大于等于零;多元函数f(X)：海塞阵半正定。★凸规划性质：★约束集是凸集；★最优解集是凸集；★任何局部最优解也是全局最优解；★若目标函数是严格凸函数，且最优解存在，则其最优解是唯一的。在非线性规划模型（NLP）中，若目标函数f（X）是凸函数，不等式约束函数为凹函数，等式约束函数为仿射函数，则称（NLP）是一个凸规划。()1,,jgXjl()1,,ihXim例4：判断下面的非线性规划是否为凸规划12221212max()1..,0fXxxxxstxx12221122132min(())()10..()0()0fXxxgXxxstgXxgXx标准化123()00200,()0000200()()000fgggHXHXHXHX计算123()()()()fXgXgXgX说明是凸函数，、、是凹函数因此，本模型是凸规划。第二节无约束极值问题★一般模型：min()nfXXR其中★求解（f(X)可微）：应用极值条件求解，往往得到一个非线性的方程组，求解十分困难。因此，求解无约束问题一般采用迭代法，称为下降类算法。一、下降类算法的基本步骤与算法收敛性1.基本思想00112()fXXPXPX基本思想是使逐步下降，逐渐趋近其最小值。迭代方式是从一个初始点出发，选取某一搜索方向，沿该方向搜索到下一个点。若达到与最优解误差的精度要求，则停止，否则再沿该点的某一方向搜索下一个点。这一过程如图所示：0P1P2P0X1X3X2X2.基本步骤0:0,0Xk选取初始点，令确定精度；(1)(),(),3kkkkXfXfXX对于点，计算若则停止,得到近似最优解，否则转（）；(2)kkXP从出发，确定搜索方向；(3)1,,:1,2)kkkkkkkkPXXPXXPkk沿方向搜索，即由＝确定搜索步长得到下一个点＝令转(。(4)注：不同的搜索方向，就形成了不同的算法，不同的算法所产生的点列收敛于最优解的速度也不一样。3.收敛性衡量标准：*1*limkkkXXXX1,01,{}kX则称是线性收敛的；①1,0,{}kX则称是超线性收敛的；②2,0,{}kX则称是二阶收敛的。③二阶收敛超线性收敛线性收敛二、一维搜索:精确搜索：一维搜索分数法近似搜索0.168法其他方法（导数信息）0min(),kkkfXP通过求极值得到最佳步长k求上面极值的近似值得到近似最佳步长1.分数法（斐波那契法）2t⑴基本思想*tOab'1t1t()ftt怎样在区间中取点最好？'11()()ftft若12()()ftft若⑵基本概念[,],0nnnab记第次缩短后的小区间为给定的精度要求为★满足绝对精度：★满足相对精度：||nnba||nnbaba★斐波那契数：12011nnnFFFFF553421138532119876543210nFn1(1)()nnFabaF1()nnFabaFab1t'1t''11111'12211111'121-111221132[,],(1-)(-)[,],()[,]-1[,]1(-)nnnnnnnnnnnnnnnnnnnFtttbFFbaFFFFFtatFFFFbaFatttnabFFFFbaFFFFF1若按的比例在区间中对称地取点和，经比较后去掉则在中所占的比例为再按比例在中取与对称，这样反复次后所得的小区间长缩短为(),1()11-nnnnnbabaFFnbaFF与原区间长之比为：，恰为相对精度表达式。于是，开始可由解出，⑶步骤①1;nnF由所给精度和定111'''11111111(1-)(-)()max{},[,]nnnnnnFFtbaFFFtbattttFab由的比例在区间[a,b]中对称地取点=a+和=a+，比较f()和f()，去掉f(),f()相应点以外的区间得到新区间；②21121'21122[,]()()min{(),()}[,]nnFabtFftftftab在中按的比例取点与区间中所剩的点对称比较和，去掉较大者对应点以外的区间，得到新区间；③32232*1-112[,][,]nnnnFabtFFabtF在中按的比例取点再比较、再缩短，直到取完，最后的小区间中的任意一点可作为的近似值。④例5：2()2[1,3]8fttt用分数法求在区间上的近似极小点，要求缩短后的区间长度不大于原区间长的％。**''()20,1'()2101.752ftftftttft解由于所以（）是严格的凸函数。由＝－＝，解得是极小点，（）＝5611''11141152211180.0812.5,6,0.081381(1)[3(1)]0.538,()1.7511381[3(1)]1.462,()2.675()135[,][1,1.462],851(1)[1.462(1)]0.077,8()2.083(),nnFFnFFtfttftftFabFtftft由知查表得故2255[,][0.077,1.462]0.538()1.751abtft故依此进行，得＝为近似极小点，2.0.618法★区别：每次取点得比例是定值0.168，即每次区间内两点得位置均在区间相对长度得0.328和0.168处。★特点：简单，更易于应用；效果也比较好。3.近似最佳步长公式2()1()()()()2TTkkkkkkkkfXfXPfXfXPPHXP设存在连续的二阶偏导数，则有泰勒展开式0()()0TTkkkkkdffXPPHXPd对求导，并令导数为，得()()TkkTkkkfXPPHXP－解得：＝kfX上式即为的近似最佳步长公式。当（）为二次函数时，此公式是精确的。例6：2212()(1)(1),[00],()TkkkkfXxxXPfX设－用近似最佳步长公式求。12()[2(1)2(1)],()[22]20()()022[22]212022[22]022TTkkfXxxfXHXHX解()kfX由于是二次函数，故所求是精确的。三、梯度法和共轭梯度法1.梯度法()()()()TkkkkkfXfXPfXfXP设有连续的二阶偏导数，则有泰勒展开式0,()()cos0(),()()2cos1,,TkkkkkkkkkfXPfXPfXPfXPfX由于应使＝其中为向量和的夹角。为使上式成立，应使又为使的绝对值尽量大，应使＝-即＝()()kkkPfXXfXP故＝即在点的负梯度方向是使下降最快的方向。以负梯度作为搜索方向的下降类算法称为梯度法或最速下降法。()0))((kkkkfXPXpXff思想：怎样选取可使下且左边差降最额快？即使尽量大。★一般步骤0:0,0Xk选取初始点，令确定精度；(1)(),(),3)kkkkXfXfXX对于点，计算若则停止计