On the Equivalence of SDP Feasibility and a Convex Hull Relaxation for System of Quadratic Equations
share
We show semidefinite programming (SDP) feasibility problem is equivalent to solving a convex hull relaxation (CHR) for system of quadratic equations. On the one hand this offers a simple description of SDP. On the other hand, this equivalence makes it possible to describe a version of the Triangle Algorithm for SDP feasibility based on solving CHR. Specifically, the Triangle Algorithm either computes an approximation to the least-norm feasible solution of SDP, or using its distance duality, provides a separation when no solution within a prescribed norm exists. The worst-case complexity of each iteration is computing largest eigenvalue of a symmetric matrix arising in that iteration. Alternate complexity bounds on the total number of iterations are derived. Further applications includes solving an SDP optimization problem. The Triangle Algorithm thus provides an alternative to the existing interior-point algorithms for SDP. Finally, gaining from these results and insights, we discuss potential extension to solving general system of polynomial equations.
READ FULL TEXT