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

《非线性规划的基本概念和基本原理精选课件.ppt》由会员分享，可在线阅读，更多相关《非线性规划的基本概念和基本原理精选课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于非线性规划的基本概念和基本原理第一页，本课件共有54页27.1 数学模型和基本概念数学模型和基本概念非线性规划是运筹学中包含内容最多，非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性应用最广泛的一个分支，计算远比线性规划复杂。规划复杂。第二页，本课件共有54页3一、数学模型一、数学模型 例例 某单位拟建一排某单位拟建一排厂房，厂房建筑平面如图厂房，厂房建筑平面如图所示。由于资金及材料的所示。由于资金及材料的限制，围墙及隔墙的总长限制，围墙及隔墙的总长度不能超过度不能超过8080米。为使建米。为使建筑面积最大，应如何选择筑面积最大，应如何选择长宽尺寸？长宽尺寸？分析：设长

2、为分析：设长为 米，米，宽为宽为 米，则有米，则有 f(x)为非线性函数为非线性函数第三页，本课件共有54页4例例 设某物理过程具有如下规律设某物理过程具有如下规律 用试验法用试验法 。现要确定参数现要确定参数 使所得试验点构成的曲线与理论曲线误差平方使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足和为最小，且满足 非负。非负。第四页，本课件共有54页5非线性规划：非线性规划：目标函数或（和）约束条件为非线性函数目标函数或（和）约束条件为非线性函数的规划。的规划。分析：分析：f(x)为非线性函为非线性函数，求最小。数，求最小。第五页，本课件共有54页6一般模型一般模型Min f(X)s

3、.t.hs.t.hi(X)=0 (i=1,2,.m)（P P）gj j(X)0 (j=1,2.l)X X En f(X)hi(X)gj(X)(X)为为为为En n上的实函数。上的实函数。上的实函数。上的实函数。或或或或第六页，本课件共有54页7二、基本概念二、基本概念1、全局极值和局部极值、全局极值和局部极值 为目标函数，为目标函数，为可行域。若存在为可行域。若存在 ，都有，都有 ，则称，则称 为该问题的为该问题的全局极小点全局极小点，为为全局极小值全局极小值。为目标函数，为目标函数，为可行域。若有为可行域。若有 ，都有都有 ，则称，则称 为该问题的为该问题的严格全局极小点严格全局极小点，为为

4、严格全局极小值严格全局极小值。第七页，本课件共有54页8若存在若存在 ，令，令 ，都有都有 ，则称则称 为该为该问题的问题的局部极小点局部极小点，为为局部极小值局部极小值。若存在若存在 ，令，令 ，都有都有 ，则称则称 为为该问题的该问题的严格局部极小点严格局部极小点，为为严格局部极小值严格局部极小值。相应不等式反号，得到相应极大点，极大值定义。相应不等式反号，得到相应极大点，极大值定义。相应不等式反号，得到相应极大点，极大值定义。相应不等式反号，得到相应极大点，极大值定义。第八页，本课件共有54页9定义定义定义定义 如果如果X满足（满足（满足（满足（P P）的约束条件）的约束条件 h hi

5、i(X)=0 (i=1,2,.m)gj j(X)(X)0 (j=1,2.l)则称则称X X E En n 为（为（P P）的一个）的一个）的一个）的一个可行解。可行解。可行解。可行解。记（记（P）的所有可行解的集合为）的所有可行解的集合为）的所有可行解的集合为）的所有可行解的集合为D D，D D称为（称为（P P）可行域可行域可行域可行域。第九页，本课件共有54页10定义定义定义定义 X*称为（称为（P）的一个）的一个（整体）最优解（整体）最优解（整体）最优解（整体）最优解，如果，如果，如果，如果X*D D，满足，满足 f(X)f(X)f(X f(X*)，X D D。定义定义 X*称为（称为（

6、P）的一个）的一个（局部）最优解（局部）最优解，如，如果果X*D，且存在一个，且存在一个X*的邻域的邻域N(X*,)=X En X-X*0满足满足 f(X)f(X*)，X D N(X*,)第十页，本课件共有54页11f(X)f(X)局部最优解局部最优解局部最优解局部最优解整体最优解整体最优解整体最优解整体最优解第十一页，本课件共有54页122.梯度向量梯度向量梯度向量梯度向量 f(X)=grad f(X)f(X)=grad f(X)=(=(f/f/x x1,f/x2,.,.,f/f/x xn n)T区间内连续的梯度的性质：区间内连续的梯度的性质：在某点的在某点的在某点的在某点的 f(Xf(X（

7、0）)必与函数过该点的等值面的切必与函数过该点的等值面的切平面相垂直。平面相垂直。梯度方向是函数值增加最快的方向（函数变化梯度方向是函数值增加最快的方向（函数变化率最大的方向）率最大的方向）负梯度方向是函数值减小最快的方向。负梯度方向是函数值减小最快的方向。负梯度方向是函数值减小最快的方向。负梯度方向是函数值减小最快的方向。第十二页，本课件共有54页13第十三页，本课件共有54页143、海赛、海赛(Hesse)矩阵矩阵矩阵矩阵 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/

8、xn2=第十四页，本课件共有54页15vv 2f(X)f(X)是对称矩阵。（是对称矩阵。（f(X)f(X)二阶偏导数连续时，混合二阶偏导数连续时，混合偏导数和取导数的顺序无关）偏导数和取导数的顺序无关）vvf(X)f(X)是二次函数，则可写成是二次函数，则可写成vv f(X)1/2X1/2XTAX+BAX+BT TX+Cvv则则则则 2 2f(X)f(X)A A（与（与X的位置无关）的位置无关）的位置无关）的位置无关）第十五页，本课件共有54页164 4、正定矩阵、负定、半定、不定、正定矩阵、负定、半定、不定正定：特征值正定：特征值00；各阶主子式；各阶主子式0(Ai0)0(Ai0)半正定：特

9、征值半正定：特征值0；detA=0,Ai 0 0负定：特征值负定：特征值0；Ai 0(iAi 0(i,Ai 0(i为偶）为偶）为偶）为偶）半负定：特征值半负定：特征值0 0；detA=0，Ai Ai 0(i0(i为奇）为奇）为奇）为奇）,Ai 0(i为偶）为偶）不定：特征值有不定：特征值有 0 0及及0,40,=4004 00 104 0 20 10 22 2 2=240H(X)正定，正定，X*=(1,1,-2)，f(X*)=0f(X*)=0第二十八页，本课件共有54页29例例 利用极值条件解无约束非线性规划问题利用极值条件解无约束非线性规划问题 解解 因为因为 ，令令 即即 求得到求得到4个

10、驻点：个驻点：，和和 不是极小点；不是极小点；是极小点。是极小点。第二十九页，本课件共有54页30凸集概念：凸集概念：凸集概念：凸集概念：设设设设D D是是n维线性空间维线性空间E En的一个点集，若的一个点集，若D中的中的任意两点任意两点x(1),x,x(2)的连的连线上的一切点线上的一切点x仍在仍在D中，则中，则中，则中，则称称称称D D为为凸集凸集。即：即：若若若若D D中的任意两点中的任意两点x x(1)(1),x(2)(2)D，任意，任意0 1 1 使得使得使得使得x=x=x(1)(1)+(1-+(1-)x)x(2)D,则称则称则称则称D为为凸集凸集凸集凸集7.3 7.3 凸函数与凸

11、规划凸函数与凸规划第三十页，本课件共有54页31一、凸函数的定义一、凸函数的定义几何解释几何解释第三十一页，本课件共有54页32f(X)f(X)X X第三十二页，本课件共有54页33f(X)f(X)X Xf(Xf(X1 1)f(Xf(X2 2)X X1 1X X2 2第三十三页，本课件共有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)第三十四页，本课件共有54页35f(X)f(X)X X

12、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)任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方第三十五页，本课件共有54页36线性函数既是凸函数线性函数既是凸函数线性函数既是凸函数线性函数既是凸函数,又是凹函数。又是凹函数。又是凹函数。又是凹函数。如果如果如果如果 -f(X)为为R上的上的(严格严格)凸函

13、数凸函数凸函数凸函数,则则f f(X X)为为R R上的上的(严格严格)凹函数凹函数.第三十六页，本课件共有54页37二 凸函数的性质凸函数的性质 性质性质性质性质1 1 设设设设 都是定义在凸集都是定义在凸集都是定义在凸集都是定义在凸集R R上的凸函数，上的凸函数，上的凸函数，上的凸函数，那么那么那么那么 仍是在凸集仍是在凸集仍是在凸集仍是在凸集R R上的凸函数。上的凸函数。上的凸函数。上的凸函数。性性性性质质质质2 2 设设设设 是是是是定定定定义义义义在在在在凸凸凸凸集集集集S S上上上上的的的的凸凸凸凸函函函函数数数数，那那那那么么么么对对对对任任任任意意意意实数实数实数实数 ，集合，

14、集合，集合，集合 是是是是S S的凸子集。的凸子集。的凸子集。的凸子集。性质性质性质性质3 3 f f(x x)是凸集是凸集是凸集是凸集R R上凸函数，则上凸函数，则上凸函数，则上凸函数，则f f(x x)在在在在R R上局部极小点就是全上局部极小点就是全上局部极小点就是全上局部极小点就是全局极小点，且极小点的集合是凸集。局极小点，且极小点的集合是凸集。局极小点，且极小点的集合是凸集。局极小点，且极小点的集合是凸集。第三十七页，本课件共有54页38三、凸函数的判别三、凸函数的判别第三十八页，本课件共有54页39例第三十九页，本课件共有54页40v作业：vP200 4.6（1）（2）第四十页，本

15、课件共有54页41v定理定理6（充要条件）：（充要条件）：若若 是二阶连续可微的凸函数，是二阶连续可微的凸函数，则则 是全局极小点是全局极小点 。类似地，若类似地，若 二阶连续可微的严格凸函数，二阶连续可微的严格凸函数，则则 是惟一全局极小点。是惟一全局极小点。四、凸函数极值点的充要条件四、凸函数极值点的充要条件第四十一页，本课件共有54页42解无约束问题的算法：解无约束问题的算法：vv求求求求f(X)的驻点的驻点X*，若是凸函数，得到最优解。，若是凸函数，得到最优解。否则，转下一步。否则，转下一步。v在驻点在驻点X*X*处，计算处，计算处，计算处，计算H(x)。v根据根据H(x)来判断该驻点

16、来判断该驻点X*X*是否是极值点。是否是极值点。是否是极值点。是否是极值点。第四十二页，本课件共有54页43例例 求极值求极值 f(X)=x1+2x3 3+x2 2x3 3-x1 12-x-x2 22-x32 X X E3 解：解：f(X)=(1-2x)=(1-2x1 1,x,x3-2x2,2+x2 2-2x2x3)=0 驻点驻点驻点驻点x*=(1/2,2/3,4/3)H(X)=xxxxf(X)=f(X)=-2 0 00 -2 10 1 -2 第四十三页，本课件共有54页44H(X)=xxxxf(X)=各阶主子式：各阶主子式：各阶主子式：各阶主子式：-20,-20-2 00 -2=-60-2

17、0 00 -2 10 1 -2-2 0 00 -2 10 1 -2 H(X)H(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第四十四页，本课件共有54页45 五、凸规划五、凸规划 下述问题为凸规划下述问题为凸规划下述问题为凸规划下述问题为凸规划.求凸函数求凸函数f(x)在凸集在凸集在凸集在凸集R上的极小点的问题，上的极小点的问题，上的极小点的问题，上的极小点的问题，称为凸规划。称为凸规划。称为凸规划。称为凸规划。第四十五页，本课件共有54页46

18、性质：性质：1、凸规划的局部极小点就是全局极小点。、凸规划的局部极小点就是全局极小点。2、极小点的集合是凸集。、极小点的集合是凸集。3、若目标函数为严格凸函数，若存在极小点，、若目标函数为严格凸函数，若存在极小点，则极小点必定唯一。则极小点必定唯一。凸规划是一类比较简单而又具有重要理论意义凸规划是一类比较简单而又具有重要理论意义的非线性规划。的非线性规划。第四十六页，本课件共有54页47例例 如下非线性规划是否为凸规划：如下非线性规划是否为凸规划：第四十七页，本课件共有54页48 的海赛矩阵：所以，该问题为凸规划。所以，该问题为凸规划。第四十八页，本课件共有54页49 如图所示，该问题如图所示

19、，该问题 最优解在最优解在C点取得。点取得。第四十九页，本课件共有54页50算法概述算法概述 一一一一个个个个算算算算法法法法（Algorithm)Algorithm)就就就就是是是是一一一一种种种种求求求求解解解解方方方方法法法法，它它它它可可可可看看看看作作作作为为为为一一一一个个个个循循循循环环环环过过过过程程程程，按按按按照照照照一一一一组组组组指指指指令令令令和和和和规规规规定定定定的的的的停停停停算算算算准准准准则则则则，产产产产生生生生近近近近似似似似解解解解序序序序列列列列，它它它它应应应应该该该该收收收收敛敛敛敛到到到到整整整整体体体体最最最最优优优优解解解解，但但但但由由由

20、由于于于于某某某某些些些些原原原原因因因因（不不不不连连连连续续续续性性性性、无无无无凸凸凸凸性性性性、规规规规模模模模大大大大、实实实实现现现现方方方方面面面面困困困困难难难难等等等等）常常常常使使使使得得得得计计计计算算算算难难难难以以以以符符符符合合合合以以以以上上上上条条条条件件件件，往往往往往往往往是是是是一一一一个个个个无无无无限限限限的的的的过过过过程程程程，因因因因而而而而给给给给出出出出停停停停算算算算准准准准则则则则，如如如如果果果果在在在在第第第第k次次循循环环时时，满满足足停停算算准准则则条条件，则停算。件，则停算。第五十页，本课件共有54页517.4 7.4 下降迭代算法下降迭代算法 下降方向下降方向：设设 ，若若存存在在 ，使使得得当当 时时，有有 ，则称，则称 为为 在在处的下降方向。处的下降方向。下降迭代法的基本思想下降迭代法的基本思想：若该点的序列收敛于若该点的序列收敛于若该点的序列收敛于若该点的序列收敛于 ，在一定条件下，在一定条件下，在一定条件下，在一定条件下，就是极点。就是极点。就是极点。就是极点。第五十一页，本课件共有54页52 下降迭代算法步骤：下降迭代算法步骤：第五十二页，本课件共有54页53几种终止迭代的准则：几种终止迭代的准则：第五十三页，本课件共有54页感谢大家观看第五十四页，本课件共有54页