ON THE COMPLEXITY OF SEMIDEFINITE PROGRAMS ARISING IN POLYNOMIAL OPTIMIZATION

Abstract

In this paper we investigate matrix inequalities which hold irrespective of the size of the matrices involved, and explain how the search for such inequalities can be implemented as a semidefinite program (SDP). We provide a comprehensive discussion of the time complexity of these SDPs.

Keywords

• optimization
• sum of squares
• semidefinite programming
• polynomial
• Matlab toolbox
• real algebraic geometry