Semidefinite programming and matrix scaling over the semidefinite cone

Let 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.5 Trace(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 Newton iterations produces d 0, d =1 such that φ(d) ε. If μ>0, in 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.