A positive definite polynomial Hessian that does not factor

Amir Ali Ahmadi; Pablo A. Parrilo

doi:10.1109/CDC.2009.5400519

A positive definite polynomial Hessian that does not factor

Amir Ali Ahmadi, Pablo A. Parrilo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

The notion of sos-convexity has recently been proposed as a tractable sufficient condition for convexity of polynomials based on a sum of squares decomposition of the Hessian matrix. A multivariate polynomial p(x) = p(x ₁,...,x_n) is said to be 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). The problem of deciding sos-convexity of a polynomial can be reduced to the feasibility of a semidefinite program, which can be checked efficiently. Motivated by this computational tractability, it has been speculated whether every convex polynomial must necessarily be sos-convex. In this paper, we answer this question in the negative by presenting an explicit example of a trivariate homogeneous polynomial of degree eight that is convex but not sos-convex.

Original language	English (US)
Title of host publication	Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009
Pages	1195-1200
Number of pages	6
DOIs	https://doi.org/10.1109/CDC.2009.5400519
State	Published - 2009
Externally published	Yes
Event	48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 - Shanghai, China Duration: Dec 15 2009 → Dec 18 2009

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0191-2216

Other

Other	48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009
Country	China
City	Shanghai
Period	12/15/09 → 12/18/09

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Access to Document

10.1109/CDC.2009.5400519

Fingerprint Dive into the research topics of 'A positive definite polynomial Hessian that does not factor'. Together they form a unique fingerprint.

Cite this

@inproceedings{02dff3202d7d4e9790e553c6bfc48028,

title = "A positive definite polynomial Hessian that does not factor",

abstract = "The notion of sos-convexity has recently been proposed as a tractable sufficient condition for convexity of polynomials based on a sum of squares decomposition of the Hessian matrix. A multivariate polynomial p(x) = p(x 1,...,xn) is said to be sos-convex if its Hessian H(x) can be factored as H(x) = MT (x)M(x) with a possibly nonsquare polynomial matrix M(x). The problem of deciding sos-convexity of a polynomial can be reduced to the feasibility of a semidefinite program, which can be checked efficiently. Motivated by this computational tractability, it has been speculated whether every convex polynomial must necessarily be sos-convex. In this paper, we answer this question in the negative by presenting an explicit example of a trivariate homogeneous polynomial of degree eight that is convex but not sos-convex.",

author = "Ahmadi, {Amir Ali} and Parrilo, {Pablo A.}",

note = "Copyright: Copyright 2010 Elsevier B.V., All rights reserved.; 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 ; Conference date: 15-12-2009 Through 18-12-2009",

year = "2009",

doi = "10.1109/CDC.2009.5400519",

language = "English (US)",

isbn = "9781424438716",

series = "Proceedings of the IEEE Conference on Decision and Control",

pages = "1195--1200",

booktitle = "Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009",

}

Ahmadi, AA & Parrilo, PA 2009, A positive definite polynomial Hessian that does not factor. in Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009., 5400519, Proceedings of the IEEE Conference on Decision and Control, pp. 1195-1200, 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009, Shanghai, China, 12/15/09. https://doi.org/10.1109/CDC.2009.5400519

A positive definite polynomial Hessian that does not factor. / Ahmadi, Amir Ali; Parrilo, Pablo A.

Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009. 2009. p. 1195-1200 5400519 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A positive definite polynomial Hessian that does not factor

AU - Ahmadi, Amir Ali

AU - Parrilo, Pablo A.

PY - 2009

Y1 - 2009

N2 - The notion of sos-convexity has recently been proposed as a tractable sufficient condition for convexity of polynomials based on a sum of squares decomposition of the Hessian matrix. A multivariate polynomial p(x) = p(x 1,...,xn) is said to be sos-convex if its Hessian H(x) can be factored as H(x) = MT (x)M(x) with a possibly nonsquare polynomial matrix M(x). The problem of deciding sos-convexity of a polynomial can be reduced to the feasibility of a semidefinite program, which can be checked efficiently. Motivated by this computational tractability, it has been speculated whether every convex polynomial must necessarily be sos-convex. In this paper, we answer this question in the negative by presenting an explicit example of a trivariate homogeneous polynomial of degree eight that is convex but not sos-convex.

AB - The notion of sos-convexity has recently been proposed as a tractable sufficient condition for convexity of polynomials based on a sum of squares decomposition of the Hessian matrix. A multivariate polynomial p(x) = p(x 1,...,xn) is said to be sos-convex if its Hessian H(x) can be factored as H(x) = MT (x)M(x) with a possibly nonsquare polynomial matrix M(x). The problem of deciding sos-convexity of a polynomial can be reduced to the feasibility of a semidefinite program, which can be checked efficiently. Motivated by this computational tractability, it has been speculated whether every convex polynomial must necessarily be sos-convex. In this paper, we answer this question in the negative by presenting an explicit example of a trivariate homogeneous polynomial of degree eight that is convex but not sos-convex.

UR - http://www.scopus.com/inward/record.url?scp=77950845514&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950845514&partnerID=8YFLogxK

U2 - 10.1109/CDC.2009.5400519

DO - 10.1109/CDC.2009.5400519

M3 - Conference contribution

AN - SCOPUS:77950845514

SN - 9781424438716

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 1195

EP - 1200

BT - Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

T2 - 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

Y2 - 15 December 2009 through 18 December 2009

ER -