Semidefinite programming and matrix scaling over the semidefinite cone

AbstractLet E be the Hilbert space of real symmetric matrices with block diagonal form diag(A,M), where A is n×n, and M is an l×l diagonal matrix, with the inner product 〈x,y〉≡Trace(xy). We assume n+l⩾1, i.e. allow n=0 or l=0. Given x∈E, we write x⪰0 (x≻0) if it is positive semidefinite (positive definite). Let Q:E→E be a symmetric positive semidefinite linear operator, and μ=min{φ(x)=0.5Trace(xQx):∥x∥=1,x⪰0}. The problem of testing if μ=0 is a significant problem called Homogeneous Programming. On the one hand the feasibility problem in semidefinite programming (SDP) can be formulated as a Homogeneous Programming problem. On the other hand it is related to the generalization of the classic problem of Matrix Scaling. Let ϵ∈(0,1) be a given accuracy, u=Qe−e, e the identity matrix in E, and N=n+l. We describe a path-following algorithm that in case μ=0, in O(Nln[N∥u∥/ϵ]) Newton iterations produces d⪰0, ∥d∥=1 such that φ(d)⩽ϵ. If μ>0, in O(Nln[N∥u∥/μ]+lnln(1/ϵ)) Newton iterations the algorithm produces d≻0 such that ∥DQDe−e∥⩽ϵ, where D is the operator that maps w∈E to d1/2wd1/2. Moreover, we use the algorithm to prove: μ>0, if and only if there exists d≻0 such that DQDe=e, if and only if there exists d≻0 such that Qd≻0. Thus via this duality the Matrix Scaling problem is a natural dual to the feasibility problem in SDP. This duality also implies that in Blum et al. [Bull. AMS 21 (1989) 1] real number model of computation the decision problem of testing the solvability of Matrix Scaling is both in NP and Co-NP. Although the above complexities can be deduced from our path-following algorithm for general self-concordant Homogeneous Programming and for Matrix Scaling obtained in [Scaling dualities and self-concordant homogeneous programming in finite dimensional spaces, Technical Report LCSR-TR-359, Department of Computer Science, Rutgers University, New Brunswick, NJ, 1999], for the problems considered here the present analysis is quite elementary, short, and complete. This simplicity is mainly due to a new inequality derived in this paper that relates the norm of scaled quantities at two successive Newton iterations and implies a quadratic rate of convergence. The present algorithm is not only a simple path-following algorithm for testing the solvability of feasibility problem in SDP, but is also capable of testing solvability of the Matrix Scaling problem. When n=0, the algorithm reduces to the diagonal Matrix Scaling/Linear Programming algorithm of Khachiyan and Kalantari [SIAM J. Optim. 4 (1992) 668]. As in the case of LP the algorithm of this paper can be used to solve the general SDP problem