存零约束优化问题的对偶问题.pdf

数学杂志Vol.43(2023)J.of Math.(PRC)No.4存零约束优化问题的对偶问题罗美铃1，李高西1，吴春2(1.重庆工商大学数学与统计学院，重庆40 0 0 6 7)(2.重庆师范大学数学科学学院，重庆40 1331)摘要：本文研究了近年提出的一类新优化问题存零约束优化问题，因存零约束的存在，使得求解最优解较困难.因此，本文针对存零约束优化问题，利用对偶理论提出了问题的Wolfe型对偶模型.在凸性和严格凸性假设下，获得了Wolfe对偶的弱、强、逆、限制逆和严格逆对偶结果.并进行了实例论证.关键词：非线性规划；存零约束；对偶问题；广义凸性(1.1)MR(2010)主题分类号：90 C30;90C25文献标识码：A1 引言本文考虑下述非线性规划问题：其中,函数f(),91,9p,h1,.,hq,G1,.,Gt,H1,H:R R均连续可微.在问题(1.1)任意可行点处，对任意固定的t,Gt(c）和Ht(）至少有一个为零，即两个函数的乘积为零，我们称这样的等式约束为存零约束，问题（1.1）则为“存零约束“优化问题，简记为MPSC.该模型首先由Mehlitz1】提出并系统研究.文献1指出，最优控制问题的离散化、Either-or约束优化、0-1规划等问题均可以转化为问题（1.1)，因此有必要讨论问题（1.1）的相关理论.由于常用的约束规范比如线性独立约束规范（LICQ)、M a n g a s a r i a n-Fr o mo v i t z 约束规范(MFCQ）在问题（1.1）的可行点处均不满足，因此不能将其看作一般的非线性规划处理.MPSC 的约束结构与具有互补约束、消失约束的优化问题密切相关，见文献2.Mehlitz1给出了一些平稳性概念，如弱平稳性,Mordukhovich(M-）平稳性和强（S-）平稳性，然后提出了MPSC特定的约束规范，例如MPSC Mangasarian-Fromovitz约束规范（MPSC-MFCQ),MP-SC线性独立约束规范（MPSC-LICQ),MPSCAbadie约束规范和MPSCGuignard约束规*收稿日期：2 0 2 2-0 9-0 5基金项目：国家自然科学基金项目（1190 10 6 8)；重庆市自然科学基金（cstc2019jcyj-msxmX0390)；重庆工商大学研究生创新型科研项目（yjscxx2022-112-184)；重庆工商大学科研项目（ZDPTTD201908).作者简介：罗美铃（1998-），女，重庆万州，研究生，主要研究方向：最优化理论及算法.通讯作者：吴春（197 6-)，男，重庆巴南，副教授，主要研究方向：值分布及偏微分方程理论.E-mail:.中图分类号：0 2 2 1.2文章编号：0 2 55-7 7 97(2 0 2 3)0 4-0 347-0 9minf()s.t.g;()0,i=1,.,p,h;()=0,j=1,.,q,Gt()Ht()=0,t=1,.,l,接收日期：2 0 2 2-11-0 8348范.Yang等人3得出了满足增广拉格朗日问题二阶必要最优性条件的点序列的极限点是原互补约束优化问题的的强平稳点.Singh等人4针对均衡约束多目标优化问题建立了Wolfe型对偶和Mond-Weir型对偶模型，并在伪凸性和拟凸性假设下建立了弱对偶和强对偶定理.对偶性在研究优化问题时非常重要.经典的Wolfe对偶是由学者Wolfe于19 6 1年引入.目前，研究问题的对偶模型已经被用作解决各种优化问题的工具，如半无限规划问题5，变分不等式问题6，分数式编程问题7，凸优化问题8 等陈世国9对不可微多目标规划在伪不变凸和拟不变凸时给出了弱有效解和有效解的Mond-Weir型对偶理论.之后，陈世国等人10针对含有锥约束的多目标变分问题，得到其广义对称对偶性.Mishra1 在一些假设下，建立了消失约束优化问题与对偶问题之间的弱、强、逆、限制逆和严格逆对偶性结果.本文基于文献11,拟研究MPSC的Wolfe型对偶问题.本文余下组成部分为：第2 节给出本文研究所需的基本定义.第3节提出Wolfe型对偶模型，在凸性和严格凸性假设下，获得原问题的Wolfe对偶问题的弱、强、逆、限制逆和严格逆对偶结果。2预备知识为便于后续研究，定义指标集：Ig=i E 1,.,p:gi()=O,Ih=1,.,q),Ic=(t E(1,.,l):Gt()=0 Ht(ac)+O),IH=t E1,.,I):Gt(ac)/O Ht()=O),IGH=(t E(1,.,l):Gt()=O Ht()=O.其中,IG,IH,IGH是 1,.,上互不相交的划分.定义MPSC 的拉格朗日函数为PL(a,a,Ae,v)=(a)-入,g;(e)+Zgh(a)+ZuG(a)+ZuH(e).=1下面将给出一些关于MPSC的平稳性和约束规范的定义.定义2.11】设ERn为MPSC的可行点，如果存在乘子满足0=Vf(a)-;Vg(a)+,Vh(a)+utVG(a)+vH(a),iIgVi EIg:入;0,Vt EIG:Vt=O,Vt EIH:t=0,Vt EIGH:tVt=0,(2.1)则称为Mordukhovich平稳点，简记为M平稳点.定义2.2 1】设Rn为MPSC的可行点，如果在点处约束函数的梯度VGt(c),t E IG U IGH,线性独立，则称MPSC-LICQ在点处成立.数学杂志j=1t=1jeTht=1Vgi;(a),i E Lg,Vh;(a),j E Ih,VHt(),t E IH UIGH,Vol.43t=1No.4在建立对偶理论时，凸性和广义凸性概念具有重要作用，因此，给出定义如下：定义2.312】设S Rn为任一非空集合,f：R n R 连续可微.则称f在c*ES点处是凸的，当且仅当对于任意的ES,有若c*时，以上定义的严格不等式成立，则称f在a*ES点处是严格凸的.定义2.412】设SRn为任一非空集合,f：R n R 连续可微.则称f在c*ES点处是拟凸的，当且仅当对于任意的E S,有f(c)f(*)(Vf(*),-*)0.定义2.512】设SCRn为任一非空集合,f：R n R 连续可微.则称f在c*S点处是伪凸的，当且仅当对于任意的ES,有(Vf(*),-*)0 f()f(a*).定义2.6 12】设SRn为任一非空集合,f：R n R 连续可微.则称f在c*S点处是严格伪凸的，当且仅当对于任意的ES且*，有罗美铃等：存零约束优化问题的对偶问题f(ac)-f(*)(Vf(a*),-a*).(Vf(*),-*)0 f()f(*).3493 Wolfe型对偶本节根据可行点EX定义MPSC的Wolfe型对偶问题（WD）如下：max,L(y,e,v)y,ai,Ae,l,入;0,i Ig,t=O,t EIH,Vt=O,t E Ic,tvt=0,t EIcH.定义WD(）所有可行点构成的集合为2():=0,j E 1,.,q:入,0,Ih=j E 1,.,q:入j 0,I=t e 1,.,I:t ,I=t e(1,.,l:Vt 0.定理3.1(弱对偶）设X，（y,入,入e,)2.如果下列条件中有一个成立：(i)L(,入,e,V)在 y E XU P2 处为凸.(i)f,-gi(ie),h;(j t),-h;(j),Gt(t),-Gt(t eI),H(t e),-Ht(t EIi)在y E XUP处为凸.则 f(c)L(y,入,入e,V).证(i）反证法，假设(a)(0)-ig()+h(0)+G()+Pi=1因为和（y,入，入e,）分别为MPSC和WD的可行点，显然有-gi(c)h(a)+G:(a)+i=1j=1将(3.2)和(3.3)相加,有Pf(a)-Ag(a)+ah(e)+G(0)+1VtHt(c)i=1j=1P(u)Ag()+Ah:()+uG(u)+uH()i=1j=1即是L(c,入t,e,v)L(y,入,入e,).根据L(,入，入e，,V）的凸性可得L(y,Ar,Ae,v)+(VL(y,入r,Ae,V),a-y)L(a,入r,Ae,D).数学杂志j=1t=1PqVol.43(3.1)vtHt(y).(3.2)t=1vtHt()0.t=1t=1t=11t=1(3.3)t=11t=1(3.4)(3.5)No.4由于(y,入,e,)是WD的可行点，即(y,入,e,)=0,则(3.5)可化简为L(y,入,e,)L(c,入，入e,V).这与(3.4)矛盾，因此结论得证.(ii）根据定理中的第二个题设条件，易得 L(,入，入e,）在yEXUP处为凸，再结合(i)的证明，即可得证。定理3.2（强对偶）令*EX是MPSC的局部最小解,MPSC-LICQ在a*处成立.则存在拉格朗日乘子（入*，入，u*,*）使得（c*，入*，入，u*,*）是WD的可行点，且P-ZXig(ar)+Zxgh;(e)+ZuGe(r)+ZH(a)=0.1另外，如果下列条件中有一个成立：(i)L(,入e,)在y E X U P 处为凸.(ii)f,-gi(i E I(a*),hi(j E I(c*),-h;(i E Ir(a*),Gt(t E(a*),-Gt(t EI(a*),Ht(t(c*),-Ht(t e I(a*)在 y E XU P2 处为凸.则，(c*，入，入，u*,*）是WD的全局最大解且f(a*）=L(*，入，入，u*,*).证由于c*是MPSC的局部最小解且MPSC-LICQ在该点处成立，再根据定义2.1，对于点a*，存在拉格朗日乘子（入*，入，u*，*）使得（2.1）成立，因此（a*，入，入，u*,*）是WD的可行点。再根据(2.1）的后四个条件和(3.1）易得(3.6)由定理3.1,有f(a*)L(y,入,入e,D),V(y,入r,Ae,V)E 2(a*).进一步将(3.6)与(3.7)相加有 L(a*,入,u*,*）L(y,入,e,V),V(y,入,e,)2(a*).即是（a*，入*，入，u*，*）为WD的全局最大解.同时,MPSC的局部最优值等价于WD的全局最优值。定理3.3(逆对偶)并有以下成立-入,g;(y*)0,i E 1,.,P),入,h;(y*)=0,j e(1,.,q),tGt(y*)=0,t e 1,.,l),tHt(y*)=0,t E 1,.,l.另外，如果下列条件中有一个成立：(i)L(,入*,入,u*,v*)在y*E X U P2 处为凸.(i)f,-gi(iI),h;(j),-h;(j),Gt(t),-Gt(t I),H(t),-Ht(t EI）在y*EXUPQ处为凸.则y*为MPSC 的全局最小解证反证法.假设y*不是MPSC的全局最小解，即存在aEX使得(i)因为岔和（y*，入，入，u*,*）分别为MPSC 和WD的可行点，由定理中的假设易得-gi(a)0,入 0,Vi Ig(a),gi(a)=0,入,R,Vi E Ig(a),h;(a)=0,入,E R,Vj E In(a),Gt(a)=O,t E R,Vt E Ic(a),Gt(a)+0,t=0,Vt E LH(a),Ht(a)=0,vt R,Vt E IH(a),Ht(a)0,vt=0,Vt E Ic(a),Gt(a)=H()=0,t=0 V vt=0,Vt E IcH(a).罗美铃等：存零约束优化问题的对偶问题q1j=1t=1令是MPSC 的非空可行集，（y*，入，入，u*,*）是WD的可行点(3.8)f(a)f(g*).(3.9)351(3.6)t=1(3.7)352进一步推得数学杂志-Xig(a)+h()+ZutG(a)+Zut H(a)PVol.43=1P-Z入igi(y)+Ah(u)+uG(g)+ZutH(u)=1将(3.9)和(3.10)相加有L(，入，入,*,*）L(y*，入，入，*,*).根据L(，入,，*,*）在yEXUP2处为凸，可得这与约束VL(y*，入*，入,u*,*)=0矛盾，因此结论得证.(ii）根据定理中的第二个题设条件，易得L(,入*,入*，*,*）在y*EXUP2处为凸，再结合(i)的证明，即可得证.定理3.4(限制逆对偶）令a*EX是MPSC的任一可行点，y*，入，入，u*,v*）是WD的可行点且满足f(*）=L(y*，入，入,u*,*）另外，如果下列条件中有一个成立：(i)L(,*,入,*,v*)在y*E XU P2 处为凸.(ii)f,-gi(i I(a*),h;(i E t(a*),-h;(i Ih(a*),Gt(t E I(a*),-Gt(t EI(c*),Ht(t(c*),-Ht(t I(a*)在 y*X UP 处为凸.则*为MPSC的全局最小解.证反之，假设c*不是MPSC 的全局最小解，则存在岔使得f(a)f(*).结合定理中的假设有f()L(g*，入*，入，*,*)，这与定理3.1的结论矛盾，因此得证定理3.4.定理3.5（严格逆对偶）令a*EX是MPSC的局部最小解，并使得MPSC-LICQ在该点处成立此外，假设定理3.2 的假设条件成立，g*，入，入，u*,*）是WD的全局最大解.如果下列条件中有一个成立：(i)L(,入*,入,*,*)在y*E XUP2处为严格凸.(i)f 是严格凸的,且-gi(i (c*),h;(i E(*),-hi(i I(a*),Gt(t E(a*),-Gt(t I(a*),Ht(t E(c*),-Ht(t E I(c*)在 y*X U P2 处为凸.则*=y*.证（i）同样用反证法假设c*。则由定理3.2，存在拉格朗日乘子（,e,）使得(c*,e,D)为WD的全局最大解，因此f(a*)=L(a*,X,Ne,P,D)=L(y*,入t,入e,*,v*).根据*和（y*，入*，入，u*,*）分别是MPSC和WD的可行点，容易得到-g;(a*)0,入,0,Vi Ig(a*),gi(a*)=0,入,R,Vi E Ig(*),h;(a*)=O,E R,Vj E Ih(a*),Gt(a*)=O,t E R,Vt E Ic(c*),Gt(r*)0,t=0,Vt E IH(a*),HH(a*)=0,vt E R,Vt E IH(*),Ht(c*)0,vt=0,Vt EIc(*),Gt(*)=Ht(*)=0,=0Vvt=0,Vt EIcH(*).j=1j=1(VL(y*,入*,e,u*,D*),a-y*)0,t=1t=1t=1t=1(3.10)(3.11)No.4从而有-Xig(a)+h(a)+ZG(a)+uH:(a)0.=1j=1将(3.11)与(3.12)相加有L(c*,入*,入*,*,v*)L(y*,入*,入*,*,v*).结合以上不等式以及L(，入，入，u*,*）在y*XUP处为严格凸，推知(VL(y*,入*,入*,*,L*),c*-y*)0.这与约束VL(y*,入，入,*,)=0矛盾，因此结论得证.(i)根据定理中的第二个题设条件，易得L(，入*，入,u*,*）在y*EXUP2处为严格凸，再结合(i）的证明，即可得证.接下来，利用下面的例子来验证Wolfe型对偶和相关定理的有效性.例3.1考虑含存零约束的优化问题min f(a):=(a1-1)2+(a2+3)+ags.t.Gi(c):=i-2a1+a3+1,Hi(ac):=a2+6a2-3+9,Gi()Hi()0,其可行点的集合X为X:=(1,2)E R2(-2c1+3+1)(c2+6c2-3+9)=0).(3.13)的对偶形式为min L(y,i,vi)=(y1-1)2+(y2+3)2+y+i(yi-2y1+y3+1)y,1,V1s.t.2(y1-1)(1+1)=0,1=0,1 E IH,(1)令a*=(1,-3,0)T X,(i,y2,3,v)=(1,-3,0,0,0)2(*),有易验证定理3.4的所有条件均成立，因此c*为（3.13）的全局最小解。故定理3.4得以验证.(2）由(3.14)的前三个等式约束可得，当y1=1,J2=-3,y3=/，结合(3.13）中的目标函数，易得到L(y,1,V1)=罗美铃等：存零约束优化问题的对偶问题P1t=1t=1+v1(y2+6y2-y3+9)2(y2+3)(1+v1)=0,V1=0,1 E Ic,f(a*)=L(y*,vi).V1-1)6_(V1-M)6(a1-1)2+(2+3)2+g=f(a).6353(3.12)(3.13)(3.14)6yg+1-Vi=0,M1V1=0,1 E IGH,6354当=-1,1R,V1=-1,2 R,3=0时,同样可得到L(y,1,Vi)=0(a1-1)2+(2+3)2+ag=f(c).当 1=-1,y1 E R,y2=-3,y3=数学杂志+时,6Vol.43V1+L(y,1,Vi)=6当 V1=-3,y2 E R,y1=1,y3=1+1L(y,1,Vi)=6综上所述，定理3.1得以验证.(3）因为VHi(）=（0,2 2+6,-1)T 和VGi(）=（2 1-2,0,1)T，即(3.13）满足MPSC-LICQ.由定义2.1，对于点a*=（1,-3,0)T,y*=（1,3,0)T，存在拉格朗日乘子(u,vi）=（0,0）使得（y*，,）为(3.14)的可行点且有iG(a*)+viH(c*)=0.因此,(*，,）为（3.14）的全局最大解，同时有f(a*）=L(y*，,t).定理3.2 得证.4小结上述考虑的均是在凸性条件下的对偶刻画，如果弱化凸性假设，则一方面，在证明弱、强和逆对偶性时，利用拟凸或伪凸性无法根据定义推出矛盾，进而也无法证得限制逆和严格逆对偶性成立；另一方面，为获得上述结论，可以通过刻画比原Wolfe型对偶约束条件更加严格的Mond-Weir型对偶问题得到由于篇幅受限，本文只针对存零约束优化问题建立了Wolfe型对偶问题，并分析了对偶问题分别在凸性、严格凸性的假设下，原问题的对偶问题的弱、强、逆、限制逆和严格逆对偶结果，并给出例子验证结论成立.(VV1+1)(1-1)+(2+3)?+g=f(c).E-时，V6(VM1+T)6(a1-1)2+(c2+3)2+g=f(c).6参考文献1 Mehlitz P.Stationarity conditions and constraint qualifications for mathematical programs withswitching constraintsJ.Mathematical Programming,2020,181(1):149-186.2 Mehlitz P.On the linear independence constraint qualification in disjunctive programmingJJ.Op-timization,2020,69(10):2241-2277.3 Yang X Q,Huang X X.Convergence analysis of an augmented Lagrangian method for mathematicalprograms with complementarity constraintsJJ.Nonlinear Analysis Theory Methods and Applica-tions,2005,63(5-7):e2247-e2256.4 Singh K,Mishra S K.On multiobjective mathematical programming problems with equilibriumconstraintsJ.Applied Mathematics and Information Sciences Letters,2019,7(1):17-25.No.45 Li S J,Yang X Q,Teo K L.Duality for semi-definite and semi-infinite programmingJ.Optimization,2003,52(4):507-528.6 Bermdez A,Moreno C.Duality methods for solving variational inequalitiesJ.Computers and Math-ematics with Applications,1983,7(1):43-58.7 Huang X X,Yang X Q.Duality for multiobjective optimization via nonlinear lagrangian functionsJ.Journal Of Optimization Theory And Applications,2004,120(1):111-127.8孙祥凯.不确定信息下凸优化问题的鲁棒解刻划J.数学物理学报，2 0 17,37(2)：2 57-2 6 4.9陈世国.非凸不可微多目标规划的Mond-Weir型对偶性J.数学杂志，1995，15(4)：38 1-38 4.10】陈世国，刘家学.含有锥约束的多目标变分问题的广义对称对偶性J.数学杂志，2 0 11,31(6)：1145-1151.11 Mishra S K,Singh V,Laha V.On duality for mathematical programs with vanishing constraintsJ.Annals of Operations Research,2016,241(1-2):249-293.12 Cambini A,Martein L.Generalized convexity and optimization:theory and applicationsM.Berlin:Springer,2009.罗美铃等：存零约束优化问题的对偶问题355DUALITY PROBLEM OF MATHEMATICAL PROGRAMS WITHSWITCHING CONSTRAINTSLUO Mei-ling,LI Gao-xil,WU Chun?(1.College of Mathematics and Statistics,Chongqing Technology and Business University,Chongqing400067,China)(2.College of Mathematical Sciences,Chongqing Normal University,Chongqing 401331,China)Abstract:In this paper,a new class of optimization problems proposed in recent years isstudied,which makes it dificult to solve the optimal solution due to the existence of switchingconstraint.Therefore,this paper proposes a Wolfe type dual model by using the duality theory tosolve the mathematical programs with switching constraints problem.Under the convexity andstrict convexity assumptions,the weak,strong,inverse,restricted inverse and strict inverse dualityresults of Wolfes duality are obtained.An example is given to demonstrate.Keywords:nonlinear programming;switching constraint;duality problem;generalizedconvexity2010 MR Subject Classification:90C30;90C25