DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
From MaRDI portal
(Redirected from Publication:5382573)
Abstract: In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear programming and second-order cone programming-based alternatives to sum of squares optimization that allow one to trade off computation time with solution quality. These are optimization problems over certain subsets of sum of squares polynomials (or equivalently subsets of positive semidefinite matrices), which can be of interest in general applications of semidefinite programming where scalability is a limitation. We show that some basic theorems from SOS optimization which rely on results from real algebraic geometry are still valid for DSOS and SDSOS optimization. Furthermore, we show with numerical experiments from diverse application areas---polynomial optimization, statistics and machine learning, derivative pricing, and control theory---that with reasonable tradeoffs in accuracy, we can handle problems at scales that are currently significantly beyond the reach of traditional sum of squares approaches. Finally, we provide a review of recent techniques that bridge the gap between our DSOS/SDSOS approach and the SOS approach at the expense of additional running time. The Supplementary Material of the paper introduces an accompanying MATLAB package for DSOS and SDSOS optimization.
Recommendations
Cites work
- A bounded degree SOS hierarchy for polynomial optimization
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- A Hierarchy of Near-Optimal Policies for Multistage Adaptive Optimization
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- A Semidefinite Programming Approach to Optimal-Moment Bounds for Convex Classes of Distributions
- Alternating current optimal power flow with generator selection
- An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems
- An introduction to polynomial and semi-algebraic optimization
- Anneaux preordonnes
- Applications of second-order cone programming
- Approximate volume and integration for basic semialgebraic sets
- Approximation of the joint spectral radius using sum of squares
- Approximation of the stability number of a graph via copositive programming
- BARON: A general purpose global optimization software package
- Blenders
- Class of global minimum bounds of polynomial functions
- Complexity of the positive semidefinite matrix completion problem with a rank constraint
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Cones of diagonally dominant matrices
- Copositive programming
- CVXGEN: a code generator for embedded convex optimization
- Diagonally dominant programming in distance geometry
- Euclidean distance geometry and applications
- Even symmetric sextics
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Fast ADMM for Sum-of-Squares Programs Using Partial Orthogonality
- Forms derived from the arithmetic-geometric inequality
- Global optimization with polynomials and the problem of moments
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- scientific article; zbMATH DE number 6617274 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 3435574 (Why is no real title available?)
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- scientific article; zbMATH DE number 3002670 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 1490041 (Why is no real title available?)
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Minimizing polynomials via sum of squares over the gradient ideal
- Moments, positive polynomials and their applications
- Multivariate convex regression with adaptive partitioning
- New upper bounds for kissing numbers from semidefinite programming
- Nonlinear systems.
- On factor width and symmetric \(H\)-matrices
- On the complexity of Putinar's Positivstellensatz
- On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity
- On the Relation Between Option and Stock Prices: A Convex Optimization Approach
- On the Shannon capacity of a graph
- Optimal Inequalities in Probability Theory: A Convex Optimization Approach
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Projection Methods in Conic Optimization
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- Robust Region-of-Attraction Estimation
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Second-order cone programming
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite Programming
- Semidefinite programming for min-max problems and games
- Semidefinite programming relaxations for semialgebraic problems
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- Some applications of polynomial optimization in operations research and real-time decision making
- Some NP-complete problems in quadratic and nonlinear programming
- Sum of squares basis pursuit with linear and second order cone programming
- Sums of squares, moment matrices and optimization over polynomials
- Symmetry groups, semidefinite programs, and sums of squares
- Symmetry in semidefinite programs
- Symmetry in Turán sums of squares polynomials from flag algebras
- Theta bodies for polynomial ideals
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Verifying Nonlinear Real Formulas Via Sums of Squares
Cited in
(87)- DC decomposition of nonconvex polynomials with algebraic techniques
- On sums of squares of \(K\)-nomials
- Real zeros of SONC polynomials
- A new bounded degree hierarchy with SOCP relaxations for global polynomial optimization and conic convex semi-algebraic programs
- Penalized semidefinite programming for quadratically-constrained quadratic optimization
- A survey on conic relaxations of optimal power flow problem
- Polyhedral approximations of the semidefinite cone and their application
- Analysis of optimization algorithms via sum-of-squares
- Hybrid \(L_\infty \times \ell_\infty \)-performance analysis and control of linear time-varying impulsive and switched positive systems
- Finding unstable periodic orbits: a hybrid approach with polynomial optimization
- Unconstrained minimization of block-circulant polynomials via semidefinite program in third-order tensor space
- Risk-averse autonomous systems: a brief history and recent developments from the perspective of optimal control
- Sparse PSD approximation of the PSD cone
- Maximum feasible subsystems of distance geometry constraints
- Second-order cone programming relaxations for a class of multiobjective convex polynomial problems
- The \(\mathrm{PPT}^2\) conjecture holds for all Choi-type maps
- Distance geometry and data science
- Rejoinder on: ``Distance geometry and data science
- Region of attraction analysis of nonlinear stochastic systems using polynomial chaos expansion
- A note on convex relaxations for the inverse eigenvalue problem
- On polyhedral and second-order cone decompositions of semidefinite optimization problems
- Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
- Stability analysis and output-feedback synthesis of hybrid systems affected by piecewise constant parameters via dynamic resetting scalings
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- A novel moving orthonormal coordinate-based approach for region of attraction analysis of limit cycles
- Some applications of polynomial optimization in operations research and real-time decision making
- Sum of squares basis pursuit with linear and second order cone programming
- Sum-of-squares optimization without semidefinite programming
- Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming
- Finding extremal periodic orbits with polynomial optimization, with application to a nine-mode model of shear flow
- Bounding extreme events in nonlinear dynamics using convex optimization
- Passivity and passivity indices of nonlinear systems under operational limitations using approximations
- On polyhedral approximations of the positive semidefinite cone
- scientific article; zbMATH DE number 7625166 (Why is no real title available?)
- Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
- Hyperbolic Relaxation of $k$-Locally Positive Semidefinite Matrices
- Nonnegative Polynomials and Circuit Polynomials
- On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity
- Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs
- Bounding extrema over global attractors using polynomial optimisation
- A Lagrange multiplier expression method for bilevel polynomial optimization
- Safe nonlinear control design for input constrained polynomial systems using sum-of-squares programming
- Limitations on the Expressive Power of Convex Cones without Long Chains of Faces
- Approximations of Countably Infinite Linear Programs over Bounded Measure Spaces
- A unified framework of SAGE and SONC polynomials and its duality theory
- Mathematical programming formulations for the alternating current optimal power flow problem
- Mathematical programming formulations for the alternating current optimal power flow problem
- Evaluating approximations of the semidefinite cone with trace normalized distance
- Higher‐order derivatives of generalized Lyapunov‐like functions for switched nonlinear systems
- A Sum of Squares Characterization of Perfect Graphs
- Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
- Approximation hierarchies for copositive cone over symmetric cone and their comparison
- A connected component labeling algorithm for implicitly defined domains
- An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials
- Tighter bounds on transient moments of stochastic chemical systems
- On semidefinite programming relaxations for a class of robust SOS-convex polynomial optimization problems
- Harmonic Hierarchies for Polynomial Optimization
- Robust second order cone conditions and duality for multiobjective problems under uncertainty data
- Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
- On difference-of-SOS and difference-of-convex-SOS decompositions for polynomials
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- The moment-SOS hierarchy: applications and related topics
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- Higher-order Newton methods with polynomial work per iteration
- Hierarchy relaxations for robust equilibrium constrained polynomial problems and applications to electric vehicle charging scheduling
- Regret optimal control for uncertain stochastic systems
- Convex hulls of monomial curves, and a sparse positivstellensatz
- Constructing piecewise quadratic Lyapunov functions with linear programming for continuous-time switched and conewise linear systems
- Sparse sub-Gaussian random projections for semidefinite programming relaxations
- Convergence rate for linear minimizer-estimators in the moment-sum-of-squares hierarchy
- A predictor-corrector algorithm for semidefinite programming that uses the factor width cone
- Instance-specific linear relaxations of semidefinite optimization problems
- Relative entropy methods in constrained polynomial and signomial optimization
- Cone-based abstract interpretation for nonlinear positive invariant synthesis
- The factor width rank of a matrix
- Polynomial optimization for nonlinear dynamics: theory, algorithms and applications. Abstracts from the workshop held July 28 -- August 2, 2024
- SPLD polynomial optimization and bounded degree SOS hierarchies
- Non-negative polynomials without hyperbolic certificates of non-negativity
- Convergent lifted Lasserre hierarchy of SDPs for minimizing expectation of piecewise polynomial loss over Wasserstein balls
- Spectral methods for polynomial optimization
- Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant
- Unifying view on sparse convex relaxations in polynomial optimization
- A hierarchy of eigencomputations for polynomial optimization on the sphere
- Verification of first-order methods for parametric quadratic optimization
- Sum-of-squares certificates for almost-sure reachability of stochastic polynomial systems
- Signomial and polynomial optimization via relative entropy and partial dualization
Describes a project that uses
Uses Software
This page was built for publication: DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5382573)
