TY - GEN
T1 - On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials
AU - Ali Ahmadi, Amir
AU - Parrilo, Pablo A.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79953150055&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79953150055&partnerID=8YFLogxK
U2 - 10.1109/CDC.2010.5717510
DO - 10.1109/CDC.2010.5717510
M3 - Conference contribution
AN - SCOPUS:79953150055
SN - 9781424477456
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 3343
EP - 3348
BT - 2010 49th IEEE Conference on Decision and Control, CDC 2010
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 49th IEEE Conference on Decision and Control, CDC 2010
Y2 - 15 December 2010 through 17 December 2010
ER -