The matricial relaxation of a linear matrix inequality

Lade...
Vorschaubild
Dateien
284 Helton.pdf
284 Helton.pdfGröße: 929.66 KBDownloads: 254
Datum
2011
Autor:innen
Helton, J. William
McCullough, Scott
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
EU-Projektnummer
DFG-Projektnummer
Projekt
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Working Paper/Technical Report
Publikationsstatus
unikn.publication.listelement.citation.prefix.version.undefined
Zusammenfassung

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 LMI
domination. Hence such problems can be NP-hard. This paper describes a natural relaxation
of an LMI, based on substituting matrices for the variables xj . With this relaxation, the
domination questions (Q1) and (Q2) have elegant answers, indeed reduce to constructible
semide nite programs. As an example, to test the strength of this relaxation we specialize it
to the matrix cube problem and obtain essentially the relaxation given in [B-TN02]. Thus our
relaxation could be viewed as generalizing it.
Assume there is an X such that L1(X) and L2(X) are both positive de nite, and suppose
the positivity domain of L1 is bounded. For our \matrix variable" relaxation a positive answer
to (Q1) is equivalent to the existence of matrices Vj such that
(A1) L2(x) = V
1 L1(x)V1 + + V
L1(x)V :
As for (Q2) we show that L1 and L2 are mutually dominant if and only if, up to certain
redundancies described in the paper, L1 and L2 are unitarily equivalent. Algebraic certi cates
for positivity, such as (A1) for linear polynomials, are typically called Positivstellens atze. The
paper goes on to derive a Putinar-type Positivstellensatz for polynomials with a cleaner and
more powerful conclusion under the stronger hypothesis of positivity on an underlying bounded
domain of the form fX j L(X) 0g:
An observation at the core of the paper is that the relaxed LMI domination problem is
equivalent to a classical problem. Namely, the problem of determining if a linear map from
a subspace of matrices to a matrix algebra is \completely positive". Complete positivity is
one 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 completely
positive maps are not so far from representations and generally are more tractable than their
merely positive counterparts, the theory of completely positive maps provides perspective on
the di culties in solving LMI domination problems.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
510 Mathematik
Schlagwörter
linear matrix inequality (LMI), completely positive, semide nite programming, Positivstellensatz, Gleichstellensatz, archimedean quadratic module, real algebraic geometry, free positivity
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690HELTON, J. William, Igor KLEP, Scott MCCULLOUGH, 2011. The matricial relaxation of a linear matrix inequality
BibTex
@techreport{Helton2011matri-15281,
  year={2011},
  series={Konstanzer Schriften in Mathematik},
  title={The matricial relaxation of a linear matrix inequality},
  number={284},
  author={Helton, J. William and Klep, Igor and McCullough, Scott}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/15281">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>McCullough, Scott</dc:creator>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/15281/2/284%20Helton.pdf"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-09-02T07:26:43Z</dc:date>
    <dcterms:issued>2011</dcterms:issued>
    <dc:contributor>Klep, Igor</dc:contributor>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:abstract xml:lang="eng">Given linear matrix inequalities (LMIs) L1 and L2 it is natural to ask:&lt;br /&gt;(Q1) when does one dominate the other, that is, does L1(X)   0 imply L2(X)   0?&lt;br /&gt;(Q2) when are they mutually dominant, that is, when do they have the same solution set?&lt;br /&gt;The matrix cube problem of Ben-Tal and Nemirovski [B-TN02] is an example of LMI&lt;br /&gt;domination. Hence such problems can be NP-hard. This paper describes a natural relaxation&lt;br /&gt;of an LMI, based on substituting matrices for the variables xj . With this relaxation, the&lt;br /&gt;domination questions (Q1) and (Q2) have elegant answers, indeed reduce to constructible&lt;br /&gt;semide nite programs. As an example, to test the strength of this relaxation we specialize it&lt;br /&gt;to the matrix cube problem and obtain essentially the relaxation given in [B-TN02]. Thus our&lt;br /&gt;relaxation could be viewed as generalizing it.&lt;br /&gt;Assume there is an X such that L1(X) and L2(X) are both positive de nite, and suppose&lt;br /&gt;the positivity domain of L1 is bounded. For our \matrix variable" relaxation a positive answer&lt;br /&gt;to (Q1) is equivalent to the existence of matrices Vj such that&lt;br /&gt;(A1) L2(x) = V&lt;br /&gt;1 L1(x)V1 +       + V&lt;br /&gt;L1(x)V :&lt;br /&gt;As for (Q2) we show that L1 and L2 are mutually dominant if and only if, up to certain&lt;br /&gt;redundancies described in the paper, L1 and L2 are unitarily equivalent. Algebraic certi cates&lt;br /&gt;for positivity, such as (A1) for linear polynomials, are typically called Positivstellens atze. The&lt;br /&gt;paper goes on to derive a Putinar-type Positivstellensatz for polynomials with a cleaner and&lt;br /&gt;more powerful conclusion under the stronger hypothesis of positivity on an underlying bounded&lt;br /&gt;domain of the form fX j L(X)   0g:&lt;br /&gt;An observation at the core of the paper is that the relaxed LMI domination problem is&lt;br /&gt;equivalent to a classical problem. Namely, the problem of determining if a linear map   from&lt;br /&gt;a subspace of matrices to a matrix algebra is \completely positive". Complete positivity is&lt;br /&gt;one of the main techniques of modern operator theory and the theory of operator algebras.&lt;br /&gt;On one hand it provides tools for studying LMIs and on the other hand, since completely&lt;br /&gt;positive maps are not so far from representations and generally are more tractable than their&lt;br /&gt;merely positive counterparts, the theory of completely positive maps provides perspective on&lt;br /&gt;the di culties in solving LMI domination problems.</dcterms:abstract>
    <dc:rights>terms-of-use</dc:rights>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/15281/2/284%20Helton.pdf"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>McCullough, Scott</dc:contributor>
    <dc:creator>Helton, J. William</dc:creator>
    <dcterms:title>The matricial relaxation of a linear matrix inequality</dcterms:title>
    <dc:language>eng</dc:language>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-09-02T07:26:43Z</dcterms:available>
    <dc:contributor>Helton, J. William</dc:contributor>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/15281"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:creator>Klep, Igor</dc:creator>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet