On Cones of Nonnegative Quadratic Functions

TLDR

These matrix cones are cones of nonconvex quadratic functions that are nonnegative on a certain domain. The paper derives LMI characterizations and dual decomposition algorithms for matrix cones generated by a set via generalized co‑positivity, and shows that quadratic optimization over an ellipsoid intersected with a half‑plane can be reformulated as semidefinite programming, establishing polynomial solvability. The authors characterize the cones using LMIs and dual decomposition, considering as domain the intersection of a quadratic level‑set and a half‑plane. The results generalize Yakubovich’s S‑procedure, enable SDP formulation of quadratic optimization over ellipsoid‑half‑plane intersections, and have further applications in control theory and robust optimization.

Abstract

We derive linear matrix inequality (LMI) characterizations and dual decomposition algorithms for certain matrix cones which are generated by a given set using generalized co-positivity. These matrix cones are in fact cones of nonconvex quadratic functions that are nonnegative on a certain domain. As a domain, we consider for instance the intersection of a (upper) level-set of a quadratic function and a half-plane. Consequently, we arrive at a generalization of Yakubovich's S-procedure result. Although the primary concern of this paper is to characterize the matrix cones by LMIs, we show, as an application of our results, that optimizing a general quadratic function over the intersection of an ellipsoid and a half-plane can be formulated as semidefinite programming (SDP), thus proving the polynomiality of this class of optimization problems, which arise, e.g., from the application of the trust region method for nonlinear programming. Other applications are in control theory and robust optimization.