Journal of Convex Analysis 25 (2018), No. 4, 1159--1182
Copyright Heldermann Verlag 2018
Tight SDP Relaxations for a Class of Robust SOS-Convex Polynomial Programs without the Slater Condition
Thai Doan Chuong
School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia
chuongthaidoan@yahoo.com
Vaithilingam Jeyakumar
School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia
v.jeyakumar@unsw.edu.au
We examine a robust SOS-convex polynomial program under a general class of bounded uncertainty, called intersection ellipsoidal uncertainty, which is described by the intersection of a family of ellipsoids and covers many commonly used uncertainty classes of robust optimization. The class of SOS-convex polynomials is a numerically tractable subclass of convex polynomials and, in particular, contains convex quadratic functions and convex separable polynomials. We present a conical linear program with a coupled sum-of-squares polynomial and linear matrix inequality constraints as its relaxation problem and show that the relaxation problem can equivalently be reformulated as a semidefinite linear program (SDP). Under a mild well-posedness condition, we establish that the so-called SDP relaxation is tight in the sense that the optimal values of the robust SOS-convex polynomial program and its relaxation problem are equal. We also show, under a general regularity condition, that the SDP relaxation is exact in the sense that the relaxation problem not only shares the same optimal value with the robust SOS-convex polynomial program but also attains its optimum, extending the corresponding known results in the robust optimization literature to the general class of intersection ellipsoidal uncertainty.
Keywords: Robust optimization, semi-infinite convex program, convex polynomial, semidefinite linear program, SDP relaxation.
MSC: 49K99, 65K10, 90C29, 90C46
[ Fulltext-pdf (163 KB)] for subscribers only.