一类增广拉格朗日函数局部鞍点的存在性

一类增广拉格朗日函数局部鞍点的存在性 第24卷第5期 2010年9月 山东理工大学(自然科学版) JournalofShandongUniversityofTechnology(NaturalScienceEdition) Vol_24No.5 Sep.2010 文章编号:1672—6197(2010)05—0026—05 一 类增广拉格朗日函数局部鞍点的存在性 张景,赵文玲,周金川,许修花 (山东理工大学理学院,山东淄博255049) 摘要:对含有等式约束和不等式约束的非线性规划问题(P)给出了一类新的增广拉格朗日函数 方法;在修正二阶充分条件下,证明了对偶问题的局部鞍点即为原问题的局部最优解;同时证明了 如果原问题的局部最优解满足修正的二阶充分条件,则原问题的局部最优解即是增广拉格朗日函 数的局部鞍点. 关键词:增广拉格朗日函数;对偶问题;局部鞍点;弱二阶充分条件 中图分类号:O224文献标识码:A Localsaddlepointstheoryofanewaugmentedlagrangians ZHANGJing,ZHAOWen—ling,ZHOUJin—chuan,XUXiu—hua (SchoolofScience,ShandongUniversityofTechnology,Zibo255049,China) Abstract:Asfortheproblems(P)withboththeequalityconstraintsandinequalityconstraints, weintroduceanewaugmentedLagrangianfunction.Weestablishtheexistenceoflocalsaddle pointundertheweakersufficientsecondordercondition,discusstherelationshipsbetweenlocal optimalsolutionoftheprimalproblemandlocalsaddlepointoftheaugmentedlagrangianfunc— tion. Keywords:augmentedLagrangianfunctions;dualproblem;localsaddlepoint;second—ordersuf— fjcjentcondition 考虑非线性规划问题 (P)minf(z) xCX S.t.g()?0,i一1,2,…,?Tl h(z)一0,J一1,2,…,Z 其中厂,g(?):R一R(i一1,2,…,)和h(?):R 一 R(j一1,2,…z)都是二次连续可微函数,XR 是非空闭子集. 问题(P)的经典拉格朗日函数定义为 m L(x,,)===厂(z)+?g(z)+?h(z)t一1J一1 其中一(1,2,…,).r?R7,p一(1,2,…, )?R. 经典拉格朗日函数的对偶函数为(,)一 inL(z,,),问题(P)的对偶问题为 (D)maxO(a,) S.t.?0 对经典的拉格朗日函数方法而言,在凸性假设 的条件下,原问题(P)与对偶问题(D)之间不存在 对偶间隙,但是对于非凸优化问题可能存在非零对 偶间隙.利用增广拉格朗日函数方法处理优化问题 的关键是对偶问题解的存在性.而鞍点的存在性与 零对偶间隙成立是等价的.所以,鞍点的存在性对解 决问题(P)起着关键作用. 近年来,各种形式的非线性拉格朗日函数和增 广拉格朗日函数被提出来,用来研究如何消除对偶 间隙.HestenesE和PowellE.针对等式约束优化问 收稿日期:2010—01—20 基金项目:国家自然科学基金资助项目(10971118) 作者简介:张景(1985一),女,硕士研究生.E-mail:zhan鲥 ingsecond@163.com 第5期张景,等:一类增广拉格朗日函数局部鞍点的存在性27 题分别提出了增广拉格朗日函数方法. Rockafellarc.引入了处理不等式约束优化问题的拉 格朗日函数法.在文献[41中Rockafellar和Wets提 出了一类具有零对偶间隙性质的凸增广拉格朗日函 数并且建立了精确罚 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示的一系列理论.对于只含 不等式约束的优化问题,黄和杨给出了一类广义 非凸增广拉格朗Et函数,但并未讨论其鞍点的性质. 文献E63对只含有不等式约束的优化问题考虑了增 广拉格朗El函数的鞍点存在性理论.其他类型的增 广拉格朗日函数方法可见参考文献E7—12]. 本文对含有等式约束和不等式约束的优化问题 (P),给出一类新的增广拉格朗日函数,证明了其鞍 点性质. 1定义与符号 首先给出本文用到的一些主要定义与符号. R表示非负向量空间.为了方便,记 G()一(g1(),g2(z),…,g(z)),A:(1, 2,…,),一(/11,2,…,f)ER,一(/11,/12, … ,lzm)?R,t一(l,t2,…,t)ER罕. 定义1若对于某个r>0,对所有的(z,, )?X×R罕×R,者B有 L(,,)?L(z,,)?L,(,A,) 成立,则称(.z,,)为L(z,,)的全局鞍点. 若对于r>0,存在>0,对所有的(z,, )E(XnN(x,))XR2-XR上述不等式都成 立,则称(z,,)为L(z,,)的局部鞍点,其 中N(x,)一{zER”lll—ll?}. 定义2(弱二阶充分性条件) 令z是原问题(P)的可行解, (i)假设KKT条件在z处成立,即存在? 0,i一1,2….,m和,J一1,2,…,,使得 Vf(x)+?Vg()+i=1 ?Vh(1z)一0(1) J一1 g()一0,i一1,2,…,(2) 成立 (ii)海塞矩阵 L(,,)一f(x)+ m ?.g(z)+?h()(3)一 1J一1 在锥 M(x)一{dER”,d?0Ih()d一0, J一1,2,…,Z;g(z)d一0,iEJ(z); g()d?0,iEI(x)\.,(z)) 上正定.其中 I(x)一{ilg()一0,i一1,2,…,} (z)一{iEI(x)l>0,i一1,2,…,m}. 显然二阶充分条件中的锥 M(x)一{dER”,d?0Ih,(z)d一0, J一1,2,…,Z;g(z)d一0,iEJ(z)} 包含弱二阶充分条件中的锥M(x),因此弱二阶充 分条件要比二阶充分条件弱. 2局部鞍点的存在性 对于只含有不等式约束的优化问题,文献I-51 给出了一类广义增广拉格朗日函数 L,(z,)一-厂(Lz)+P(一G(1z),) 其中,P(s,):R×R一R定义为 P(s.)一inf{一甜t4-YO”(“)}us~<0 口()满足下面的假设: (A1)(0)一0,对于U?o,>0; (A2)对于任意的iE{1,2,…,m},当?0 时,(“)是不减的函数,当U<0时,()是不增的 函数; (A3)a(u)连续可微且口(0)一0; (A4)a(u)在零点的邻域内二次连续可微且对 于任意的VhER,h?0有口(0)矗>0. 本文对同时含有等式约束和不等式约束的非线 性优化问题提出一类增广拉格朗日函数 l Lr(z,,)==:(z)+?h(Lz)+ J=1 l 吾?()十P(一G(),)J=1 其中口()满足上述的条件(A1),(A4). 例1函数()一?(分量可分离的函i一1 数). 例2函数(M)一Pii”ii一1(分量不可分离的 函数). 容易验证这2个例子都满足性质(A1), (A4). 下面的定理给出了鞍点与最优解之间的关系, 即增广拉格朗日函数的鞍点是原问题(P)的最优 解. 28山东理工大学(自然科学版) 定理1如果对于某个r>0,(z,,/1)是 L(z,,)的局部鞍点,则z是问题(P)的局部最 优解. 证明对r>0,令(z,A,)是L,(z,,) 的局部鞍点,则有 L(z,,)?L(z,,/1)? L(,,)(4) 对所有的(,,)?(XnN(z,))×R军× R成立.用反证法说明z是原问题的可行解.假设 . 3C不是原问题的可行解,则存在i.使得g()> 0或存在.使得h()?0. (1)如果存在i.使得g(z)>0.由于 L(z,,)一厂(z)+?h(z)+J—i f 吾?;(z)+P,(一G(z),A)J=1 选取>0,对于i?.,一0.由(A1)得 P(一G(z),)一inf{一”+,t『())? G(z)?O inf{一”}一g(z) 井G()?0 令一+cx3,则P(一G(Iz),)一+..,与(4) 式第1个不等式矛盾,故对iE{1,2,…,m}都有 g(z)?0. (2)如果存在Jo使得h(z)?0.取与 h(z)同号,且令一oo,此时与(4)式第1个不 等式矛盾.所以对任意的JE{1,2,…,z}都有 h,(z)=:=0.因此,z是原问题(P)的可行解. 因为z是原问题(P)的可行解,所以h() 一0.特别当一0时,有 P,(一G(z),O)一inf{,0+tO”())一 u-G()?O (O):0(5) 将(5)式代人(4)式可得 P(一G(z),)?0(6) 又因为是可行解,所以对任意的?0有 P(一G(z),)一inf{,+tO”())? 抖G()?O 0+TO”(0)一0(7) 由(6)式和(7)式可得P(一G(),):0. 所以L(z,,)一f(x),故对于任意的可行 解EXnN(-z,)有 L(z,,)一(z)?L(Jc,,)一 ,, -厂(-z)+?h(z)+号?;()+,=l1 P(一G(.z),)?-厂(z) 所以z是原问题(P)的局部最优解. 定理2令z是原问题(P)的局部最优解,若 弱二阶最优性条件在z点处成立,则存在,..>0和 >0使得 L(,,)?L(,,)?L(z,,) 对所有的(,,)E(XnN(x,))×R罕× .R成立. 证明因为z是原问题的可行解,我们有 h,(z)一0和对?0有P(,G(z),)?0成立. 由(A1)和(2)式我们得到 P(一G(z),)一inf{一,uT2+()}? {一)一?gi(z)一0 推出P(一G(x),)一0.因此有L(z,,)? fez)===L(z,,),于是我们得到(4)式的第 1个不等式成立.下面证明第2个不等式成立. 因为L(z,,)关于r>0不减,故只需证存在 某个r.>0和>0使第2个不等式成立即可.我们 用反证法证明.假设不存在这样的r.>0和>0, 则对任意正整数愚,存在EX和z一z使得 L(z,,)?f(x)一L(z,,) 定义ll一(,,…,?), f0,iE{1,2,…,}\l(x) 晚一Ji,E小(8)一{,g(z),EJl(z*) I—g(z),iE(z) 其中: (z)一{I(x)\J(z)}n{i1g(z)?0) .厂(z):{I(x)\.,(1z))n{工】g(z)?0} 由的定义我们有 P(,G(x),)一in{?一”+ui+gi()?Ol?,(z) 胁()}一?g(z)+胁(“) 事实上,根据性质(A2)可以得到 当iE{{1,2,…,m)\j())UJ{()时,固 定(EJ(-z)UJ(z)),因为一0,所以零点 是问题 in{?一”+” t +g()?OiEJ(z) ?”l,2.…,m)\I())u,(z) (“)} 的最优解. 当iEJ!(z)时,?一+胁()在 (一..,,g()]上是关于”的减函数,故”一一 第5期张景,等:一类增广拉格朗日函数局部鞍点的存在性29 g()是问题 in{?,uTa+胁()}的最优解.+gi()??(*) iE(z) 当iEJ(x)时,令Va(u)为口(“)的第个 分量,由(A3)可知,对任意的0??一毋()有 )?,V是EN iEJ(z) 即,十忌(“)?0,故?一”+ 幻()在(一..,,g()]上是关于的减函数 因此一一g()是问题 in{?一+ka()}的最优解,”i+gi()?0 J?J() iEJ(oc) 所以可得到 0>f(x)一f(x)十?h,()+ 等?(+?毋(xk)274-ka(各)一J一 ,?J() L(x,,)一L(x,,)+ {(z)+Vh()(z,)+ D(11.22,J)}.+(0)+志(.)T+ 告(9)式可等价地写成 O>]- “TL(z,*,*)+ l』,ff) J』.17一05JJ. — o —— (———— l— t—— x —— * ———— - ———— x ———— . —————— )— ffz一zll + 记z为.(0)的最小特征值,则z>0. 如果当 志._一 2一Z 不收敛到0,我们有 .(O)”+ (Il?)?klff+ ff)(11) 令尼一+Cx3,对上式取极限,则上式右边收敛到 +..,这与(1O)式矛盾.所以我们一定有 一0.注意到(8)式等价于 i?{1,2,…,m)\I(x) i?J() Iz一l1)?.,(z*) fz一ff)EJ(z*) 一 I1) 一 32Il 』:二兰: 一 I_ i?{1,2,…,m}\I(x) i?J() ? l / ?引睾 + (( 00 ++ )) 0O**z ,, ZZ (/ TT )) (( gg 一一 r???????,,??????【 一 女G oo f= ++ 巩 1』T’ ,,) *zz 30山东理工大学(自然科学版)2010生 因此对任意的i?J(z)UJ{(),令k一+.. 对(10)式取极限,一定可以得到 dL(z,,/1)d?0(12) h()d一0,J一1,2,…,Z;(13) g(z)d一0,i?JU.,(z)(14) 对于i?I(x)\(J(z)UJl(z)},存在一个 无穷指标集N.N满足Vk?N.,有g()?0 成立.所以我们有 g(z)d—limg:(誉)d一 … lim?0) 其中位于-z和x之间.由(13)式,(15)式推 出d?M(x).而由定义2可知 dL(,,)d>0 这与(12)式矛盾.所以(4)式的第2个不等式也成 立.证毕. 参考文献: [1]HestenesMR.Multiplierandgradientmethods[J].Optim TheoryAPP1,1969,4:303—320. E2]PowellMJD.Amethodfornonlinearconstraintsinminimiza— tionproblemsinOptimizationRFletcher(Ed)EM].NewYork: AcademiePress,1969:283—298.. E3]RockafellarRT.Augmentedlagrangemultiplierfunctionsand dualityinnonconvexprogramming,SIAM口].ControlandOp— tim,1974,12:268—285. E4]RockafellarRT.Variationalanalysis[M].Berlin:Springer- Verlag,1998. [5]HuangXX,YangXQ.AunifiedaugmentedLagrangianap— proachtodualityandexactpenalizationEJ].MathOperRes, 2003,28:524—532. [6]LiuQ,TangWM,YangXM.Propertiesofsaddlepointsfor generalizedaugmentedLagrangian[J].MathMethOperRes, 2009,69:111-124. [73PolakE,RoysetJ0.OntheuseofaugmentedLagrangiansin thesolutionofgeneralizedsemiinfinitemin—maxproblems[J]. 192. ComputOptimAppl,2005,31:173— E8]HuangXx,YangXQ.FurtherstudyonaugmentedLagrang— iandualitytheoryEJ].GlobalOptim,2005,31:193—210. E9]SunXL,LiD,MckinnonK.Onsaddlepointsofaugmented Lagrangiansforconstrainednonconvexoptimization[J],SlAM JOptim.,2005,15:1128—1146. [1o]HuangXX,YangXQ.Approximateoptimalsolutionsand nonlinearLagrangianfunctions[J].GlobalOptim,2001.21: 51-65. [11]ZhouYY,YangXQ.AugmentedLagrangianfunction,non— quadraticgrowthconditionandexactpenalizationEJ].Opera— tionsResearchLetters,2006,34:127—134 [12]WangCY,ZhouJC,XuxH.Saddlepointstheoryoftwo classesofaugmentedLagrangiansanditsapplicationstogeneral— izedsemi—infiniteprogramming[J].ApplMathOptim,2009, 59:413-434. (编辑:郝秀清) (上接第25页) 4结束语 本文 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 了XML模式与关系模式的映射过 程,并给出两个模式问无损映射算法,依据该算法可 以实现XML数据与关系数据的可逆交互,使得关 系数据库可以充当XML虚拟数据库来管理XML 数据,同时XML数据也可以以关系数据的形式显 示在系统中. 参考文献: Eli方洁,刘广钟.XML模式到关系数据模式转换的研究[J].计算 机工程与应用,2009,45(9):157—160. [2]严丽,马宗民,刘健,等.基于XMLSchema的模糊数据建模方法 『J].东北大学:自然科学版,2008(10):1406,I409. [3]康晓兵,张二虎,吴学毅.一种XMLSchema模式到关系模式的 映射算法[J].计算机应用,2004,24(5):106—108 [4]王志平.基于XML的异质多数据库集成系统的设计与实现rJ]. 河南大学:自然科学版,2007,37(5):530—532. E5]田磊.覃征,衡星辰,等.基于本体的多源异构XML数据近似 查询方法[J].西安交通大学,2007(6):702—706. [6]洪欣.基于XDR模式的XML文档与关系数据库的映射技术研 究[D].泉州:华侨大学,2004. (编辑:姚佳良)