On cones of nonnegative quadratic functions

Jos F. Sturm (j.f.sturmkub.nl)
Shuzhong Zhang (zhangse.cuhk.edu.hk)

Abstract: We derive 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 non-convex 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. We arrive at a generalization of Yakubovich's S-procedure result. As an application we show that optimizing a general quadratic function over the intersection of an ellipsoid and a half-plane can be formulated as 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.

Keywords: LMI, SDP, Co-Positive Cones, Quadratic Functions, S-Procedure, Matrix Decomposition.

Category 1: Linear, Cone and Semidefinite Programming

Citation: CentER Report 2001-26

Download: [Postscript][PDF]

Entry Submitted: 05/02/2001
Entry Accepted: 05/11/2001
Entry Last Modified: 05/11/2001

Modify/Update this entry