Sum-of-squares optimization without semidefinite programming
From MaRDI portal
Publication:4629344
DOI10.1137/17M1160124zbMATH Open1412.90114arXiv1712.01792WikidataQ128181100 ScholiaQ128181100MaRDI QIDQ4629344FDOQ4629344
Authors: Dávid Papp, Sercan Yıldız 
Publication date: 22 March 2019
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: We propose a homogeneous primal-dual interior-point method to solve sum-of-squares optimization problems by combining non-symmetric conic optimization techniques and polynomial interpolation. The approach optimizes directly over the sum-of-squares cone and its dual, circumventing the semidefinite programming (SDP) reformulation which requires a large number of auxiliary variables. As a result, it has substantially lower theoretical time and space complexity than the conventional SDP-based approach. Although our approach avoids the semidefinite programming reformulation, an optimal solution to the semidefinite program can be recovered with little additional effort. Computational results confirm that for problems involving high-degree polynomials, the proposed method is several orders of magnitude faster than semidefinite programming.
Full work available at URL: https://arxiv.org/abs/1712.01792
Recommendations
- Univariate polynomial optimization with sum-of-squares interpolants
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Sum of squares basis pursuit with linear and second order cone programming
- Sum of squares generalizations for conic sets
- A Sum-of-Squares Approach to Fixed-Order H∞-Synthesis
polynomial optimizationsemidefinite programmingpolynomial interpolationsum-of-squares optimizationnonsymmetric conic optimization
Convex programming (90C25) Interior-point methods (90C51) Semidefinite programming (90C22) Numerical interpolation (65D05)
Cites Work
- CSDP, A C library for semidefinite programming
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- \texttt{Padua2DM}: Fast interpolation and cubature at the Padua points in \texttt{MATLAB/Octave}
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- Title not available (Why is that?)
- Global optimization with polynomials and the problem of moments
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- GloptiPoly
- Representing polynomials by positive linear functions on compact convex polyhedra
- The \(K\)-moment problem for compact semi-algebraic sets
- Symmetry groups, semidefinite programs, and sums of squares
- A mathematical view of interior-point methods in convex optimization
- Sums of squares, moment matrices and optimization over polynomials
- Title not available (Why is that?)
- Semidefinite Optimization and Convex Algebraic Geometry
- Optimal Designs for Rational Function Regression
- Optimal Inequalities in Probability Theory: A Convex Optimization Approach
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Bivariate Lagrange interpolation at the Padua points: the generating curve approach
- The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
- Title not available (Why is that?)
- Title not available (Why is that?)
- Towards non-symmetric conic optimization
- Positive polynomials and sums of squares
- Optimization of Polynomial Functions
- Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
- Computing approximate Fekete points by QR factorizations of Vandermonde matrices
- Bivariate polynomial interpolation on the square at new nodal sets
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- An algorithm for computing Fekete points in the triangle
- An Introduction to Polynomial and Semi-Algebraic Optimization
- Tensor product Gauss-Lobatto points are Fekete points for the cube
- New upper bounds for kissing numbers from semidefinite programming
- Title not available (Why is that?)
- Computing sum of squares decompositions with rational coefficients
- Optimization Problems over Positive Pseudopolynomial Matrices
- Estimating arrival rate of nonhomogeneous Poisson processes with semidefinite programming
- Experimental study of energy-minimizing point configurations on spheres
- Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
- GpoSolver: a Matlab/C++ toolbox for global polynomial optimization
- The complexity of optimizing over a simplex, hypercube or sphere: a short survey
- On the complexity of approximating extremal determinants in matrices
- Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables
- Convex optimization problems involving finite autocorrelation sequences
- Parallel and superfast algorithms for Hankel systems of equations
- Title not available (Why is that?)
- Semi-Infinite Programming using High-Degree Polynomial Interpolants and Semidefinite Programming
- Title not available (Why is that?)
- Positive trigonometric polynomials and signal processing applications
- Sum-of-Squares Optimization without Semidefinite Programming
- Semidefinite approximations of the polynomial abscissa
Cited In (18)
- Approximations of Countably Infinite Linear Programs over Bounded Measure Spaces
- Alfonso: Matlab Package for Nonsymmetric Conic Optimization
- Time-Varying Semidefinite Programs
- Global minimization of polynomial integral functionals
- Bounding Extreme Events in Nonlinear Dynamics Using Convex Optimization
- Exploiting constant trace property in large-scale polynomial optimization
- Rational dual certificates for weighted sums-of-squares polynomials with boundable bit size
- A faster interior-point method for sum-of-squares optimization
- Finding Extremal Periodic Orbits with Polynomial Optimization, with Application to a Nine-Mode Model of Shear Flow
- Performance enhancements for a generic conic interior point algorithm
- Solving Natural Conic Formulations with Hypatia.jl
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming
- Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets
- Sum of squares generalizations for conic sets
- (Global) optimization: historical notes and recent developments
- A Convex Relaxation to Compute the Nearest Structured Rank Deficient Matrix
- Sum-of-Squares Optimization without Semidefinite Programming
Uses Software
This page was built for publication: Sum-of-squares optimization without semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629344)
