随机二阶锥规划问题的统计推断.pdf

第4 2卷第3期2023年5月大 连 工 业 大 学 学 报J o u r n a l o fD a l i a nP o l y t e c h n i cU n i v e r s i t yV o l.4 2N o.3M a y2023收稿日期:2 0 2 3-0 3-0 8.基金项目:国家自然科学基金项目(1 2 1 7 1 2 1 9);辽宁省“兴辽英才”青年拔尖人才项目(X L Y C 2 0 0 7 1 1 3).作者简介:林 爽(1 9 8 1-),女,讲师.信息科学与技术D O I:1 0.1 9 6 7 0/j.c n k i.d l g y d x x b.2 0 2 3.0 3 1 2随机二阶锥规划问题的统计推断林 爽1,李 思 颖2,张 杰2(1.大连工业大学 基础教学部,辽宁 大连 1 1 6 0 3 4;2.辽宁师范大学 数学学院,辽宁 大连 1 1 6 0 2 9)摘要:随机二阶锥规划问题是确定型二阶锥规划问题的扩展形式,在诸多领域有重要的应用。本文研究了一类随机二阶锥规划问题的统计推断,对一类随机二阶锥规划问题的样本均值近似问题的可行域的收敛速度和样本规模的大小进行了阐述,得出了随机二阶锥规划问题的样本均值近似问题的最优值的收敛速度和样本规模,得到的结果为进一步建立随机二阶锥规划问题的最优值的置信区间提供理论保证。关键词:随机二阶锥规划;样本均值近似;收敛速度;样本规模中图分类号:O 2 2 4文献标志码:A文章编号:1 6 7 4-1 4 0 4(2 0 2 3)0 3-0 2 2 6-0 5S t a t i s t i c a l i n f e r e n c e f o r s t o c h a s t i c s e c o n d-o r d e rc o n ep r o g r a mm i n gp r o b l e m sL I N S h u a n g1,L I S i y i n g2,Z H A N G J i e2(1.D e p a r t m e n t o fB a s i cC o u r s e sT e a c h i n g,D a l i a nP o l y t e c h n i cU n i v e r s i t y,D a l i a n1 1 6 0 3 4,C h i n a;2.S c h o o l o fM a t h e m a t i c s,L i a o n i n gN o r m a lU n i v e r s i t y,D a l i a n1 1 6 0 2 9,C h i n a)A b s t r a c t:T h e s t o c h a s t i c s e c o n d-o r d e r c o n ep r o g r a mm i n gp r o b l e mi s a ne x t e n d e d f o r mo f d e t e r m i n i s t i cs e c o n d-o r d e rc o n ep r o g r a mm i n gp r o b l e ma n dh a s i m p o r t a n t a p p l i c a t i o n s i nm a n y f i e l d s.T h e s t a t i s t i c a li n f e r e n c ef o r a c l a s s o fs t o c h a s t i c s e c o n d-o r d e r c o n e p r o g r a mm i n g p r o b l e m si s s t u d i e d.T h ec o n v e r g e n c er a t eo ft h ef e a s i b l ed o m a i na n dt h es i z eo ft h es a m p l es c a l eo ft h es a m p l ea v e r a g ea p p r o x i m a t i o np r o b l e m so fac l a s so fs t o c h a s t i cs e c o n d-o r d e rc o n ep r o g r a mm i n gp r o b l e m sa r ef i r s td e s c r i b e d,a n dt h e nt h ec o n v e r g e n c er a t ea n dt h es a m p l es c a l eo ft h eo p t i m a lv a l u eo ft h es a m p l ea v e r a g ea p p r o x i m a t i o n p r o b l e m f o rt h es t o c h a s t i cs e c o n d-o r d e rc o n ep r o g r a mm i n g p r o b l e m sa r eo b t a i n e d.T h eo b t a i n e dr e s u l t sp r o v i d eat h e o r e t i c a lb a s i sf o rf u r t h e re s t a b l i s h i n gt h ec o n f i d e n c ei n t e r v a l o f t h eo p t i m a l v a l u eo f t h es t o c h a s t i cs e c o n d-o r d e rc o n ep r o g r a mm i n gp r o b l e m.K e yw o r d s:s t o c h a s t i cs e c o n d-o r d e rc o n ep r o g r a mm i n g;s a m p l ea v e r a g ea p p r o x i m a t i o n;c o n v e r g e n c er a t e;s a m p l es c a l e0 引 言二阶锥规划作为一种特殊的非线性优化,广泛应用于各领域。B u s s等1将图论控制优化转化为二阶锥规划进行求解,鲁棒多级有价证券以及其他鲁棒有价证券优化也可转化为二阶锥规划。L o b o等2将二阶锥规划应用于天线阵重量设计、抓取力优化、滤波器设计、带有损失风险的金融问题、桁架设计、线性弹簧系统平衡等。A l-i z a d e h等3将线性规划、二次规划和具有二次约束的二次规划以及范数极小化问题、鲁棒线性规划问题、鲁棒最小二乘问题转化为二阶锥规划。在二阶锥规划中,如果问题中定义的参数都是确定的,那么这样的问题就是确定性二阶锥规划,确定性优化问题是在数据确定的问题中寻找最优值,但在实际应用模型中常存在许多不确定的变量。自2 0世纪5 0年代以来,随机规划作为处理各种优化问题中的数据的不确定性被广泛研究,特别是一些随机锥优化模型不断涌现。随机二阶锥规划问题应用广泛,M a g g i o n i等4将随机二阶锥规划应用于移动和特设网络;A l z a l g5将随机二阶锥规划应用于随机欧几里得选址问题、带有损失风险的投资组合问题、随机椭球的最优收敛以及结构优化问题中;Z h a n g等6将随机二阶锥规划应用于投资组合问题中;L i u等7研究了分布类型的二阶锥规划问题。学者们对等式与不等式约束的随机规划收敛速度与样本规模估计做了大量研究,但是对于随机二阶锥规划问题的收敛速度与样本规模估计的研究未见报道。为了通过本研究把随机规划收敛速度与样本规模估计的研究成果推广到随机二阶锥规划问题中,本文研究了一类随机二阶锥规划问题的样本均值近似(S AA)问题的最优值的收敛速度以及样本规模的估计,为以后提供估计真实最优值置信上下界的方法提供理论保障。1 问题描述与构造所研究随机二阶锥规划问题如式(1)所示。m i nEf(x,()s.t.gi(x)=EGi(x,()Kni+1,i=1,2,m,xX(1)其中XRRn是一个非空凸集,Kni+1是一个ni+1维二阶锥,即:Kni+1=(x0,x)RRRRnixx0,i=1,2,m,令n1n2nm,n=mi=1ni,RRk是一个定义在概率空间(,F,P)中的一个随机变量,E表示数学期望,f:XRRkRR和Gi(x,)=(Gi0(x,),Gi(x,)RR RRni是两个随机函数,使得Ef(x,()与EGi(x,()(i=1,2,m)对于任意的xX都是适定的。为了方便,用来代替()。对于任意的i=1,2,m,定义Gi(x,)=(Gi0(x,),Gi(x,)RRRRni(2)gi(x)=(gi0(x),gi(x)RRRRni(3)其中,Gi(x,)=(Gi1(x,),Gi ni(x,)RRni(4)gi(x)=(gi1(x),gi ni(x)RRni(5)利用S AA方法,问题(1)的样本均值近似问题如式(6)所示。m i nxXfN(x)s.t.gNi(x)Kni+1,i=1,2,m(6)其中,fN(x)=1NNj=1f(x,j)(7)gNi(x)=(gNi0(x),gNi(x)=1NNj=1Gi(x,j)(8)分别是f(x,)和Gi(x,)的样本均值近似函数。且gNi(x)=(gNi1(x),gNi ni(x)RRni(9)将式(1)称为真问题,式(6)为式(1)的样本均值近似问题。2 等价形式的建立为了方便研究随机二阶锥规划问题的收敛速度,将问题(3)转换成一种等价形式。根据二阶锥的定义可得式(1 0)。gi(x)gi0(x),i=1,2,m(1 0)因此问题(1)等价于如式(1 1)优化问题。m i nxXEf(x,()s.t.gi(x)-gi0(x)0,i=1,m(1 1)即m i nxXEf(x,()s.t.m a x1imgi(x)-gi0(x)0(1 2)同样式(6)可以表述为式(1 3)和式(1 4)。m i nxXfN(x)s.t.gNi(x)-gNi0(x)0,i=1,m(1 3)即m i nxXfN(x)s.t.m a x1imgNi(x)-gNi0(x)0(1 4)3 收敛速度分析令1,N是随机变量的一组大小为N722第3期林爽等:随机二阶锥规划问题的统计推断的样本,给定0,定义Z:=xX:gi(x)-gi0(x),i=1,m (1 5)ZN:=xX:gNi(x)-gNi0(x),i=1,m (1 6)则Z0表示问题随机二阶锥规划问题的可行域。要估计P r o bZ-Z0NZ ,需要假设(C 1)XRRn是一个非空紧集;(C 2)xX,Mi0(t)=Eet(Gi0(x,)-gi0(x),Mi(t)=Eet(Gi(x,)-gi(x),i=1,2,m,=1,2,ni,在t=0的邻域内是有限的;(C 3),存在可积函数:i0(),i ni():RR+使得Gi0(x1,()-Gi0(x2,()i0()x1-x2,Gi(x1,)-Gi(x2,)i()x1-x2,1ni;(C 4)Mi(t)=Eet(i()-i),0ni,1im,在t=0的邻域内是有限的,其中i:=Ei(),0ni,1im;令X表示集合X的基数,有如下的命题:命题1如果假设(C 1)(C 2)成立,并且X是有限的,那么对于任意的0,有如下结论:(1)P r o bZ-Z0NZ 1-2X me-N 282+ne-N 28n22;(2)如果P r o bZ-Z0NZ1-,则样本大小N满足:N8n222l g2X(m+n)其中2:=m a xxX,1im,1niV a rGi0(x,)-gi0(x),V a rGi(x,)-gi(x)。证明(1)对于任意的xX以及i=1,2,m,m a xgN1(x)-gN1 0(x),gNm(x)-gNm0(x)-m a xg1(x)-g1 0(x),gm(x)-gm0(x)m a xgN1(x)-gN1 0(x),gNm(x)-gNm0(x)-gi(x)+gi0(x)设i 1,2,m 满足giN(x)-gNi0(x)=m a xgN1(x)-gN1 0(x),gNm(x)-gNm0(x)则可以得出m a xgN1(x)-gN1 0(x),gNm(x)-gNm0(x)-m a xg1(x)-g1 0(x),gm(x)-gm0(x)gNi(x)-gNi0(x)-gi(x)+gi0(x)。因此有P r o bZ-ZN0Z=1-P r o bxX,m a x1imgi(x)-gi0(x)-,m a x1imgNi(x)-gNi0(x)0或xX,m a x1imgNi(x)-gNi0(x)0,m a x1imgi(x)-gi0(x)1-P r o bxX,m a x1imgNi(x)-gNi0(x)-m a x1imgi(x)-gi0(x)-P r o bxX,m a x1imgNi(x)-gNi0(x)-m a x1imgi(x)-gi0(x)+P r o bm a x1imgNi(x)-gNi0(x)-m a x1imgi(x)-gi0(x)+P r o bgNi(x)-gNi0(x)-gi(x)+gi0(x)-1-xX2(me-N 282+ne-N 28n22)=1-2X(me-N 282+ne-N 28n22)由上面的命题有如下结论:P r o b gNi0(x)-gi0(x)-2 e-N Ix-2 e-N-2 2221=e-N 2821其中,21=m a xxX,1imV a rGi0(x,)-gi0(x)。同时有 P r o b nik=1(gNi k(x)-gi k(x)224 nik=1P r o b(gNi k(x)-gi k(x)224ni=nik=1P r o b gNi k(x)-gi k(x)2ni nik=1P r o b gNi k(x)-gi k(x)e-N 2821+nie-N 28n2i22同理有P r o bgNi(x)-gNi0(x)-gi(x)+gi0(x)0。那么根据假设(C3),对于任意的xX,x Xv,以及1im,且满足x-x v,有Gi0(x,)-Gi0(x,)i0()v,Gi(x,)-Gi(x,)i()v(1ni)。进而得出gi0(x)-gi0(x)i0vgi(x)-gi(x)i v(1ni)gNi0(x)-gNi0(x)Ni0v,gNi(x)-gNi(x)Ni v(1ni)其中,Ni=N-1Nj=1i(j)(0ni,1im)。令=n1=01+nm=0m,N=n1=0N1+nm=0Nm。命题2令 假 设(C 1)(C 4)成 立,并 且X是无限的,则对于任意的0,有如下结论:(1)P r o bZ-Z0NZ1-2m(m+n)+Dv k(2m+2n)e-N 22(2)如果P r o bZ-Z0NXZ1-,则样本大小N满足:N 22l g2m(m+n)+Dv k(2m+2n)其中v:=4+-1,2=m a x1im,0ni8 V a r(m+n)(i()-i),3 22,3 2n22,2=m a xxX,1im,1niV a rGi0(x,)-gi0(x),V a rGi(x,)-gi(x)。证明(1)P r o bZ-Z0NZ1-P r o bxX,m a x1imgNi(x)-gNi0(x)-m a x1imgi(x)-gi0(x)-P r o bxX,m a x1imgNi(x)-gNi0(x)-m a x1imgi(x)-gi0(x)+P r o bgi(x)-gi0(x)-gNi(x)+gNi0(x)1-mi=1P r o bgNi(x)-gNi0(x)-gi(x)+gi0(x)-(+N)v+P r o bgi(x)-gi0(x)-gNi(x)+gNi0(x)-(+N)v 1-mi=1 2 P r o b N+2+P r o b xXv,s.t.gNi(x)-gNi0(x)-gi(x)+gi0(x)2+P r o b xXv,s.t.gi(x)-gi0(x)-gNi(x)+gNi0(x)2 1-mi=1 2(m+n)e-N a()+xXv 2 e-N 23 22+nie-N 23 2n2i2 =1-2m(m+n)+922第3期林爽等:随机二阶锥规划问题的统计推断Xv(2m+2n)e-N b()1-2m(m+n)+Dv k(2m+2n)e-N b()其中b()=m i n a(),23 22,23 2n22,a()=m i n1im,0ni Ii 2(m+n),Ii 2(m+n)=s u psR s2(m+n)-l gEes(i()-i),i=1,m,=1,ni,同时b()m i ni=1,m,=1,ni-N 28(m+n)2V a ri()-i,23 22,23 2n22=2m a x8 V a r(m+n)(i()-i),3 22,3 2n22=22。因此结论(1)得证。若P r o bZ-Z0NZ1-成立,则有:2m+Dv k(2m+2n)e-N 2-2,因此结论(2)得证。式(1 1)等价于 m i nxX,tTts.t.Ef(x,()tgi(x)-gi0(x)0,i=1,m(1 7)其中,T=Ef(x,():xX。令V:=m i ntT:Ef(x,()t+,xZ(1 8)VN:=m i ntT:fN(x)t+,xZN(1 9)其中,fN(x)=1NNn=1f(x,n),则直接由命题得到定理1。定理1令假设条件(C 1)(C 2)成 立且f(x,()满足假设条件(C 2),X是有限的,那么对于任意的0,有如下结论:(1)P r o bV-V0NV1-2X me-N 282+ne-N 28n22;(2)如果P r o bV-V0NV1-,则样本大小N满足:N8n222l g2X(m+n),其中2:=m a xxX,1im,1nV a rf(x,)-Ef(x,),V a rGi0(x,)-gi0(x),V a rGi(x,)-gi(x)在这个定理中,为了使V0N是S AA问题(1 5)的最优解,可以选择一个更大的集合T来完成证明。当X无限时,由前面的命题可以得到类似的结论。4 结 语本文研究了一类随机二阶锥规划的S AA方法的渐近行为,分析了S AA最优值的收敛速度,估计了样本规模,这为给出置信最优值上下界提供了理论保证。参考文献:1B U S SM,HA S H I MO T OH,MO O R EJB.D e x t r o u sh a n dg r a s p i n gf o r c eo p t i m i z a t i o nJ.I E E ET r a n s a c-t i o n so n R o b o t i c sa n d A u t o m a t i o n,1 9 9 6,1 2(3):4 0 6-4 1 8.2L O B O MS,VAN D E N B E R GHEL,B OY DS,e t a l.A p p l i c a t i o n so fs e c o n d-o r d e rc o n ep r o g r a mm i n gJ.L i n e a rA l g e b r aa n dI t sA p p l i c a t i o n s,1 9 9 8,2 8 4(1/2/3):1 9 3-2 2 8.3A L I Z A D EH F,G O L D F A R B D.S e c o n d-o r d e rc o n ep r o g r a mm i n gJ.M a t h e m a t i c a lP r o g r a mm i n g,2 0 0 3,9 5(1):3-5 1.4MA G G I ON IF,P O T R A F A,B E R T O C CH I M I,e ta l.S t o c h a s t i cs e c o n d-o r d e rc o n ep r o g r a mm i n gi nm o b i l ea dh o cn e t w o r k sJ.J o u r n a lo fO p t i m i z a t i o nT h e o r ya n dA p p l i c a t i o n s,2 0 0 9,1 4 3(2):3 0 9-3 2 8.5A L Z A L G B M.S t o c h a s t i cs e c o n d-o r d e rc o n ep r o-g r a mm i n g:a p p l i c a t i o n sm o d e l sJ.A p p l i e d M a t h e-m a t i c a lM o d e l l i n g,2 0 1 2,3 6(1 0):5 1 2 2-5 1 3 4.6Z HAN GJ,S H IY,T ONG M M,e t a l.A s y m p t o t i ca n a l y s i sf o ras t o c h a s t i cs e c o n d-o r d e rc o n ep r o g r a m-m i n ga n da p p l i c a t i o n sJ.A s i a-P a c i f i c J o u r n a l o fO p-e r a t i o n a lR e s e a r c h,2 0 2 2,3 9(6):2 2 5 0 0 0 2.7L I UJ,TANGZ,Z E NGPP,e t a l.F u l l yd i s t r i b u t e ds e c o n d-o r d e rc o n ep r o g r a mm i n gm o d e l f o re x p a n s i o ni nt r a n s m i s s i o na n dd i s t r i b u t i o nn e t w o r k sJ.I E E ES y s t e m sJ o u r n a l,2 0 2 2,1 6(4):6 6 8 1-6 6 9 2.(责任编辑:刘发盛)032大 连 工 业 大 学 学 报第4 2卷