Abstract: A multivariate polynomial is sos-convex if its Hessian can be factored as with a possibly nonsquare polynomial matrix . It is easy to see that sos-convexity is a sufficient condition for convexity of . 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.
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
Cites work
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- scientific article; zbMATH DE number 1490041 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- An Example of a Positive Polynomial which is not a Sum of Squares of Polynomials A Positive, but not Strongly Positive Functional
- Class of global minimum bounds of polynomial functions
- Computing sum of squares decompositions with rational coefficients
- Convex Analysis
- Convexity in SemiAlgebraic Geometry and Polynomial Optimization
- Exploiting Algebraic Structure in Sum of Squares Programs
- Matrix sum-of-squares relaxations for robust semi-definite programs
- ON THE DIFFICULTY OF DECIDING THE CONVEXITY OF POLYNOMIALS OVER SIMPLEXES
- Open questions in complexity theory for numerical optimization
- Positive semidefinite biquadratic forms
- Representation of nonnegative convex polynomials
- Semidefinite Programming
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite representation of convex sets
- Some NP-complete problems in quadratic and nonlinear programming
- Symmetry groups, semidefinite programs, and sums of squares
- Uniform denominators in Hilbert's seventeenth problem
Cited in
(33)- Solving fractional multicriteria optimization problems with sum of squares convex polynomial data
- Positive semi-definiteness and sum-of-squares property of fourth order four dimensional Hankel tensors
- Three dimensional strongly symmetric circulant tensors
- On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems
- 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
- Finding efficient solutions in robust multiple objective optimization with SOS-convex polynomial data
- NP-hardness of deciding convexity of quartic polynomials and related problems
- Characterizing robust solution sets of convex programs under data uncertainty
- Multi-objective optimization problems with SOS-convex polynomials over an LMI constraint
- Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations
- On solving a class of fractional semi-infinite polynomial programming problems
- Exact SDP relaxations for classes of nonlinear semidefinite programming problems
- On difference-of-SOS and difference-of-convex-SOS decompositions for polynomials
- On semidefinite programming relaxations for a class of robust SOS-convex polynomial optimization problems
- A hybrid approach for finding efficient solutions in vector optimization with SOS-convex polynomials
- Polynomial norms
- Conic relaxations with stable exactness conditions for parametric robust convex polynomial problems
- Exact dual semi-definite programs for affinely adjustable robust SOS-convex polynomial optimization problems
- A boosted-DCA with power-sum-DC decomposition for linearly constrained polynomial programs
- Multi-objective convex polynomial optimization and semidefinite programming relaxations
- Farkas' lemma: three decades of generalizations for mathematical optimization
- Dual semidefinite programs without duality gaps for a class of convex minimax programs
- 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
- A complete characterization of the gap between convexity and sos-convexity
- Further results on sum-of-squares tensors
- On cones of nonnegative quartic forms
- Semidefinite Representation of Convex Sets and Convex Hulls
- Exact conic programming relaxations for a class of convex polynomial cone programs
- A new class of alternative theorems for SOS-convex inequalities and robust optimization
- Finding efficient solutions for multicriteria optimization problems with SOS-convex polynomials
- Robust SOS-convex polynomial optimization problems: exact SDP relaxations
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)
