SOS-Convex Semialgebraic Programs and its Applications to Robust Optimization: A Tractable Class of Nonsmooth Convex Optimization

作     者：Chieu, N. H. Feng, J. W. Gao, W. Li, G. Wu, D. 

作者机构：Univ New South Wales Sch Math Stat Sydney NSW 2052 Australia Vinh Univ Dept Math Vinh 42118 Nghe An Vietnam Univ New South Wales Sch Civil & Environm Engn Sydney NSW 2052 Australia 

出 版 物：《SET-VALUED AND VARIATIONAL ANALYSIS》 (集值分析)

年 卷 期：2018年第26卷第2期

页      面：305-326页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Australian Research Council Vietnam National Foundation 465 for Science and Technology Development (NAFOSTED) [101.01-2017.325] 

主　　题：Nonsmooth optimization Convex optimization SOS-convex polynomial Semidefinite program Robust optimization 

摘      要：In this paper, we introduce a new class of nonsmooth convex functions called SOS-convex semialgebraic functions extending the recently proposed notion of SOS-convex polynomials. This class of nonsmooth convex functions covers many common nonsmooth functions arising in the applications such as the Euclidean norm, the maximum eigenvalue function and the least squares functions with a (1)-regularization or elastic net regularization used in statistics and compressed sensing. We show that, under commonly used strict feasibility conditions, the optimal value and an optimal solution of SOS-convex semialgebraic programs can be found by solving a single semidefinite programming problem (SDP). We achieve the results by using tools from semialgebraic geometry, convex-concave minimax theorem and a recently established Jensen inequality type result for SOS-convex polynomials. As an application, we show that robust SOS-convex optimization proble ms under restricted spectrahedron data uncertainty enjoy exact SDP relaxations. This extends the existing exact SDP relaxation result for restricted ellipsoidal data uncertainty and answers an open question in the literature on how to recover a robust solution of uncertain SOS-convex polynomial programs from its semidefinite programming relaxation in this broader setting.