非线性规划：无约束极值问题

《非线性规划：无约束极值问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章：非线性规划一、什么是非线性规划：目标函数和约束条件中有非线性函数的规划问题。例1某企业生产一种产品y需要生产资料x1和x2，用经济计量学方法根据统计资料可写出生产函数为:但是投入的资源有限，能源总共1O个单位，而每单位生产资料x1要消耗1单位能源，每单位生产资料x2要消耗2单位能源。问:应如何安排生产资料使产出最大？解:Max、生产资料1(x1)生产资料2(x2)能源限量能源1210产量y例2某厂生产两种产品，第一种产品每件售价30元，第二种产品每件售价450元。设x1与x2分别为第一、二种产品的数量，据统计，生产第一种产品所需工作时间平均为0.5小时，生

2、产第二种产品所需工作时间平均为(2+0.25x2)小时。已知该工厂在这段时间内允许的总工作时间为800小时，试确定使总收入最大的生产计划？解:max二、非线性规划问题的特点局部最优点不是全局最优点。三、极值问题1、一元函数y=f(x)：①局部极值点存在的必要条件：f’(x0)=0，此时求出的x0为驻点。②局部极值点存在的充分条件：a.若f’’(x0)<0，则该点x0为局部极大值点。b.若f’’(x0)>0，则该点x0为局部极小值点。产品1(x1)产品2(x2)工作时间限量工作时间0.52+0.25x2800售价304502、多元函数y=f(X)=f(x1,x2,…

3、,xn)：在X0附近作泰勒展开，得①极值点存在的必要条件：f(x)=0，此时求出的x0为驻点。②极值点存在的充分条件：二次型ZTHZ称为半正定，如果对任意Z≠0,有ZTHZ≥0二次型ZTHZ称为正定，如果对任意Z≠0,有ZTHZ>0四、凸函数与凹函数：1、定义：y=f(x)是En中某凸集R上的函数①对(0,1)及X1、X2R，且X1≠X2若f[X1+(1-)X2]≤f(X1)+(1-)f(X2)，则f(x)为R上的凸函数。若f[X1+(1-)X2]＜f(X1)+(1-)f(X2)，则f(x)为R上的严格凸函数。②对(0,1)及X

4、1、X2R，且X1≠X2若f[X1+(1-)X2]≥f(X1)+(1-)f(X2)，则f(x)为R上的凹函数。若f[X1+(1-)X2]＞f(X1)+(1-)f(X2)，则f(x)为R上的严格凹函数。yxoX1X2X1+(1-)X2y=f(x)凸函数yxoX1X2X1+(1-)X2y=f(x)凹函数yxoX1X2y=f(x)非凸、非凹函数2、性质：fi(X)为凸集R上的凸函数，则对ki≥0，i=1,2,…,m，有k1f1(X)+k2f2(X)+…+kmfm(X)仍为凸函数。3、凸函数的判定：f(X)定义在凸集R上，若f(X)有连

5、续的二阶导数，则f(X)为凸函数H为半正定。f(X)为严格凸函数H为正定。4、凸函数的局部极值与全局极值的关系若目标函数在可行域中为凸函数，则其极值点为最优值点；若目标函数在可行域中为严格凸函数，则其极值点为唯一最优值点。五、凸规划：1、定义：非线性规划(p)Minf(X)gi(X)≥0，i=1,2,…,m若f(X)，-gi(X)为凸函数，则(p)称为凸规划。2、性质：①(p)的可行解集R是凸集；最优解集R*也是凸集。②(p)的任何局部最优解均是全局最优解。③若f(X)为严格凸函数时，其最优解必唯一。特例:线性函数既是凸函数又是凹函数，故L.P.为凸规划。六、

6、寻优方法概述：1、非线性规划问题分类①无约束条件的非线性规划。②有约束条件的非线性规划。2、寻优方法①间接法(解析法)：适应于目标函数有简单明确的数学表达式。②直接法(搜索法)：目标函数复杂或无明确的数学表达式。a.消去法(对单变量函数有效)：不断消去部分搜索区间，逐步缩小极值点存在的范围。b.爬山法(对多变量函数有效)：根据已求得的目标值，判断前进方向，逐步改善目标值。迭代法无约束极值问题的解法一、梯度法(最速下降法):选择负梯度方向为搜索方向2、算法步骤：设求S=f(X)=f(x1,x2,...,xn)的极值点。第一步：从给定起点X(0)出发第二步：从点X(1

7、)出发，照此进行下去，直至满足给定的精度为止:

8、f(X(k+1))-f(X(k))

9、＜or

10、

11、▽f(X(k))

12、

13、＜例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的极小值点，=0.1解:①②从点X(1)出发，照此进行下去，直至满足给定的精度=0.1为止

14、f(X(k+1))-f(X(k))

15、＜0.1或

16、

17、G(k)

18、

19、＜0.1计算结果见下表：缺点：①愈接近极值点，步长愈小，目标值改进愈小。当遇到山脊时，会慢慢爬行。②在远离极点时，收敛速度较快;在极点附近，收敛速度不快。k01234507.636.817.957.827.9903.055.

20、115.5