Exact algorithms for linear matrix inequalities

DOI10.1137/15M1036543zbMATH Open1356.90102arXiv1508.03715OpenAlexW2962893120MaRDI QIDQ2834563FDOQ2834563

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)

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.

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

Recommendations

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

zbMATH Keywords

polynomial optimizationsemidefinite programminglinear matrix inequalitiessymbolic computationcomputer algebra algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (26)

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

Uses Software

• FGb
• Kronecker
• RAGlib
• ISOLATE

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)