第十三章-非线性规划基础

第十三章非线性规划第一节非线性规划的基本概念第二节凸函数第三节最优性条件第四节非线性规划问题的算法第一节非线性规划的基本概念一、非线性规划模型二、非线性规划的几何求解一、非线性规划模型非线性规划的一般形式：0)(0g(x)..)(minxhtsxfxmTnRxgxgxg))(,),(()(1nRxlTlRxhxhxh))(,),(()(1nixgljxhRxDijn,,1,0)(,,1,0)(|;称为决策变量称为不等式约束称为等式约束可行域Rxf)(称为目标函数1、局部解局部极大值局部极小值2、全局解全局最大值全局最小值局部最优解≠全局最优解线性规划问题的最优解在角点取到，对非线性规划问题，最优解在何处取到呢？二、非线性规划的几何求解例13.1求解下列非线性规划的最优解。作图求解0,..)()()(min2121212221xxxxxxtsxxxfx243222例13.2求解下列非线性规划的最优解。0,..).()()(min2121212221xxxxxxtsxxxfx24500.522作图求解例13.3求解下列非线性规划的最优解。0442..)(min212221222121xxxxxxtsxxxfx,)-(4)-(作图求解线性规划与非线性规划有很大的区别：如果线性规划的最优解存在，其最优解只能在可行域的边界达到。而非线性规划的最优解（如果最优解存在）则可能在可行域的任何一点达到。第二节凸函数一、凸函数的基本概念二、凸函数的判断三、凸规划凸函数定义凹函数定义)()1()())1((2121xfxfxxf-)()1()())1((2121xfxfxxf-一、凸函数的基本概念凸函数凹函数非凸非凹函数凸函数具有如下性质二、凸函数的判断一元函数凸性的判断0)(xf))(()()(21221xxxfxfxf多元函数凸性的判断梯度：Hessian矩阵：Tnxxfxxfxf))(,,)(()(1nnnnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxfxH22221222222122122122122)()()()()()()()()()()(f(x)=x13+3x1x2+x22，则f(x)的Hessian矩阵为：判定正定的方法：当一个n×n矩阵A的任意k阶顺序主子式大于0时，则该矩阵为正定的。2336121xxxH),(2222122222212212212212)()()()()()()()()(knnkkkxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxH)(D为凸集合，f(x)是定义在上的二次可微函数，则f(x)为凸函数的充要条件为f(x)在任意一点的Hessian矩阵为半正定。则f(x)为凸函数的充要条件为：))(()()(,,2122121xxxfxfxfDxx)()()()(21212xxxfxfxfT例13.4判别下列函数的凸凹性122),(121222121xxxxxxxf2212-2-4),(xxH222121),(xxxxf解：1）1）2）H(x1,x2)的两个顺序主子式分别H1(x1,x2)=4和H2(x1,x2)=8-4=4均大于0。所以f(x)为凸函数。2）221-002),(xxHH(x1,x2)的两个顺序主子式分别H1(x1,x2)=20和H2(x1,x2)=-40。所以f(x)不是凸函数。三、凸规划当f(x),g(x)为凸函数，h(x)=(h1(x),…,hl(x))是线性函数时，上述规划问题称为凸规划问题。凸规划的求解可借助下节的KKT定理。0),),(()()(..)(min1xgxgxgtsxfmxh(x)=(h1(x),…,hl(x))=0第三节最优性条件一、无约束优化的最优性条件二、约束极值问题的最优性条件引入两个概念下降方向：可行方向：)()(xfdxf)},0(),()(,|{xfdxfDxdDdx}),,0(,0,,0|{DdxDxddG则称d为f(x)在点的下降方向。则称d为D在点的可行方向。x定理13.6若f(x)在点可微，如果存在方向d，使，则使有x0)(dxfT0),0()()(xfdxf一、无约束优化的最优性条件在无约束规划问题中，由于不涉及到可行域的问题，因此，只涉及下降方向。不涉及可行方向的问题。定理13.7（一阶必要条件）若f(x)在点可微，且为无约束优化问题（13.4）的局部最优解，则。定理13.8（二阶必要条件）若f(x)在点二阶连续可微，且点为无约束优化问题（13.4）的局部最优解。则且半正定。定理13.9（二阶充分条件）设满足且正定，则点为无约束优化问题（13.4）的局部最优解。定理13.10若目标函数f(x)是Rn上的连续可微凸函数，则的充分必要条件为无约束优化问题（13.4）的全局最优点和局部最优点。x0)(xfx0)(xf)(2xfnRx0)(xf)(2xfx0)(xfx例13.5求函数f(x)的最优值点，即。1222122121xxx)x()x(fminnRx0)(xfTx)0,1(20010)x(f2正定解：所以为局部最小值点。Tx)0,1(二、约束极值问题的最优性条件在x点取到局部最优值的条件为：0)(xg.t.s)x(fminx}{Im,,i,)x(g|ii10})x(g|xD0{}0)(,|{0dxfDxdFT},0)(,|{0IidxgDxdGTi00GF0)(0)(dxfdxgTTi无解0)(dxgTi0)()(xgdxgii约束规划问题不仅涉及到目标函数，还涉及到可行域。因此既要考虑下降方向，还要考虑可行方向定理13.11（Gorden）：设，则Ax0有解的充分必要条件为：不存在非零向量，使得。无解的充分必要条件为：存在不全为零的非负实数使上述定理的几何意义为：),,1(0miyAT01miiiAwdA1A2A3A3A1A2Ad0有解Ad0无解miRAAAAnim,,1,),,,(10)(mRy定理（Fritz-John）：问题（13.5）在点取到局部极小值，则存在不全为零的非负实数使例13.6：是下列优化问题的最优解，验证x满足Fritz-John定理。0)()(0IiiixgwxfwTx)1,3(,0)(,04)(,010)(..)3()7()(min23212222112221xxgxxxgxxxgtsxxxfx4-8-)(xf26)(xg111)(xg201126210={1,2}如(w0,w1,w2)=(1,1,2)。因此，x满足Fritz-John定理。例13.7(0,2)T是下列优化问题的最优解，验证x满足Fritz-John定理00)2(2..)(min13212xxxtsxxfx00w012100-021-0(w0,w1,w2)=(0,k,2k)，w0=0因此，x满足Fritz-John定理。约束规格：线性无关定理（KKT）：设是问题（13.5）局部最优解，在处可微，在处连续，且线性无关，则存在不全为零的非负实数使}),({Iixgi0)()(IiiixgwxfDx)(,Iigfix)(Iigix}),({Iixgim例13.8求下列问题的KKT点。00..)1()(min221221xxxtsxxxfx0,00)2(010)1(221222112111wwxwxxwwTx)0,1(KKT点：11)-2(x)(1xf11)(xg11-0)(xg2定理13.14.在问题（13.5）中，f,gi(i=1,…,m)是凸函数，，，在处可微，在处连续，且在处KKT条件成立，则是问题（13.5）全局最优解。x)(IigiDx}{I0)x(g|ii)(,Iigfixxx第四节非线性规划问题的算法一、一维搜索法二、最速下降法minf(x)f:RnR是一阶连续函数无约束优化问题的极值条件基本迭代格式寻找搜索方向是无约束优化的关键问题*0fxkkkkdtxx1一、一维搜索法一维搜索法是求解无约束优化的一种方法。它是沿射线xk+1=xk+tdk，求f(x)在该射线上的极小值，这一问题可转化为求一元函数的极小值，即因此，这一过程称为一维搜索法。)tdx(f)t(kk)t(mint0通常，无约束优化问题算法的一般形式为：初始步：给定初始点，令k=0。第1步：如果，停止计算；否则，进入下一步。第2步：计算下降方向dk，使。第3步：计算步长tk，使得，令；k=k+1，转第1步。0,Rx0)(kxf0）（kTkxfd)(kktkkktdxfmin)dtx(f0kkkkdtxx1一维搜索的方法很多，归纳起来，可分为试探法和函数逼近法。试探法中包括如黄金分割法、Fibonacci法等；函数逼近法中包括如牛顿法、割线法等。牛顿算法计算步骤如下：初始步：给定初始点，令k=0。第1步：如果，则停止计算，得到点xk。否则，转第2步。第2步：计算点xk+1：令k=k+1，转第1步。该算法特点是：收敛速度快，为二阶收敛。初始点要选在最优解附近。但有时初始点的选取困难，甚至无法实施。)()(-kkkkxfxfxx1)(|kxf0,Rx0二、最速下降法算法的计算步骤为第1步：给定初始点第2步：计算搜索方向第3步：若，则停止，否则求使得第4步：令，转第2步。nRx0)x(fdkk||d||kkt)tdx(fmin)dtx(fkkkkk0kkkkdxx11）程序设计简单计算量小,存储量小,并且计算效率在最初几步迭代时较高,常与其他方法一起使用.2）对初始点没有特别要求,有着很好的全局收敛性.优点缺点最速下降法是线性收敛的，但当接近最优解时，收敛速度很慢．原因：1）仅反映f(x)在点xk处的局部性质。2）相继两次迭代中搜索方向是正交的，即。)x(fdkk01kkdd谢谢！