DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization
From MaRDI portal
Publication:5382573
DOI10.1137/18M118935XzbMath1465.90061arXiv1706.02586OpenAlexW2964239200WikidataQ90328049 ScholiaQ90328049MaRDI QIDQ5382573
Amir Ali Ahmadi, Anirudha Majumdar
Publication date: 18 June 2019
Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.02586
linear programmingsemidefinite programmingsecond-order cone programmingpolynomial optimizationnonnegative polynomialssum of squares optimization
Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Convex programming (90C25) Automated systems (robots, etc.) in control theory (93C85) Polynomials in general fields (irreducibility, etc.) (12E05) Semialgebraic sets and related spaces (14P10)
Related Items (57)
Signomial and polynomial optimization via relative entropy and partial dualization ⋮ Some applications of polynomial optimization in operations research and real-time decision making ⋮ Maximum feasible subsystems of distance geometry constraints ⋮ Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints ⋮ Second-order cone programming relaxations for a class of multiobjective convex polynomial problems ⋮ Hyperbolic Relaxation of $k$-Locally Positive Semidefinite Matrices ⋮ Nonnegative Polynomials and Circuit Polynomials ⋮ The \(\mathrm{PPT}^2\) conjecture holds for all Choi-type maps ⋮ SONC optimization and exact nonnegativity certificates via second-order cone programming ⋮ 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 ⋮ Distance geometry and data science ⋮ Rejoinder on: ``Distance geometry and data science ⋮ 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 ⋮ 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 ⋮ On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones ⋮ 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 ⋮ A novel moving orthonormal coordinate-based approach for region of attraction analysis of limit cycles ⋮ Region of attraction analysis of nonlinear stochastic systems using polynomial chaos expansion ⋮ Bounding extrema over global attractors using polynomial optimisation ⋮ Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming ⋮ A note on convex relaxations for the inverse eigenvalue problem ⋮ On sums of squares of \(K\)-nomials ⋮ Unnamed Item ⋮ A Lagrange Multiplier Expression Method for Bilevel Polynomial Optimization ⋮ DC decomposition of nonconvex polynomials with algebraic techniques ⋮ Real zeros of SONC polynomials ⋮ Safe nonlinear control design for input constrained polynomial systems using sum-of-squares programming ⋮ 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 ⋮ Mathematical programming formulations for the alternating current optimal power flow problem ⋮ Mathematical programming formulations for the alternating current optimal power flow problem ⋮ Finding Extremal Periodic Orbits with Polynomial Optimization, with Application to a Nine-Mode Model of Shear Flow ⋮ 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 ⋮ Limitations on the Expressive Power of Convex Cones without Long Chains of Faces ⋮ Hybrid \(L_\infty \times \ell_\infty \)-performance analysis and control of linear time-varying impulsive and switched positive systems ⋮ Bounding Extreme Events in Nonlinear Dynamics Using Convex Optimization ⋮ 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 ⋮ Approximations of Countably Infinite Linear Programs over Bounded Measure Spaces ⋮ A unified framework of SAGE and SONC polynomials and its duality theory ⋮ Passivity and passivity indices of nonlinear systems under operational limitations using approximations ⋮ On Polyhedral Approximations of the Positive Semidefinite Cone ⋮ Sparse PSD approximation of the PSD cone
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some applications of polynomial optimization in operations research and real-time decision making
- CVXGEN: a code generator for embedded convex optimization
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Semidefinite programming for min-max problems and games
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- On the complexity of Putinar's Positivstellensatz
- Symmetry in semidefinite programs
- Forms derived from the arithmetic-geometric inequality
- Even symmetric sextics
- Applications of second-order cone programming
- Second-order cone programming
- Semidefinite programming relaxations for semialgebraic problems
- Symmetry in Turán sums of squares polynomials from flag algebras
- Alternating current optimal power flow with generator selection
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- Cones of diagonally dominant matrices
- Symmetry groups, semidefinite programs, and sums of squares
- BARON: A general purpose global optimization software package
- Anneaux preordonnes
- A bounded degree SOS hierarchy for polynomial optimization
- Approximation of the joint spectral radius using sum of squares
- On factor width and symmetric \(H\)-matrices
- Minimizing polynomials via sum of squares over the gradient ideal
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- Global Optimization with Polynomials and the Problem of Moments
- Lectures on Modern Convex Optimization
- Approximation of the Stability Number of a Graph via Copositive Programming
- Copositive Programming
- Projection Methods in Conic Optimization
- Diagonally Dominant Programming in Distance Geometry
- Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint
- Regularization Methods for SDP Relaxations in Large-Scale Polynomial Optimization
- Blenders
- An Introduction to Polynomial and Semi-Algebraic Optimization
- Sum of squares basis pursuit with linear and second order cone programming
- A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
- Theta Bodies for Polynomial Ideals
- Verifying Nonlinear Real Formulas Via Sums of Squares
- New upper bounds for kissing numbers from semidefinite programming
- On the Relation Between Option and Stock Prices: A Convex Optimization Approach
- Approximate Volume and Integration for Basic Semialgebraic Sets
- Some NP-complete problems in quadratic and nonlinear programming
- Class of global minimum bounds of polynomial functions
- On the Shannon capacity of a graph
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Semidefinite Programming
- Semidefinite Optimization and Convex Algebraic Geometry
- Robust Region-of-Attraction Estimation
- On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Fast ADMM for Sum-of-Squares Programs Using Partial Orthogonality
- An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Optimal Inequalities in Probability Theory: A Convex Optimization Approach
- A Hierarchy of Near-Optimal Policies for Multistage Adaptive Optimization
- Euclidean Distance Geometry and Applications
- A Semidefinite Programming Approach to Optimal-Moment Bounds for Convex Classes of Distributions
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
This page was built for publication: DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization
