随机二阶锥互补约束优化模型的一般光滑化SAA方法_王博.pdf

第 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)摘要:讨论一般随机二阶锥互补约束问题的求解算法 为处理模型中的不确定性，算法采用样本平均近似(SAA)抽样技术 不同于之前的工作，设计了一般光滑化 SAA 算法框架，可以在满足要求的一类光滑化函数中根据需要进行选择，从而构造光滑化 SAA 算法，并保证收敛性 具体的，若 SOCMPCC 线性无关约束规范等条件成立，则算法构造子问题的稳定点和最优解分别以概率 1 收敛到原问题的 C 稳定点和最优解 最后具体给出两个光滑化函数与其对应光滑化 SAA 算法的例子，由一般光滑化算法框架可得这两种算法收敛关键词:随机优化;互补约束优化;二阶锥;样本平均近似(SAA)中图分类号:O2215;O224文献标识码:AA unified SAA framework for stochastic optimization 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，algorithms 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 accepts 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 generated 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 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是有限个二阶锥的笛卡尔乘积，其维数 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(即 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 方法的一般框架该框架的构造对 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，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: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预备知识本章介绍变分分析和二阶锥的部分基础知识 对于单值 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 期王博，等:随机二阶锥互补约束优化模型的一般光滑化 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()的光滑化映射 为了研究 SSOCMPCC 模型，在可行点 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 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可行点 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 稳定点，若