Tight SDP Relaxations for a Class of Robust SOS-Convex Polynomial Programs without the Slater Condition

T. D. Chuong ; V. Jeyakumar

Journal of convex analysis, Tome 25 (2018) no. 4, pp. 1159-1182

Résumé

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.

Détail

Classification : 49K99, 65K10, 90C29, 90C46
Mots-clés : Robust optimization, semi-infinite convex program, convex polynomial, semidefinite linear program, SDP relaxation