Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization

Details Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization

2007-01-02

arxiv.org/abs/math/0701070v1

Mathematics

Optimization and Control

Scientific paper

In this paper we study the relationship between the optimal value of a homogeneous quadratic optimization problem and that of its Semidefinite Programming (SDP) relaxation. We consider two quadratic optimization models: (1) $\min \{x^* C x \mid x^* A_k x \ge 1, x\in\mathbb{F}^n, k=0,1,...,m\}$; and (2) $\max \{x^* C x \mid x^* A_k x \le 1, x\in\mathbb{F}^n, k=0,1,...,m\}$. If \emph{one} of $A_k$'s is indefinite while others and $C$ are positive semidefinite, we prove that the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by $O(m^2)$ when $\mathbb{F}$ is the real line $\mathbb{R}$, and by $O(m)$ when $\mathbb{F}$ is the complex plane $\mathbb{C}$. This result is an extension of the recent work of Luo {\em et al.} \cite{LSTZ}. For (2), we show that the same ratio is bounded from below by $O(1/\log m)$ for both the real and complex case, whenever all but one of $A_k$'s are positive semidefinite while $C$ can be indefinite. This result improves the so-called approximate S-Lemma of Ben-Tal {\em et al.} \cite{BNR02}. We also consider (2) with multiple indefinite quadratic constraints and derive a general bound in terms of the problem data and the SDP solution. Throughout the paper, we present examples showing that all of our results are essentially tight.

Affiliated with

Also associated with

No associations

Rating

Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-189261