关于非线性约束最优化方法-乘子法

1、非线性约束最优化方法乘子法1.1研究背景最优化理论与方法是一门应用性相当广泛的学科，它的最优性主 要表现在讨论决策问题的最佳选择性，讨论计算方法的理论性质，构 造寻求最佳解的计算方法，以及实际计算能力。伴随着计算数学理论 的发展、优化计算方法的进步以及计算机性能的迅速提高，规模越来 越大的优化问题得到解决。因为最优化问题广泛见于经济计划、工程 设计、生产管理、交通运输、国防等重要领域，它已受到政府部门、 科研机构和产业部门的高度重视。然而，随着人们对模型精度和最优 性的要求所得到的优化命题往往具有方程数多、变量维数高、非线性 性强等特点，使得相关变量的存储、计算及命题的求解都相当困难， 从而导

2、致大规模非线性优化很难实现。因此，寻求高效、可靠的大规 模非线性优化算法成为近年来研究的热点。本文讨论的问题属于非线性约束规划的范畴，讨论了其中的非线 性等式约束最优化问题方面的一些问题。1. 2非线性约束规划问题的研究方法非线性约束规划问题的一般形式为min /(x),兀 w r",(npl) st c,(兀)= 0, iw e = 1，2,，c.(x) 5 0,i w i = i + 1,1 + 2,.,z + m其中，/(x),c,.(x)是连续可微的.在求解线性约束优化问题时，可以利用约束问题本身的性质, 但是对于非线性约束规划问题，由于约束的非线性使得求解这类问题 比较复杂

3、、困难。因此，我们将约束问题转化为一系列无约束优化问 题，通过求解一系列无约束优化问题，来得到约束优化问题的最优解。 我们用到的几类主要的方法有:罚函数法、乘子法以及变尺度法。传统上我们所提出的非线性约束最优化方法一般都遵循下列三 个基本思路之一1借助反复的线性逼近把线性方法扩展到非线性优化问题中来2采用罚函数把约束非线性问题变换到一系列无约束问题3采用可变容差法以便同时容纳可行的和不可行的x矢量其中源于思路2的乘子罚函数法具有适合于等式及不等式约束 不要求初始点为严格内点，甚至不要求其为可行点对自由度的大小无 任何要求等特点。1.3乘子法罚函数法的主要缺点在于需要惩罚因子趋于无穷大，才能得到

4、约 束问题的极小点，这会使罚函数的hesse矩阵变得病态，给无约束问 题的数值求解带来很大问题，为克服这一缺点，hestenes和powell 于1964年各自独立地提出乘子法。所谓乘子法是：由问题的lagrange 函数出发，考虑它的精确惩罚，从而将约束优化问题化为单个函数的 无约束优化问题，它同精确罚函数法一样，具有较好的收敛速度和数 值稳定性，且避免了寻求精确罚函数法中关于罚参数阈值的困难，它 们一直是求解约束优化问题的主要而有效的算法。考虑如下非线性等式约束优化问题：(nep)min f (x)s. t. q(x) = °, i 二 1,2, ，！.设兀 为问题(nep)的最

5、优解，且它的lagrange函数为l(x, 2) = f(x) - x c(x)其中c(x)=(c(x)，c2(x),，c/(x) , 2 =(人，入，,&)t是与x相对 应的lagrange的乘了向量。在一般正规假设条件(fritz john必要 条件)下，(讥才)是l(x9a)的稳定点，即vxl(x) = 0o因此, 若能找到才，则厶幺才)的极小值是才,那么求解问题(nep)转化 成求解一个无约束极小化问题。然而l(x,a)的极小值往往不存在。为了避免出现厶(兀刃的极小值不存在的问题，我们构造增广 lagrange 函数如,力)=心“心)+扣(讥由于vx£(/,*) =

6、0,则vv(xz,cr) = vx£(x*, z) + ov c(x* )c(x*) = ovc(x*)c(x*) = 0 这样x*是的一个稳定点。由此可知，当a = x时，适当的选取ct可以使0(x,/tq)的无 约束极小点就是问题(nep)的最优解。1.4乘子法的相关定理和引理引理设w是沁畀阶矩阵，°为兀阶向量，若对一切满足 d0,atd = 0 ,均有dtwd>0 ,则存在a > 0 ,使当(y>a时，矩阵 w +aaat 正定.证明考虑集合(4. 20)只需证明，vrfe k,当时，有/(w+6i/)d>0.事实 上， vzo ,贝lj d=

7、 e k ,贝lj zt(w +(jaat)z>0 与 zdt (w aaat )d > 0 等价.令k, = dd1wd<0,de k,若 k = 0 ,贝0 vrfe k,有 dtwd>0 ,因此 vcr>0 ,有 dj (w+(raar)d>djwd>0 因 此假设 kt 0 , 当w k/k 时，有 dtwd >09 因止匕 0<7>o, dt (yv + aaat )d > dtwd > 0.下而考虑de k由于k是有界闭集，则函数/wd与s%)2在k 上取到极小值，不妨设(da)twd与(atd(2)2分别为函

8、数的极小值，并 且曲j。；否则由定理条件,有(di2)twd>0与dwk矛盾因此>0,当(7 n(j时，有dt(w +(yaat)rf = dtwd +(y(atd)2 > (j(l)rwrf(,)+<r(arrf尸 >0, 因此，vjg k, (4. 20)式成立.*定理1设兀 是问题(nep)的最优解，且满足二阶充分条件，其 相应的lagrange乘子为才，则当充分大时，x 为无约束优 化问题min=0(兀久 q)x的最优解，且满足二阶充分条件。证 只要证明对于充分大的ct,使得= 0并且 v>(/,x,ct)为对称正定矩阵，则命题成立。由于x *是最优

9、解所以q(x) = 0m = l,2，jv(/,z,<r)=w*)-zax*)i=lv(xz,(t)= v7(/)-2/l；v2cz(/) +(jbrb = va2l(/,z) + c«rb i=其中b = (vqcf),.,vc/(t)为hxl阶的矩阵，有一阶必要条 件知va.(/,/,ct) = o再有二阶充分条件可知，若对任意的ywm(f) = y|by = o,且兀0, 有/v/l(x/)y >0成立.因此，存在a >0,使得v：厶(门才"bwb为对称正定矩阵事实上，只需要证明v/£(xx) +(y*brb在 = yern y =1上是正

10、定的即可.对任意的yeq,/(vx2l(x,x) + brb)y = ytvx2l(x,x)y + a by 2» /vx2l(xx)y故只需证存在/ 0使得vx2l(x,x) + cr*brb在q_ = ygq|/v,2£(/,z)；0 上正定.对任意的y w q_ ,(vx2l(/, x) + ct*brb) y + inf 叭|by其中(7为va2l(/,x)的最小特征值。下面只需证明密“by02若即by =°,则存在几wq_,使得lim|by,| = o.因为%是有界序列，故有收敛了列，不妨设几t.wq_,因此有 ypjux；才)y 5 0.又由于h=|b

11、limjj|=liml|byj|=okt8at8故ye m(x),这与ytvx2l(xx')y0矛盾，从而有2inf b)r >0，这就证明了对于充分大的 (t ,矩阵vv2l(/,/) + obrb是对称正定的。定理2对给定的入(i "2小和(70,设x*是无约束优化问题min=0(兀入6的最优解，且满足二阶充分条件如果xc.(x ) = 0(/= 1,2,.,/),则t也是问题(nep)的最优解，且满足 二阶充分条件.1.5乘子罚函数法乘子罚函数法是解决非线性等式约束优化问题的一种重要方法，它具有不要求初始点为严格内点，不要求其为可行点，对自由度的大 小无任何要求的

12、特点,它利用lagrange乘子求近似解的方法逼近原 问题最优解，而不需要无穷大的罚因了，因此对它的研究有重要的理 论和实用价值最早的乘子罚函数法是由henstenes (1969)针对等 式约束问题导出的，其形式为：增广lagrange函数的另一种等价形式是在1969年rfl powell提出的, 其特征是对c;(x)进行平移，即用代替c;(x), 0i是参数，由此 powell (1969)得到罚函数:zy加2卩(兀入(t)= /(%)-才c(x)+ 牙工 £ (%) 一 0)2 i=i当构造岀函数0(xq)后，可以通过求解一个无约束问题得到约束 问题的最优解但事实上，做到这一点

13、很困难.因为0(兀,6中的才未 知，在得到t之前，我们是无法知道它的为了克服上述困难的我们 用参数2代替；t,得到增广lagrange函数也就是我们所说的乘了罚 函数0(兀，入(t)= /(x)+ ac(x)+ c2(x)9考虑其相应的无约束问题min 0(兀入(7),其最优解为x = x(a,ct).由前面定理1我们知道，只要当7充分大(不一定趋于8),就 有lim 元(入 er) = x .2t/t因此，要想求得只需要不断的调整参数2使之逐渐接近最优乘子；t.下面考虑如何调整参数使它逐渐接近才在给定於)s后，求解无约束问题min 0(兀,2 ，q),其最优解为兀.由无约束问题的一阶必要条件

14、有vj(x(k),於)qk)= vf(x(fc) + 炉)vc(兀)+ q c(兀)vc(x )=0, 当q充分大吋，由卿元(入6 = t可知严=兀v/(兀)-v/(x ),vc(x(') - vc(x),因此有v/(*j + 2 +cr/lc(xu)vc(x") = 0而在t处，由约束问题的一阶条件有v/dj + ztvcg) = 0,所以有才q炉)+qc(x)，这样得到乘子迭代公式2(d =z(k)+akc(xw).最后就是算法的终止准则条件若严是无约束问题的局部解，并且满足c(严)= 0,则有v/(f) +炉)vc(兀) = 0,因此,兀是约束问题的k-t点,炉)为相应的乘子.有定理2知兀 是约束问题(nep)的最优解，停止计算因此其终止准则为|c( )| < £其中£是指定的精度要求.1.6结论从原问题的l