A new class of alternative theorems for SOS-convex inequalities and robust optimization

Abstract

In this paper, we present a new class of alternative theorems for SOS-convex inequality systems without any qualifications. This class of theorems provides an alternative equations in terms of sums of squares to the solvability of the given inequality system. A strong separation theorem for convex sets, described by convex polynomial inequalities, plays a key role in establishing the class of alternative theorems. Consequently, we show that the optimal values of various classes of robust convex optimization problems are equal to the optimal values of related semidefinite programming problems (SDPs) and so, the value of the robust problem can be found by solving a single SDP. The class of problems includes programs with SOS-convex polynomials under data uncertainty in the objective function such as uncertain quadratically constrained quadratic programs. The SOS-convexity is a computationally tractable relaxation of convexity for a real polynomial. We also provide an application of our theorem of the alternative to a multi-objective convex optimization under data uncertainty.

Keywords:

• theorems of the alternative
• convex optimization
• multi-objective optimization
• optimization under data uncertainty

Acknowledgments

The authors are grateful to the referee for his/her helpful comments and valuable suggestions which have contributed to the final preparation of the paper.

Notes

Dedicated to Boris Mordukhovich on the occasion of his 65th Birthday.