Solving rank-constrained semidefinite programs in exact arithmetic

DOI10.1016/j.jsc.2017.07.009zbMath1380.90212OpenAlexW2734887310MaRDI QIDQ2409017

Simone Naldi

Publication date: 10 October 2017

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2017.07.009

zbMATH Keywords

sums of squareslinear matrix inequalitiessemidefinite programmingcomputer algebrapolynomial optimizationexact algorithmsdeterminantal varietiesspectrahedrarank constraints

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Related Items (4)

Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints ⋮ Solving generic nonarchimedean semidefinite programs using stochastic game algorithms ⋮ Exact algorithms for semidefinite programs with degenerate feasible set ⋮ Exact Semidefinite Programming Bounds for Packing Problems

Uses Software

• FGb
• Maple
• LMIRank
• ISOLATE
• SPECTRA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Handbook on semidefinite, conic and polynomial optimization
• The algebraic degree of semidefinite programming
• A Newton-like method for solving rank constrained linear matrix inequalities
• Nearly optimal refinement of real roots of a univariate polynomial
• Real root finding for determinants of linear matrices
• Deformation techniques for sparse systems
• Geometric algorithms and combinatorial optimization
• Solving zero-dimensional systems through the rational univariate representation
• An algorithm for sums of squares of real polynomials
• On the complexity of semidefinite programs
• Semidefinite programming relaxations for semialgebraic problems
• Global Optimization with Polynomials and the Problem of Moments
• Lectures on Modern Convex Optimization
• Real Root Finding for Rank Defects in Linear Hankel Matrices
• Exact Algorithms for Linear Matrix Inequalities
• Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint
• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• Solving Rank-Constrained Semidefinite Programs in Exact Arithmetic
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• Linear Matrix Inequalities in System and Control Theory
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Gram spectrahedra
• Semidefinite Programming
• Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices
• FGb: A Library for Computing Gröbner Bases

This page was built for publication: Solving rank-constrained semidefinite programs in exact arithmetic