非线性规划的基本概念和基本原理课件.ppt

非线性规划的基本概念和基本原理1第1页，此课件共51页哦7.1 数学模型和基本概念数学模型和基本概念非线性规划是运筹学中包含内容最多，应非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性规划用最广泛的一个分支，计算远比线性规划复杂。复杂。2第2页，此课件共51页哦一、数学模型一、数学模型 例例 某单位拟建一排某单位拟建一排厂房，厂房建筑平面如图厂房，厂房建筑平面如图所示。由于资金及材料的所示。由于资金及材料的限制，围墙及隔墙的总长限制，围墙及隔墙的总长度不能超过度不能超过8080米。为使建米。为使建筑面积最大，应如何选择筑面积最大，应如何选择长宽尺寸？长宽尺寸？分析：设长为分析：设长为 米，米，宽为宽为 米，则有米，则有 f(x)为非线性函数为非线性函数3第3页，此课件共51页哦例例 设某物理过程具有如下规律设某物理过程具有如下规律 用试验法用试验法 。现要确定参数现要确定参数 使所得试验点构成的曲线与理论曲线误差平方和使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足为最小，且满足 非负。非负。4第4页，此课件共51页哦非线性规划：非线性规划：目标函数或（和）约束条件为非线性函数目标函数或（和）约束条件为非线性函数的规划。的规划。分析：分析：f(x)为非线性函数，为非线性函数，求最小。求最小。5第5页，此课件共51页哦一般模型一般模型Min f(X)s.t.hs.t.hi i(X)=0 (i=1,2,.m)(X)=0 (i=1,2,.m)（P P）g gj j(X)(X)0 (j=1,2.l)0 (j=1,2.l)X E En f(X)h f(X)hi i(X)g(X)gj j(X)(X)为为E En上的实函数。上的实函数。上的实函数。上的实函数。或或或或6第6页，此课件共51页哦二、基本概念二、基本概念1、全局极值和局部极值、全局极值和局部极值 为目标函数，为目标函数，为可行域。若存在为可行域。若存在 ，都有，都有 ，则称，则称 为该问题的为该问题的全局极小点全局极小点，为为全局极小值全局极小值。为目标函数，为目标函数，为可行域。若有为可行域。若有 ，都有都有 ，则称，则称 为该问题的为该问题的严格全局极小点严格全局极小点，为为严格全局极小值严格全局极小值。7第7页，此课件共51页哦若存在若存在 ，令，令 ，都有都有 ，则称则称 为该为该问题的问题的局部极小点局部极小点，为为局部极小值局部极小值。若存在若存在 ，令，令 ，都有都有 ，则称则称 为为该问题的该问题的严格局部极小点严格局部极小点，为为严格局部极小值严格局部极小值。相应不等式反号，得到相应极大点，极大值定义。相应不等式反号，得到相应极大点，极大值定义。相应不等式反号，得到相应极大点，极大值定义。相应不等式反号，得到相应极大点，极大值定义。8第8页，此课件共51页哦定义定义定义定义 如果如果如果如果X X满足（满足（满足（满足（P P）的约束条件）的约束条件）的约束条件）的约束条件 h hi i(X)=0 (i=1,2,.m)(X)=0 (i=1,2,.m)g gj j(X)(X)0 (j=1,2.l)则称则称则称则称X X En n 为（为（为（为（P P）的一个）的一个）的一个）的一个可行解。可行解。记（记（记（记（P P）的所有可行解的集合为）的所有可行解的集合为）的所有可行解的集合为）的所有可行解的集合为D D，D D称为（称为（P P）可行域可行域。9第9页，此课件共51页哦定义定义 X X*称为（称为（称为（称为（P P）的一个）的一个）的一个）的一个（整体）最优解（整体）最优解（整体）最优解（整体）最优解，如果，如果，如果，如果X X*D D，满足，满足，满足，满足 f(X)f(X f(X*)，X X D D。定义定义 X*称为（称为（P）的一个）的一个（局部）最优解（局部）最优解，如，如果果X*D，且存在一个，且存在一个X*的邻域的邻域N(X*,)=X En X-X*0满足满足 f(X)f(X*)，X D N(X*,)10第10页，此课件共51页哦f(X)f(X)局部最优解局部最优解局部最优解局部最优解整体最优解整体最优解整体最优解整体最优解11第11页，此课件共51页哦2.梯度向量梯度向量梯度向量梯度向量 f(X)=grad f(X)f(X)=grad f(X)=(=(f/f/x x1 1,f/f/x x2 2,.,.,f/f/x xn n)T T区间内连续的梯度的性质：区间内连续的梯度的性质：区间内连续的梯度的性质：区间内连续的梯度的性质：在某点的在某点的 f(X（0 0）)必与函数过该点的等值面的切必与函数过该点的等值面的切平面相垂直。平面相垂直。梯度方向是函数值增加最快的方向（函数变化率最梯度方向是函数值增加最快的方向（函数变化率最梯度方向是函数值增加最快的方向（函数变化率最梯度方向是函数值增加最快的方向（函数变化率最大的方向）大的方向）大的方向）大的方向）负梯度方向是函数值减小最快的方向。负梯度方向是函数值减小最快的方向。负梯度方向是函数值减小最快的方向。负梯度方向是函数值减小最快的方向。12第12页，此课件共51页哦13第13页，此课件共51页哦3 3、海赛、海赛、海赛、海赛(Hesse)(Hesse)矩阵矩阵矩阵矩阵 2 2f(X)=H(X)f(X)=H(X)2f/x12 2f/x1 x2 .2f/x1 xn 2f/x2 x1 2f/x22 .2f/x2 xn.2f/xn x1 2f/xn x2 .2f/xn2=14第14页，此课件共51页哦vv 2 2f(X)是对称矩阵。（是对称矩阵。（是对称矩阵。（是对称矩阵。（f(X)二阶偏导数连续时，混合偏二阶偏导数连续时，混合偏二阶偏导数连续时，混合偏二阶偏导数连续时，混合偏导数和取导数的顺序无关）导数和取导数的顺序无关）导数和取导数的顺序无关）导数和取导数的顺序无关）vvf(X)f(X)是二次函数，则可写成是二次函数，则可写成vv f(X)1/2X1/2XT TAX+BAX+BT TX+CX+Cvv则则 2f(X)f(X)A（与（与（与（与X的位置无关）的位置无关）的位置无关）的位置无关）15第15页，此课件共51页哦4 4、正定矩阵、负定、半定、不定、正定矩阵、负定、半定、不定、正定矩阵、负定、半定、不定、正定矩阵、负定、半定、不定正定：特征值正定：特征值正定：特征值正定：特征值00；各阶主子式；各阶主子式0(Ai0)0(Ai0)半正定：特征值半正定：特征值半正定：特征值半正定：特征值 0 0；detA=0,detA=0,Ai Ai 0负定：特征值负定：特征值负定：特征值负定：特征值00；Ai 0(iAi 0(i,Ai 0(i为偶）为偶）为偶）为偶）半负定：特征值半负定：特征值半负定：特征值半负定：特征值0 0；detA=0detA=0，Ai Ai 0(i0(i为奇）为奇）为奇）为奇）,Ai 0(i0(i为偶）为偶）为偶）为偶）不定：特征值有不定：特征值有不定：特征值有不定：特征值有 0 0及及及及 0,40,=400=4004 00 104 0 20 10 22 2 2=240=240H(X)正定，正定，正定，正定，X*=(1,1,-2)X*=(1,1,-2)，f(X*)=0f(X*)=028第28页，此课件共51页哦例例 利用极值条件解无约束非线性规划问题利用极值条件解无约束非线性规划问题 解解 因为因为 ，令令 即即 求得到求得到4个驻点：个驻点：，和和 不是极小点；不是极小点；是极小点。是极小点。29第29页，此课件共51页哦凸集概念：凸集概念：凸集概念：凸集概念：设设D D是是是是n n维线性空间维线性空间维线性空间维线性空间E En n的一个点集，若的一个点集，若的一个点集，若的一个点集，若D D中的任意中的任意两点两点x x(1)(1),x,x(2)(2)的连的连线上的一切点线上的一切点x x仍在仍在仍在仍在D D中，则称中，则称中，则称中，则称D为为为为凸集凸集凸集凸集。即：即：即：即：若若若若D中的任意两点中的任意两点中的任意两点中的任意两点x x(1)(1),x,x(2)(2)D D，任意，任意00 1 使使使使得得得得x=x x(1)(1)+(1-+(1-)x(2)(2)D,D,则称则称D为为为为凸集凸集凸集凸集7.3 7.3 凸函数与凸规划凸函数与凸规划凸函数与凸规划凸函数与凸规划30第30页，此课件共51页哦一、凸函数的定义一、凸函数的定义几何解释几何解释几何解释几何解释31第31页，此课件共51页哦f(X)f(X)X X32第32页，此课件共51页哦f(X)f(X)X Xf(Xf(X1 1)f(Xf(X2 2)X X1 1X X2 233第33页，此课件共51页哦f(X)f(X)X X f(xf(x1 1)+(1-+(1-)f(x)f(x2 2)f(Xf(X1 1)f(Xf(X2 2)X X1 1X X2 2 x x1 1+(1-+(1-)x)x2 2f(f(x x1 1+(1-+(1-)x)x2 2)34第34页，此课件共51页哦f(X)f(X)X X f(xf(x1 1)+(1-+(1-)f(x)f(x2 2)f(Xf(X1 1)f(Xf(X2 2)X X1 1X X2 2 x x1 1+(1-+(1-)x)x2 2f(f(x x1 1+(1-+(1-)x)x2 2)任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方35第35页，此课件共51页哦线性函数既是凸函数线性函数既是凸函数线性函数既是凸函数线性函数既是凸函数,又是凹函数。又是凹函数。又是凹函数。又是凹函数。如果如果如果如果 -f f(X X)为为为为R R上的上的上的上的(严格严格严格严格)凸函数凸函数凸函数凸函数,则则则则f f(X X)为为为为R上的上的上的上的(严严格格)凹函数凹函数凹函数凹函数.36第36页，此课件共51页哦二 凸函数的性质凸函数的性质 性质性质性质性质1 1 设设设设 都是定义在凸集都是定义在凸集都是定义在凸集都是定义在凸集R R上的凸函数，上的凸函数，上的凸函数，上的凸函数，那么那么那么那么 仍是在凸集仍是在凸集仍是在凸集仍是在凸集R R上的凸函数。上的凸函数。上的凸函数。上的凸函数。性性性性质质质质2 2 设设设设 是是是是定定定定义义义义在在在在凸凸凸凸集集集集S S上上上上的的的的凸凸凸凸函函函函数数数数，那那那那么么么么对对对对任任任任意意意意实数实数实数实数 ，集合，集合，集合，集合 是是是是S S的凸子集。的凸子集。的凸子集。的凸子集。性质性质性质性质3 3 f f(x x)是凸集是凸集是凸集是凸集R R上凸函数，则上凸函数，则上凸函数，则上凸函数，则f f(x x)在在在在R R上局部极小点就是全上局部极小点就是全上局部极小点就是全上局部极小点就是全局极小点，且极小点的集合是凸集。局极小点，且极小点的集合是凸集。局极小点，且极小点的集合是凸集。局极小点，且极小点的集合是凸集。37第37页，此课件共51页哦三、凸函数的判别三、凸函数的判别38第38页，此课件共51页哦例39第39页，此课件共51页哦v作业：vP200 4.6（1）（2）40第40页，此课件共51页哦v定理定理6（充要条件）：（充要条件）：若若 是二阶连续可微的凸函数，是二阶连续可微的凸函数，则则 是全局极小点是全局极小点 。类似地，若类似地，若 二阶连续可微的严格凸函数，二阶连续可微的严格凸函数，则则 是惟一全局极小点。是惟一全局极小点。四、凸函数极值点的充要条件四、凸函数极值点的充要条件四、凸函数极值点的充要条件四、凸函数极值点的充要条件41第41页，此课件共51页哦解无约束问题的算法：解无约束问题的算法：解无约束问题的算法：解无约束问题的算法：求求求求f(X)f(X)的驻点的驻点的驻点的驻点X*X*，若是凸函数，得到最优解。否，若是凸函数，得到最优解。否，若是凸函数，得到最优解。否，若是凸函数，得到最优解。否则，转下一步。则，转下一步。则，转下一步。则，转下一步。在驻点在驻点X*处，计算处，计算处，计算处，计算H(x)H(x)。根据根据根据根据H(x)H(x)来判断该驻点来判断该驻点来判断该驻点来判断该驻点X*X*是否是极值点。是否是极值点。是否是极值点。是否是极值点。42第42页，此课件共51页哦例例例例 求极值求极值求极值求极值 f(X)=x x1 1+2x3 3+x+x2 2x3 3-x x1 12 2-x2 22 2-x-x3 32 X X E E3 3 解：解：解：解：f(f(X X)=(1-2x1 1,x,x3 3-2x-2x2 2,2+x,2+x2 2-2x2x3 3)=0 )=0 驻点驻点驻点驻点x*=(1/2,2/3,4/3)x*=(1/2,2/3,4/3)H(X)=H(X)=xxxxf(X)=f(X)=-2 0 00 -2 10 1 -2 43第43页，此课件共51页哦H(X)=H(X)=xxxxf(X)=f(X)=各阶主子式：各阶主子式：各阶主子式：各阶主子式：-20,-20=40-2 00 -2=-60=-60-2 0 00 -2 10 1 -2-2 0 00 -2 10 1 -2 H(X)H(X)负定，负定，负定，负定，f(X)f(X)是凹函数是凹函数是凹函数是凹函数X*=(1/2,2/3,4/3)X*=(1/2,2/3,4/3)为极大值点。为极大值点。为极大值点。为极大值点。f(X*)=f(1/2,2/3,4/3)=19/12f(X*)=f(1/2,2/3,4/3)=19/1244第44页，此课件共51页哦 五、凸规划五、凸规划五、凸规划五、凸规划 下述问题为凸规划下述问题为凸规划.求凸函数求凸函数求凸函数求凸函数f(x)f(x)在凸集在凸集在凸集在凸集R R上的极小点的问题，上的极小点的问题，上的极小点的问题，上的极小点的问题，称为凸规划。称为凸规划。称为凸规划。称为凸规划。45第45页，此课件共51页哦性质：性质：1、凸规划的局部极小点就是全局极小点。、凸规划的局部极小点就是全局极小点。2、极小点的集合是凸集。、极小点的集合是凸集。3、若目标函数为严格凸函数，若存在极小点，、若目标函数为严格凸函数，若存在极小点，则极小点必定唯一。则极小点必定唯一。凸规划是一类比较简单而又具有重要理论意义凸规划是一类比较简单而又具有重要理论意义的非线性规划。的非线性规划。46第46页，此课件共51页哦例例 如下非线性规划是否为凸规划：如下非线性规划是否为凸规划：47第47页，此课件共51页哦 的海赛矩阵：所以，该问题为凸规划。所以，该问题为凸规划。48第48页，此课件共51页哦 如图所示，该问题如图所示，该问题 最优解在最优解在C点取得。点取得。49第49页，此课件共51页哦算法概述算法概述 一一个个算算法法（Algorithm)Algorithm)就就就就是是是是一一一一种种种种求求求求解解解解方方方方法法法法，它它它它可可可可看看看看作作作作为为为为一一一一个个个个循循循循环环环环过过过过程程程程，按按按按照照照照一一一一组组组组指指指指令令令令和和和和规规规规定定定定的的的的停停停停算算算算准准准准则则则则，产产产产生生生生近近近近似似似似解解解解序序序序列列列列，它它它它应应应应该该该该收收收收敛敛敛敛到到到到整整整整体体体体最最最最优优优优解解解解，但但但但由由由由于于于于某某某某些些些些原原原原因因因因（不不不不连连连连续续续续性性性性、无无无无凸凸凸凸性性性性、规规规规模模模模大大大大、实实实实现现现现方方方方面面面面困困困困难难难难等等等等）常常常常使使使使得得得得计计计计算算算算难难难难以以以以符符符符合合合合以以以以上上上上条条条条件件件件，往往往往往往往往是是是是一一一一个个个个无无无无限限限限的的的的过过过过程程程程，因因因因而而而而给给给给出出出出停停停停算算算算准准准准则则则则，如如如如果果果果在在在在第第第第k k次次循循环环时时，满满足足停停算算准准则条件，则停算。则条件，则停算。50第50页，此课件共51页哦7.4 7.4 下降迭代算法下降迭代算法 下降方向下降方向：设设 ，若若存存在在 ，使使得得当当 时时，有有 ，则称，则称 为为 在在处的下降方向。处的下降方向。下降迭代法的基本思想下降迭代法的基本思想：若该点的序列收敛于若该点的序列收敛于若该点的序列收敛于若该点的序列收敛于 ，在一定条件下，在一定条件下，在一定条件下，在一定条件下，就是极点。就是极点。就是极点。就是极点。51第51页，此课件共51页哦