Sparsity in sums of squares of polynomials

DOI10.1007/S10107-004-0554-3zbMath1079.90092OpenAlexW1989190791MaRDI QIDQ1777218

Hayato Waki, Sunyoung Kim, Kojima, Masakazu

Publication date: 12 May 2005

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

Full work available at URL: https://doi.org/10.1007/s10107-004-0554-3

zbMATH Keywords

Polynomial optimization problem Semidefinite program Sparsity Sums of squares of polynomial

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Related Items (40)

Algebraic Perspectives on Signomial Optimization ⋮ Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets ⋮ Sum of squares method for sensor network localization ⋮ Approximate gcds of polynomials and sparse SOS relaxations ⋮ Set-membership errors-in-variables identification of MIMO linear systems ⋮ Duality of sum of nonnegative circuit polynomials and optimal SONC bounds ⋮ Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables ⋮ Solving polynomial least squares problems via semidefinite programming relaxations ⋮ On the complexity of Putinar's Positivstellensatz ⋮ Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity ⋮ Facial reduction algorithms for conic optimization problems ⋮ Reference dependent invariant sets: sum of squares based computation and applications in constrained control ⋮ An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones ⋮ A facial reduction algorithm for finding sparse SOS representations ⋮ One-shot set-membership identification of generalized Hammerstein-Wiener systems ⋮ Polynomial sum of squares in fluid dynamics: a review with a look ahead ⋮ A Geometrical Analysis on Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems ⋮ Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization ⋮ Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017 ⋮ TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity ⋮ LP Formulations for Polynomial Optimization Problems ⋮ An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming ⋮ SDP RELAXATIONS FOR QUADRATIC OPTIMIZATION PROBLEMS DERIVED FROM POLYNOMIAL OPTIMIZATION PROBLEMS ⋮ On minimizing difference of a SOS-convex polynomial and a support function over a SOS-concave matrix polynomial constraint ⋮ Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces ⋮ Global minimization of rational functions and the nearest GCDs ⋮ A polynomial optimization approach to constant rebalanced portfolio selection ⋮ Canonical dual least square method for solving general nonlinear systems of quadratic equations ⋮ Positive polynomials on projective limits of real algebraic varieties ⋮ Alternative SDP and SOCP approximations for polynomial optimization ⋮ A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones ⋮ Exploiting Sparsity in SDP Relaxation of Polynomial Optimization Problems ⋮ Perturbed sums-of-squares theorem for polynomial optimization and its applications ⋮ Recognizing underlying sparsity in optimization ⋮ Smaller SDP for SOS decomposition ⋮ Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP ⋮ A prolongation-projection algorithm for computing the finite real variety of an ideal ⋮ Newton polytopes and relative entropy optimization ⋮ A unified framework of SAGE and SONC polynomials and its duality theory ⋮ Univariate parameterization for global optimization of mixed-integer polynomial problems

Uses Software

Cites Work

This page was built for publication: Sparsity in sums of squares of polynomials