Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials

DOI10.1137/060668791MaRDI QIDQ3648519zbMATH OpenOpenAlexFDO

Authors Jiawang Nie, James Demmel

Publication date 27 November 2009

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityglobal minimumnonlinear differential equationsnonlinear least squaresnumerical experimentspolynomial systempolynomialssensor network localizationsparsitysum of squares

Mathematics Subject Classification ID

Nonlinear boundary value problems for ordinary differential equations (34B15) Numerical computation of solutions to systems of equations (65H10) Numerical mathematical programming methods (65K05) Numerical solution of boundary value problems involving ordinary differential equations (65L10) Complexity and performance of numerical algorithms (65Y20) Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: This paper discusses how to find the global minimum of functions that are summations of small polynomials (``small means involving a small number of variables). Some sparse sum of squares (SOS) techniques are proposed. We compare their computational complexity and lower bounds with prior SOS relaxations. Under certain conditions, we also discuss how to extract the global minimizers from these sparse relaxations. The proposed methods are especially useful in solving sparse polynomial system and nonlinear least squares problems. Numerical experiments are presented, which show that the proposed methods significantly improve the computational performance of prior methods for solving these problems. Lastly, we present applications of this sparsity technique in solving polynomial systems derived from nonlinear differential equations and sensor network localization.

Recommendations

• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Sparsity in sums of squares of polynomials
• Exploiting sparsity in SDP relaxation of polynomial optimization problems
• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
• Sum of squares method for sensor network localization

Cited in

(25)

• Sparsity in sums of squares of polynomials
• Newton polytopes and relative entropy optimization
• A sublevel moment-SOS hierarchy for polynomial optimization
• Certifying the global optimality of quartic minimization over the sphere
• Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation
• Univariate parameterization for global optimization of mixed-integer polynomial problems
• Positive polynomials on fibre products
• Approximate gcds of polynomials and sparse SOS relaxations
• A dynamic inequality generation scheme for polynomial programming
• Sum-of-squares chordal decomposition of polynomial matrix inequalities
• Perturbed sums-of-squares theorem for polynomial optimization and its applications
• Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
• Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets
• An iterative scheme for valid polynomial inequality generation in binary polynomial programming
• A multigrid approach to SDP relaxations of sparse polynomial optimization problems
• scientific article; zbMATH DE number 7125122 (Why is no real title available?)
• A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
• Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\)
• Global minimization of polynomial integral functionals
• The moment-SOS hierarchy: applications and related topics
• A characterization for tightness of the sparse moment-SOS hierarchy
• Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces
• Comparing SOS and SDP relaxations of sensor network localization
• Sparse polynomial optimization with matrix constraints
• Positive polynomials on projective limits of real algebraic varieties

Describes a project that uses

Uses Software

• SeDuMi
• SNLSDP
• GloptiPoly
• YALMIP
• tn

This page was built for publication: Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3648519)