The matricial relaxation of a linear matrix inequality


Dateien zu dieser Ressource

Prüfsumme: MD5:b10fa2389a9a2e81cd1c57a7c3d0114d

HELTON, J. William, Igor KLEP, Scott MCCULLOUGH, 2011. The matricial relaxation of a linear matrix inequality

@techreport{Helton2011matri-15281, series={Konstanzer Schriften in Mathematik}, title={The matricial relaxation of a linear matrix inequality}, year={2011}, number={284}, author={Helton, J. William and Klep, Igor and McCullough, Scott} }

Given linear matrix inequalities (LMIs) L1 and L2 it is natural to ask:<br />(Q1) when does one dominate the other, that is, does L1(X) 0 imply L2(X) 0?<br />(Q2) when are they mutually dominant, that is, when do they have the same solution set?<br />The matrix cube problem of Ben-Tal and Nemirovski [B-TN02] is an example of LMI<br />domination. Hence such problems can be NP-hard. This paper describes a natural relaxation<br />of an LMI, based on substituting matrices for the variables xj . With this relaxation, the<br />domination questions (Q1) and (Q2) have elegant answers, indeed reduce to constructible<br />semide nite programs. As an example, to test the strength of this relaxation we specialize it<br />to the matrix cube problem and obtain essentially the relaxation given in [B-TN02]. Thus our<br />relaxation could be viewed as generalizing it.<br />Assume there is an X such that L1(X) and L2(X) are both positive de nite, and suppose<br />the positivity domain of L1 is bounded. For our \matrix variable" relaxation a positive answer<br />to (Q1) is equivalent to the existence of matrices Vj such that<br />(A1) L2(x) = V<br />1 L1(x)V1 + + V<br />L1(x)V :<br />As for (Q2) we show that L1 and L2 are mutually dominant if and only if, up to certain<br />redundancies described in the paper, L1 and L2 are unitarily equivalent. Algebraic certi cates<br />for positivity, such as (A1) for linear polynomials, are typically called Positivstellens atze. The<br />paper goes on to derive a Putinar-type Positivstellensatz for polynomials with a cleaner and<br />more powerful conclusion under the stronger hypothesis of positivity on an underlying bounded<br />domain of the form fX j L(X) 0g:<br />An observation at the core of the paper is that the relaxed LMI domination problem is<br />equivalent to a classical problem. Namely, the problem of determining if a linear map from<br />a subspace of matrices to a matrix algebra is \completely positive". Complete positivity is<br />one of the main techniques of modern operator theory and the theory of operator algebras.<br />On one hand it provides tools for studying LMIs and on the other hand, since completely<br />positive maps are not so far from representations and generally are more tractable than their<br />merely positive counterparts, the theory of completely positive maps provides perspective on<br />the di culties in solving LMI domination problems. The matricial relaxation of a linear matrix inequality Klep, Igor Helton, J. William 2011-09-02T07:26:43Z McCullough, Scott 2011-09-02T07:26:43Z Helton, J. William 2011 eng Klep, Igor McCullough, Scott deposit-license

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

284 Helton.pdf 121

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto