2020/04/08 by Claus Scheiderer, Scheiderer, Claus
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Optimization and Variational Analysis #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2004.04196
Semidefinite programming (SDP) is the task of optimizing a linear function over the common solution set of finitely many linear matrix inequalities (LMIs). For the running time of SDP solvers, the maximal matrix size of these LMIs is usually more critical than their number. The semidefinite extension degree sxdeg(K) of a convex set K⊆\mathbb Rn is the smallest number d such that K is a linear image of a finite intersection S1∩…∩ SN, where each Si is a spectrahedron defined by a linear matrix inequality of size ≤ d. Thus sxdeg(K) can be seen as a measure for the complexity of performing semidefinite programs over the set K. We give several equivalent characterizations of sxdeg(K), and use them to prove our main result: sxdeg(K)≤2 holds for any closed convex semialgebraic set K⊆\mathbb R2. In other words, such K can be represented using the second-order cone.