随机二阶锥互补约束优化模型的一般光滑化SAA方法_王博.pdf
《随机二阶锥互补约束优化模型的一般光滑化SAA方法_王博.pdf》由会员分享,可在线阅读,更多相关《随机二阶锥互补约束优化模型的一般光滑化SAA方法_王博.pdf(7页珍藏版)》请在咨信网上搜索。
1、第 51 卷 第 1 期2023 年 2 月福州大学学报(自然科学版)Journal of Fuzhou University(Natural Science Edition)Vol 51 No 1Feb 2023DOI:107631/issn1000224322136文章编号:10002243(2023)01001307随机二阶锥互补约束优化模型的一般光滑化 SAA 方法王博1,初丽2(1 福州大学数学与统计学院,福建 福州350108;2 福建工程学院计算机科学与数学学院,福建 福州350118)摘要:讨论一般随机二阶锥互补约束问题的求解算法 为处理模型中的不确定性,算法采用样本平均近似(
2、SAA)抽样技术 不同于之前的工作,设计了一般光滑化 SAA 算法框架,可以在满足要求的一类光滑化函数中根据需要进行选择,从而构造光滑化 SAA 算法,并保证收敛性 具体的,若 SOCMPCC 线性无关约束规范等条件成立,则算法构造子问题的稳定点和最优解分别以概率 1 收敛到原问题的 C 稳定点和最优解 最后具体给出两个光滑化函数与其对应光滑化 SAA 算法的例子,由一般光滑化算法框架可得这两种算法收敛关键词:随机优化;互补约束优化;二阶锥;样本平均近似(SAA)中图分类号:O2215;O224文献标识码:AA unified SAA framework for stochastic opti
3、mization problems withsecond-order cone complementarity constraintsWANG Bo1,CHU Li2(1 College of Mathematics and Statistics,Fuzhou University,Fuzhou,Fujian 350108,China;2 College of Computer Science and Mathematics,Fujian University of Technology,Fuzhou,Fujian 350118,China)Abstract:In this paper,alg
4、orithms for a general class of stochastic optimization problem with second-order cone complementarity constraints are investigated Sample average approximation technique isintroduced to handle the uncertainty This paper suggests a unified smoothing sample average approxi-mation(SAA)framework,which a
5、ccepts a smoothing function from a broad class to build a convergentsmoothing SAA algorithm It can be proved that if the linear independent constraint qualification forsecond-order cone constrained optimizations and some other mild assumptions hold,the stationarypoints and optimal solutions of the g
6、enerated sub-problem converge to C-stationary points and optimalsolutions of second-order cone complementarity constraints with probability one,respectively In addi-tion,two example smoothing functions and corresponding smoothing SAA algorithms are presented,which can be proved convergent according
7、to the unified smoothing SAA frameworkKeywords:stochastic optimization;optimization with complementarity constraints;second-ordercone;sample average approximation(SAA)0引言本研究分析一类较为一般的含有二阶锥互补约束(SSOCMPCC)的随机优化模型:min E f(z,()KmE G(z,()E H(z,()Km其中:Kmj:=(x1;x2)mj1x1x2为二阶锥,Km=Km1 Km2 KmJ是有限个二阶锥的笛卡尔乘积,其维数
8、m=Jj=1mj;:k为定义在概率空间(,F,P)上的随机向量,E 是数学期望;f:m 为一个连续可微的随机函数,G,H:m m是随机映射SSOCMPCC 模型是有实际意义的 其中随机变量的引入可以源于数据的误差和未来的不确定性;互补约束可以来自于逆问题12 或双层规划问题3 的转化收稿日期:20220402通信作者:初丽(1986),讲师,主要从事最优化理论和算法方面研究,sophiatruly 126com基金项目:国家自然科学青年基金资助项目(11701091)福州大学学报(自然科学版)第 51 卷http:/xbzrbfzueducnSSOCMPCC 模型在所有二阶锥维数都为 1(即
9、m1=m2=mn=1)时,退化为随机互补模型(SMPCC):min E f(z,()0 E G(z,)E H(z,)0关于相对简单的随机互补模型的理论研究和求解方法,可参考相关文献 47 需要指出,SSOC-MPCC 模型并非 SMPCC 模型的平凡推广 SSOCMPCC 模型可行集合不再有多面体性质,其一阶必要性条件更为复杂 稳定性理论可参考 Zhang 等8、Liang 等9 和 Ye 等3 的工作 需要注意关于 C 稳定点的定义是有歧义的,具体可以参见 Chu 等10 的工作本研究希望构造一个求解 SSOCMPCC 模型的不依赖具体光滑化函数的光滑化 SAA 方法的一般框架该框架的构造对
10、 SSOCMPCC 模型有效算法的研究具有积极作用假设 E f(z,()、E G(z,()和 E H(z,()对所有的 z m都是有定义的()简记为 对应于锥 Km,映射 G(z,)和 H(z,)可以进行如下分块,即:G(z,)=G1(z,);G2(z,);GJ(z,)(),H(z,)=H1(z,);H2(z,);HJ(z,)()假设可以抽样得到随机向量 的N个独立同分布的样本1,2,N 由此可构造SSOCMPCC 模型的近似问题:min fN(z)KmGN(z)HN(z)Km其中:fN(z):=1NNi=1f(z,i),GN(z):=1NNi=1G(z,i),HN(z):=1NNi=1H(z
11、,i)将上述问题中的约束条件替换成 HN(z)(HN(z)GN(z)=0(其中()表示到二阶锥 Km上投影算子 SKm()的光滑化函数),可得光滑化 SAA 子问题:min fN(z)HN(z)(HN(z)GN(z)=0(1)问题(1)依赖于 的解z()是随机变量 期望当 0时,z()在某种概率意义下能接近SSOCMPCC模型的解 若()为CHKS 光滑化函数时,由文献 10知,上述期望是成立的 后续讨论将指出较一般的一类光滑化函数也有类似的性质符号说明 本研究中 I 和 0 分别表示单位阵和零矩阵(向量)B(z,)为以 z 为心,以 为半径的闭球 +:=max 0,为到正半轴的投影 设 H:
12、mn可微,则 JH(z)表示 H 在 z处的雅克比矩阵,而 H(z):=JH(z)Tx,y=xTy 为向量 x 和 y 的内积,x=xTx 为向量的 2 范数 对向量 x=(x1;x2)m1,定义 x=(x1;x2)函数 h:m 的上图为集合 epi h:=(x,y)m h(x)y 集合 O0为二阶锥互补集合,由所有满足 Tii=0 的(,)Km Km构成,其中 i=1,2,J 设 Z0为 SSOCMPCC 模型的可行集合 常数 0记为 SSOCMPCC 的最优函数值 集合 C 的指示函数记为 C(x):=0(x C)+(否则),且引入记号 f(z):=E f(z,)+Z0(z)1预备知识本章
13、介绍变分分析和二阶锥的部分基础知识 对于单值 Lipschitz 连续的映射 H:mn,B(ouligand)次微分定义为 BH(x)=limkJ H(xk)xkx,H 在 xk处可微,Clarke 广义雅各比 H(x)定义为 BH(x)的凸包11 给定 x=(x1;x2)t,在二阶锥 Kt意义下的谱分解为:x=1(x)c1(x)+2(x)c2(x)(2)其中:i=1,2,i(x)和 ci(x)分别为 x 的特征值与特征向量,即:i(x)=x1+(1)ix2,ci(x)=121;(1)ix2x2()(若 x2 0)12(1;(1)iv)(若 x2=0)41第 1 期王博,等:随机二阶锥互补约束
14、优化模型的一般光滑化 SAA 方法http:/xbzrbfzueducn这里,v 满足 v=1 单值函数 g?()可以利用谱分解,按如下方式诱导二阶锥上的变换 g(x),即:g(x)=g?(1)c1(x)+g?(2)c2(x)(3)其中:1,2,c1(x)和 c2(x)分别为 x 的特征值与特征向量 取 g?(z)=z+,可得到二阶锥 K 上的投影算子:SK(x)=1(x)+c1(x)+2(x)+c2(x)为了方便,SKm(x)简记为 S(x),SKmj(x)简记为 Sj(x)显然 S(x)=S1(x)S2(x)Sm(x)易知 +的光滑化函数也将诱导 S()的光滑化映射 为了研究 SSOCMP
15、CC 模型,在可行点 z 处定义指标集,对锥 Km进行分拆(bd 为集合的边界):N1=j E Gj(z,)=0,E Hj(z,)int KmjN2=j E Gj(z,)int Kmj,E Hj(z,)=0N3=j E Gj(z,)bd Kmj 0,E Hj(z,)bd Kmj 0 N4=j E Gj(z,)=0,E Hj(z,)bd Kmj 0 N5=j E Gj(z,)bd Kmj 0,E Hj(z,)=0N6=j E Gj(z,)=0,E Hj(z,)=0,N=N3 N4 N5 N6SSOCMPCC 模型的拉格朗日函数可定义为:L(z,u,v)=E f(z,)+Jj=1E Gj(z,)T
16、 uj+Jj=1E Hj(z,)T vj计算可得其关于 z 的梯度为:zL(z,u,v)=E f(z,)+Jj=1E Gj(z,)uj+Jj=1E Hj(z,)vj为了建立收敛性理论,还需要如下约束规范成立:定义 1假设期望 E G(z,)和 E H(z,)关于 z 在 z 处是连续可微的 称 SSOCMPCC 模型在 z处 SOCMPCC 线性无关约束规范(SOCMPCC-LICQ)成立,若矩阵 C(z)=JE GN1N(z,)JE HN2N(z,)()行满秩给定SSOCMPCC模型的一个可行点z,稳定性条件可参考含互补约束问题12 此处沿用文献 8中的“弱稳定性”和“C 稳定性”定义 2可
17、行点 z 被称为 SSOCMPCC 模型的弱稳定点,若存在乘子 u=(u1;u2;uJ)和 v=(v1;v2;vJ),使得:E f(z,)+Jj=1E Gj(z,)uj+Jj=1E Hj(z,)vj=0(4)vj=0(j N1);uj=0(j N2)(5)uj=BSj(E Hj(z,)E Gj(z,)(uj vj)(j N3)(6)定义 3可行点 z 称为 SSOCMPCC 模型的 C 稳定点,若存在乘子 u=(u1;u2;uJ)和 v=(v1;v2;vJ),使得式(4)(6)成立,且有:uj Sj(E Hj(z,)E Gj(z,)(uj vj)(j N4 N5 N6)(7)注意 C 稳定性强
18、于弱稳定性10 稳定性定义中需要计算投影算子 Sj的 B 次微分的具体形式 此处可利用 Zhang 等8 文献中的引理 21 而广义雅克比可由公式Sj=convBSj得到接下来的讨论需要假设随机向量 的样本 1,N是独立同分布的,且满足下述条件条件 1映射 f(,)、G(,)和 H(,)在 m上对几乎所有的 都二阶连续可微条件 2对任意的 z m,存在 z 的邻域 D,以及一个满足 E g()+的非负可测函数 g(),51福州大学学报(自然科学版)第 51 卷http:/xbzrbfzueducn使得对所有的 z D 和几乎所有的 ,有:max f(z,),2f(z,),JG(z,),J2G(
19、z,),JH(z,),J2H(z,)g()由条件 1 和条件2 可知,E f(z,)、E G(z,)和 E H(z,)是二阶连续可微的(参见文献 4定理 744)根据大数定律,如下引理成立(参见文献 4定理 748)引理 1设条件 1 和 2 成立 令 zN ZN,若 N+时有 zNz 以概率 1 成立,则数学期望和微分算子是可交换的,下述收敛性以概率 1 成立:fN(zN)E f(z,),fN(zN)E f(z,)=E f(z,)GN(zN)E G(z,),JGN(zN)E JG(z,)=JE G(z,)HN(zN)E H(z,),JHN(zN)E JH(z,)=JE H(z,)2SSOCM
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 随机 二阶锥 互补 约束 优化 模型 一般 光滑 SAA 方法 王博
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。