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

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