一類不確定凸多項式優化的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）.