资源描述：
《关于非线性约束最优化方法-乘子法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、非线性约束最优化方法——乘子法1.1研究背景最优化理论与方法是一门应用性相当广泛的学科，它的最优性主要表现在讨论决策问题的最佳选择性，讨论计算方法的理论性质，构造寻求最佳解的计算方法，以及实际计算能力。伴随着计算数学理论的发展、优化计算方法的进步以及计算机性能的迅速提高，规模越来越大的优化问题得到解决。因为最优化问题广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领域，它已受到政府部门、科研机构和产业部门的高度重视。然而，随着人们对模型精度和最优性的要求所得到的优化命题往往具有方程数多、变量维数高、非线性性强等特点，使得相关变量的存储、计算及命题的求解都相当困难，
2、从而导致大规模非线性优化很难实现。因此，寻求高效、可靠的大规模非线性优化算法成为近年来研究的热点。本文讨论的问题属于非线性约束规划的范畴，讨论了其中的非线性等式约束最优化问题方面的一些问题。1.2非线性约束规划问题的研究方法非线性约束规划问题的一般形式为min/(x),兀wR",(NPL)stc,(兀)=0,iwE={1，2,，c.(x)50,iwI=[I+1,1+2,.・・,Z+m}其中，/(x),c,.(x)是连续可微的.在求解线性约束优化问题时，可以利用约束问题本身的性质,但是对于非线性约束规划问题，由于约束的非线性使得求解这类问题比较复杂、困难。因此，我们将约束问题
3、转化为一系列无约束优化问题，通过求解一系列无约束优化问题，来得到约束优化问题的最优解。我们用到的几类主要的方法有:罚函数法、乘子法以及变尺度法。传统上我们所提出的非线性约束最优化方法一般都遵循下列三个基本思路之一1借助反复的线性逼近把线性方法扩展到非线性优化问题中来2采用罚函数把约束非线性问题变换到一系列无约束问题3采用可变容差法以便同时容纳可行的和不可行的X矢量其中源于思路2的乘子罚函数法具有适合于等式及不等式约束不要求初始点为严格内点，甚至不要求其为可行点对自由度的大小无任何要求等特点。1.3乘子法罚函数法的主要缺点在于需要惩罚因子趋于无穷大，才能得到约束问题的极小点，
4、这会使罚函数的Hesse矩阵变得病态，给无约束问题的数值求解带来很大问题，为克服这一缺点，Hestenes和Powell于1964年各自独立地提出乘子法。所谓乘子法是：由问题的Lagrange函数出发，考虑它的精确惩罚，从而将约束优化问题化为单个函数的无约束优化问题，它同精确罚函数法一样，具有较好的收敛速度和数值稳定性，且避免了寻求精确罚函数法中关于罚参数阈值的困难，它们一直是求解约束优化问题的主要而有效的算法。考虑如下非线性等式约束优化问题：(NEP)minf(x)s.t.q(x)=°,i二1,2,・・・，！.设兀为问题(NEP)的最优解，且它的Lagrange函数为L(
5、x,2)=f(x)-Xc(x)其中C(X)=(C](X)，C2(X),・・・，C/(X)),2=(人，入，…,&)T是与x相对应的Lagrange的乘了向量。在一般正规假设条件(FritzJohn必要条件)下，(讥才)是L(x9A)的稳定点，即VxL(x^)=0o因此,若能找到才，则厶幺才)的极小值是才,那么求解问题(NEP)转化成求解一个无约束极小化问题。然而L(x,A)的极小值往往不存在。为了避免出现厶(兀刃的极小值不存在的问题，我们构造增广Lagrange函数如,力)=心“心)+扣(讥⑴由于Vx£(/,^*)=0,则Vv^(xZ,cr)=Vx£(x*,Z)+oVc
6、(x*)c(x*)=oVc(x*)c(x*)=0这样X*是的一个稳定点。由此可知，当A=X时，适当的选取CT可以使0(x,/Tq)的无约束极小点就是问题(NEP)的最优解。1.4乘子法的相关定理和引理引理设W是沁畀阶矩阵，°为兀阶向量，若对一切〃满足d^0,aTd=0,均有dTWd>0,则存在a>0,使当(y>a时，矩阵W+aaaT正定.证明考虑集合(4.20)只需证明，VrfeK,当时，有/(W+6i/)d>0.事实上，Vz^O,贝ljd=—eK,贝ljzT(W+(jaaT)z>0与zdT(WaaaT)d>0等价.令K,={dd1Wd<0,deK},若K=0,贝0Vrf
7、eK,有dTWd>0,因此Vcr>0,有dJ(W+(raar)d>dJWd>0•因此假设Kt0,当〃wK/K时，有dTWd>09因止匕0<7>O,dT(yv+aaaT)d>dTWd>0.下而考虑deK由于K是有界闭集，则函数/Wd与S%)2在K上取到极小值，不妨设(da))TWd⑴与(aTd(2))2分别为函数的极小值，并且曲J。；否则由定理条件,有(di2))TWd⑵>0与d⑵wK‘矛盾•因此>0,当(7n(J时，有dT(W+(yaaT)rf=dTWd+(y(aTd)2>(J(l))rWrf(,)+
