A convex polynomial that is not sos-convex

DOI10.1007/S10107-011-0457-ZzbMATH Open1254.90159arXiv0903.1287OpenAlexW3105811395MaRDI QIDQ715094FDOQ715094

Authors: Amir Ali Ahmadi, Pablo A. Parrilo 

Publication date: 15 October 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: A multivariate polynomial $p(x)=p(x_1,\mathrm{...},x_n)$ is sos-convex if its Hessian $H(x)$ can be factored as $H(x)=M^T(x)M(x)$ with a possibly nonsquare polynomial matrix $M(x)$. It is easy to see that sos-convexity is a sufficient condition for convexity of $p(x)$. Moreover, the problem of deciding sos-convexity of a polynomial can be cast as the feasibility of a semidefinite program, which can be solved efficiently. Motivated by this computational tractability, it has been recently speculated whether sos-convexity is also a necessary condition for convexity of polynomials. In this paper, we give a negative answer to this question by presenting an explicit example of a trivariate homogeneous polynomial of degree eight that is convex but not sos-convex. Interestingly, our example is found with software using sum of squares programming techniques and the duality theory of semidefinite optimization. As a byproduct of our numerical procedure, we obtain a simple method for searching over a restricted family of nonnegative polynomials that are not sums of squares.

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

Recommendations

• A complete characterization of the gap between convexity and sos-convexity
• Sufficient conditions for a real polynomial to be a sum of squares
• NP-hardness of deciding convexity of quartic polynomials and related problems
• Generalized SOS-convexity and strong duality with SDP dual programs in polynomial optimization
• Convexity in SemiAlgebraic Geometry and Polynomial Optimization

zbMATH Keywords

semidefinite programmingconvexitysum of squaressos-convexity

Mathematics Subject Classification ID

Convex programming (90C25) Semidefinite programming (90C22) Convex functions and convex programs in convex geometry (52A41)

Cites Work

• Title not available (Why is that?)
• Semidefinite Programming
• Convex Analysis
• Some NP-complete problems in quadratic and nonlinear programming
• Semidefinite programming relaxations for semialgebraic problems
• Symmetry groups, semidefinite programs, and sums of squares
• Uniform denominators in Hilbert's seventeenth problem
• Matrix sum-of-squares relaxations for robust semi-definite programs
• Class of global minimum bounds of polynomial functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing sum of squares decompositions with rational coefficients
• Semidefinite representation of convex sets
• Positive semidefinite biquadratic forms
• Convexity in SemiAlgebraic Geometry and Polynomial Optimization
• Representation of nonnegative convex polynomials
• Exploiting Algebraic Structure in Sum of Squares Programs
• Open questions in complexity theory for numerical optimization
• An Example of a Positive Polynomial which is not a Sum of Squares of Polynomials A Positive, but not Strongly Positive Functional
• ON THE DIFFICULTY OF DECIDING THE CONVEXITY OF POLYNOMIALS OVER SIMPLEXES

Cited In (33)

• Characterizing robust solution sets of convex programs under data uncertainty
• A hybrid approach for finding efficient solutions in vector optimization with SOS-convex polynomials
• A complete characterization of the gap between convexity and sos-convexity
• Finding efficient solutions in robust multiple objective optimization with SOS-convex polynomial data
• On solving a class of fractional semi-infinite polynomial programming problems
• Exact dual semi-definite programs for affinely adjustable robust SOS-convex polynomial optimization problems
• Finding efficient solutions for multicriteria optimization problems with SOS-convex polynomials
• Positive semi-definiteness and sum-of-squares property of fourth order four dimensional Hankel tensors
• A new class of alternative theorems for SOS-convex inequalities and robust optimization
• On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems
• Farkas' lemma: three decades of generalizations for mathematical optimization
• Dual semidefinite programs without duality gaps for a class of convex minimax programs
• Robust SOS-convex polynomial optimization problems: exact SDP relaxations
• Solving fractional multicriteria optimization problems with sum of squares convex polynomial data
• DC decomposition of nonconvex polynomials with algebraic techniques
• On minimizing difference of a SOS-convex polynomial and a support function over a SOS-concave matrix polynomial constraint
• Multi-objective convex polynomial optimization and semidefinite programming relaxations
• Semidefinite Representation of Convex Sets and Convex Hulls
• Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations
• An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials
• Characterizing a class of robust vector polynomial optimization via sum of squares conditions
• NP-hardness of deciding convexity of quartic polynomials and related problems
• Multi-objective optimization problems with SOS-convex polynomials over an LMI constraint
• Exact SDP relaxations for classes of nonlinear semidefinite programming problems
• On semidefinite programming relaxations for a class of robust SOS-convex polynomial optimization problems
• Three dimensional strongly symmetric circulant tensors
• Polynomial norms
• Further results on sum-of-squares tensors
• Exact conic programming relaxations for a class of convex polynomial cone programs
• A boosted-DCA with power-sum-DC decomposition for linearly constrained polynomial programs
• Conic relaxations with stable exactness conditions for parametric robust convex polynomial problems
• On difference-of-SOS and difference-of-convex-SOS decompositions for polynomials
• On cones of nonnegative quartic forms

Uses Software

• Macaulay2
• Sostools
• SeDuMi
• YALMIP
• SOS.m2

This page was built for publication: A convex polynomial that is not sos-convex

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