This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Sturm, J. F. Articles by Zhang, S. Search for Related Content

On Cones of Nonnegative Quadratic Functions

Department of Econometrics, Tilburg University, The Netherlands
Department of System Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, Hong Kong
j.f.sturm{at}uvt.nl
zhang{at}se.cuhk.edu.hk

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.

Key Words: LMI; SDP; co-positive cones; quadratic functions; S-procedure; matrix decomposition
History: Received: April 14, 2001; revision received: March 24, 2002;

This article has been cited by other articles:

				W. Ai, Y. Huang, and S. Zhang On the Low Rank Solutions for Linear Matrix Inequalities Mathematics of Operations Research, November 1, 2008; 33(4): 965 - 975. [Abstract] [PDF]

				Y. Huang and S. Zhang Complex Matrix Decomposition and Quadratic Programming Mathematics of Operations Research, August 1, 2007; 32(3): 758 - 768. [Abstract] [PDF]

				F. Lutgens, J. Sturm, and A. Kolen Robust One-Period Option Hedging Operations Research, November 1, 2006; 54(6): 1051 - 1062. [Abstract] [PDF]

				L. F. Zuluaga and J. F. Pena A Conic Programming Approach to Generalized Tchebycheff Inequalities Mathematics of Operations Research, May 1, 2005; 30(2): 369 - 388. [Abstract] [PDF]