Exact Algorithms for Linear Matrix Inequalities
From MaRDI portal
Publication:2834563
DOI10.1137/15M1036543zbMath1356.90102arXiv1508.03715OpenAlexW2962893120MaRDI QIDQ2834563
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
linear matrix inequalitiessemidefinite programmingsymbolic computationpolynomial optimizationcomputer algebra algorithms
Symbolic computation and algebraic computation (68W30) Semidefinite programming (90C22) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)
Related Items (23)
Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients ⋮ Auxetic deformations and elliptic curves ⋮ Symbolic computation in hyperbolic programming ⋮ Real root finding for low rank linear matrices ⋮ Solving generic nonarchimedean semidefinite programs using stochastic game algorithms ⋮ Solving rank-constrained semidefinite programs in exact arithmetic ⋮ Convex computation of maximal Lyapunov exponents ⋮ Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization ⋮ On Sum of Squares Representation of Convex Forms and Generalized Cauchy--Schwarz Inequalities ⋮ Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials ⋮ Exact algorithms for semidefinite programs with degenerate feasible set ⋮ Gram spectrahedra ⋮ 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 ⋮ A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors ⋮ A Matrix Positivstellensatz with Lifting Polynomials ⋮ Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs ⋮ In SDP Relaxations, Inaccurate Solvers Do Robust Optimization ⋮ Exact Semidefinite Programming Bounds for Packing Problems ⋮ Solving SDP completely with an interior point oracle ⋮ On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of the generalized MinRank problem
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Handbook on semidefinite, conic and polynomial optimization
- Properness defects and projections and computation of at least one point in each connected component of a real algebraic set
- Sums of squares of polynomials with rational coefficients
- The algebraic degree of semidefinite programming
- On the complexity of Putinar's Positivstellensatz
- On the complexity of Schmüdgen's Positivstellensatz
- Real root finding for determinants of linear matrices
- Deformation techniques for sparse systems
- Solving systems of polynomial inequalities in subexponential time
- The \(K\)-moment problem for compact semi-algebraic sets
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Geometric algorithms and combinatorial optimization
- Solving zero-dimensional systems through the rational univariate representation
- An algorithm for sums of squares of real polynomials
- 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
- On the complexity of semidefinite programs
- Sparse FGLM algorithms
- Some geometric results in semidefinite programming
- On the geometry of polar varieties
- Global Optimization with Polynomials and the Problem of Moments
- Lectures on Modern Convex Optimization
- Real Root Finding for Rank Defects in Linear Hankel Matrices
- Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
- Computing rational solutions of linear matrix inequalities
- Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
- Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions
- A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
- Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets
- A general formula for the algebraic degree in semidefinite programming
- Linear Matrix Inequalities in System and Control Theory
- On the combinatorial and algebraic complexity of quantifier elimination
- Semidefinite Representation for Convex Hulls of Real Algebraic Curves
- Sharp estimates for triangular sets
- Semidefinite Programming
- Semidefinite Optimization and Convex Algebraic Geometry
- Stability and Stabilization of Linear Systems with Saturating Actuators
- An Exact Duality Theory for Semidefinite Programming Based on Sums of Squares
- Critical points and Gröbner bases
- Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions
- Exact Solutions in Structured Low-Rank Approximation
- Generic Spectrahedral Shadows
- Nonlinear Optimal Control via Occupation Measures and LMI-Relaxations
- FGb: A Library for Computing Gröbner Bases
- Algorithms in real algebraic geometry
- A Gröbner free alternative for polynomial system solving
- Polar varieties and efficient real elimination
- The Euclidean distance degree of an algebraic variety
This page was built for publication: Exact Algorithms for Linear Matrix Inequalities
