2019/11/10 by Kalantari, Bahman
#32C37 #52A20 #68W25 #90C06 #90C20 #90C22 #90C25 #90C90 #Computational Complexity (cs.CC) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #G.1.3 #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1911.03989
We show \it semidefinite programming (SDP) feasibility problem is equivalent to solving a \it convex hull relaxation (CHR) for a finite 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 \it 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 \it distance duality, provides a separation when no solution within a prescribed norm exists. The worst-case complexity of each iteration is computing the largest eigenvalue of a symmetric matrix arising in that iteration. Alternate complexity bounds on the total number of iterations can be derived. The Triangle Algorithm thus provides an alternative to the existing interior-point algorithms for SDP feasibility and SDP optimization. In particular, based on a preliminary computational result, we can efficiently solve SDP relaxation of \it binary quadratic feasibility via the Triangle Algorithm. This finds application in solving SDP relaxation of MAX-CUT. We also show in the case of testing the feasibility of a system of convex quadratic inequalities, the problem is reducible to a corresponding CHR, where the worst-case complexity of each iteration via the Triangle Algorithm is solving a \it trust region subproblem. Gaining from these results, we discuss potential extension of CHR and the Triangle Algorithm to solving general system of polynomial equations.