用外点法求解非线性约束最优化问题

1、题目:31923JIANGXI UNIVERSITY OF FINANCE AND ECONOMICS用外点法求解非线性约束最优化问题学 院信息管理学院学生姓名余楠学号81320442专 业数量经济学届别2013指导教师易伟明职称教 授二O一三年十二月用外点法求解非线性约束最优化问题摘要约束最优化问题是一类重要的数学规划问题。本文主要研究了用外点罚函数 法对约束非线性规划问题进行求解。对于一个约束非线性规划用罚函数求解的基 本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列 无约束的极值问题。本文最后利用c语言编程得到满足允许误差内的最优解。本文主要对一个约束非线性规划问题

2、的实例，首先利用上述迭代的方法，计 算出各迭代点的无约束极值问题的最优解。然后应用c语言编程，得到精确地最 优解，需迭代四次次才使得8 0(*)定理1(Kuhn-Tucker条件)在(*)中假设：X*是局部最小值；f(X),gj (X) i=1,2,m 在点 X * 连续可微；* ( X * ),i e E二心比. * )=0, i = 1,2.,m 线性无关，则存在一组参数i ii=1u* 0,i = 1,2.,m,使得广义 Lagrange 函数L(X, p)= f (X) -工 p g(X)满足:iVf X*)* p*Vg G*)= 0i ii=1P* 0, i = 1,2.,m p*g

3、 X J= 0, i = 1,2 , mi i对以上定理做几点说明:Vf G*)工 p*Vg G * )= 0 本应是：VfX*)一p*Vg X*)= 0 或 r ) r )(，、.应Vf X *)=p*Vg G *),即Vf G *)是紧约束函数g。)在x *处的梯度的非负线性ieE组合，但若规定：当i W E时P *= 0,则等式可写成：Vf G*)-工p*Vg G*)= 0 ii ii=i，p*g.(X*)= 0当，e E时 有g.G*)= 0、p*g.k*)= 0当i W E时 有p* = 0(3)如果对所有i e E, VgG*)线性无关，则X*称为约束的一个正则点，即如果在X*处起

4、作用的约束函数的梯度是线性无关的，则X*是一个正则点。如果X*不 是正则点，则K-T条件可能不成立。定理2设X*是问题(*)的可行解，f(X), gj(X)i = 1,2.,m是凸函数，且在X*可微，又有X*满足K-T条件，则X*是全局最优解。根据以上两个定理可见，对凸规划来说，K-T条件也是借的充分必要条件。然而从具体例子可以看出利用极值的必要条件和充分条件去求非线性规划问题的最优解不都是很容易的，下面介绍应用广泛的外点罚函数法的基本算法。2.2外点罚函数法的基本思想它的基本思路是通过目标函数加上惩罚项，这种惩罚体现在求解过程中，对于 企图违反约束的那些迭代点，给与很大的目标函数值，迫使这一

5、系列无约束问题 的极小值点或者无限的向可行集逼近，或者一直保持在可行集内移动，直到收敛 于原来约束问题的极小值点。先考虑不含等式约束的非线性规划问题： TOC o 1-5 h z min/(X)R =Xg.&)Z 0,i = 1,2-,m)(1)如止()0当t 2。时 HYPERLINK l bookmark104 o Current Document 构造一个函数：p( )=.8 当t 0时现把 g.(X加为t，则当 x e R 时，P(g.(X)= 0,i = 1,2,.,m，当 X W R 时， HYPERLINK l bookmark110 o Current Document P (

6、g (X )=8, i = 1,2,-, m，即有：pG.G)0X e *时ii 8 当 X W R 时再构造函数：9(X)= f (X)+m P(g (X)求解无约束极值问题：min(X)ii=1(3)若有极小值X *，则由可看出，这时应有P (g (X顶=0, i = 1,2, -, m，即点iX* e R，因而X*不仅是问题(3)的最优解，同时也是原问题(1)的最优解。从而把 约束极值问题(1)的求解变为无约束极值问题(3)的求解。但是，用上述方法构造的函数p(t)在t = 0处不连续，更没有导数。为了求解 方便，将该函数修改为：P()=若-t 2 当 t 0修改后的函数PQ在t = 0

7、处的导数等于0，而且P(t)，P(t)对任意的t都连续。当 X e R 时仍有 m P(g (X)= 0，当 X W R 时有：0 咒 P(g (X) f (X*(M)。即使X*(M)a R，它也会相当接近于式(1) 的约束条件的边界。这是因为：若X*(M)为式(4)的最优解，则在M相当大的情况 下，只可能使并|min(0, g (X)1相当小，即X*(M)相当靠近约束域R的边界。ii=1函数9(X,M)称为罚函数，其中第二项M并P(g (X)称为惩罚项，M称为罚 ii=1因子。实际计算时，总是先给定一个初始点X (0)和初始罚因子M 0，求解无约束 1极值问题(4)： minp(X,M，若其

8、最优解X*(Mg R，则它已是(1)的最优解；否 则，以X*(M 1)为新的起始点，加大罚因子，取M1 M2，重新求解(4)。如此循环， 或者存在某个Mk，使得min(X,M)的最优解X* Mg R，即是式(1)的最优解； 或者存在M的一个无穷大序列：0 M1 M2 就从R的外部趋于R的 边界点。即趋于原问题(1)最优解X *。2.3约束非线性优化问题的外点罚函数法迭代步骤外点法的迭代步骤:第1步选取初始点X0，取M 0 (可取M=1)，给定8 0,令k=1；第2步求无约束极值问题的最优解X Q): min (x , M )=(x M ),其1+ M并k i =1kin(0, g(X k )1

9、 ；i则取M1 = CMk，其中若对某一个内 i eC = 510，置k=k+1,转(2)；否则，迭代终止，取X *= X()。由以上计算步骤可知，外点罚函数法迭代终止时，求得的是目标函数驻点的 一个近似点。三、题目举例用外点罚函数法求解约束非线性规划问题：min(咋+ 2X2)，s.t.气+ % 1设初始取为X(0)=(1,1) T,迭代到满足允许误差8 =0.001为止的解。四、问题求解3.1对原无约束非线性规划迭代构造罚函数中(X,M )= f(X)+ M产 Imin(0, g(X )2i=1,M )= X2 + 2X2 + M min(0, x + x 一1)1 = 2x + 2M m

10、in(0, x + x 1)1- = 4x + 2M min(0, x + x 1)2对于不满足约束条件的点X =G,X2，有：X + X2 1 = 0.001进行第二次迭代取 C=10，得 M 2 = CM=10代入公式(*)5，8G)=-兰 +1 = J_ w = 0.0018 1616x2 16进行第三次迭代M = 100代入公式(*)得x-g (X(3)=i200100302200 100 + 1 = 2 g302 302= 302 302=0.001进行第四次迭代M4 = 1000代入公式得气2000，300210003002(4 )=-鲍-迎 + 1 =3002 3002 = 0.

11、0013002至此满足了精度要求，迭代终止，所得原问题的最优近似解为:20003002牝 0.66710003002牝 0.3334x + 2M min(0, x + x -1)= 4x + 2M (x3.2对原约束非线性规划进行c语言编程求解就这样无限的迭代下去，直到-g. 1心）8为止，为此，我们可以用c语言编程得到，其算法设计如下图所示：C语言源程序代码：#include stdio.h”void fun(double a,double b,double w)(double re2;re0=re1=0.0;if(a0=0.0&a1=0.0)|(a0=0.0&b0=0.0)|(b0=0.0

12、&b1=0.0)|(a1=0.0&b1=0.0)(printf(无解);return;if(a0!=0.0)(if(a0*b1-a1*b0=0.0)(printf(无解);re1 = (a0*b2-b0*a2)/(a0*b1-a1*b0);re0 = (a2-re1*a1)/a0;else(re1=a2/a1;re0 = (a2-a1*re1)/b0;if(1-re0-re1w);printf(x1=%f ,re0);printf(x2=%fn,re1);void main()( double a13,b13,w;int m,c=1;printf(请输入初始罚因子:m=);scanf(%f,&

13、m);printf(请输入所要到的精度:w=);scanf(%f,&c);a10=2*m;a11=4+2*m;a12=2*m;b10=2+2*m;b11=2*m;b12=2*m;fun(a1,b1,w);所得结果截屏如图所示:*C: DocuAent s and Set t ingsstudent 桌面Debug3f 建 文本文档.eke隋瑜入初始罚因子罪=1 隋输入所宴刻的精度：w=0 -丽1 *1*.666667 x2 =0.333333 Press any key to continue五、结论与展望从求解的过程中可以看出，随着罚因子的增大，在求解无约束最优化问题的 过程中，将迫使乂0向

14、可行域接近。因此，很自然的会想到：初始罚因子气是 否取得大一些好呢？因为这样一开始就比较接近可行域。但是理论和实践都证明 了这样做是不合适的。当罚因子很大时，在惩罚函数的极小点附近，其等高线会 变得十分狭长，这就意味着其最小点位于一个十分狭长的深谷之中。为了使搜索 不至于太困难，M1不能选的过大，采取渐近的方式则情况就会得到改善。初始罚 因子一般可取广1，C=510，这在多数情况下较为恰当。外点法不只适用于含有不等式约束条件的非线性规划，对于含有等式约束的 问题也适用。外点法的另一个优点是初始点容易选择，它可以在整个n维空间中 选取。外点法的缺陷是：惩罚项的二阶偏导数在R的边界上不存在，因而在

15、选择 无约束最优化方法时要受到限制；另外，外点法的中间结果不是可行解，不能作 为近似最优解，只有迭代到最后才能得到切合实际的可行解。在使用罚函数法的 过程中，当点X（Mk）接近最优点时，即罚因子心/艮大时，罚函数9（X,Mk）的性质 变坏，这就是其Hesse矩阵陷入严重的病态，使搜索相当困难，严重时甚至过早 停机。这就是罚函数法所固有的困难。要克服这一困难，改进方法是：可考虑把 罚函数和Lagrange函数结合起来，构造一个新的增广Lagrange函数，通过求解 该函数的无约束极值来获得原问题的最优解。六、参考文献范玉妹，徐尔等编著.数学规划及其应用M.冶金工业出版社,2009黄红选等编著.运筹学：数学规划M.清华大学出版社,2006李虹等编著.C语言程序设计M.南京大学出版社,2010包振宇，孙干等编著.C语言程序设计M.清华大学出版社有限公司，2009刘满凤，陶长琪，柳键等编