The matricial relaxation of a linear matrix inequality

Abstract

Given linear matrix inequalities (LMIs) L1 and L2 it is natural to ask:(Q1) when does one dominate the other, that is, does L1(X) 0 imply L2(X) 0?(Q2) when are they mutually dominant, that is, when do they have the same solution set?The matrix cube problem of Ben-Tal and Nemirovski [B-TN02] is an example of LMIdomination. Hence such problems can be NP-hard. This paper describes a natural relaxationof an LMI, based on substituting matrices for the variables xj . With this relaxation, thedomination questions (Q1) and (Q2) have elegant answers, indeed reduce to constructiblesemide nite programs. As an example, to test the strength of this relaxation we specialize itto the matrix cube problem and obtain essentially the relaxation given in [B-TN02]. Thus ourrelaxation could be viewed as generalizing it.Assume there is an X such that L1(X) and L2(X) are both positive de nite, and supposethe positivity domain of L1 is bounded. For our \matrix variable" relaxation a positive answerto (Q1) is equivalent to the existence of matrices Vj such that(A1) L2(x) = V1 L1(x)V1 + + VL1(x)V :As for (Q2) we show that L1 and L2 are mutually dominant if and only if, up to certainredundancies described in the paper, L1 and L2 are unitarily equivalent. Algebraic certi catesfor positivity, such as (A1) for linear polynomials, are typically called Positivstellens atze. Thepaper goes on to derive a Putinar-type Positivstellensatz for polynomials with a cleaner andmore powerful conclusion under the stronger hypothesis of positivity on an underlying boundeddomain of the form fX j L(X) 0g:An observation at the core of the paper is that the relaxed LMI domination problem isequivalent to a classical problem. Namely, the problem of determining if a linear map froma subspace of matrices to a matrix algebra is \completely positive". Complete positivity isone of the main techniques of modern operator theory and the theory of operator algebras.On one hand it provides tools for studying LMIs and on the other hand, since completelypositive maps are not so far from representations and generally are more tractable than theirmerely positive counterparts, the theory of completely positive maps provides perspective onthe di culties in solving LMI domination problems.