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

第四章：非线性规划 一、什么是非线性规划： 目标函数和约束条件中有非线性函数的规划问题。 二、非线性规划问题的特点 局部最优点不是全局最优点。 三、极值问题 1、一元函数 y=f(x) ： ① 局部极值点存在的必要条件：f’(x0)=0，此时求出的 x0 为驻点。 ② 局部极值点存在的充分条件： a. 若f’’(x0)0，则该点 x0 为局部极大值点。 b. 若f’’(x0)0，则该点 x0 为局部极小值点。 2、多元函数 y=f(X)=f(x1,x2,…,xn)：在 X0 附近作泰勒展开，得 四、凸函数与凹函数： 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)及?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上的严格凹函数。 2、性质：fi(X) 为凸集R上的凸函数，则对?ki≥0，i=1,2,…,m，有 k1f1(X)+k2f2(X)+…+kmfm(X)仍为凸函数。 3、凸函数的判定：f(X) 定义在凸集R上，若f(X)有连续的二阶导数， 则f(X)为凸函数 ? H为半正定。 f(X)为严格凸函数 ? H为正定。 4、凸函数的局部极值与全局极值的关系 若目标函数在可行域中为凸函数，则其极值点为最优值点； 若目标函数在可行域中为严格凸函数，则其极值点为唯一最优值点。 五、凸规划： 1、定义：非线性规划 迭代法 无约束极值问题的解法 * 例1 某企业生产一种产品y需要生产资料x1和x2，用经济计量学方法根据统计资料可写出生产函数为: 但是投入的资源有限，能源总共1O个单位，而每单位生产资料x1要消耗1单位能源，每单位生产资料x2要消耗2单位能源。 问:应如何安排生产资料使产出最大？ 解: Max 、 10 能源 限量 产量y 2 1 能源 生产资料2 (x2) 生产资料1 (x1) 例2 某厂生产两种产品，第一种产品每件售价30元，第二种产品每件售价450 元。设x1与x2分别为第一、二种产品的数量，据统计，生产第一种产品所需工作 时间平均为0.5小时，生产第二种产品所需工作时间平均为(2+0.25x2)小时。已 知该工厂在这段时间内允许的总工作时间为800小时，试确定使总收入最大的生 产计划？ 解: max 800 工作时间 限量 450 30 售价 2+0.25 x2 0.5 工作时间 产品2 (x2) 产品1 (x1) ① 极值点存在的必要条件：?f(x)=0，此时求出的 x0 为驻点。 ② 极值点存在的充分条件： 二次型ZTHZ称为半正定，如果对任意Z≠0,有ZTHZ≥0 二次型ZTHZ称为正定， 如果对任意Z≠0,有ZTHZ0 y x o X1 X2 ?X1+(1-?)X2 y=f(x) ? ? 凸函数 y x o X1 X2 ?X1+(1-?)X2 y=f(x) ? ? 凹函数 y x o X1 X2 y=f(x) 非凸、非凹函数 ( p ) Min f(X) gi(X)≥0 ，i=1,2,…,m 若 f(X)，-gi(X)为凸函数，则( p )称为凸规划。 2、性质： ① ( p )的可行解集 R 是凸集；最优解集 R* 也是凸集。 ② ( p )的任何局部最优解均是全局最优解。 ③ 若f(X)为严格凸函数时，其最优解必唯一。 特例:线性函数既是凸函数又是凹函数，故 L.P. 为凸规划。 六、寻优方法概述： 1、非线性规划问题分类 ① 无约束条件的非线性规划。 ② 有约束条件的非线性规划。 2、寻优方法 ① 间接法(解析法)：适应于目标函数有简单明确的数学表达式。 ② 直接法(搜索法)：目标函数复杂或无明确的数学表达式。 a.消去法(对单