非线性规划的基本概念和基本原理精选PPT.ppt

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