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

第四章：非线性规划,一、什么是非线性规划： 目标函数和约束条件中有非线性函数的规划问题。,例1 某企业生产一种产品y需要生产资料x1和x2，用经济计量学方法根据统计资料可写出生产函数为:,但是投入的资源有限，能源总共1O个单位，而每单位生产资料x1要消耗1单位能源，每单位生产资料x2要消耗2单位能源。 问:应如何安排生产资料使产出最大？,解: Max,、,例2 某厂生产两种产品，第一种产品每件售价30元，第二种产品每件售价450 元。设x1与x2分别为第一、二种产品的数量，据统计，生产第一种产品所需工作 时间平均为0.5小时，生产第二种产品所需工作时间平均为(2+0.25x2)小时。已 知该工厂在这段时间内允许的总工作时间为800小时，试确定使总收入最大的生 产计划？,解: max,二、非线性规划问题的特点 局部最优点不是全局最优点。 三、极值问题 1、一元函数 y=f(x) ： 局部极值点存在的必要条件：f(x0)=0，此时求出的 x0 为驻点。 局部极值点存在的充分条件： a. 若f(x0)0，则该点 x0 为局部极小值点。,2、多元函数 y=f(X)=f(x1,x2,xn)：在 X0 附近作泰勒展开，得, 极值点存在的必要条件：f(x)=0，此时求出的 x0 为驻点。, 极值点存在的充分条件：,二次型ZTHZ称为半正定，如果对任意Z0,有ZTHZ0 二次型ZTHZ称为正定， 如果对任意Z0,有ZTHZ0,四、凸函数与凹函数： 1、定义：y=f(x) 是En中某凸集R上的函数 对(0,1)及X1、X2 R，且 X1X2 若fX1+(1-)X2f(X1)+(1-)f(X2) ，则f(x)为R上的凸函数。 若fX1+(1-)X2f(X1)+(1-)f(X2) ，则f(x)为R上的严格凸函数。 对(0,1)及X1、X2 R，且 X1X2 若fX1+(1-)X2f(X1)+(1-)f(X2) ，则f(x)为R上的凹函数。 若fX1+(1-)X2f(X1)+(1-)f(X2) ，则f(x)为R上的严格凹函数。,2、性质：fi(X) 为凸集R上的凸函数，则对ki0，i=1,2,m，有 k1f1(X)+k2f2(X)+kmfm(X)仍为凸函数。 3、凸函数的判定：f(X) 定义在凸集R上，若f(X)有连续的二阶导数， 则f(X)为凸函数 H为半正定。 f(X)为严格凸函数 H为正定。 4、凸函数的局部极值与全局极值的关系 若目标函数在可行域中为凸函数，则其极值点为最优值点； 若目标函数在可行域中为严格凸函数，则其极值点为唯一最优值点。,五、凸规划： 1、定义：非线性规划,若 f(X)，-gi(X)为凸函数，则( p )称为凸规划。,2、性质： ( p )的可行解集 R 是凸集；最优解集 R* 也是凸集。 ( p )的任何局部最优解均是全局最优解。 若f(X)为严格凸函数时，其最优解必唯一。 特例:线性函数既是凸函数又是凹函数，故 L.P. 为凸规划。,六、寻优方法概述： 1、非线性规划问题分类 无约束条件的非线性规划。 有约束条件的非线性规划。 2、寻优方法 间接法(解析法)：适应于目标函数有简单明确的数学表达式。 直接法(搜索法)：目标函数复杂或无明确的数学表达式。 a.消去法(对单变量函数有效)： 不断消去部分搜索区间，逐步缩小极值点存在的范围。 b.爬山法(对多变量函数有效)： 根据已求得的目标值，判断前进方向，逐步改善目标值。,迭代法,无约束极值问题的解法,一、梯度法(最速下降法):选择负梯度方向为搜索方向,2、算法步骤：设求 S=f(X)=f(x1,x2,.,xn)的极值点。 第一步：从给定起点 X(0) 出发,第二步：从点 X(1) 出发，照此进行下去，直至满足给定的精度为止: |f(X(k+1) -f(X(k)| or | f(X(k)|,例 求 S = f(x) = x12 + x22 - x1x2 -10x1 - 4x2 + 60 的极小值点， =0.1,解:,从点 X(1) 出发，照此进行下去，直至满足给定的精度 =0.1 为止 |f(X(k+1) -f(X(k)|0.1 或 |G(k) |0.1,计算结果见下表：,缺点：愈接近极值点，步长愈小，目标值改进愈小。 当遇到山脊时，会慢慢爬行。 在远离极点时，收敛速度较快; 在极点附近，收敛速度不快。,二、共轭梯度法:选择共轭方向为搜索方向 问题的提出：在极值点附近，如何加快收敛速度， 须对函数在极值点附近的性质进行研究。 设有n维目标函数 S=f(X)=f(x1,x2,xn),在极值点X*附近展开成泰勒级数：,特别：对二元正定二次函数，可证明：在极值点附近，其等高线可近似视为同心 椭园族，而同心椭园族的任意两根平行切线的切点连线必通过椭园中心。,故：在极值点附近，沿搜索方向P(0)上巳得到一个 切点X(1)，则只要得出通过极值点的连线方向 P(1),在此方向上寻优,可一步直达极值点。 而这个连线方向P(1)是上一次搜索方向P(0)的 共轭方向。, 共轭方向的定义： 1、定义：设 X,Y 是n维向量空间En中两个向量，A 为nn对称正定矩阵， 若 XTAY = 0 ，则称向量X与Y对于矩阵A共轭。 特例：若 A = I，得 XTY = 0，则称向量X与Y正交。 2、几何意义：共轭方向是通过极值点的方向。, 寻优原理： 设n元函数 S=f(X)=f(x1,x2,xn),在极值点X*附近可用一个二次函数逼近,其中 H 为nn对称正定矩阵,特别：对二元正定二次函数 S=f(X)=f(x1，x2) 从某点X(0)出发,以P(0)方向搜索,使f(X)达到极小值点X(1), 则:X(1)必为该点处等高线的切点,P(0)为切线方向， 且点X(1)的梯度方向f(X(1)为该等高线的法线方向，这两个方向正交。,从另一点X(0)出发,仍以P(0)方向搜索,使f(X)达到另一个极小值点X(2), 则:X(2)也必为该点处等高线的切点,P(0)为切线方向， 且点X(2)的梯度方向f(X(2)为该等高线的法线方向，这两个方向正交。,故:对二元正定二次函数,只须搜索两个方向P(0)和P(1)就可达到极值点 X* 。 一般:对n元正定二次函数,可用不超过n次搜索就可达到极值点 X* 。 而n元非二次函数在极值点附近可用二次函数逼近。, 寻优步骤： 例 求 S = f(x) = x12 + x22 - x1x2 -10x1 - 4x2 + 60 的极小值点。,解,对二元二次函数,只须两次搜索就可达到极值点 X* , 一般:对n元二次函数,可用不超过n次搜索就可达到极值点 X* 。 而n元非二次函数在极值点附近可用二次函数逼近。, 适用于一般目标函数的共轭梯度法： f(x)为严格凸函数，且具有二阶连续偏导数