非线性规划的概念和原理

1、第五章非线性规划的概念和原理非线性规划的理论是在线性规划的基础上发展起来的。1951年，库恩(H.W.Kuhn)和 塔克(A.W.Tucker)等人提出了非线性规划的最优性条件，为它的发展奠定了基础。以后随 着电子计算机的普遍使用，非线性规划的理论和方法有了很大的发展，其应用的领域也越来 越广泛，特别是在军事，经济，管理，生产过程自动化，工程设计和产品优化设计等方面都 有着重要的应用。一般来说，解非线性规划问题要比求解线性规划问题困难得多，而且也不像线性规划那 样有统一的数学模型及如单纯形法这一通用解法。非线性规划的各种算法大都有自己特定的 适用范围。都有一定的局限性，到目前为止还没有适合于各

2、种非线性规划问题的一般算法。 这正是需要人们进一步研究的课题。5.1非线性规划的实例及数学模型例题6.1投资问题:假定国家的下一个五年计划内用于发展某种工业的总投资为b亿元，可供选择兴建的项 目共有几个。已知第j个项目的投资为.亿元，可得收益为匕亿元，问应如何进行投资， 才能使盈利率(即单位投资可得到的收益)为最高？解：令决策变量为，则应满足条件Xj 1广1)= 0同时x应满足约束条件W a x_ bj=1乙X1,1j j最大。a xj jj=1例题6.2厂址选择问题：设有n个市场，第j个市场位置为(七,),它对某种货物的需要量为bj (j = 1,2, ,n)o 现计划建立m个仓库，第i个仓

3、库的存储容量为aj (i = 1,2, ,m)。试确定仓库的位置，使 各仓库对各市场的运输量与路程乘积之和为最小。.解：设第i个仓库的位置为(土,七.)(i = 12,m)，第i个仓库到第j个市场的货物供应量为乙一 (i = 1,2, ,m, j = 1,2,n)，则第i个仓库到第j个市场的距离为d = ： 1 - p 2 +(-q)目标函数为乙.二二,i=1 j=1i=1 j=1约束条件为：(1)(2)(3)i j(i = 1,2,每个仓库向各市场提供的货物量之和不能超过它的存储容量; 每个市场从各仓库得到的货物量之和应等于它的需要量； 运输量不能为负数。因此，问题的数学模型为：min z

4、y(x -p)2 + (y -q)2i j t i ji ji=1 j=1s.t.乙.a,j=1Y z 0,(i = 1,2,m, j = 1,2, ,n)一般非线性规划的数学模型可表示为：min f (x)；s.t. g,(X) 0 (i = 1,2,m),七(X)= 0,(j = 1,2,l)式中 X =(x,x , ,xg Rn 是 n 维向量，f, g. (i= 1,2；,m)，h(j= 1,2,l)都是12nIjRn - R1的映射(即自变量是n维向量，因变量是实数的函数关系)，且其中至少存在一个非线性映射。与线性规划类似，把满足约束条件的解称为可行解。若记X =匕站(X ) 0,

5、i = 1,2, ,m, hj (X )= 0, j = 1,2, ,l则称X为可行域。因此上述模型可简记为.min f (X )s.t. X gx当一个非线性规划问题的自变量X没有任何约束，或说可行域即是整个n维向量空间,即穴=Rn，则称这样的非线性规划问题为无约束问题:min f(X )或 min f (X )X eRn有约束问题与无约束问题是非线性规划的两大类问题，它们在处理方法上有明显的不 同。5.2无约束非线性规划问题5.2.1无约束极值条件对于二阶可微的一元函数f (x)，如果x*是局部极小点，则f ,(x *)= 0，并且 f，(x*) 0；反之，如果f r(x*)= 0，f r

6、r(x*)。5.2.3无约束极值问题的解法5.2.3.1梯度法（i）给定初始点X（。）， 0 ；，迭代停止，得近似极小点（ii）计算 f （x（k）和 Vf （x（k） X（k）和近似极小值f （X（k）；否则，进行下一步;（iii） 做一维搜索或取入 kW （x a） w （x a）（V一（）（一作为近似最佳步长， Vfx （k），v 2 f X （k） Pfx （W并计算 X（k+i） = X（k）一人kNf Q（k），令k = k +1，转向第二步。例题6.4求解无约束极值问题min f （X ）=（气-2 ）2 +（%2 -1）2 解：取X （0 ）= （0,0，Vf （X）=（2（气

7、-2）,2（气一1，则Vf（X（0）= （一4, 一2，V2f（X（0）=Vf（x（0）vf（x（0）1Vf（X（0）v 2 f （x（0）vf（X（0）= 2， X（1）= X （0 ）-X 0Vf G（0）= （2,1 ，Vf（X（1）=（0,0，故x（1）为极值点，极小值为fG（1）=0。5.2.3.2牛顿法对正定二次函数，f （x）= XtAx + Btx + c，其中A为n阶方阵，B为n维列向量， c为常数，设X*为其极小点，则Vf （X *）= AX *+ B = 0，所以AX * = -B ；任给X（0）e En， Vf G（0）= AX（0）+ B，消去 B，得Vf G（0）=

8、 AX（0）一 AX *所以 X* = X（。）- A-iVf （X（。），点。步长为1，一步即可达极小这说明，从任意近似点出发，沿-A-iVf （x（。）方向搜索，例题6.5求解无约束极值问题minf （X）=工2 + 5侦A-i =解：任取 X（。）=（2,1，Vf （X（。）=（4,1。X * = X （0） - A-iVf G（。）= （0,。由 Vf （X *）=（。,。）t 可知，x *确实为极小点。牛顿法与梯度法的搜索方向不同，优点是收敛速度快，但有时不好用而需采取改进措施，当维数较高时，A-i的计算量很大。5.3约束非线性规划问题前面我们介绍了无约束问题的最优化方法，但实际问题

9、中，大多数都是有约束条件的问 题。求解带有约束条件的问题比起无约束问题要困难得多，也复杂得多。在每次迭代时，不 仅要使目标函数值有所下降，而且要使迭代点都落在可行域内（个别算法除外）。求解带有 约束的极值问题常用方法是：将约束问题化为一个或一系列的无约束极值问题；将非线性规 划化为近似的线性规划；将复杂问题变为较简单问题等等。5.3.1凸规划问题约束问题的情况较为复杂，先讨论其中的一种较为特殊的情况，即凸规划问题。一般来说，非线性规划的局部最优解和全局最优解是不同的，但是，对凸规划问题，局 部最优解就是全局最优解。定义6.1设f （X）为定义在非空凸集S匚En上的实值函数，如果对于任意的两点X

10、 （i） e S， X（2） e S和任意实数人el。），恒有f GX（i） + （i-X）X（2）Xf （x（i）+（i-Df （x（2）则称f （x）为S上的凸函数。定理6.4设S是n维欧氏空间E上的一个开凸集，/（X）是定义在S上的具有二阶连 续导数的函数，那么，/（X）在S上为凸函数的充要条件是：对所有XeS,海赛矩阵 V2/（X）都是半正定的；如果对所有的XeS, V2/（X）都是正定的，则f（X）在s上 为严格凸函数。定义6.2非线性规划问题：min/（x）, X eEns.t. g（X）VO, i = 1,2, ,mih（X）= O, j= 1/2, pj中，如果 f （x）和

11、g （x） （i = l,2, ,m）为 x 的凸函数,3 （x）（顶= 1,2, ,p ）为XiJ的线性函数，则称此问题为一凸规划问题。.凸规划具有两个重要性质:1.凸规划的可行集是凸集证：设凸规划的可行集为s,即Rg（X）VO” = 1,2, ,m;h（X）=O” = 1,2, ,p; XeE ijn其中g（X）（，二 1,2, ,m）为X的凸函薮，h （x）（顶二 1,2,，万）为X的线性函数。，j对于任意的x（共S, X（2）eS和任意实数人6（0,1）,利用彳（x） （i = l,2, ,m）i的凸性，对X=X（1）+ （1人）x（2）,有g（x） 二i但g（x（i）vo, g （i

12、i所以g （x）oi同理/z（X）= Ojg Gx（i）+ （1一人）x（2）v*g（X（1）+（1 Dg（x（2）iiX（2）VO因此，X=2iX（i）+ （l人）x（2）es,故s 为凸集。2.凸规划的局部最小解就是它的全局最小解证：用反证法。设X*是凸规划的一个局部最小解，又是它的全局最小解，但X。X*。 因为 X * S，X G S，所以 VX e(0,1), X =XX *+(1人)X e S 由 f (X)为凸函数得，f (X)= f (XX*+(1 X)X)Xf (X*)+(1 X)f (X)因为X是一个全局最小解，所以f (X )X f (X *)+(1 x) f (X ) 0

13、112g (X )= x2 + x 1 0 g4 (X)= x2 0解：第1，3, 4三个约束条件为线性函数，因此也是凸函数;您(X)dx2第2个约束条件应写成g2 (X)=气2 x2 +1 0, i = 1,2, ,m或写成.min f (X )X e/其中可行域 X = XI X e En, g (X) 0,i = 1,2, ,m。i定义6.3对于上述问题，设X e/，若有gi (X )= 0 (1 i 0为点X处的起作用约束；若有gi (X ) 0 (1 i 0为点X处的不起作用约束。定义6.4对于上述非线性规划问题，如果可行点X处，各起作用约束的梯度向量线性无 关，则称X是约束条件的一

14、个正则点。库恩一塔克条件是非线性规划领域中的重要理论成果之一，是确定某点为局部最优解的 一阶必要条件，只要是最优点就必满足这个条件。但一般来说它不是充分条件，即满足这个 条件的点不一定是最优点。但对于凸规划，库恩塔克条件既是必要条件，也是充分条件。对于只含有不等式约束的非线性规划问题，有定理如下：定理6.5设X *是非线性规划问题min f(X)X以X =XIXwE，g (X)0,/ = l,2,.,mi的极小点，若X*起作用约束的梯度Vg(X*)线性无关(即X*是一个正则点)，则 i*=(/*,丫*, ，丫*),使下式成立12mW(X*)-u Y* -Vg (X*) = 0i ii=l 0,

15、 z =i对同时含有等式与不等式约束的问题minf (%)；s.t. g(X)O G = 1,2, ,m),ih(X)=O,(y = l,2,/)j为了利用以上定理，将久(X)=0,用j/z (x)o0i j来代替。这样即可得到同时含有等式与不等式约束条件的库恩塔克条件如下：设X*为上述问题的极小点，若X*起作用约束的梯度Vg和WZj(x*)线性无关,则m*=G*,y*, ，丫*)和*=(*,人*,，人*),使下式成立12m12m, fW(X*)-(X*)-2a* -V/z (X*) = 0i ij jZ=1j=l 0,z = 1,2,-,m例题6.7求下列非线性规划问题的K-T点：min f

16、 (X ) = 2x2 + 2xx + x2 -10 x - 10 x解：将上述问题的约束条件改写为g（X）0的形式:ig (X ) =-x 2 - x 2 + 5 0g (X ) = 3x x + 6 0Nf(X*)二设5点为X *=（x1，x2 ，有4 x + 2 x -101 22 x1 + 2 x2 -10由定理得Vgi (x *)二Ng2 (X *)=-2 xQ 1-2 x23-14x + 2x -10 + 2 x + 3 = 02x + 2x -10 + 2yx +y = 01(2 1 22y V5 - x2 - x2 )= 0y 2 (63尤-x2 )=0/ 01y2 0求解上述

17、方程组即可求出y 1 y 2 ,x1，x2 ,则可得到满足K-T条件的点。上述方程组是非线性方程组，求解时一般都要利用松紧条件（即上述方程组中的第3 4个方程），其实质是分析X *点处，哪些是不起作用约束，以便得到y i = 0,这样分情况讨论求解较为容易:（1）假设两个约束均是X *点处的不起作用约束，即有则有4 x + 2 x -10 = 02 x + 2 x -10 = 012解得x1 = 0 x = 52但将该点代入约束条件，不满足gj（X） 0，因此该点不是可行点。（2）若g1（X）0是起作用约束，g2（X）0是不起作用约束，则有Y2=。，则4 尤+ 2 x -10 + 2y x = 02 x + 2 x -10 + 2 x = 0121 25 - x2 - x2 ）= 01 1 2 0 1x1=1x = 2解得0是起作用约束，此时V 0，可以是V0，也可以是V= 0，若V= 0也成立，则结果同（1），已知求出的解不是可行点。（3）若g （X ） 0是不起作用约束，g 2 （X ） 0是起作用约束，即有V1 = 0，代入方程组，有4 x + 2 x -10 + 3丫 = 02； + 2； -1