A facial reduction algorithm for finding sparse SOS representations

DOI10.1016/j.orl.2010.05.011zbMath1205.90219MaRDI QIDQ613325

Hayato Waki, Masakazu Muramatsu

Publication date: 20 December 2010

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2010.05.011

zbMATH Keywords

semidefinite programming; sum of squares; facial reduction algorithms; polynomial optimization problems

Mathematics Subject Classification ID

90C22: Semidefinite programming

Related Items

Facially Dual Complete (Nice) Cones and Lexicographic Tangents, Validating numerical semidefinite programming solvers for polynomial invariants, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, Facial reduction algorithms for conic optimization problems, Smaller SDP for SOS decomposition, Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone, Chordal graphs in triangular decomposition in top-down style, Douglas-Rachford splitting and ADMM for pathological convex optimization, Perturbed sums-of-squares theorem for polynomial optimization and its applications

Uses Software

• SparsePOP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Facial reduction algorithms for conic optimization problems
• Regularizing the abstract convex program
• Extremal psd forms with few terms
• An algorithm for sums of squares of real polynomials
• Semidefinite programming relaxations for semialgebraic problems
• Sparsity in sums of squares of polynomials
• Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
• Global Optimization with Polynomials and the Problem of Moments
• Strong Duality for Semidefinite Programming
• Pre- and Post-Processing Sum-of-Squares Programs in Practice
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity