一類不確定凸多項式優(yōu)化的SOS松弛對偶問題

黃嘉譯　孫祥凱

摘要： 考慮一類目標(biāo)函數(shù)和約束函數(shù)均具有譜面不確定數(shù)據(jù)的平方和（SOS）凸多項式優(yōu)化問題. 首先， 借助SOS條件建立帶有不確定數(shù)據(jù)的SOS凸多項式系統(tǒng)的擇一性定理; 其次， 引入該SOS多項式優(yōu)化問題的SOS松弛對偶問題， 并刻畫它們之間的魯棒弱對偶性與強對偶性質(zhì); 最后， 借助數(shù)值算例說明該SOS松弛對偶問題可以重構(gòu)為半定規(guī)劃問題.

關(guān)鍵詞： SOS凸多項式; 魯棒對偶性; 擇一性定理

中圖分類號： O221.6； O224

文獻標(biāo)志碼： 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凸多項式在機器學(xué)習(xí)、 信號處理、 自動控制和最優(yōu)電力流等領(lǐng)域應(yīng)用廣泛. 但多項式的凸性檢驗十分困難， 而多項式的SOS凸性可借助求解相應(yīng)的半定規(guī)劃（SDP）問題進行檢驗. 進一步， SOS凸多項式不僅涵蓋了凸二次函數(shù)和凸可分離多項式等經(jīng)典的凸多項式［1-2］， 而且也可以是非二次和非分離的多項式. 文獻［2-9］給出了SOS凸多項式的理論及實際應(yīng)用的相關(guān)成果.

近年來， 關(guān)于SOS凸多項式結(jié)構(gòu)的不確定性優(yōu)化問題的魯棒對偶性研究已得到廣泛關(guān)注. 借助標(biāo)量化方法和SOS條件， Sun等［10］研究了目標(biāo)函數(shù)和約束函數(shù)均具有譜面不確定數(shù)據(jù)的多目標(biāo)SOS凸多項式問題的精確SDP對偶問題; Jeyakumar等［11］首先給出了SOS凸不等式系統(tǒng)的擇一性定理， 并借助SOS條件研究了SOS凸多項式結(jié)構(gòu)的極大極小優(yōu)化問題的對偶理論； Jeyakumar等［12］借助凸集強分離定理， 刻畫了SOS凸不等式系統(tǒng)的擇一性定理， 并研究了目標(biāo)函數(shù)帶有不確定數(shù)據(jù)的SOS凸多項式優(yōu)化問題與其對應(yīng)的SDP松弛對偶問題之間的零對偶間隙性質(zhì)； Jeyakumar等［13］借助經(jīng)典的法錐條件， 給出了魯棒SOS凸多項式優(yōu)化問題的最優(yōu)性條件， 并分別在不確定數(shù)據(jù)屬于多面體不確定集和橢球不確定集的情形下， 刻畫了該優(yōu)化問題的精確SDP松弛； Chuong［14］借助SOS條件和線性矩陣不等式， 建立了SOS凸多項式結(jié)構(gòu)的不確定性優(yōu)化問題的魯棒對偶定理， 并將該不確定性優(yōu)化問題的SOS對偶問題重構(gòu)為SDP問題； Chuong等［15］借助魯棒松弛型條件， 研究了一類SOS凸多項式結(jié)構(gòu)的兩階段自適應(yīng)優(yōu)化問題的精確SDP對偶問題.

受文獻［10-12］工作的啟發(fā)， 本文研究一類目標(biāo)函數(shù)和約束函數(shù)均具有譜面不確定數(shù)據(jù)的多目標(biāo)SOS凸多項式優(yōu)化問題. 先建立一類不確定SOS凸多項式系統(tǒng)的魯棒擇一性定理， 再引入該SOS凸多項式優(yōu)化問題的SOS松弛對偶問題， 并刻畫它們之間的魯棒弱對偶與強對偶性質(zhì).

參考文獻

［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］譚玟， 孫祥凱. 不確定平方和凸多項式優(yōu)化的SDP松弛與魯棒鞍點刻畫 [J]. 吉林大學(xué)學(xué)報（理學(xué)版）， 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］葉冬平， 方東輝. 魯棒復(fù)合優(yōu)化問題的Lagrange對偶 ［J］. 數(shù)學(xué)物理學(xué)報， 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］劉娟， 龍憲軍. 非光滑多目標(biāo)半無限規(guī)劃問題的混合型對偶 ［J］. 應(yīng)用數(shù)學(xué)和力學(xué)， 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］孫祥凱， 曾靜， 郭曉樂. 一類不確定優(yōu)化問題的魯棒對偶性刻畫 [J]. 吉林大學(xué)學(xué)報（理學(xué)版）， 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.

（責(zé)任編輯： 李 琦）

收稿日期： 2023-09-06.

第一作者簡介： 黃嘉譯（1998—）， 女， 漢族， 碩士研究生， 從事最優(yōu)化理論與算法的研究， E-mail： huangjyzk@163.com.

通信作者簡介： 孫祥凱（1984—）， 男， 漢族， 博士， 教授， 從事最優(yōu)化理論與算法的研究， E-mail： sunxk@ctbu.edu.cn.

基金項目： 國家自然科學(xué)基金（批準(zhǔn)號： 11701057）、 重慶市自然科學(xué)基金面上項目（批準(zhǔn)號： cstc2021jcyj-msxmX1191）、 重慶市教委重點項目（批準(zhǔn)號： KJZD-K202100803）和重慶市研究生科研創(chuàng)新項目（批準(zhǔn)號： CYS23566）.