Convex hull of two quadratic constraints is an LMI set

Yildiran U.

IMA JOURNAL OF MATHEMATICAL CONTROL AND INFORMATION, vol.26, no.4, pp.417-450, 2009 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 26 Issue: 4
  • Publication Date: 2009
  • Doi Number: 10.1093/imamci/dnp023
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED)
  • Page Numbers: pp.417-450
  • Keywords: S-lemma, SDP relaxation, LMI representation, quadratic programming, convex hull, matrix pencil, RELAXATION METHODS, NONCONVEX SETS, OPTIMIZATION, CONES
  • Yıldız Technical University Affiliated: No


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 R(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.