Exact algorithms for linear matrix inequalities

DOI10.1137/15M1036543MaRDI QIDQ2834563zbMATH OpenOpenAlexFDO

Authors Simone Naldi, Didier Henrion, Mohab Safey El Din

Publication date 23 November 2016

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.03715

zbMATH Keywords

computer algebra algorithmslinear matrix inequalitiespolynomial optimizationsemidefinite programmingsymbolic computation

Mathematics Subject Classification ID

Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Symbolic computation and algebraic computation (68W30) Semidefinite programming (90C22)

Abstract: Let $A(x)=A_0+x_1{A}_1+\mathrm{...}+x_n{A}_n$ be a linear matrix, or pencil, generated by given symmetric matrices $A_0,A_1,\mathrm{...},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.

Recommendations

• Computing rational solutions of linear matrix inequalities
• Solving rank-constrained semidefinite programs in exact arithmetic
• Solving rank-constrained semidefinite programs in exact arithmetic

Cites work

• A general formula for the algebraic degree in semidefinite programming
• A Gröbner free alternative for polynomial system solving
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• Algorithms in real algebraic geometry
• An algorithm for sums of squares of real polynomials
• An exact duality theory for semidefinite programming based on sums of squares
• Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions
• Computing rational points in convex semialgebraic sets and sum of squares decompositions
• Computing rational solutions of linear matrix inequalities
• Critical points and Gröbner bases: the unmixed case
• Deformation techniques for sparse systems
• Description of the connected components of a semialgebraic set in single exponential time
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Exact solutions in structured low-rank approximation
• FGb: A Library for Computing Gröbner Bases
• Generic Spectrahedral Shadows
• Geometric algorithms and combinatorial optimization
• Global optimization with polynomials and the problem of moments
• Handbook on semidefinite, conic and polynomial optimization
• scientific article; zbMATH DE number 52497 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 3563286 (Why is no real title available?)
• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• scientific article; zbMATH DE number 637062 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 2151204 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Linear Matrix Inequalities in System and Control Theory
• Nonlinear Optimal Control via Occupation Measures and LMI-Relaxations
• On the combinatorial and algebraic complexity of quantifier elimination
• On the complexity of Putinar's Positivstellensatz
• On the complexity of Schmüdgen's Positivstellensatz
• On the complexity of semidefinite programs
• On the complexity of the generalized MinRank problem
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• On the geometry of polar varieties
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Polar varieties and efficient real elimination
• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
• Properness defects and projections and computation of at least one point in each connected component of a real algebraic set
• Real root finding for determinants of linear matrices
• Real root finding for rank defects in linear Hankel matrices
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite Programming
• Semidefinite Representation for Convex Hulls of Real Algebraic Curves
• Sharp estimates for triangular sets
• Solving systems of polynomial inequalities in subexponential time
• Solving zero-dimensional systems through the rational univariate representation
• Some geometric results in semidefinite programming
• Sparse FGLM algorithms
• Stability and stabilization of linear systems with saturating actuators
• Sufficient and necessary conditions for semidefinite representability of convex hulls and sets
• Sums of squares of polynomials with rational coefficients
• Sums of squares, moment matrices and optimization over polynomials
• Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
• The K-moment problem for compact semi-algebraic sets
• The algebraic degree of semidefinite programming
• The Euclidean distance degree of an algebraic variety

Cited in

(31)

• Auxetic deformations and elliptic curves
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
• Bounding averages rigorously using semidefinite programming: mean moments of the Lorenz system
• An SOS counterexample to an inequality of symmetric functions
• Convex computation of extremal invariant measures of nonlinear dynamical systems and Markov processes
• On exact Reznick, Hilbert-Artin and Putinar's representations
• Real root finding for low rank linear matrices
• Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
• Solving rank-constrained semidefinite programs in exact arithmetic
• Computing rational solutions of linear matrix inequalities
• Solving rank-constrained semidefinite programs in exact arithmetic
• On Sum of Squares Representation of Convex Forms and Generalized Cauchy--Schwarz Inequalities
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• Symbolic computation in hyperbolic programming
• Gram spectrahedra
• A complete semidefinite algorithm for detecting copositive matrices and tensors
• Exact Semidefinite Programming Bounds for Packing Problems
• Solving SDP completely with an interior point oracle
• A matrix Positivstellensatz with lifting polynomials
• In SDP Relaxations, Inaccurate Solvers Do Robust Optimization
• Numerical Sensitivity of Linear Matrix Inequalities Using Shift and Delta Operators
• On the central path of semidefinite optimization: degree and worst-case convergence rate
• Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
• Convex computation of maximal Lyapunov exponents
• Automated tight Lyapunov analysis for first-order methods
• Bounding escape rates and approximating quasi-stationary distributions of Brownian dynamics
• Euclidean distance degree in manifold optimization
• Certifying solutions of degenerate semidefinite programs
• Solving generic parametric linear matrix inequalities
• Solving parametric linear matrix inequalities

Describes a project that uses

Uses Software

• ISOLATE
• FGb
• Kronecker
• RAGlib

This page was built for publication: Exact algorithms for linear matrix inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2834563)