非线性规划基础学习资料

1、非线性规划基础1 1、局部解、局部解 局部极大值局部极大值 局部极小值局部极小值2 2、全局解、全局解 全局最大值全局最大值 全局最小值全局最小值 局部最优解局部最优解全局最优解全局最优解 线性规划问题的最优解在角点取到，对非线性规划问题，最优解在何处取到呢？二、非线性规划的几何求解二、非线性规划的几何求解例例13.1 13.1 求解下列非线性规划的最优解。求解下列非线性规划的最优解。作图求解作图求解0,. .)()()(min2121212221xxxxxxtsxxxfx24 3222例例13.2 求解下列非线性规划的最优解。求解下列非线性规划的最优解。 0,. .).()()(min212

2、1212221xxxxxxtsxxxfx24 500.522作图求解作图求解例例13.3 求解下列非线性规划的最优解。求解下列非线性规划的最优解。 0442. .)(min212221222121xxxxxxtsxxxfx,)-(4)-( 作图求解作图求解线性规划与非线性规划有很大的区别：如果线线性规划与非线性规划有很大的区别：如果线性规划的最优解存在，其最优解只能在可行域性规划的最优解存在，其最优解只能在可行域的边界达到。而非线性规划的最优解（如果最的边界达到。而非线性规划的最优解（如果最优解存在）则可能在可行域的任何一点达到。优解存在）则可能在可行域的任何一点达到。 一、凸函数的基本概念一

3、、凸函数的基本概念二、凸函数的判断二、凸函数的判断三、凸规划三、凸规划凸函数定义凸函数定义凹函数定义凹函数定义)()1 ()()1 (2121xfxfxxf-)()1 ()()1 (2121xfxfxxf-一、凸函数的基本概念一、凸函数的基本概念凸函数凹函数非凸非凹函数一元函数凸性的判断一元函数凸性的判断0)( xf)()()(21221xxxfxfxf多元函数凸性的判断多元函数凸性的判断 梯度：梯度： Hessian矩阵矩阵 ：Tnxxfxxfxf)(,)()(1nnnnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxfxH222212222221221221221

4、22)()()()()()()()()()()(f(x)=x13+3x1x2+x22，则，则 f(x) 的的Hessian矩阵为矩阵为：判定正定的方法：当一个判定正定的方法：当一个nn矩阵矩阵A的任意的任意k阶顺序阶顺序主子式大于主子式大于0时，则该矩阵为正定的。时，则该矩阵为正定的。 2336121xxxH),(2222122222212212212212)()()()()()()()()(knnkkkxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxH)(D为凸集合，为凸集合，f(x)是定义在上的二次可微函数，则是定义在上的二次可微函数，则f(x)为凸函数的充要条件为为凸

5、函数的充要条件为f(x)在任意一点的在任意一点的Hessian矩阵为半正定。矩阵为半正定。 则则f(x)为凸函数的充要条件为：为凸函数的充要条件为：)()()(,2122121xxxfxfxfDxx)()()()(21212xxxfxfxfT例例13.4 判别下列函数的凸凹性判别下列函数的凸凹性 122),(121222121xxxxxxxf2212-2-4),(xxH222121),(xxxxf解：解： 1 1）1）2）H(x1, x2) 的两个顺序主子式分别的两个顺序主子式分别H1(x1,x2)=4和和H2(x1,x2)=8-4=4均大于均大于0。所以所以 f(x) 为凸函数为凸函数。2

6、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一、无约束优化的最优性条件一、无约束优化的最优性条件二、约束极值问题的最优性条件

7、二、约束极值问题的最优性条件引入两个概念引入两个概念 下降方向：下降方向： 可行方向：可行方向：)()(xfdxf), 0(),()(,|xfdxfDxdDdx), 0(, 0, 0|DdxDxddG则称d为f(x)在点的下降方向。 则称d为D在 点的可行方向。 x定理13.6 若f(x)在点 可微，如果存在方向d，使 ，则 使 有x0)(dxfT0), 0()()(xfdxf一、无约束优化的最优性条件一、无约束优化的最优性条件在无约束规划问题中，由于不涉及到可行域的在无约束规划问题中，由于不涉及到可行域的问题，因此，只涉及下降方向。不涉及可行方问题，因此，只涉及下降方向。不涉及可行方向的问题

8、。向的问题。定理定理13.713.7（一阶必要条件）（一阶必要条件） 若f(x)在点 可微，且为无约束优化问题（13.4）的局部最优解，则 。定理定理13.813.8（二阶必要条件）（二阶必要条件）若f(x)在点 二阶连续可微，且点为无约束优化问题（13.4）的局部最优解。则 且 半正定。定理定理13.913.9（二阶充分条件）（二阶充分条件）设 满足 且 正定，则 点为无约束优化问题（13.4）的局部最优解。定理定理13.1013.10 若目标函数f(x)是Rn上的连续可微凸函数，则 的充分必要条件 为无约束优化问题（13.4）的全局最优点和局部最优点。x0)( xfx0)(xf)(2xfn

9、Rx 0)(xf)(2xfx0)(xfx例例13.5 求函数求函数f(x)的最优值点，即。的最优值点，即。1222122121xxx)x()x(fminnRx0)(xfTx)0 , 1 (20010)x(f2正定解：所以 为局部最小值点。 Tx) 0 , 1 (二、约束极值问题的最优性条件二、约束极值问题的最优性条件在在x点取到局部最优值的条件为：点取到局部最优值的条件为： 0)( xg. t . s)x(fminxIm,i ,)x(g| ii10)x(g|xD00)(,|0dxfDxdFT, 0)(,|0IidxgDxdGTi00GF 0)(0)(dxfdxgTTi无解无解0)(dxgTi0

10、)()(xgdxgii约束规划问题不仅涉及到目约束规划问题不仅涉及到目标函数，还涉及到可行域。标函数，还涉及到可行域。因此既要考虑下降方向，还因此既要考虑下降方向，还要考虑可行方向要考虑可行方向定理定理13.11（Gorden）：）： 设设 ，则，则Ax0有解的充有解的充分必要条件为：不存在非零向量分必要条件为：不存在非零向量 ，使，使得得 。 无解的充分必要条件为：存在不全为零的非负实数使 上述定理的几何意义为：上述定理的几何意义为： ), 1(0miyAT01miiiAwdA1A2A3A3A1A2Ad0Ad0有解有解 Ad0无解无解 miRAAAAnim, 1,),(10)(mRy定理（定

11、理（Fritz-John）：问题（）：问题（13.5）在点取到局部极）在点取到局部极小值，则存在不全为零的非负实数使小值，则存在不全为零的非负实数使 例例13.6： 是下列优化问题的最优解，验证是下列优化问题的最优解，验证x满满足足Fritz-John定理。定理。0)()(0IiiixgwxfwTx) 1 , 3 ( , 0)( , 04)(, 010)(. .)3()7()(min23212222112221xxgxxxgxxxgtsxxxfx4-8-)(xf26)(xg111)(xg201126210www4-8-紧指标集紧指标集 I=1,2 如如(w0, w1, w2)=(1,1,2)。

12、 因此，因此，x满足满足Fritz-John定理。定理。 例例13.7 (0,2)T是下列优化问题的最优解，验证是下列优化问题的最优解，验证 x 满满足足Fritz-John定理定理 00)2(2. .)(min13212xxxtsxxfx00 w012100-021-0www(w0, w1, w2)=(0, k, 2k)，w0=0 因此，因此，x满足满足Fritz-John定理。定理。 约束规格约束规格 ： 线性无关线性无关 定理（定理（KKT）：）：设设 是问题（是问题（13.513.5）局部最）局部最优解，优解， 在在 处可微，处可微， 在在 处连续，处连续，且且 线性无关，则存在不全为

13、零的非负线性无关，则存在不全为零的非负实数实数 使使),(Iixgi0)()(IiiixgwxfDx )(,Iigfix)(Iigix),(Iixgimwww,10例例13.8 求下列问题的求下列问题的KKT点。点。 00. .) 1()(min221221xxxtsxxxfx0,00)2(010) 1(221222112111wwxwxxwwwwx1012wwTx)0 , 1 (KKT点：点：11)-2(x)(1xf11)(xg11-0)(xg2定理定理13.14. 在问题（在问题（13.5）中，）中，f, gi(i=1,m)是是凸函数，凸函数， ， ， 在在 处可微，处可微， 在在 处连续

14、，且在处连续，且在 处处KKT条件成立，则条件成立，则 是问题（是问题（13.5）全局最优解。）全局最优解。x)(IigiDxI0)x(g| ii)(,Iigfixxx 第四节第四节 非线性规划问题的算法非线性规划问题的算法一、一、 一维搜索法一维搜索法二、二、 最速下降法最速下降法 min f(x) f : RnR 是一阶连续函数是一阶连续函数无约束优化问题的极值条件基本迭代格式寻找搜索方向是无约束优化的关键问题*0f xkkkkdtxx1一、一维搜索法一、一维搜索法一维搜索法是求解无约束优化的一种方法。它是一维搜索法是求解无约束优化的一种方法。它是沿射线沿射线 xk+1 = xk+tdk，

15、求，求 f(x) 在该射线上的极小值，在该射线上的极小值，这一问题可转化为求一元函数这一问题可转化为求一元函数的极小值，即的极小值，即因此，这一过程称为一维搜索法。因此，这一过程称为一维搜索法。)tdx(f)t (kk)t(mint0通常，无约束优化问题算法的一般形式为：通常，无约束优化问题算法的一般形式为：初始步：给定初始点初始步：给定初始点 ，令，令k=0。第第1步：如果步：如果 ，停止计算；否则，进入，停止计算；否则，进入下一步。下一步。第第2步：计算下降方向步：计算下降方向dk，使，使 。第第3步：计算步长步：计算步长tk，使得，使得 ，令令 ；k=k+1，转第，转第1步。步。0, Rx0)(kxf0）（kTkxfd)(kktkkktdxfmin)dtx(f0kkkkdtxx1一维搜索的方法很多，归纳起来，可分为试探一维搜索的方法很多，归纳起来，可分为试探法和函数逼近法。试探法中包括如黄金分割法、法和函数逼近法。试探法中包括如黄金分割法、Fibonacci法等；函数逼近法中包括如牛顿法、法等；函数逼近法中包括如牛顿法、割线法等割线法等。牛顿算法计算步骤如下：牛顿算法计算步骤如下：初始步：给定初始点初始步：给定初始点 ，令，令k = 0= 0。第第1 1步：如果步：如果 ，则停止计算，得到点，则停止计算，得到点xk。否则，转第否则，