Exact algorithms for linear matrix inequalities

Autor: Mohab Safey El Din, Simone Naldi, Didier Henrion
Přispěvatelé: Czech Technical University in Prague (CTU), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Polynomial Systems (PolSys), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-11-BS03-0011,GEOLMI,Geométrie et algèbre des inégalités matricielles linéaires avec applications en commande(2011), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées
Jazyk: angličtina
Rok vydání: 2016
Předmět:
Computer Science - Symbolic Computation
FOS: Computer and information sciences
Semialgebraic set
MathematicsofComputing_NUMERICALANALYSIS
Mathematics::Optimization and Control
010103 numerical & computational mathematics
Positive-definite matrix
Symbolic Computation (cs.SC)
01 natural sciences
Theoretical Computer Science
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
polynomial optimization
FOS: Mathematics
Symmetric matrix
0101 mathematics
Algebraic number
Mathematics - Optimization and Control
linear matrix inequalities
Pencil (mathematics)
Mathematics
Semidefinite programming
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
010102 general mathematics
semidefinite programming
symbolic computation
Exact algorithm
Optimization and Control (math.OC)
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Algorithm
Software
Interior point method
computer algebra al-gorithms
Zdroj: SIAM Journal on Optimization
SIAM Journal on Optimization, 2016, 26 (4), pp.2512-2539. ⟨10.1137/15M1036543⟩
SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2016, 26 (4), pp.2512-2539. ⟨10.1137/15M1036543⟩
ISSN: 1052-6234
DOI: 10.1137/15M1036543⟩
Popis: Let $A(x)=A\_0+x\_1A\_1+...+x\_nA\_n$ be a linear matrix, or pencil, generated by given symmetric matrices $A\_0,A\_1,...,A\_n$ of size $m$ with rational entries. The set of real vectors x such that the pencil is positive semidefinite is a convex semi-algebraic set called spectrahedron, described by a linear matrix inequality (LMI). We design an exact algorithm that, up to genericity assumptions on the input matrices, computes an exact algebraic representation of at least one point in the spectrahedron, or decides that it is empty. The algorithm does not assume the existence of an interior point, and the computed point minimizes the rank of the pencil on the spectrahedron. The degree $d$ of the algebraic representation of the point coincides experimentally with the algebraic degree of a generic semidefinite program associated to the pencil. We provide explicit bounds for the complexity of our algorithm, proving that the maximum number of arithmetic operations that are performed is essentially quadratic in a multilinear B\'ezout bound of $d$. When $m$ (resp. $n$) is fixed, such a bound, and hence the complexity, is polynomial in $n$ (resp. $m$). We conclude by providing results of experiments showing practical improvements with respect to state-of-the-art computer algebra algorithms.
Comment: SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2016
Databáze: OpenAIRE
Externí odkaz: