Journal Article

Convex hull of two quadratic constraints is an LMI set

Uğur Yildiran

in IMA Journal of Mathematical Control and Information

Published on behalf of Institute of Mathematics and its Applications

Volume 26, issue 4, pages 417-450
Published in print December 2009 | ISSN: 0265-0754
Published online October 2009 | e-ISSN: 1471-6887 | DOI:
Convex hull of two quadratic constraints is an LMI set

Show Summary Details


In this work, we are interested in the convex hull of the region determined by two quadratic polynomial constraints. The main result is that if this region is not empty, the convex hull is either ℝn or the feasible set of another pair of quadratic constraints which are, in fact, positive linear combinations of the original ones. Based on this result, a losslessness condition is also derived for the classical semidefinite programming relaxation. The characterization of the convex hull we found does not have to be composed of concave quadratic constraints. However, we propose an algorithm to convert them into linear matrix inequalities (LMIs) and explain how the LMI characterization can be employed to solve a certain class of non-convex optimization problems. It is shown that this approach may perform better than the available relaxation methods for the optimization problem considered. Lastly, we show how the results developed can be applied to a certain class of control problems.

Keywords: S-lemma; SDP relaxation; LMI representation; quadratic programming; convex hull; matrix pencil

Journal Article.  0 words. 

Subjects: Mathematics

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.