Original scientific paper

ON THE COMPLEXITY OF SEMIDEFINITE PROGRAMS ARISING IN POLYNOMIAL OPTIMIZATION

Igor Klep
Janez Povh
Angelika Wiegele

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

Hrčak ID:

96809

URI

https://hrcak.srce.hr/96809

Publication date:

30.12.2012.

Visits: 1.275 *