Sampling algebraic varieties for sum of squares programs

DOI10.1137/15M1052548MaRDI QIDQ4594913zbMATH OpenOpenAlexFDO

Authors Diego Cifuentes, Pablo A. Parrilo

Publication date 27 November 2017

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

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

zbMATH Keywords

algebraic varietynumerical algebraic geometrysamplingSDPsum of squares

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Semidefinite programming (90C22)

Abstract: We study sum of squares (SOS) relaxations to optimize polynomial functions over a set $Vcap{R}^n$, where $V$ is a complex algebraic variety. We propose a new methodology that, rather than relying on some algebraic description, represents $V$ with a generic set of complex samples. This approach depends only on the geometry of $V$, avoiding representation issues such as multiplicity and choice of generators. It also takes advantage of the coordinate ring structure to reduce the size of the corresponding semidefinite program (SDP). In addition, the input can be given as a straight-line program. Our methods are particularly appealing for varieties that are easy to sample from but for which the defining equations are complicated, such as $SO(n)$, Grassmannians or rank $k$ tensors. For arbitrary varieties we can obtain the required samples by using the tools of numerical algebraic geometry. In this way we connect the areas of SOS optimization and numerical algebraic geometry.

Recommendations

• Global optimization of polynomials restricted to a smooth variety using sums of squares
• Polynomial optimization problems and their relaxations
• Moments and sums of squares for polynomial optimization and related problems
• scientific article; zbMATH DE number 1984325
• Exploiting Algebraic Structure in Sum of Squares Programs

Cites work

• Algorithm 795
• Algorithm 875
• Approximating amoebas and coamoebas by sums of squares
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Discrete Transforms, Semidefinite Programming, and Sum-of-Squares Representations of Nonnegative Polynomials
• Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 1944720 (Why is no real title available?)
• scientific article; zbMATH DE number 1795734 (Why is no real title available?)
• scientific article; zbMATH DE number 2160654 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Maximization of the sum of the trace ratio on the Stiefel manifold. I: Theory
• Minimizing polynomials via sum of squares over the gradient ideal
• Numerically solving polynomial systems with Bertini
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• On the ideals and singularities of secant varieties of Segre varieties
• Polynomial interpolation in several variables: lattices, differences, and ideals
• Positivity and sums of squares: a guide to recent results
• Progress on polynomial identity testing
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite programming relaxations for semialgebraic problems
• Solving semidefinite-quadratic-linear programs using SDPT3
• Sums of squares and varieties of minimal degree
• Sums of squares, moment matrices and optimization over polynomials
• The K-moment problem for compact semi-algebraic sets
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Une majoration de la fonction de Hilbert et ses conséquences pour l'interpolation algébrique

Cited in

(14)

• A hybrid procedure for finding real points on a real algebraic set
• Learning algebraic varieties from samples
• On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems
• On the local stability of semidefinite relaxations
• Sampling algebraic sets in local intrinsic coordinates
• Certified Hermite matrices from approximate roots
• Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power
• Discovering the Characteristics of Mathematical Programs via Sampling
• A convex relaxation to compute the nearest structured rank deficient matrix
• Certifying Polynomial Nonnegativity via Hyperbolic Optimization
• Stability analysis of complementarity systems with neural network controllers
• Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
• Stable and optimal conductance recovery on networks
• Kernel-based learning of safety barriers

Describes a project that uses

Uses Software

• PHCpack
• DSDP5
• Bertini
• Macaulay2
• SDPT3

This page was built for publication: Sampling algebraic varieties for sum of squares programs

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