Approximate gcds of polynomials and sparse SOS relaxations

DOI10.1016/J.TCS.2008.09.003zbMath1156.90424OpenAlexW2142099171MaRDI QIDQ2378493

Lihong Zhi, Bin Li, Jia-Wang Nie

Publication date: 8 January 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.003

zbMATH Keywords

sums of squaressemidefinite programminggreatest common divisorglobal minimization

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semidefinite programming (90C22) Computational aspects and applications of commutative rings (13P99) Semialgebraic sets and related spaces (14P10)

Related Items (8)

Computation of the nearest non-prime polynomial matrix: structured low-rank approximation approach ⋮ An ODE-based method for computing the approximate greatest common divisor of polynomials ⋮ A heuristic verification of the degree of the approximate GCD of two univariate polynomials ⋮ Overdetermined Weierstrass iteration and the nearest consistent system ⋮ Approximate square-free part and decomposition ⋮ A complete algorithm to find exact minimal polynomial by approximations ⋮ Exact Certification in Global Polynomial Optimization Via Rationalizing Sums-Of-Squares ⋮ Variable projection methods for approximate (greatest) common divisor computations

Uses Software

• Sostools
• SeDuMi
• GloptiPoly
• YALMIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hybrid method for computing the nearest singular polynomials
• Extremal psd forms with few terms
• Modified \(r\)-algorithm to find the global minimum of polynomial functions
• On approximate GCDs of univariate polynomials
• Nearest singular polynomials
• Sparsity in sums of squares of polynomials
• Global minimization of rational functions and the nearest GCDs
• Global optimization of rational functions: a semidefinite programming approach
• Global Optimization with Polynomials and the Problem of Moments
• Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
• Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
• Class of global minimum bounds of polynomial functions
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Detecting Global Optimality and Extracting Solutions in GloptiPoly
• Semidefinite Programming
• Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
• Handbook of semidefinite programming. Theory, algorithms, and applications

This page was built for publication: Approximate gcds of polynomials and sparse SOS relaxations