一类不确定凸多项式优化的SOS松弛对偶问题

黄嘉译　孙祥凯

摘要： 考虑一类目标函数和约束函数均具有谱面不确定数据的平方和（SOS）凸多项式优化问题. 首先， 借助SOS条件建立带有不确定数据的SOS凸多项式系统的择一性定理; 其次， 引入该SOS多项式优化问题的SOS松弛对偶问题， 并刻画它们之间的鲁棒弱对偶性与强对偶性质; 最后， 借助数值算例说明该SOS松弛对偶问题可以重构为半定规划问题.

关键词： SOS凸多项式; 鲁棒对偶性; 择一性定理

中图分类号： O221.6； O224

文献标志码： A文章编号： 1671-5489（2024）02-0285-08

SOS Relaxation Dual Problem for a Class of Uncertain Convex Polynomial Optimization

HUANG Jiayi， SUN Xiangkai

（College of Mathematics and Statistics， Chongqing Technology and Business University， Chongqing 400067， China）

Abstract： We considered a class of sum of squares （SOS） convex polynomial optimization problems with spectrahedral uncertainty data in both objective and constraint functions. Firstly， an alternative theorem for SOS-convex polynomial system with uncertain data was established in terms of SOS conditions. Secondly， we introduced a SOS relaxation dual problem for this SOS polynomial optimization problem and characterized the robust weak and strong duality properties between them. Finally， a numerical example was used to demonstrate that the SOS relaxation dual problem could be reformulated as a semidefinite  programming problem.

Keywords： SOS-convex polynomial; robust duality; alternative theorem

SOS凸多项式在机器学习、 信号处理、 自动控制和最优电力流等领域应用广泛. 但多项式的凸性检验十分困难， 而多项式的SOS凸性可借助求解相应的半定规划（SDP）问题进行检验. 进一步， SOS凸多项式不仅涵盖了凸二次函数和凸可分离多项式等经典的凸多項式［1-2］， 而且也可以是非二次和非分离的多项式. 文献［2-9］给出了SOS凸多项式的理论及实际应用的相关成果.

近年来， 关于SOS凸多项式结构的不确定性优化问题的鲁棒对偶性研究已得到广泛关注. 借助标量化方法和SOS条件， Sun等［10］研究了目标函数和约束函数均具有谱面不确定数据的多目标SOS凸多项式问题的精确SDP对偶问题; Jeyakumar等［11］首先给出了SOS凸不等式系统的择一性定理， 并借助SOS条件研究了SOS凸多项式结构的极大极小优化问题的对偶理论； Jeyakumar等［12］借助凸集强分离定理， 刻画了SOS凸不等式系统的择一性定理， 并研究了目标函数带有不确定数据的SOS凸多项式优化问题与其对应的SDP松弛对偶问题之间的零对偶间隙性质； Jeyakumar等［13］借助经典的法锥条件， 给出了鲁棒SOS凸多项式优化问题的最优性条件， 并分别在不确定数据属于多面体不确定集和椭球不确定集的情形下， 刻画了该优化问题的精确SDP松弛； Chuong［14］借助SOS条件和线性矩阵不等式， 建立了SOS凸多项式结构的不确定性优化问题的鲁棒对偶定理， 并将该不确定性优化问题的SOS对偶问题重构为SDP问题； Chuong等［15］借助鲁棒松弛型条件， 研究了一类SOS凸多项式结构的两阶段自适应优化问题的精确SDP对偶问题.

受文献［10-12］工作的启发， 本文研究一类目标函数和约束函数均具有谱面不确定数据的多目标SOS凸多项式优化问题. 先建立一类不确定SOS凸多项式系统的鲁棒择一性定理， 再引入该SOS凸多项式优化问题的SOS松弛对偶问题， 并刻画它们之间的鲁棒弱对偶与强对偶性质.

参考文献

［1］HELTON J W， NIE J. Semidefinite Representation of Convex Sets ［J］. Mathematical Programming， 2010， 122（1）： 21-64.

［2］AHMADI A A， PARRILO P A. A Convex Polynomial That Is Not SOS-Convex ［J］. Mathematical Programming， 2012， 135（1）： 275-292.

［3］LASSERRE J B. Moments， Positive Polynomials and Their Applications ［M］. London： Imperial College Press， 2009： 43-239.

［4］JEYAKUMAR V， LI G. Exact SDP Relaxations for Classes of Nonlinear Semidefinite Programming Problems ［J］. Operations Research Letters， 2012， 40（6）： 529-536.

［5］AHMADI A A， PARRILO P A. A Complete Characterization of the Gap between Convexity and SOS-Convexity ［J］. SIAM Journal on Optimization， 2013， 23（2）： 811-833.

［6］CHUONG T D， JEYAKUMAR V. Tight SDP Relaxations for a Class of Robust SOS-Convex Polynomial Programs without the Slater Condition ［J］. Journal of Convex Analysis， 2018， 25（4）： 1159-1182.

［7］JIAO L， LEE J H. Finding Efficient Solutions in Robust Multiple Objective Optimization with SOS-Convex Polynomial Data ［J］. Annals of Operations Research， 2021， 296（1）： 803-820.

［8］WANG M， LI X B， CHEN J， et al. On Radius of Robust Feasibility for Convex Conic Programs with Data Uncertainty ［J］. Numerical Functional Analysis and Optimization， 2021， 42（16）： 1896-1924.

［9］谭玟， 孙祥凯. 不确定平方和凸多项式优化的SDP松弛与鲁棒鞍点刻画 [J]. 吉林大學学报（理学版）， 2023， 61（3）： 525-530. （TAN W， SUN X K. Characterizations of SDP Relaxation and Robust Saddle Points for Uncertain Sum of Squares Convex Polynomial Optimization [J]. Journal of Jilin University （Science Edition）， 2023， 61（3）： 525-530.）

［10］SUN X K， TAN W， TEO K L. Characterizing a Class of Robust Vector Polynomial Optimization via Sum of Squares Conditions ［J］. Journal of Optimization Theory and Applications， 2023， 197（2）： 737-764.

［11］JEYAKUMAR V， VICENTE-PREZ J. Dual Semidefinite Programs without Duality Gaps for a Class of Convex Minimax Programs ［J］. Journal of Optimization Theory and Applications， 2014， 162（3）： 735-753.

［12］JEYAKUMAR V， LI G. A New Class of Alternative Theorems for SOS-Convex Inequalities and Robust Optimization ［J］. Applicable Analysis， 2015， 94（1）： 56-74.

［13］JEYAKUMAR V， LI G， VICENTE-PREZ J. Robust SOS-Convex Polynomial Optimization Problems： Exact SDP Relaxations ［J］. Optimization Letters， 2015， 9（1）： 1-18.

［14］CHUONG T D. Linear Matrix Inequality Conditions and Duality for a Class of Robust Multiobjective Convex Polynomial Programs ［J］. SIAM Journal on Optimization， 2018， 28（3）： 2466-2488.

［15］CHUONG T D， JEYAKUMAR V， LI G， et al. Exact Dual Semi-definite Programs for Affinely Adjustable Robust SOS-Convex Polynomial Optimization Problems ［J］. Optimization， 2022， 71（12）： 3539-3569.

［16］RAMANA M， GOLDMAN A J. Some Geometric Results in Semidefinite Programming ［J］. Journal of Global Optimization， 1995， 7（1）： 33-50.

［17］VINZANT C. What Is Aspectrahedron？ ［J］. Notices of the American Mathematical Society， 2014， 61（5）： 492-494.

［18］BEN-TAL A， EL GHAOUI L， NEMIROVSKI A. Robust Optimization ［M］. Princeton： Princeton University Press， 2009： 3-25.

［19］叶冬平， 方东辉. 鲁棒复合优化问题的Lagrange对偶 ［J］. 数学物理学报， 2020， 40（4）： 1095-1107. （YE D P， FANG D H. Lagrange Dualities for Robust Composite Optimization Problems ［J］. Acta Mathematica Scientia， 2020， 40（4）： 1095-1107.）

［20］刘娟， 龙宪军. 非光滑多目标半无限规划问题的混合型对偶 ［J］. 应用数学和力学， 2021， 42（6）： 595-601. （LIU J， LONG X J. Mixed Type Duality for Nonsmooth Multiobjective Semi-infinite Programming Problems ［J］. Applied Mathematics and Mechanics， 2021， 42（6）： 595-601.）

［21］孙祥凯， 曾静， 郭晓乐. 一类不确定优化问题的鲁棒对偶性刻画 [J]. 吉林大学学报（理学版）， 2016， 54（4）： 715-719. （SUN X K， ZENG J， GUO X L. Characterizations of Robust Duality for a Class of Uncertain Optimization Problems [J]. Journal of Jilin University （Science Edition）， 2016， 54（4）： 715-719.）

［22］EHRGOTT M. Multicriteria Optimization ［M］. Berlin： Springer， 2005： 1-248.

［23］SION M. On General Minimax Theorems ［J］. Pacific Journal of Mathematics， 1958， 8（1）： 171-176.

［24］PARRILO P A. Polynomial Optimization， Sums of Squares， and Applications ［M］//BLEKHERMAN G， PARRILO P A， THOMAS R R. Semidefinite Optimization and Convex Algebraic Geometry. Philadelphia PA： SIAM， 2013： 47-157.

（責任编辑： 李 琦）

收稿日期： 2023-09-06.

第一作者简介： 黄嘉译（1998—）， 女， 汉族， 硕士研究生， 从事最优化理论与算法的研究， E-mail： huangjyzk@163.com.

通信作者简介： 孙祥凯（1984—）， 男， 汉族， 博士， 教授， 从事最优化理论与算法的研究， E-mail： sunxk@ctbu.edu.cn.

基金项目： 国家自然科学基金（批准号： 11701057）、 重庆市自然科学基金面上项目（批准号： cstc2021jcyj-msxmX1191）、 重庆市教委重点项目（批准号： KJZD-K202100803）和重庆市研究生科研创新项目（批准号： CYS23566）.