Sum-of-squares optimization without semidefinite programming
From MaRDI portal
Publication:4629344
DOI10.1137/17M1160124zbMATH Open1412.90114WikidataQ128181100 ScholiaQ128181100MaRDI QIDQ4629344FDOQ4629344
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.
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
Cites Work
- scientific article; zbMATH DE number 1682655 (Why is no real title available?)
- scientific article; zbMATH DE number 3950731 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 1534296 (Why is no real title available?)
- scientific article; zbMATH DE number 1862742 (Why is no real title available?)
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- A mathematical view of interior-point methods in convex optimization
- An algorithm for computing Fekete points in the triangle
- An introduction to polynomial and semi-algebraic optimization
- Approximation theory and approximation practice
- Bivariate Lagrange interpolation at the Padua points: the generating curve approach
- Bivariate polynomial interpolation on the square at new nodal sets
- CSDP, A C library for semidefinite programming
- Computing approximate Fekete points by QR factorizations of Vandermonde matrices
- Computing sum of squares decompositions with rational coefficients
- Convex optimization problems involving finite autocorrelation sequences
- Estimating arrival rate of nonhomogeneous Poisson processes with semidefinite programming
- Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
- Experimental study of energy-minimizing point configurations on spheres
- Global optimization with polynomials and the problem of moments
- GloptiPoly
- Gposolver: a Matlab/C++ toolbox for global polynomial optimization
- Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
- Lasserre hierarchy for large scale polynomial optimization in real and complex variables
- New upper bounds for kissing numbers from semidefinite programming
- On the complexity of approximating extremal determinants in matrices
- Optimal Inequalities in Probability Theory: A Convex Optimization Approach
- Optimal designs for rational function regression
- Optimization Problems over Positive Pseudopolynomial Matrices
- Optimization of Polynomial Functions
- Parallel and superfast algorithms for Hankel systems of equations
- Positive polynomials and sums of squares
- Positive trigonometric polynomials and signal processing applications
- Representing polynomials by positive linear functions on compact convex polyhedra
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Semi-infinite programming using high-degree polynomial interpolants and semidefinite programming
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite approximations of the polynomial abscissa
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- Sum-of-squares optimization without semidefinite programming
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Sums of squares, moment matrices and optimization over polynomials
- Symmetry groups, semidefinite programs, and sums of squares
- Tensor product Gauss-Lobatto points are Fekete points for the cube
- The \(K\)-moment problem for compact semi-algebraic sets
- The complexity of optimizing over a simplex, hypercube or sphere: a short survey
- The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
- Towards non-symmetric conic optimization
- 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}
Cited In (22)
- Approximations of Countably Infinite Linear Programs over Bounded Measure Spaces
- Alfonso: Matlab Package for Nonsymmetric Conic Optimization
- Time-Varying Semidefinite Programs
- Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets
- Global minimization of polynomial integral functionals
- An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems
- Exploiting constant trace property in large-scale polynomial optimization
- Rational dual certificates for weighted sums-of-squares polynomials with boundable bit size
- A convex relaxation to compute the nearest structured rank deficient matrix
- A faster interior-point method for sum-of-squares optimization
- Performance enhancements for a generic conic interior point algorithm
- Sum-of-squares optimization without semidefinite programming
- Solving Natural Conic Formulations with Hypatia.jl
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming
- Analysis of optimization algorithms via sum-of-squares
- Bounding extreme events in nonlinear dynamics using convex optimization
- Sum of squares generalizations for conic sets
- Sum of squares basis pursuit with linear and second order cone programming
- Finding extremal periodic orbits with polynomial optimization, with application to a nine-mode model of shear flow
- (Global) optimization: historical notes and recent developments
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)
