Title: 
Approximation Bounds for Quadratic Optimization with
Homogeneous Quadratic Constraints


Authors:
Zhi-Quan Luo
Department of Electrical and Computer Engineering
University of Minnesota
USA

Nicholas D. Sidiropoulos
Department of Electronic and 
Computer Engineering
Technical University of Crete
Greece.

Paul Tseng
Department of Mathematics
University of Washington
U.S.A.

Shuzhong Zhang
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
Shatin, Hong Kong


Abstract:
We consider the NP-hard problem of finding a minimum norm vector in
$n$-dimensional real or complex Euclidean space, subject to $m$
concave homogeneous quadratic constraints.
We show that a semidefinite programming (SDP) relaxation
for this nonconvex quadratically constrained quadratic program (QP)
provides an $O(m^2)$ approximation in the real case, and an
$O(m)$ approximation in the complex case.
Moreover, we show that these bounds are tight up to a constant factor.
When the Hessian of each constraint function is of rank one
(namely, outer products of some given so-called {\it steering}
vectors) and the phase spread of the entries of these steering
vectors are bounded away from $\pi/2$, we establish a certain
``constant factor'' approximation (depending on the phase spread
but independent of $m$ and $n$) for both the SDP relaxation and a
convex QP restriction of the original NP-hard problem. Finally, we
consider a related problem of finding a maximum norm vector
subject to $m$ convex homogeneous quadratic constraints. We show
that a SDP relaxation for this nonconvex QP provides an
$O(1/\ln(m))$ approximation, which is analogous to a result of
Nemirovski, Roos and Terlaky \cite{NRT99} for the real case.