极大熵方法与指数罚函数

1、第18卷第2期数学研究与评论Vol 18Nq 2I 9 9 8 年 5 月 JOURNAL OFMATHEMATrAL RESEARCH AND EXPOS IT DN M ay 1 9 9 8陈国庆唐焕文(内蒙古大学数学系.呼和浩特010021)(大连理工大学应用数学系.116024)就非线性极大极小问魁阐明了极大埔方法与指数罚方法的关系通过分析 相关Hessian阵的条件数对二者进行了对比极大烤方法.指数罚方法.极大极小问题不可微规划AM S( 1991) 90C/tCL 0 221I考虑极大极小问题m ) = m in m ax p( (x),(1)其中gcRJRA 1,2,加连续可微因

2、的不可微性问题(1)通常属不可微优化范畴 文1 I利用极大炳原理导出一类逼近氓小的可微函数m卑(x) =In刀exp cg,(x) , c > Q(2)易证I in V(x)=,且0 V0(x) <M.vXc 1995年8月21日收到国家教委博士点基金资助项目297 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.ln/n, Vx R：基于该性质文1 提出求解C*-*. cn极大极小问题的算法其简单便易、数值效果良好的特点已引起人们的兴趣，如26】文 3,4,5还研究了算法的

3、性质，并在一定条件下，证明了凸规划极大爛方法的收敛性文6 通过应用实例说明了极大爛方法的优点2将极大极小问题写为如下等价形式(3 a)(3 b)(4)minmaxg,(x)m,x. u l< iCjhs t m < 0, / = 1.2, ,/«,其中沪 G, “2,5)气IT为附加变量利用指数罚函数mc p = C 1 Xp exp (t7i)1,0. c > 0,消除约束(3 b)可导出关于的指数增广Lagnmge函数Lc(x.p)= 0g (x)；=in in (max g(Cv)u1 f“ + Pcu “)=J "ln£“'exp

4、 cgi(x) ,(5)其中 g= (gi, g2,，gjl R JR" p= (p1, “2,”)丁 R： + 为 Lagrange 乘子;c> 0 为罚因 子 根据Berskas的结果3可以构造求解(3)的序贯指数乘子罚方法的算法记解为“并 可应用于求解极大极小问题等复合函数不可微优化问题.系统阐述可参见文81显然，由式 定义的极大壻函数卩匕)是指数增广Lagninge函数(5)关于乘子“;三1 (匸1, 2,宀)的 特殊情形，即瞅x)=Lc(x,e),其中e (1,1,-, l)r6ir.文10利用收缩函数概念也得到了 该特殊情况设指标集(XU I, 2,宀且使如下极大极

5、小问题有解：(Pa) min%(x) =m inmaxp/Cv),记其最优值为对任意(x,/) R*XR,定义指标集K(x,A i：g心)V/,匸1,2,，加.引 入如下非退化假设:对任意0G,0feC 1,2,，加，记xX2分别为(Po,), (P7的最优解若 K (x ； , * )上 K (x； , %)则% 工傀.若g,(x),匸1,2宀 为凸函数且非退化假设成立，则指数乘子罚方法所生成的 点列(.“,/)的每个聚点(仁石均是极大极小问题(1)的最优解和Kuhn-Tucker乘子对即mnim inQ(x) = £五，(门，£丁= L命题的证明利用文18命题5 12可

6、得文|12对不等式约束非线性规划提出一修正指数乘子罚方法在适当条件下的非凸函数情形，证明了当罚因子纤保持较大有限值时，方法生成 的点列线性收敛列原非凸规划问题的解:当 d+ 8时，相应乘子的收敛率是超线性的指数 乘子罚方法(或其它高次乘子罚方法)可以克服二次乘子罚函数方法的某些缺点3 Hessian V xxl pj设g,(X)(/= 1, 2,7 )二次连续可微直接运算知mG刀広 g，(X&) gXk)TgiCs)(刀况"(“)其中记“炉(小),広=piexp ckfi(xk)P* =(“I "二，/A ) .M k = diag(山，"二从).(8)2

7、98 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.(10)(11)(12)(13)hll2- bll2-()2=刀ai hiaj bj=(a,bj ajbi)2.则(刀可写为V ；aL Ck (xk. p*) = :上 oCn,/A)+ a V (a*) (AT* pip*) V (x*)r 1 对任意 zR",记)u (y ?, ,/*)=V g (xk)Tz，则g Co)【肪- V g (,v*)72= yT Mt- pkiJk y= (Aav)2- (A*v)7X*,

8、其中At = （1扫，捺，）丁，瓦=,J"忘）.由及口； 0易知P 0.故（12）,（有意义 由Lagrange恒等式:对任意a = am）T. b= （bi. bz ） 7 R 成立m故由（及| Ai |2 = £応=i可得(14)yT k pipf y =牙広広（y yJ）2.设y（xk,从,ck）和f （.vi,叫ct）分别为；丄q （xk.从）的最小和最大特征值.则y(xk. 4 ct)= m in:*oxk, IJk)zz V :L o(xk. uQz、II zII2 Vm in:()kll2 ,(15)> 0g Pk)zI (x知"ck)= ma

9、x二=0hII2Xk.zr V j? (x*) fM k- Uklh 1V £ (x*)rz=in illIl 2十ct m axII ZII:（）II Z IIzr V仁厶0（Xk. Mi)z刀讷（八/）2=in inII| 2 +ct m ax(lb)1 Z1Iz II当 XkX ,从f “（从而,（J , /）满足，则（15）右端项和（16）右端第一项均有限注意到只要）在厂不可微，便有&（/）"且由知刀/（y= 厂）， 0故(17)lin r（Xi9 Pk. Ck）/y（Xk. Px, Ck） = + OQQ-*4- 00所以，当o较大时，无约束优化问题nin

10、LflCv,p；）是病态的指数乘子罚方法可以克服由x Rn病态所带来的困难叫另一方面,极大炳方法阐明了指数简单罚函数（x）=Lc（x,e）对有限极 大箱函数®x）的一致逼近性质当然两种算法在求解极大极小问题的数值效果及互补性等 理论研究方面还有待进一步的深入299 © 1995-2005 Tsinghiui Tongfang Optical Disc Co., Ltd. All rights reserved.Hl李兴斯.非线性极大极小问题的一个有效解法，科学通报.36: 19(1991), 1448145Q|21李兴斯，解非线性规划的凝聚函数法.中国科学，12(1991)

11、, 1283- 12883李兴斯，一类不可微问题的有效解法.中国科学，4(1994), 371377.41唐焕文、张立卫.凸规划的极大埔方法.科学通报，39:8(1994), 682- 6845 唐焕文、张立卫、王雪华.一类约束不可微优化问题的极大埔方法，计算数学.15:3(1993), 268 2756 杨钟候等.结构优化设计与最大箱原理，河海大学学报，23: 1(1995), 8- 15B. W Kort, D. P. Bertsekas. A /iar penalty1 function m ethod for const ran ined m in hi ization. Pro* c

12、eedings of the 1972 IEEE Conference on Decisbn and Control. New Orleans. Louisiana. 1972, 162 1668 D. P. Bersekas. Constrained tin izcition and lag rang e m u hip Her nt eth(xl A cadem ic Press, N ew York London, 198219 D. P. Bersekas, N ond iff eren tiable op tin ization via app rox in at ion. M at

13、h Prog Study 3. 197S| 10 A. Ben-TaL M. Teboulle. A sn oothing technique f or nonderentiable op tin ization p roblan Op* tin izatbn*Fifth French"Gennan Conference Castel Novel 198& Lecture Notes in M athanatics, 1405, SpringerVerlag 1989, 1- 1LI 1 1 I D. P. BertsekaSt A pp rox in at ion p ro

14、cedu res based on the m ethod qf m ultip liersixx 9 J. O. T. A 23： 4(1977), 487- 510I 12 V H Hguycn, J J Strodb t, On the convergence rate for apenalty f unction ni ethod cf exponential type, J. O. T. A, 27:4(1979), 495- 508The Relation between Max in un Entropy M ethod andExponenth 1 Penalty FunctionCh en Guoqing(Dept of M atb hnerMongolia U niversity. Hohhot 010020)T ang H uanw en(Depl of Applied M ath Dalian U niversity of Techno fogy, Dalian 116023)AbstractThe re lation between the max in mn entropy m ethod and the exponential penalty functbn