An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints

Abstract

In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor’s semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method.

1 Introduction

In this paper, we study the following nonconvex quadratic programs with convex quadratic constraints:

where Q and $Q_{i}$ are $n\times n$ real symmetric matrices, c and $c_{i}$ are $n\times 1$ real vectors, and $b_{i}$ are real numbers, for $i=1,\ldots ,m$. We assume all constraint functions $G_{i}(x)$, $i=1,\ldots ,m$, are convex, and the feasible domain $\mathcal {F}=\{x\in \mathbb {R}^{n}\,|\,\frac{1}{2} x^{T}Q_{i}x+c_{i}^{T}x\leqslant b_{i}, i=1,2,\ldots ,m\}$ is bounded and strictly feasible. Without loss of generality, we assume that Slater’s condition holds, i.e., there exist $\mu _{1},\ldots ,\mu _{m}\geqslant 0$ such that the matrix $Q+\sum _{i=1}^{m}\mu _{i}Q_{i}$ is positive definite. Indeed, we can always add a ball-constraint $x^{T}x\leqslant M$ with M being large enough such that $\mathcal {F}$ is contained in the ball and Slater’s condition is satisfied automatically.

NQPCQC has been investigated extensively in the literature. In fact, several well-known problems, such as the Celis–Dennis–Tapia problem [8], box constrained quadratic programming problem [40], generalized trust-region problem [17, 19], standard quadratic programming problem [4, 5], are subclasses of NQPCQC problems. It also has important applications in communication systems [18, 27]. For NQPCQC, if the objective function is also convex, the problem is solvable in polynomial time for a given precision (see [23]). However, NQPCQC with a nonconvex objective function is known to be NP-Hard in general, even for cases that the matrix Q has only one negative eigenvalue [29].

Branch-and-bound based algorithms are typical enumeration methods to find global solutions of nonconvex quadratically constrained quadratic programming problems (e.g., ref. [10, 22, 39]). Various convex relaxations are adopted to estimate lower bounds in each enumeration. Among them, semidefinite program (SDP) relaxation attracted great attention in the past few decades (see [3] for a recent review), due to its polynomial time solvability by interior-point method [41]. It has been shown that the classical Lagrangian relaxation is equivalent to the SDP relaxation under Shor’s scheme ([21, 35]). Another widely used relaxation method is linear program relaxation such as reformulation–linearization technique (RLT in short, see [32] and [33]). In RLT relaxation, valid linear RLT inequalities are introduced by replacing the bilinear term $x_ix_j$ with the additional variable $X_{ij}$ and relaxing the nonconvex constraints $X_{ij}=x_{i}x_{j}$ to a set of linear constraints. Anstreicher showed that RLT inequalities can be used to strengthen the SDP relaxation [1]. Recently, a new method is to reformulate quadratic programming problems to conic programming problems with copositive cone constraints [5, 6, 11, 15], or set-semidefinite cone constraints [2, 24, 37], and then to approximate these cones by some computationally tractable cones. The key idea of these conic reformulations is to pack the hard part of the nonconvex quadratic programming problems into copositive cones or set-semidefinite cones, such that relaxations become tractable to provide improved lower bounds [7, 12, 13, 16, 20, 25, 30].

In this paper, we focus on an SDP relaxation based branch-and-bound methods. In the conventional SDP relaxations, the constraint $X=xx^{T}$ is usually relaxed to the semidefinite constraint $X\succeq xx^{T}$ (where $X\succeq xx^{T}$ means $X-xx^T$ is a positive semidefinite matrix). As pointed out in [9] and [31], it is very helpful to pay additional attention to the nonconvex constraint $X\preceq xx^{T}$. Buchheim and Wiegele [9] showed that, under the condition $X\succeq xx^{T}$, the constraint $X\preceq xx^{T}$ is satisfied if and only if $X_{ii}=x_{i}^{2}$ for all $i=1,\ldots ,n$. Based on this observation, they designed a branch-and-bound algorithm to reduce the difference between $X_{ii}$ and $x_{i}^{2}$ in the branch nodes. Once the difference between $X_{ii}$ and $x_{i}^{2}$ becomes small enough for all $i=1,\ldots ,n$, the gap between NQPCQC and its relaxation is close to zero. In this paper, we provide another insight that the gap is closely related to the eigenvectors corresponding to the negative eigenvalues of Q and the condition $X=xx^{T}$ is not a requirement in optimality. To close the gap, we construct a new convex relaxation based on the eigenvalue decomposition of Q and branch along the directions of eigenvectors.

The rest of this paper is arranged as follows. In Sect. 2, based on the eigenvalue decomposition of Q, a new reformulation of the problem NQPCQC is proposed. In Sect. 3, we use a convex relaxation of the reformulation problem and design a branch-and-bound algorithm to close the gap. In Sect. 4, we discuss the relation between the proposed algorithm and the one in [9]. Numerical results are presented in Sect. 5. Finally, we conclude the paper in Sect. 6.

Throughout the paper, we use e to denote an n-dimensional column vector with each entry being 1, $e_{i}$ to denote an n-dimensional column vector with the i-th entry being 1 and all other entries being 0, $\mathbb {R}$ to denote the real domain, and $\mathbb {C}$ to denote the complex domain.

2 Eigenvalue decomposition based reformulation

By introducing a new variable $X=xx^{T}$, NQPCQC can be reformulated as

$$\begin{aligned} \min _{(x,X)}\;&\;\frac{1}{2}Q\cdot X+c^{T}x\\ \text {s.t.} \;&\;\frac{1}{2}Q_{i}\cdot X+c_{i}^{T}x -b_{i}\leqslant 0, \quad i=1,2,\ldots ,m, \\&X=xx^{T}, \end{aligned}$$

where “$\cdot$” is the inner product of two matrices. The only nonconvexity involved is $X=xx^{T}$. In the conventional SDP relaxation of Shor [34], this constraint is replaced by $X\succeq xx^T$, i.e.,

$$\begin{aligned} \min _{(x,X)}\;&\;\frac{1}{2}Q\cdot X+c^{T}x\\ \text {s.t.} \;&\;\frac{1}{2}Q_{i}\cdot X+c_{i}^{T}x -b_{i}\leqslant 0,\quad i=1,2,\ldots ,m ,\\&X\succeq xx^{T}. \end{aligned}$$

(NQPCQC)

The following two lemmas reveal connections between solutions of SDP and NQPCQC.

Lemma 1

When $Q_{i}\succeq 0$ for $i=1,2,\ldots ,m$, x is feasible for NQPCQC if and only if there exists an $n\times n$ real symmetric matrix X, such that (x, X) is feasible for SDP.

Proof

If $Q_{i}\succeq 0$ for $i=1,2,\ldots ,m$ and (x, X) is feasible for SDP, then $Q_{i}\cdot X \geqslant x^{T}Q_{i}x$. We have $\frac{1}{2} x^{T}Q_{i}x+c_{i}^{T}x -b_{i} \leqslant \frac{1}{2}Q_{i}\cdot X+c_{i}^{T}x -b_{i}\leqslant 0$, which means x is feasible for NQPCQC. Conversely, if x is feasible for NQPCQC, then it is easy to verify that $(x,xx^{T})$ is feasible for SDP. $\square$

Lemma 2

Let $(\bar{x},\bar{X})$ be an optimal solution of SDP, then $Q\cdot \bar{X} -Q\cdot (\bar{x}\bar{x}^{T})\leqslant 0$.

Proof

Since $(\bar{x},\bar{X})$ is optimal for SDP and $(\bar{x},\bar{x}\bar{x}^{T})$ is feasible for SDP, we have $\frac{1}{2}Q\cdot \bar{X}+c^{T}\bar{x} \leqslant \frac{1}{2}Q\cdot (\bar{x}\bar{x}^{T})+c^{T}\bar{x}$, which implies $Q\cdot \bar{X} -Q\cdot (\bar{x}\bar{x}^{T})\leqslant 0$. $\square$

In general, a nonzero gap exists between SDP and NQPCQC. In some special cases, this gap can be zero (ref. [24]). The next lemma provides a sufficient condition for the zero gap.

Lemma 3

Assume that $Q_{i}\succeq 0$ for $i=1,2,\ldots ,m$. Given an optimal solution $(\bar{x},\bar{X})$ of SDP, if $Q\cdot \bar{X} =Q\cdot (\bar{x}\bar{x}^{T})$, then $\bar{x}$ is optimal for NQPCQC.

Proof

If $(\bar{x},\bar{X})$ is optimal for SDP with $Q\cdot \bar{X} =Q\cdot (\bar{x}\bar{x}^{T})$, then $\bar{x}$ is feasible for NQPCQC by Lemma 1, and $\frac{1}{2}Q\cdot (\bar{x}\bar{x}^{T})+c^{T}\bar{x}=\frac{1}{2}Q\cdot \bar{X}+c^{T}\bar{x}$. Since SDP is a relaxation of NQPCQC, $\bar{x}$ is optimal for NQPCQC. $\square$

Lemma 3 indicates that the gap between SDP and NQPCQC indeed comes from $Q\cdot (\bar{X}-\bar{x}\bar{x}^T)$. This motivates us to focus on the structure of Q. Assume that Q has an eigenvalue decomposition $Q=\sum _{i\in \mathcal {P}}\lambda _{i}v_{i}v_{i}^{T}-\sum _{i\in \mathcal {N}}\lambda _{i}v_{i}v_{i}^{T}$ with $\lambda _{i}>0$ for each $i\in \mathcal {P}\cup \mathcal {N}$, where $\mathcal {P}$ and $\mathcal {N}$ are index sets of all positive and negative eigenvalues, respectively. We also assume that $v_{i}$ are mutually orthogonal unit vectors for $i\in \mathcal {P}\cup \mathcal {N}$ and denote $r = |\mathcal {N}|$ as the number of negative eigenvalues of Q.

Since $X=xx^{T}$ implies $X\succeq xx^{T}$ and $X\cdot (v_{i}v_{i}^{T})=(v_{i}^{T}x)^{2}, i\in \mathcal {N}$, we can add valid constraints $X\cdot (v_{i}v_{i}^{T})=(v_{i}^{T}x)^{2}$ to SDP and consider the following problem based on the eigenvectors of negative eigenvalues of Q:

We will show that EV-QCQP is actually equivalent to NQPCQC.

Theorem 1

Assume that $Q_{i}\succeq 0$ for $i=1,2,\ldots ,m$. If $(\bar{x},\bar{X})$ is an optimal solution of EV-QCQP, then $\bar{x}$ is optimal for NQPCQC.

Proof

Since $(\bar{x},\bar{X})$ is feasible for EV-QCQP, it is also feasible for SDP. According to Lemma 1, $\bar{x}$ is feasible for NQPCQC. By the constraint $\bar{X}-\bar{x}\bar{x}^{T} \succeq 0$, we have

$$\begin{aligned}&Q\cdot \bar{X} -Q\cdot (\bar{x}\bar{x}^{T})\\&\quad =\left( \sum _{i\in \mathcal {P}}\lambda _{i}v_{i}v_{i}^{T}-\sum _{i\in \mathcal {N}}\lambda _{i}v_{i}v_{i}^{T}\right) \cdot (\bar{X}-\bar{x}\bar{x}^{T})\\&\quad =\sum _{i\in \mathcal {P}}\lambda _{i}v_{i}v_{i}^{T} \cdot (\bar{X}-\bar{x}\bar{x}^{T})\\&\quad \geqslant 0. \end{aligned}$$

Since $(\bar{x},\bar{X})$ is optimal for EV-QCQP and $(\bar{x},\bar{x}\bar{x}^{T})$ is feasible for EV-QCQP, we have $Q\cdot \bar{X} -Q\cdot (\bar{x}\bar{x}^{T})\leqslant 0$. Hence $Q\cdot \bar{X} =Q\cdot (\bar{x}\bar{x}^{T})$. Similar to the proof of Lemma 3, $\bar{x}$ is optimal for NQPCQC. $\square$

As suggested in [9], given $X\succeq xx^{T}$, if $X_{ii}=x_{i}^{2}$ is satisfied for $i=1,\ldots ,n$, then $xx^{T}=X$ and x is feasible for NQPCQC. The authors of [9] use convex relaxations of $X_{ii}=x_{i}^{2}$ and branch along axes accordingly. Here, we show that the gap between SDP and NQPCQC is closely related to $Q\cdot (\bar{X} - \bar{x}\bar{x}^{T})$, especially the eigenvectors of the negative eigenvalues of Q. Based on this observation, we propose to relax $Q\cdot \bar{X}=Q\cdot (\bar{x}\bar{x}^{T})$ directly and branch along the directions of negative eigenvectors of Q.

3 A new relaxation of NQPCQC and a branch-and-bound algorithm

After introducing nonconvex constraints $X\cdot (v_{i}v_{i}^{T})=(v_{i}^{T}x)^{2}$ with $i\in \mathcal {N}$ into the SDP relaxation, the condition $Q\cdot X=Q\cdot (xx^{T})$ is satisfied at the optimal solution of EV-QCQP. In this section, we relax the constraints $X\cdot (v_{i}v_{i}^{T})=(v_{i}^{T}x)^{2}$ with $i\in \mathcal {N}$ and design a branch-and-bound algorithm to solve NQPCQC.

Since the feasible domain $\mathcal {F}$ is bounded, we can find $l_{i}=\min \{v_{i}^{T}x|\,x\in \mathcal {F}\}$ and $u_{i}=\max \{v_{i}^{T}x|\,x\in \mathcal {F}\}$. Let $t_i = v_i^Tx$ and $s_i=t_i^2$. Then $l_{i}\leqslant t_{i} \leqslant u_{i}, i\in \mathcal {N}$. The convex envelope of $s_{i}=t_{i}^{2}$ over $l_{i}\leqslant t_{i} \leqslant u_{i}$ is $\{(t_{i},s_{i})| s_{i}\geqslant t_{i}^{2}, s_{i}\leqslant (l_{i}+u_{i})t_{i}-l_{i}u_{i}, l_{i}\leqslant t_{i} \leqslant u_{i} \}$.

EV-QCQP can then be relaxed to the following convex problem:

$$\begin{aligned} \min _{(x,X,t,s)}\;&\;\frac{1}{2}Q\cdot X+c^{T}x\\ \text {s.t.} \;&\;\frac{1}{2}Q_{i}\cdot X+c_{i}^{T}x -b_{i}\leqslant 0, \quad i=1,2,\ldots ,m, \\&(v_{i}v_{i}^{T})\cdot X=s_{i}, \quad i\in \mathcal {N},\\&v_{i}^{T}x=t_{i},\quad i\in \mathcal {N},\\&s_{i}\geqslant t_{i}^{2}, \quad s_{i}\leqslant (l_{i}+u_{i})t_{i}-l_{i}u_{i}, \quad l_{i}\leqslant t_{i} \leqslant u_{i}, i\in \mathcal {N},\\&X\succeq xx^{T}, \end{aligned}$$

where $l_i$ and $u_i$ are lower and upper bounds of $t_i$, respectively. Furthermore, the constraint $s_{i}\geqslant t_{i}^{2}$ is redundant due to $X\succeq xx^{T}$. Also, $s_{i}\geqslant t_{i}^{2}$ and $s_{i}\leqslant (l_{i}+u_{i})t_{i}-l_{i}u_{i}$ together imply $l_{i}\leqslant t_{i} \leqslant u_{i}$. Therefore, we can drop these redundant constraints to form the following problem:

Theorem 2

Let $(\bar{x},\bar{X},\bar{t},\bar{s})$ be an optimal solution of CR$_{[l,u]}$. If $\bar{s}_{i}= \bar{t}_{i}^{2}$ for all $i \in \mathcal {N}$, then $\bar{x}$ is optimal for NQPCQC.

Proof

Given an optimal solution $(\bar{x},\bar{X},\bar{s},\bar{t})$ of $\hbox {CR}_{[l,u]}$, if $\bar{s}_{i}= \bar{t}_{i}^{2}$ for all $i \in \mathcal {N}$, then $(\bar{x},\bar{X})$ is feasible (and also optimal) for EV-QCQP. By Theorem 1, $\bar{x}$ is optimal for NQPCQC. $\square$

If the solution of CR$_{[l,u]}$ is infeasible for EV-QCQP, we can split the current domain $\{t| l_{i}\leqslant t_{i} \leqslant u_{i}, i\in \mathcal {N}\}$ into two smaller boxes and update the convex envelope of $s_{i}=t_{i}^{2}$ for $i\in \mathcal {N}$ over these new boxes. The new convex envelope provides valid constraints to cut off the optimal solution of CR$_{[l,u]}$ so that the lower bound can be improved. Based on the above idea, we propose a new branch-and-bound algorithm for solving NQPCQC. The pseudo-code is presented in Algorithm 1.

In our algorithm, we use index k as the index of iterations. In each iteration, a subproblem is chosen and one or two new subproblems are created to replace the old one. The gap is reduced by the new subproblems while the new upper bound and lower bound are updated accordingly.

Based on Lemma 1, we can prove that NQPCQC is feasible if and only if CR$_{[l^{0},u^{0}]}$ is feasible. Hence, in Line 3 of the proposed algorithm, if CR$_{[l^{0},u^{0}]}$ is infeasible, then NQPCQC is infeasible, and the algorithm stops.

In general the initial bounds $l^0_i$ and $u_i^0$ can be obtained by solving convex quadratically constrained linear programs, which can be solved easily as second-order cone programs [23]. The procedure of computing initial bounds can be simpler for certain types of problems (e.g., the box constrained cases).

Remark 1

In the k-th iteration, if the algorithm does not stop at Line 13, the subproblem $\{[l^{k},u^{k}],\bar{x}^{k},\bar{X}^{k},\bar{s}^{k},\bar{t}^{k},L^{k} \}$ satisfies $\bar{s}_{i}^k> (\bar{t}_{i}^k)^{2}$ for some $i \in \mathcal {N}$. Otherwise, if $\bar{s}_{i}^k= (\bar{t}_{i}^k)^{2}$ for all $i \in \mathcal {N}$, then, by Theorem 2 and the node selection scheme, $L^k$ is the smallest lower bound (which satisfies $L^k \leqslant V_\textit{NQPCQC}$) and we can verify that $\bar{x}^k$ is an optimal solution of NQPCQC. In this case, the algorithm should stop at line 13, which causes a contradiction. Hence $l_{id}^k<z_{id}<u_{id}^k$ and the two boxes $[l^a, u^a]$ and $[l^b, u^b]$ generated in Lines 15–17 will not degenerate.

The intuition of introducing the constraint $s_{i}\leqslant (l_{i}+u_{i})t_{i}-l_{i}u_{i}$ is that the difference between $s_i$ and $t_{i}^2$ is controlled by the constraint, and can be effectively reduced when the interval $[l_i,u_i]$ is branched to smaller ones. Indeed, even on the root node (with $l=l^0$ and $u=u^0$), this constraint is still effective.

Consider the following example:

$$\begin{aligned} \min \,&-2x_{1}x_{2}\\ s.t.\,&(x_1-1)^{2}+(x_{2}-1)^2\leqslant 1\\&x_1^{2}+x_2^2+100x_1+100x_2\leqslant 202. \end{aligned}$$

Its optimal solution is $(x^*_1,x^*_2)=(1,1)$, with optimal value $-2.0$. The conventional SDP relaxation bound for this example is $-2.98$, with a gap 0.98. In comparison, the $CR_{[l,u]}$ bound on the root node, with $l=l^0$ and $u=u^0$, is $-2.0$ already. This example verifies the effectiveness of the above inequality constraints in the $CR_{[l,u]}$ relaxation.

Given an error bound $\varepsilon >0$, and a feasible solution x of NQPCQC, if $F(x)\leqslant V_\mathrm{NQPCQC}+\varepsilon$, then we say that x is an $\varepsilon$-optimal solution. If the proposed branch-and-bound algorithm stops at Line 13, then an $\varepsilon$-optimal solution is returned. We show that the algorithm always returns an $\varepsilon$-optimal solution in a finite number of iterations.

Lemma 4

For real numbers $s_{i},t_{i},l_{i},u_{i} \in \mathbb {R}$, if $s_{i}\leqslant (l_{i}+u_{i})t_{i}-l_{i}u_{i}$ and $s_{i}\geqslant t_{i}^{2}$, then $s_{i}- t_{i}^{2}\leqslant \frac{(u_{i}-l_{i})^{2}}{4}$.

Proof

$s_{i}- t_{i}^{2} \leqslant (l_{i}+u_{i})t_{i}-l_{i}u_{i}-t_{i}^{2}=-[t_{i}-\frac{1}{2}(l_{i}+u_{i})]^2 +\frac{(u_{i}-l_{i})^{2}}{4}\leqslant \frac{(u_{i}-l_{i})^{2}}{4}$. $\square$

Lemma 5

Assume that the NQPCQC problem has a bounded feasible domain, with a nonempty interior. In the k-th iteration, if the subproblem $\{[l^{k},u^{k}],\bar{x}^{k},\bar{X}^{k},\bar{s}^{k},\bar{t}^{k},L^{k} \}$ satisfies $u^{k}_{id}-l^{k}_{id}\leqslant (\frac{4\varepsilon }{r\lambda _{id}})^{\frac{1}{2}}$, where $id=\arg \max _{i \in \mathcal {N}}\lambda _{i}[\bar{s}^{k}_{i}-(\bar{t}^{k}_{i})^{2}]$, then Algorithm 1 stops at line 13 with an $\varepsilon$-optimal solution returned.

Proof

In the subproblem $\{[l^{k},u^{k}],\bar{x}^{k},\bar{X}^{k},\bar{s}^{k},\bar{t}^{k},L^{k} \}$, we omit index k for simplicity of the proof without ambiguity. Based on Lemma 4, we have

$$\begin{aligned} \max _{i \in \mathcal {N}}\lambda _{i}(\bar{s}_{i}-\bar{t}_{i}^{2})=\lambda _{id}(\bar{s}_{id}-\bar{t}_{id}^{2}) \leqslant \lambda _{id} \frac{(u_{id}-l_{id})^{2}}{4}\leqslant \frac{\varepsilon }{r}. \end{aligned}$$

This implies

$$\begin{aligned} Q\cdot (\bar{X} -\bar{x}\bar{x}^{T}) \geqslant -\sum _{i\in \mathcal {N}}\lambda _{i}v_{i}v_{i}^{T} \cdot (\bar{X}-\bar{x}\bar{x}^{T}) =-\sum _{i\in \mathcal {N}}\lambda _{i} (\bar{s}_{i}- \bar{t}_{i}^{2})\geqslant -\varepsilon . \end{aligned}$$

Since $L^k$ is the smallest lower bound, $\bar{x}$ satisfies $F(\bar{x})\leqslant L_{k}+\varepsilon \leqslant V_\mathrm{NQPCQC}+\varepsilon$. Meanwhile, we have $U^{*}=F(x^{*})\leqslant F(\bar{x})$. Therefore, $U^*-L^k<\varepsilon$. The algorithm stops at line 13 and $x^*$ is an $\varepsilon$-optimal solution. $\square$

Remark 2

In the k-th iteration, if the algorithm does not stop, then the original box $[l^{0},u^{0}]$ is split to $k+1$ sub-boxes during the previous iterations. By Lemma 5, $u^{k}_{id}-l^{k}_{id}> (\frac{4\varepsilon }{r\lambda _{id}})^{\frac{1}{2}}$ for the chosen id in the k-th iteration. Since the interval $[l^{k}_{id},u^{k}_{id}]$ is divided to two intervals at the middle point $\frac{1}{2}(l^{k}_{id}+u^{k}_{id})$, the sub-intervals generated in Lines 16–17 satisfies $u^{a}_{id}-l^{a}_{id}=u^{b}_{id}-l^{b}_{id}> (\frac{\varepsilon }{r\lambda _{id}})^{\frac{1}{2}}$. This implies that for each box $[l^{g},u^{g}]$ among the $k+1$ sub-boxes, $u_{i}^{g}-l_{i}^{g}\ge \min \{(\frac{\varepsilon }{r\lambda _{i}})^{\frac{1}{2}}, u_{i}^{0}-l_{i}^{0}\}$ for all $i\in \mathcal {N}$. Furthermore, if $u_{i}^{0}-l_{i}^{0} \leqslant (\frac{4\varepsilon }{r\lambda _{i}})^{\frac{1}{2}}$, then the i-th direction is never chosen in line 15 as a branching direction in these k iterations.

The next theorem shows that Algorithm 1 will stop in a finite number of iterations for any given error tolerance $\varepsilon >0$.

Theorem 3

Given an error tolerance $\varepsilon >0$, the proposed branch-and-bound algorithm returns an $\varepsilon$-optimal solution in at most $\prod _{i\in \mathcal {N}} \lceil (\frac{r\lambda _{i}}{\varepsilon })^{\frac{1}{2}}(u^{0}_{i}-l^{0}_{i}) \rceil$ iterations, where $\lceil \cdot \rceil$ is the ceiling function.

Proof

By Lemma 5 and Remark 2, the original box $[l^{0},u^{0}]$ is split to $k+1$ sub-boxes at the end of the k-th iterations. Each sub-box $[l^{g},u^{g}]$ among these $k+1$ sub-boxes satisfies $u_{i}^{g}-l_{i}^{g}\ge \min \{(\frac{\varepsilon }{r\lambda _{i}})^{\frac{1}{2}}, u_{i}^{0}-l_{i}^{0}\}$ for all $i \in \mathcal {N}$. The total volume of all these sub-boxes is larger than $(k+1)\prod _{i\in \mathcal {N}}\min \{(\frac{\varepsilon }{r\lambda _{i}})^{\frac{1}{2}}, u_{i}^{0}-l_{i}^{0}\}$. If $k>\prod _{i\in \mathcal {N}} \lceil (\frac{r\lambda _{i}}{\varepsilon })^{\frac{1}{2}}(u^{0}_{i}-l^{0}_{i}) \rceil$, then the total volume of these sub-boxes is larger than $\prod _{i\in \mathcal {N}} ( \lceil (\frac{r\lambda _{i}}{\varepsilon })^{\frac{1}{2}}(u^{0}_{i}-l^{0}_{i}) \rceil \cdot \min \{(\frac{\varepsilon }{r\lambda _{i}})^{\frac{1}{2}}, u_{i}^{0}-l_{i}^{0}\})$. Since $( \lceil (\frac{r\lambda _{i}}{\varepsilon })^{\frac{1}{2}}(u^{0}_{i}-l^{0}_{i}) \rceil \cdot \min \{(\frac{\varepsilon }{r\lambda _{i}})^{\frac{1}{2}}, u_{i}^{0}-l_{i}^{0}\})\ge \min \{(u_i^0-l_i^0), 1\cdot (u_i^0-l_i^0) \}= u_{i}^{0}-l_{i}^{0}$, the total volume is larger than $\prod _{i\in \mathcal {N}}(u_{i}^{0}-l_{i}^{0})$, which is a contradiction. Hence the proposed branch-and-bound algorithm stops in at most $\prod _{i\in \mathcal {N}} \lceil (\frac{r\lambda _{i}}{\varepsilon })^{\frac{1}{2}}(u^{0}_{i}-l^{0}_{i}) \rceil$ iterations.$\square$

Remark 3

If the index $id=\text {argmax}_{i\in \mathcal {N}} (\bar{s}_{i}-\bar{t}_{i}^{2})$ without including $\lambda _{i}$, then, similar to proofs of Lemma 5 and Theorem 3, the condition $\frac{\lambda _{i}(\bar{s}_{i}-\bar{t}_{i}^{2})}{4} \leqslant \frac{\varepsilon }{r}$ for all $i\in \mathcal {N}$ can be satisfied if $\max _{i\in \mathcal {N}}\frac{\lambda _{i}(\bar{s}_{i}-\bar{t}_{i}^{2})}{4}\leqslant \max _{i\in \mathcal {N}}\frac{\lambda _{i}(\bar{s}_{id}-\bar{t}_{id}^{2})}{4}= \frac{\lambda _{b}(\bar{s}_{id}-\bar{t}_{id}^{2})}{4} \leqslant \frac{\varepsilon }{r}$, where $\lambda _{b}=\max \{\lambda _{i}|i\in \mathcal {N}\}$. Then the worst case bound is $\prod _{i\in \mathcal {N}} \lceil (\frac{r\lambda _{b}}{\varepsilon })^{\frac{1}{2}}(u_{i}^0-l_{i}^0) \rceil$, which exceeds the one in Theorem 3.

4 Connections to previous work

Our method is closely related to the method proposed by Buchheim and Wiegele in [9], although the two methods are based on different observations and for different purposes. In this section, we briefly discuss the relationship and difference between the two methods.

The method proposed by Buchheim and Wiegele is a branch-and-bound algorithm for solving nonconvex mixed-integer quadratic program (MIQP) problems.

$$\begin{aligned} \min _{x} \;&\; x^{T}Qx+c^{T}x \\ \text {s.t.} \;&\; x\in D_1\times \cdots \times D_n, \end{aligned}$$

(SDP)

where each $D_i$ is a closed subset of $\mathbb {R}$. They use the following SDP relaxation:

$$\begin{aligned} \min _{x} \;&\;Q\cdot X +c^{T}x \\ \text {s.t.} \;&\;(x_{i},X_{ii})\in P(D_{i}) \\&X\succeq xx^{T}, \end{aligned}$$

(EV-QCQP)

where $P(D_{i})$ is the convex envelope of $\{(x_{i},x_i^2)| x_i\in D_i\}$. For example, in the box constrained quadratic program (BQP) problem, each $D_i$ is [0, 1], and $P(D_i)=\{(x_i,X_{ii}) | X_{ii}\ge x_i^2, X_{ii}\le x_i\}$ for $i=1,\ldots ,n$.

Although Buchheim and Wiegele’s algorithm is specially designed for MIQP problem with variables being independent in the constraints, their method can be extended to solve NQPCQC problem by adding valid constraints $(x_{i},X_{ii})\in P(D_{i})$ into the conventional SDP relaxation of NQPCQC, where $D_i=[l_i,u_i]$, with $l_i=\min \{x_i|x\in \mathcal F\}$ and $u_i=\max \{x_i|x\in \mathcal F\}$ for $i=1,\ldots ,n$, and using a similar branch-and-bound algorithm as Buchheim and Wiegele’s algorithm. It selects $id = \text {arg}\max _{i\in \mathcal {N}} (\bar{X}_{ii}-\bar{x}^{2}_i)$ and branches the box [l, u] along the direction $x_{id}$ in each iteration. For simplicity, we call their original algorithm as BW algorithm and its extension to general NQPCQC as Extended-BW algorithm.

To see the relationship between BW algorithm (or Extended-BW algorithm) and our algorithm, for the convex relaxation CR$_{[l,u]}$ in Sect. 3, if we choose $(v_{1},v_{2},\ldots ,v_{n})$ to be $(e_{1},e_{2},\ldots ,e_{n})$, rather than the eigenvectors of negative eigenvalues of Q, then CR$_{[l,u]}$ becomes the SDP relaxation used in BW algorithm (or Extended-BW algorithm). All these methods exploit valid constraints from the convex envelope of the set $\{(t,s)|\,s=t^2, t=(v^Tx),x\in \mathcal {F}\}$, but with different choices of $v\in \mathbb {R}^{n}$. BW algorithm and Extended-BW algorithm try to enforce $X=xx^T$ by selecting $(v_{1},v_{2},\ldots ,v_{n})=(e_{1},e_{2},\ldots ,e_{n})$, while our algorithm focuses on reducing the gap $Q\cdot (X-xx^T)$ by selecting $(v_{1},v_{2},\ldots ,v_{r})$ to be the eigenvectors of negative eigenvalues. The branching rules of these algorithms are similar. In BW algorithm or Extended-BW algorithm, we choose an $id\in \{1,2,\ldots ,n\}$ such that $id=\arg \max _{i\in \{1,\ldots ,n\}} \{\bar{X}_{ii}-\bar{x}_{i}^{2}\}$ and split the box along $x_{id}$. In our algorithm, we choose $id=\arg \max _{i \in \mathcal {N}}\lambda _{i}[\bar{s}^{k}_{i}-(\bar{t}^{k}_{i})^{2}]$ and split the box [l, u] along $t_{id}$ (i.e., split the feasible domain along the direction of $v_{id}$).

To see the difference, note that both BW algorithm and Extended-BW algorithm always branch on an n-dimensional box. In comparison, we introduce an r-dimensional box $[l^0,u^0]$ and branch on this lower dimensional box in our algorithm. As we will see in the numerical experiments, this branching strategy is very effective when r is relatively small, although NQPCQC is in general NP-hard even if $r=1$ as in [29]. It is worth mentioning that BW algorithm is more suitable for solving integer programs since integral cuts for $(X_{ii},x_{i})$ can be easily applied to the branching directions in the BW algorithm.

5 Numerical experiments

In this section, we test the proposed algorithm on three classes of randomly generated problems: $[0,1]^n$ box constrained quadratic program (BQP) problems, nonconvex quadratic programs with multip ellipsoids constraints (ECQP), and homogeneous nonconvex quadratic programming problems with homogeneous convex quadratic constraints (HQCQP).

Our branch-and-bound algorithm is implemented in Matlab 7.10 and uses SeDuMi [36] to solve semidefinite relaxations. Besides, the eigenvalue decomposition of Q is realized directly using the Matlab function eig(Q). We run all experiments on a PC with Intel Core i7-2600 (3.40 GHz) and 4GB memory.

5.1 $[0,1]^n$ box constrained cases

A set of test instances with dimensions $n=40$ and 50 are randomly generated. For each instance, all entries of a matrix $\tilde{Q}\in \mathbb {R}^{n\times n}$ and a vector $\tilde{c}\in \mathbb {R}^n$ are generated independently from the uniform distribution $U[-100,100]$. Then we compute eigenvalues $\lambda _{1}\le \cdots \le \lambda _{n}$ of $\tilde{Q}$. For a given integer r with $1\leqslant r<n$, let $\nu =\frac{1}{2}(\lambda _{r}+\lambda _{r+1})$. Set $Q=\tilde{Q}-\nu I$ and $c=\tilde{c}+\frac{\nu }{2} e$. It can be seen easily that Q has exactly r negative eigenvalues (Without loss of generality, we may drop any instance with $\lambda _{r}=\lambda _{r+1}$, so the number of negative eigenvalues is always r). This instance generating procedure is similar to the one in Pardalos and Rodgers [28] with minor modifications to control the total number of negative eigenvalues. For the $[0,1]^n$ box, the initial bounds for $v_{i}^{T}x$ is computed by $l_{i}=\sum _{j=1}^{n} \min \{0,[v_{i}]_{j}\}$ and $u_{i}=\sum _{j=1}^{n} \max \{0,[v_{i}]_{j}\}$, where $[v_{i}]_{j}$ denotes the j-th entry of $v_{i}$, $i=1,\ldots , r$.

We compare our algorithm with BW algorithm as in [9]. BW algorithm is also implemented in Matlab following the description in [9]. In our experiments, we set $\varepsilon =10^{-4}$ and the maximum number of iterations be $3\times 10^{4}$. Besides, the smallest negative eigenvalues for these generated test instances, which are important in the theoretical complexity bound, are generally between $-60$ and $-150$. The computational results are listed in Tables 1 and 2 for $r=4,6,8$ and $r=10,20,30$, respectively.

As we can see from Table 1, when r is relatively small, our algorithm uses much fewer iterations and less computing time than BW algorithm. The main reason is that the proposed algorithm introduces a lower dimensional box for branching.

The advantages diminish as r increases in the BQP test. Table 2 lists the comparison results on 40-dimensional instances, with the number of negative eigenvalues ranging from 10 to 30 (the smallest negative eigenvalues for these problems are generally between $-120$ and $-360$). Our algorithm is better for cases $(n,r)=(40,10)$, while BW algorithm outperforms ours for cases $(n,r)=(40,20)$ and $(n,r)=(40,30)$. The explanation is that on one hand, as r increases, the dimensions of the two boxes $[l^0,u^0]$ and $[0,1]^n$ become close. This reduces the advantage of our algorithm. On the other hand, in BQP test, the bounds used in BW algorithm form the box exactly, while the bounds used in our algorithm form a much larger domain containing extra regions which requires more iterations to reduce. As we will see in the next two tests, for general NQPCQC problems, the bounds used by both methods will enlarge the feasible domain and our algorithm performs quite well even for large r.

Table 1 Comparison on box constrained cases with $n=40,50$ and $r=4,6,8$

Table 2 Comparison of two methods for box constrained cases with $n=40$ and $r=10,20,30$

5.2 Quadratic programming with convex quadratic constraints

We test the proposed algorithm on ECQP problems which is an extension of the Celis–Dennis–Tapia problem (nonconvex quadratic program over two ellipsoids) [8].

The test set is randomly generated as follows. In an instance with n-dimensional variable and m constraints, the matrices $\tilde{Q}$ and $\tilde{Q}_{i}$, $i=1,2,\ldots ,m$, are generated for quadratic terms, with each entry being in $U[-1,1]$. Then we use eigenvalue decomposition to obtain $\tilde{Q}=P^{T} DP$ and $\tilde{Q}_{i}=P_{i}^{T}D_{i}P_{i}$. After that, we generate diagonal matrices $\tilde{D}$ and $\tilde{D}_{i}$ with the first r diagonal entries of $\tilde{D}$ being in $U[-10,0]^r$, the rest diagonal entries of $\tilde{D}$ being in $U[0,10]^{n-r}$, and diagonal entries of $\tilde{D}_{i}$ being in $U[1,100]^n$. Then we set the matrices $Q=P^{T}\tilde{D}P$ and $Q_{i}=P_{i}^{T}\tilde{D}_{i}P_{i}$. Finally, we generate $c_{i}$ from $U[-100,100]^{n}$, $b_{i}$ from U[1, 50] for $i=1,\ldots ,m$, and set the term c to zero. It is easy to verify that all instances generated by the above procedure are strictly feasible with $x=0$ being a strictly feasible solution. Since $Q_{i}\succ 0$ for $i=1,2,\ldots ,m$, the feasible domain is bounded, and Slater’s condition holds. To drop those easy cases, after generating an instance, we solve its conventional SDP relaxation and get the optimal solution $(\bar{x},\bar{X})$. We only select instances with $\bar{x}^{T}Q\bar{x} \ne Q\cdot \bar{X}$ in our experiments. In ECQP test, the initial bounds $l_{i}$ and $u_{i}$ are computed by Cplex solver (using the “cplexqcp” interface for Matlab). The computing time of each lower or upper bound is less than 0.1 seconds. Furthermore, to simplify the calculation of initial bounds, we set $[l_i^0,u_i^0]$ to be $[-10^6,10^6]$ and only compute the exact bound $l_{i}=\min _{x\in \mathcal {F}}v_{i}^{T}x$ and $u_{i}=\max _{x\in \mathcal {F}}v_{i}^{T}x$ for those directions chosen as branching directions for the first time.

We compare our algorithm with the Extended-BW algorithm with various configurations (n, m, r). In both algorithms, the error tolerance is $\varepsilon =5\times 10^{-4}$. We also compare our algorithm with some state-of-the-art solvers provided by the NEOS Server [14]. The NEOS Server provides a number of solvers including Baron, Couenne and SCIP. We tested these solvers with our instances, and found that Baron [38] is the most efficient and stable one among them. Thus, we list the computational results of Baron. The same error bound is set for Baron solver (the relative error is set to $\varepsilon /\bar{v}_\textit{NQPCQC}$, where $\varepsilon =5\times 10^{-4}$ and $\bar{v}_\textit{NQPCQC}$ is the optimal value obtained by our algorithm). Numerical results for our algorithm, Extended-BW algorithm, and Baron solver are listed in Table 3.

Test results show that our method performs better than the Extended-BW algorithm in most cases (even for the cases $r=n$) except instance 19. This indicates that branching along the eigen-directions is very effective for ECQP.

Besides, we find that Baron fails to solve instances with $n\geqslant 15$ within one hour. We test same instances by other solvers (including Couenne and SCIP) provided by NEOS Server and do not get better results than Baron. For 10 instances of small problems with $n=10$, Baron is slower than our method in 8 cases. Since the experiments for our algorithm and for Baron are carried out on different machines, the CPU time for $n=10$ instances may not reveal the efficiency of our algorithm. However, the significant differences between the two methods when $n\geqslant 15$ demonstrate that our algorithm is indeed more efficient than Baron in solving medium-scale nonconvex quadratic programms with multiple ellipsoidal constraints (with $n\geqslant 15$).

Table 3 Comparison on ECQP instances

5.3 Homogeneous quadratic programs

We consider an important subclass of NQPCQC problem: homogeneous quadratic programs with homogeneous quadratic constraints (i.e., with multiple homogeneous ellipsoid constraints, denoted as HCQCQP problem). This class of problems has many applications in communication systems [27]. It is known that homogeneous quadratic programs with only two homogeneous ellipsoid constraints are solvable in polynomial time [37]. For general cases, it is NP-Hard [26]. Besides, The SDP relaxations for general homogeneous quadratic programs have been studied in [18, 26]. In this subsection, we test our algorithm on solving HCQCQP problems.

A set of test instances are generated as follows. For each $Q_{i}$ with $i=1,\ldots ,m$, we first generate a symmetric matrix $\bar{B}_{i}$ with each entry being in $U[-1,1]$, and compute the eigenvalue decomposition $\bar{B}_{i}=\bar{V}\bar{D}\bar{V}^{T}$. Then, we generate a diagonal matrix D by setting $D_{ii}=|\bar{D}_{ii}|$ for $i=1,\ldots ,n$, and set $Q_{i}=\bar{V}D\bar{V}^{T}$. The symmetric matrix Q is generated with each entry being in $U[-1,1]$. c and $c_{i}$ with $i=1,\ldots ,m$ are set to zero. $b_{i}$ is set to 1 for all $i=1,\ldots ,m$. In our experiments, all the instances have nonzero relaxation gaps.

We compare our algorithm with the Extended-BW algorithm. The error tolerance is $\varepsilon =5\times 10^{-4}$. Numerical results can be found in Table 4. Similar to the results in Sect. 5.2, we discover that our algorithm performs better than the Extended-BW algorithm. The results indicate that branching along the eigen-directions of negative eigenvalues is effective for HCQCQP problems.

In addition, we test Baron solver on these instances. Similarly, we discover that Baron fails to solve all these problems within one hour.

Table 4 Comparison on homogeneous quadratic programming problems

5.4 Applications in MIMO cognitive radio networks

We consider the spectrum sharing problem defined in [42], which is a special homogeneous quadratic programs with strong application background. We first present a short introduction to the problem background (more details can be found in [42]). Consider a cognitive radio network, in which a secondary user intends to share the spectrum with a primary system consisting of K primary links. the subscript S denotes the secondary link, and k denotes the k-th primary link. Let $M_{S}$ (or $M_{k}$) denote the number of transmit antennae of the secondary link (or the k-th primary link), and $N_{S}$ (or $N_{k}$) denote the number of receive antennae of the secondary link (or the k-th primary link). For two links i and j, the matrix $H_{i,j}\in \mathbb {C}^{N_i \times M_j}$ denotes the channel matrix from transmitter i to receiver j. Let $t_{k}$ and $r_{k}$ denote the beamforming vectors at the k-th receiver and transmitter. $t_{S}$ and $r_{S}$ denote the beforming vectors at the secondary transmitter and receiver. The problem is to maximize the signal to interference and noise ratio

$$\begin{aligned} \max _{t_{k}\in \mathbb {C}^{M_{S}},r_{k}\in \mathbb {C}^{N_{S}},\Vert r_{k}\Vert =1}\,\frac{ \alpha _{S,S}|r_{S}^H H_{S,S}t_S|^{2}}{\sum _{k=1}^{K} \alpha _{S,k}|r_{S}^H H_{S,k}t_k|^{2} +N_{0}\Vert r_{S}\Vert ^{2} }, \end{aligned}$$

where $\alpha _{S,S}$, $\alpha _{S,k}$ and $N_{0}$ are some given constant. The power of $t_{S}$ is constrained by $t_{S}^{H}t_{S}\leqslant P_{S,max}$, where $P_{S,max}$ is the maximum transmission power. Besides, the introduced new secondary link should has little interference to primary links, so that $t_{S}$ should satisfy $\alpha _{k,S}|r_{k}^H H_{k,S} t_{S}|^{2} \leqslant \zeta _{k}$, which means the interference to primary link k is below a threshold $\zeta _{k}$. If we know $r_k$ exactly (Scenario 1 in [42]), then the interference constraint can be written as $t_S^{H}Q_{k}t_S\leqslant 1$, where $Q_{k}= \frac{\alpha _{k,S}}{\zeta }H^H_{k,S} r_k r_{k}^H H_{k,S}$. However, for some applications, we do not know $r_k$ exactly, but only assume that $r_{k}$ has a normalized complex Gaussian distribution (Scenario 2 model in [42]). Then, we wish the interference constraint is satisfied with high probability, i.e., $t_{k}$ satisfies $Pr\{ \alpha _{k,S}|r_{k}^H H_{k,S} t_{S}|^{2} \leqslant \zeta _{k} \}>1-\delta$ for a given $\delta \in (0,1)$. As was shown in [42], the above probability constraint is equivalent to the constraint $t_S^{H}\hat{Q}_{k}t_S\leqslant 1$, where $\hat{Q}_{k}=\frac{1-\delta ^{ \frac{1}{N_k}} }{\zeta _{k}}H_{k,S}^H H_{k,S}$. For any fixed $t_{S}$ in the objective function, we optimize $r_{S}$, and the optimal solution $r^{*}_{S}$ satisfies $r^{*}_{S}=\beta _{S}\Phi ^{-1}H_{S,S}t_{S}$, where $\Phi = \sum _{k=1}^{K} \alpha _{S,k}H_{S,k} t_k t_{k}^H H^H_{S,k}+N_{0}I$, and $\beta _{S}=\frac{1}{\Vert \Phi ^{-1}H_{S,S}t_{S}\Vert }$. Hence, the objective function can be transformed to $\max _{t_{S}}\,t_{S}^{H}At_{S}$, where $A=\alpha _{S,S} H_{S,S}^{H}\Phi ^{-1}H_{S,S}$. Based on the above observations, the model can be formulated as the following NQPCQC problem:

$$\begin{aligned} \max _{t}\;&\; t_{S}^{H}At_{S}\\ \text {s.t.} \;&\; t_S^{H}Q_{k}t_S\leqslant 1, \quad i=1,2,\ldots ,K ,\\&t_{S}^{H}t_S\leqslant P_{S,max}, \end{aligned}$$

where $Q_{k}= \frac{\alpha _{k,S}}{\zeta }H^H_{k,S} r_k r_{k}^H H_{k,S}$ for Scenario 1, and $Q_{k}=\frac{1-\delta ^{ \frac{1}{N_k}} }{\zeta }H_{k,S}^H H_{k,S}$ for Scenario 2. It is easy to verify that an $M_{S}$-dimensional complex quadratic programming problem can be reformulated as a $2M_{S}$-dimensional real quadratic programming problem by regarding the real part and imaginary part of each entry in $t_{S}$ as two real variables, so that it can be solved by the proposed algorithm.

Now, we simulate the network with K primary links and one secondary link. Each link has 5 transmit antennae and 5 receive antennae. A Rayleigh fading and rich scattering environment is assumed (i.e., the entries of the channel matrices are independently and identically distributed complex Gaussian random variables with zero mean and unit variance). The parameters of $P_{S,max}$, $\alpha _{S,k}$, $\alpha _{k,S}$, $t_k$ and $r_k$ are set in the same manner as in [42] (more details can be found in Section VII of [42]). $N_0$ is set to 0.05, $\zeta _k$ is set to 1, and $\delta$ is set to 0.01. For each scenario, 20 instances, with different number of primary links K, are generated for test. The problem instances are globally solved by using the proposed algorithm and the Extended-BW algorithm, respectively, with error bound $10^{-6}$. Numerical results for Scenario 1 and Scenario 2 are listed in Tables 5 and 6, respectively, which show that the proposed algorithm is efficient for the homogeneous quadratic programs with practical parameter distributions, and the comparison between the proposed algorithm and the Extended-BW algorithm further proves that branching along the eigen-directions of negative eigenvalues is a very efficient and robust branching strategy for homogeneous quadratic programs. Our algorithm is quite different to the algorithm in [42], which provides a high quality approximate solution, but the globally optimality is not guaranteed. In comparison, the proposed algorithm can obtain a global solution within a guaranteed error bound $10^{-6}$ in acceptable CPU time, which further demonstrates the potential of the proposed algorithm in practical applications.

Table 5 Scenario 1 of MIMO cognitive radio network problems

Table 6 Scenario 2 of MIMO cognitive radio network problems

6 Conclusions

In this paper, we design a new branch-and-bound algorithm for solving NQPCQC. We first show that a nonzero gap between the original problem and Shor’s SDP relaxation is caused by the difference between $\bar{x}^{T} Q\bar{x}$ and $Q\cdot \bar{X}$, where $(\bar{x},\bar{X})$ is the optimal solution of the SDP relaxation. Then, based on the eigenvalue decomposition of Q, we derive a new reformulation of NQPCQC by adding valid nonconvex constraints $X\cdot (v_iv_i^T)=(v_i^Tx)^2$ to ensure the condition $x^{T} Qx = Q\cdot X$, and design a new SDP relaxation using the convex envelopes of these nonconvex constraints. A branch-and-bound algorithm is proposed based on the new SDP relaxation and its convergence property is proved.

Numerical experiments confirm the efficiency of our algorithm and validate the idea of closing the gap directly from $Q\cdot (X-xx^T)$. Our algorithm performs better than BW algorithm in the box constrained cases when the numbers of negative eigenvalues is small (e.g., when $r\leqslant \frac{1}{4}n$), and also performs better than the Extended-BW algorithm in nonhomogeneous (ECQP) and homogeneous (HCQCQP) cases. We also compared our algorithm with Baron (and some other solvers in NEOS server) on nonhomogeneous and homogeneous ellipsoidal constrained cases. The results indicate that the proposed algorithm is more efficient than Baron for solving medium-scale ellipsoidal constrained quadratic programs (especially when $n\geqslant 15$). We also test the proposed algorithm with quadratic programs arise in MIMO cognition radio networks, which further demonstrates that the proposed algorithm is promising for real applications in telecommunication systems.

Further directions of our study include extension to solving nonconvex quadratically constrained quadratic programs and adapting to MIQP problems. Besides, by exploiting the RLT inequalities for improving the tightness of $CR_{[l,u]}$ relaxation may bring further improvement to our branch-and-bound algorithm.