On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials

Amir Ali Ahmadi, Pablo A. Parrilo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

This paper is concerned with algebraic relaxations, based on the concept of sum of squares decomposition, that give sufficient conditions for convexity of polynomials and can be checked efficiently with semidefinite programming. We propose three natural sum of squares relaxations for polynomial convexity based on respectively, the definition of convexity, the first order characterization of convexity, and the second order characterization of convexity. The main contribution of the paper is to show that all three formulations are equivalent; (though the condition based on the second order characterization leads to semidefinite programs that can be solved much more efficiently). This equivalence result serves as a direct algebraic analogue of a classical result in convex analysis. We also discuss recent related work in the control literature that introduces different sum of squares relaxations for polynomial convexity. We show that the relaxations proposed in our paper will always do at least as well the ones introduced in that work, with significantly less computational effort. Finally, we show that contrary to a claim made in the same related work, if an even degree polynomial is homogeneous, then it is quasiconvex if and only if it is convex. An example is given.

Original languageEnglish (US)
Title of host publication2010 49th IEEE Conference on Decision and Control, CDC 2010
Pages3343-3348
Number of pages6
DOIs
StatePublished - Dec 1 2010
Externally publishedYes
Event2010 49th IEEE Conference on Decision and Control, CDC 2010 - Atlanta, GA, United States
Duration: Dec 15 2010Dec 17 2010

Publication series

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

Other

Other2010 49th IEEE Conference on Decision and Control, CDC 2010
CountryUnited States
CityAtlanta, GA
Period12/15/1012/17/10

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials'. Together they form a unique fingerprint.

  • Cite this

    Ali Ahmadi, A., & Parrilo, P. A. (2010). On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials. In 2010 49th IEEE Conference on Decision and Control, CDC 2010 (pp. 3343-3348). [5717510] (Proceedings of the IEEE Conference on Decision and Control). https://doi.org/10.1109/CDC.2010.5717510