高级运筹学-第9章：非线性规划

第 九 章：非线性规划模型9.1 基本概念和基本原理一、什么是 非线性规划 ：目标函数和约束条件中有非线性函数的规划问题。例 9-1 某企业生产一种产品 y需要生产资料 x1和 x2，用 经济计量学方法根据统计资料可写出生产函数为 :但是投入的资源有限，能源总共 1O个单位，而每单位生产资料 x1要消耗 1单位能源，每单位生产资料 x2要消耗 2单位能源。问 :应如何安排生产资料使产出最大？解 : Max 、生 产资 料 1(x1)生 产资 料 2(x2)能源限量能源 1 2 10产 量 y1例 9-2 某厂生产两种产品，第一种产品每件售价 30元，第二种产品每件售价 450元 。设 x1与 x2分别为第一、二种产品的数量，据统计 ， 生产第一种产品所需工作时间平均为 0.5小时，生产第二种产品所需工作时间平均为 (2+0.25x2)小时。已知该工厂在这段时间内允许的总工作时间为 800小时，试确定使总收入最大的生产计划？解 : Max 二、 非线性规划问题的特点局部最优点不是全局最优点。三、 极值问题1、一元函数 y=f(x) ： 极值点存在的必要条件： f(x)=0 ， 此时求出的 x0 为驻点。 极值点存在的充分条件：a. 若在驻点 x0 附近 f(x 0)0， 则该点 x0 为极小值点。产 品 1(x1)产 品 2(x2)工作时间限量工作时间 0.5 2+0.25 x2 800售价 30 45022、多元函数 y=f(X)=f(x1,x2, xn)： 在 X0 附近作泰勒展开，得3 极值点存在的必要条件： f(x)=0， 此时求出的 x0 为驻点。 极值点存在的充分条件：4四、 凸函数与凹函数 ：1、定义 ： y=f(x) 是 En中某凸集 R上的函数 对 0,1及 X1、 X2 R，且 X1X 2 若 fX1+(1-)X2 f(X1)+(1-)f(X2) ，则 f(x)为 R上的凸函数。若 fX1+(1-)X2 f(X1)+(1-)f(X2) ，则 f(x)为 R上的严格凸函数。 对 0,1及 X1、 X2 R， 且 X1X 2 若 fX1+(1-)X2 f(X1)+(1-)f(X2) ，则 f(x)为 R上的 凹 函数。若 fX1+(1-)X2 f(X1)+(1-)f(X2) ，则 f(x)为 R上的严格 凹 函数。yxo X1 X2X1+(1-)X2y=f(x)凸函数yxo X1 X2X1+(1-)X2y=f(x)凹 函数yxo X1 X2y=f(x)非凸 、 非 凹 函数52、性质 ： 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、 凸函数的局部极值与全局极值的关系若目标函数在可行域中为 凸函数，则其极值点为最优值点；若目标函数在可行域中为 严格凸函数，则其极值点为唯一最优值点。6五、 凸规划 ：1、定义 ： 非线性规划 ( 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、 N.L.P.问题分类 无约束条件的 NLP问题。 有约束条件的 NLP问题。2、 寻优方法 间接法 (解析法 )：适应于目标函数有简单明确的数学表达式。 直接法 (搜索法 )：目标函数复杂或无明确的数学表达式。a.消去法 (对单变量函数有效 )：不断消去部分搜索区间，逐步缩小极值点存在的范围。b.爬山法 (对多变量函数有效 )：根据已求得的目标值，判断前进方向，逐步改善目标值。 79.2 无约束条件下单变量函数寻优一、消去法原理：逐步缩小搜索区间，直至极值点存在的区间达到允许的误差范围为止。设要寻求 f(X)的 极小值点为 X* ，起始搜索区间为 a0,b0。x1、 x2 a0,b0，且 x2 x1， 计算 f(x1)和 f(x2)， 并且比较结果：f(x)xo a0 b0X*x1,x2 在 x*的右侧x1x2f(x)xo a0 b0X*x1,x2 在 x*的左侧x1x2f(x)xo a0 b0X*x1,x2 在 x*的两侧x1x2 x1,x2 均在 x*的右侧， f(x2) f(x1)， 去掉 x1,b0， 此时 x*a0,x1 x 1,x2 均在 x*的左侧， f(x2) f(x1)， 去掉 a0,x2， 此时 x*x2,b0 x 1,x2 均在 x*的两侧 ， f(x2) f(x1)：a.去掉 x1,b0， 此时 x*a0,x1 b.去掉 a0,x2， 此时 x*x2,b0 8二、黄金分割法 (0.618法 )：是一种常用的消去法与对分法、 Fibonacci法比较，具有计算次数少，过程简单的特点。1、原理：Lx L-xL x1x22、取点法则：L x1x2a0 b0L f(x 2)f(x 1)， 取 a1=a0,b1=x1 x 1=x2x 2=b1-(b1-a1) a1 b1x1x2 f(x 2) f(x1)， 取 a1=x2,b1=b0 x 1=a1+(b1-a1)x 2=x1 a1 b1x1x2计算 n个点后，总缩短率为 En=n-1 ， 可得试点数 n。 93、计算步骤：求函数 f(x)的极值点第一步：取初始区间 a0,b0 x1x2a0 b0 若求 f(x)的极小值点，则 f(x 2)f(x 1)， 取 a1=a0,b1=x1 x 1=x2x 2=b1-(b1-a1) f(x 2) f(x1)， 取 a1=x2,b1=b0 x 1=a1+(b1-a1)x 2=x1 a1 b1x1x2 a1 b1x1x2 若求 f(x)的极大值点，则 f(x 2)f(x 1)， 取 a1=a0,b1=x1 x 1=x2x 2=b1-(b1-a1) f(x 2) f(x1)， 取 a1=x2,b1=b0 x 1=a1+(b1-a1)x 2=x1第二步：求区间的缩短率10例 求解 f(x)=-18x2+72x+28 的极大值点 ， 0.1 ， 起始搜索区间为 0,3解： 用间接法：令 f (x)=-36x+72=0， 得驻点 x=2又因为 f (x)=-36 0， 故 x=2 为 f(x)的极大值点， fmax=100 用直接法中的黄金分割法：令 n-1=，得 n=1+(lg)/(lg)5.78442约 6步即可，计算结果见下表：k ak bk f(ak) f(bk) pk=bk- akpk/ p0 x1k=ak+ pkx2k=bk- pkf (x2k) f (x1k)0 0 3 28 82 3 1 1.854 1.146 86.9 99.62f(x)xo 3x1x21 1.146 3 86.9 82 1.854 0.618 2.292 1.854 99.62 98.462 1.146 2.292 86.9 98.46 1.146 0.382 1.854 1.584 96.89 99.623 1.584 2.292 96.89 98.46 0.708 0.236 2.022 1.854 99.62 99.994 1.854 2.292 99.62 98.46 0.438 0.146 2.125 2.022 99.99 98.725 1.854 2.125 99.62 99.72 0.271 0.0903119.3 无约束条件下多变量函数寻优一、爬山法原理：通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。由以下二部分组成： 选定搜索方向； 在选定的方向上爬山搜索。二、变量轮换法 (或降维法 ):选择与坐标轴平行的方向为搜索方向设 S=f(X)=f(x1,x2, xn)， 极值点存在的区间为x1*a1,b1， x2*a2,b2， ， xn*an,bn1、 原理 ： 从起点 X(0) 出发 ， 沿平行于 x1 轴的方向 P(1)进行一维搜索，求得 f(X) 在该方向 P(1)上近似极值点 X(1) ； 从点 X(1) 出发 ， 沿平行于 x2 轴的方向 P(2)进行一维搜索，求得 f(X) 在该方向 P(2)上近似极值点 X(2) ； 从点 X(2) 出发 ， 照此交替进行下去，直至满足给定的精度 为止|f(X(k) -f(X(k-1)| 或 |S(k)-S(k-1)| 122、 算法步骤：设 S=f(X)=f(x1,x2)， 极值点存在的区间为 x1*a1,b1， x2*a2,b2第一步：从 X(0)=(x1(0),x2(0)T出发 先固定 x1=x1(0): 求以 x2为单变量的目标函数的极值点，得 X(1)=(x1(0),x2(1)T ， S(1)=f(X(1) 再固定 x2=x2(1): 求以 x1为单变量的目标函数的极值点，得 X(2)=(x1(2),x2(1)T ， S(2)=f(X(2)此时 S(2)优于 S(1)，且 搜索区间缩短为 x1*x1(2),b1， x2*x2(1),b2第二步：如此交替搜索，直至满足给定精度 为止|f(X(k) -f(X(k-1)| 或 |S(k)-S(k-1)| o x1X(0) X(1) X(2)X(3)X(4)x213例 求 S = f(x) = x12 + x22 - x1x2 -10x1 - 4x2 + 60 的极小值点， =0.01解：设起始点 X(0)=(0,0)T， 用变量轮换法 计算： 先固定 x1=x1(0)=0: 则 f(0,x2)=x22 - 4x2 +60， 寻优得 x2(1)=2于是 X(1)=(x1(0),x2(1)T=(0,2)T ， S(1)=f(X(1)=56 再固定 x2=x2(1)=2: 则 f(x1,2)=x12 - 12x1 +56， 寻优得 x1(2)=6于是 X(2)=(x1(2),x2(1)T=(6,2)T ， S(2)=f(X(2)=20如此交替搜索，直至满足给定精度 =0.01 为止|f(X(k) -f(X(k-1)| 0.01 或 |S(k)-S(k-1)| 0.01最后得极小点 X*=(8,6)T， f(X*)=8o x1X(0) X(1) X(2)X(3)X(4)x2计算结果见下表：14k 固定的xi单变 量的目 标 函数f(xj)求得极点 xj 目 标值S(k)|S( k ) - S( k-1 )|12345678x1=x1(0)=0x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.88x2=x2(7)=5.94f(0,x2)=x22 - 4x2 +60f(x1,2)=x12 - 12x1 +56f(6,x2)=x22 - 10x2 +36f(x1,5)=x12 - 15x1 +65f(7.5,x2)=x22 11.5x2 +41.25f(x1,5.75)=x12 15.75x1 +70.06f(7.88,x2)=x22 11.88x2 +43.27f(x1,5.94)=x12 15.94x1 +71.50x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.875x2=x2(7)=5.94x1=x1(8)=7.975620118.758.18758.04698.01178.00293692.250.56250.14060.03520.0088o x1X(0) X(1) X(2)X(3)X(4)x2缺点 ： 很大程度上取决于目标函数性质。目标函数等高线的性质很重要。 道路迂回曲折，多次变换方向，在极点附近，目标值改进更小，收敛速度慢。故不是一个有利方向。 15三、一阶梯度法 (最速下降或上升法 ):选择负梯度方向为搜索方向设求 S=f(X)=f(x1,x2, xn)的极值点 。1、 原理 ： 从起点 X(0) 出发 ， 沿某个有利方向 P(0) 进行一维搜索，求得 f(X) 在 P(0) 方向近似极小点 X(1) ； 从点 X(1) 出发 ， 沿某个新有利方向 P(1) 进行一维搜索，求得 f(X) 在 P(1) 方向近似极小点 X(2) ； 从点 X(2) 出发 ， 照此进行下去，直至满足给定的精度 为止|f(X(k) -f(X(k-1)| 或 |S(k)-S(k-1)| 2、 算法步骤：设求 S=f(X)=f(x1,x2)的极值点。第一步：从给定起点 X(0) 出发第二步：从点 X(1) 出发 ， 照此进行下去，直至满足给定的精度 为止|f(X(k+1) -f(X(k)| 或 |G(k) | 16例 求 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 17计算结果见下表：缺点 ： 搜索效果比变量轮换法快，但愈接近极值点，步长愈小，目标值改进愈小。当遇到强交互作用时，不是有效的方法 ;当遇到山脊时，会慢慢爬行。 在远离极点时，收敛速度较快 ;在极点附近，收敛速度不快。k01234507.636.817.957.827.9903.055.115.565.875.93-102.21-1.490.33-0.220.05-4-5.53-0.60-0.82-0.09-0.1210.775.591.600.890.240.13-0.930.37-0.930.37-0.930.37-0.37 -0.93-0.37-0.93-0.37-0.9288.222.211.220.330.180.056015.749.158.178.038.003744.266.590.980.140.026o x1x(0)x(1)x(2)X(3)x218四、共轭梯度法 :选择共轭方向为搜索方向 问题的提出： 在极值点附近，如何加快收敛速度，须对函数在极值点附近的性质进行研究。设有 n维目标函数 S=f(X)=f(x1,x2, xn),在极值点 X*附近展开成泰勒级数 ：特别：对二元二次函数，可证明：在极值点附近，其等高线可近似视为同心椭园族，而同心椭园族的任意两根平行切线的切点连线必通过椭园中心。o x1X(0)P(0)X(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1) P(1)与 P(0)共轭故：在极值点附近，沿搜索方向 P(0)上巳得到一个切点 X(1)， 则只要得出通过极值点的连线方向P(1),在此方向上寻优 ,可一步直达极值点。而这个连线方向 P(1)是 上一次搜索方向 P(0)的共轭方向。 19 共轭方向的定义：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 对称正定矩阵20特别：对二元二次函数 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)为该等高线的法线方向，这两个方向正交。o x1X(0)P(0)X(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1)P(1)与 P(0)共轭故 :对二元二次函数 ,只须搜索两个方向 P(0)和 P(1)就可达到极值点 X* 。一般 :对 n元二次函数 ,可用不超过 n次搜索就可达到极值点 X* 。而 n元非二次函数在极值点附近可用二次函数逼近。 21 寻优步骤：例 求 S = f(x) = x12 + x22 - x1x2 -10x1 - 4x2 + 60 的极小值点。解o x1X(0)P(0)X(1)x222即o x1X(0)P(0)X(1)x2P(1)与 P(0)共轭X(2)对二元二次函数 ,只须两次搜索就可达到极值点 X* , 一般 :对 n元二次函数 ,可用不超过 n次搜索就可达到极值点 X* 。而 n元非二次函数在极值点附近可用二次函数逼近。 23 适用于一般目标函数的共轭梯度法：1、共轭方向的计算问题：须用到目标函数的海赛矩阵 H(二阶偏导数矩阵 )，若目标函数为二次函数时， H 容易求出；若目标函数为高次或高维函数时， H 难以求出，此时共轭方向难以求出。2、共轭方向的计算方法： F-R 法，由 Fletcher和 Reeves提出，可避免海赛矩阵 H 的计算，方便地确定共轭方向，