LMI formulations for a class of nonconvex quadratic programming problems

Abstract

Finding the optimal value of a polynomial function over a region determined by a finite number of polynomial constraints and determining the emptiness of such a region constitute major problems encountered in control theory and other branches of engineering. In general, such problems are known to be hard, and hence, it is very unlikely that effiient algorithms will developed for their solution. A general approach employed in the literature to overcome this difficulty is to develop approximations that can be computed efficiently or to identify special subproblems which can be solved easily due to their special structure. In this thesis, we follow the second approach and derive linear matrix inequality (LMI) formulations for some nonconvex quadratic optimization problems. To be more specific, we develop two related results. First, it is shown that the convex hull of a region determined by two quadratic inequality constraints is an LMI set and an algorithm producing the LMI description of the convex hull is obtained. By this way, it becomes possible to find the optimal value of a linear objective function over such a region efficiently and exactly. Second, we show that in R2 the convex hull of a region determined by a finite number of quadratic constraints is LMI set. However, this time the proof developed is not constructive, and hence, an algorithm for attaining the convex hull could not be derived.