Bahman Kalantari, Rutgers University

Given  a subset S={A_1, ..., A_m}  of nxn  real symmetric  matrices, we define  its spectrahull as the set of all m-tuples  (Tr(A_1X),...,Tr(A_mX)),  where X ranges in the spectraplex,  the set of nxn  symmetric PSD matrices with  trace one.  We let  spectrahall membership (SHM) stand for testing if a given m-tuple  b  lies in the spectrahull of S.  On the one hand when each A_i is diagonal, SHM  reduces to  the convex hull membership problem (CHM), a fundamental problem in LP.  On the other hand, a bounded SDP feasibility is reducible to SHM.  By building on the  Triangle Algorithm (TA),  a fully polynomial time approximation scheme developed for CHM and its generalization,  we design a version  for SHM that  inherits  the O(1/epsilon^2) iteration complexity of TA,  as well as its faster versions applicable  under special conditions.  The complexity of each iteration is O(mn^2), plus  estimating  the least eigenvalue of a symmetric  matrix.  This iterative property together with a semidefinite  version of Caratheodory theorem allow implementing  TA for SHM  as if  solving a CHM,  resorting to  the power method  for eigenvalue estimation only as needed, thereby improving the complexity of iterations. The proposed TA for SHM is simple and practical, applicable to general SDP feasibility and optimization.  Additionally, TA extends to an spectral analogue of SVM for separation of two spectrahulls.  We discuss generalizations  and combinatorial  applications.   

The article is scheduled to appear at arxiv.