The algebraic degree of semidefinite programming

DOI10.1007/s10107-008-0253-6zbMath1184.90119arXivmath/0611562OpenAlexW2039539620MaRDI QIDQ847857

Kristian Ranestad, Bernd Sturmfels, Jia-Wang Nie

Publication date: 19 February 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

Chern classEuler-Poincaré characteristicGenericityDeterminantal varietyDual varietyMultidegree

Mathematics Subject Classification ID

Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Optimality conditions and duality in mathematical programming (90C46) Computational aspects of higher-dimensional varieties (14Q15) Enumerative problems (combinatorial problems) in algebraic geometry (14N10) Projective techniques in algebraic geometry (14N05)

Related Items (49)

Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets ⋮ Algebraic boundaries of convex semi-algebraic sets ⋮ Extreme points of Gram spectrahedra of binary forms ⋮ Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry ⋮ Certifying the global optimality of quartic minimization over the sphere ⋮ Symbolic computation in hyperbolic programming ⋮ A Lower Bound on the Positive Semidefinite Rank of Convex Bodies ⋮ Solving generic nonarchimedean semidefinite programs using stochastic game algorithms ⋮ Solving rank-constrained semidefinite programs in exact arithmetic ⋮ The Maximum Likelihood Degree of Sparse Polynomial Systems ⋮ The geometry of SDP-exactness in quadratic optimization ⋮ Real root finding for determinants of linear matrices ⋮ Nonlinear algebra and applications ⋮ A characterization of the algebraic degree in semidefinite programming ⋮ Linear optimization on varieties and Chern-Mather classes ⋮ Quartic curves and their bitangents ⋮ Equations and multidegrees for inverse symmetric matrix pairs ⋮ Discriminants and nonnegative polynomials ⋮ Defect of Euclidean distance degree ⋮ Singularities and genus of the \(k\)-ellipse ⋮ Wasserstein distance to independence models ⋮ Exact algorithms for semidefinite programs with degenerate feasible set ⋮ A Morse theoretic approach to non-isolated singularities and applications to optimization ⋮ A guide to conic optimisation and its applications ⋮ Gram spectrahedra ⋮ Bounding averages rigorously using semidefinite programming: mean moments of the Lorenz system ⋮ A nearly optimal algorithm to decompose binary forms ⋮ A note on the unsolvability of the weighted region shortest path problem ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ The Maslov cycle as a Legendre singularity and projection of a wavefront set ⋮ An SOS counterexample to an inequality of symmetric functions ⋮ Validating numerical semidefinite programming solvers for polynomial invariants ⋮ On exact Reznick, Hilbert-Artin and Putinar's representations ⋮ Algebraic Degree in Semidefinite and Polynomial Optimization ⋮ Intrinsic volumes of symmetric cones and applications in convex programming ⋮ Sums of squares over totally real fields are rational sums of squares ⋮ Parametric analysis of semidefinite optimization ⋮ Bad projections of the PSD cone ⋮ Characterizing the universal rigidity of generic frameworks ⋮ Positive semidefinite rank ⋮ ORBITOPES ⋮ Limitations on the Expressive Power of Convex Cones without Long Chains of Faces ⋮ Exact Algorithms for Linear Matrix Inequalities ⋮ Exact Semidefinite Programming Bounds for Packing Problems ⋮ Characterizing Bad Semidefinite Programs: Normal Forms and Short Proofs ⋮ A note on the nonexistence of sum of squares certificates for the Bessis–Moussa–Villani conjecture ⋮ The leading coefficient of Lascoux polynomials ⋮ Generic Spectrahedral Shadows ⋮ On Computing the Nonlinearity Interval in Parametric Semidefinite Optimization

Uses Software

• Macaulay2
• SeDuMi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On symmetric and skew-symmetric determinantal varieties
• Triangulations. Structures for algorithms and applications
• The algebraic degree of geometric optimization problems
• Self-adjoint determinantal representations of real plane curves
• Complementarity and nondegeneracy in semidefinite programming
• Schubert varieties and degeneracy loci
• Projective duality and homogeneous spaces
• Horn's problem, Vinnikov curves, and the hive cone
• Solving the likelihood equations
• Linear matrix inequality representation of sets
• A general formula for the algebraic degree in semidefinite programming
• Images of homogeneous vector bundles and varieties of complexes
• Enumerative geometry of degeneracy loci
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Combinatorial Commutative Algebra
• The Lax conjecture is true
• Semidefinite Programming
• The maximum likelihood degree
• Universality of Nash Equilibria
• Handbook of semidefinite programming. Theory, algorithms, and applications

This page was built for publication: The algebraic degree of semidefinite programming