1 Introduction

An important class of optimization problems, known as (QCQP), is to minimize an n-variate quadratic function subject to m quadratic constraints as follows

$$\begin{aligned} \mathrm{(P_m)} \begin{array}{rl} \min \,q_0(x)&{}=x^TQ_0x+2q_0^Tx\\ q_i(x)&{}=x^TQ_ix+2q_i^Tx+\alpha _i\le (=)\, 0, i=1,2,\ldots ,m, \end{array} \end{aligned}$$

where \(Q_i\in {\mathbb {R}}^{n\times n}\) are symmetric matrices, \(q_i\in {\mathbb {R}}^n,~ \alpha _i\in {\mathbb {R}},\) and the constraints can be either equalities or inequalities. It consists of many practical applications such as chance-constrained programming, location allocation problems, problem of production planning and many others. See [13]. On the other hand, \(\mathrm{(P_m)}\) is often used to develop approximate methods for solving general nonlinear optimization problems, including the trust region methods [7, 12, 17, 18, 24], the sequential quadratic methods [4, 27], and the CDT problem [6]. For more special cases and applications of (QCQP), please refer to [8, 20, 21] and the references therein.

In this paper, we aim to study the homogeneous (QCQP) with \(m=3,\)\(q_0=q_1=q_2=q_3=0,\) and \(Q_3=I.\) Specifically, the target problem takes the following form:

$$\begin{aligned} \text {(P) } \begin{array}{lll} v\mathrm{(P)}=&{}\min &{}x^TQ_0x\\ &{}\mathrm{s.t.} &{} x^TQ_1x\le \delta _1,\\ &{} &{} x^TQ_2x\le \delta _2,\\ &{} &{} \Vert x\Vert = 1. \end{array} \end{aligned}$$

Due to the unit sphere constraint \(\Vert x\Vert = 1,\) (P) can be written as

$$\begin{aligned} \begin{array}{lll} v\mathrm{(P)}=&{}\min &{}x^TQ_0x\\ &{}\mathrm{s.t.} &{} x^T(Q_1- \delta _1 I)x\le 0,\\ &{} &{} x^T(Q_2- \delta _2I)x\le 0,\\ &{} &{} \Vert x\Vert = 1. \end{array} \end{aligned}$$

Therefore, we may assume that \(\delta _1= \delta _2=0\) and denote the constraint set of (P) by

$$\begin{aligned} {\mathcal {C}}=\{x\in {\mathbb {R}}^n| x^TQ_1x\le 0, x^TQ_2x\le 0\}. \end{aligned}$$

The problem (P) first appeared in [9] where Fallahi and Salahi showed that an indefinite quadratic fractional problem can be transformed into the form of (P) by the generalized Charnes-Cooper transformation. The solution method of (P), however, has not been well studied in [9].

In fact, our interest in (P) goes along with a string of efforts for solving the general (QCQP), i.e. \(\mathrm{(P_m)}\), in which only some important special cases have been solved by now. To name just a few, they include

  • the trust region subproblem (TRS), e.g., [7, 33]: \(m=1,Q_1=I,q_1=0,\alpha _1<0;\)

  • the general QP1QC (quadratic problem with one quadratic constraint), e.g., [7, 14, 28]: \(m=1;\)

  • the CDT (Celis–Dennis–Tapia) problem, e.g., [1]: \(m=2,Q_1=I,q_1=0,\alpha _1=-1.\)

In general, for \(m\ge 2,\) the problem \(\mathrm{(P_m)}\) becomes very difficult. One can find some recent results in [15, 16, 26]. Our paper deals with (P) which has \(m=3\), and as such it is not expected to be straightforward.

The difficulty of (P) lies in its intrinsic nature of non-convexity. However, in a similar situation occurring to other \(\mathrm{(P_m)}\) problems, it is still possible to dig out some hidden convexity for a few special cases. For example, when \(m=1\) and the Slater condition is satisfied, Sturm and Zhang [28] showed that \(\mathrm{(P_1)}\) admits a tight SDP relaxation and its optimal solutions can be recovered from the optimal solutions of its SDP relaxation by using the matrix rank-one decomposition procedure. The same strong duality result can be also obtained by the celebrated S-Lemma [31]. See, e.g., [7, 25, 32]. For \(m=2,\) one can use an extension of S-Lemma obtained from Brickman’s result [22, Theorem 5.17] to show that the strong duality of the following special case of \(\mathrm{(P_2)}\) holds for \(n\ge 3\):

$$\begin{aligned} \min q_0(x)= & {} x^TQ_0x \nonumber \\ q_1(x)= & {} x^TQ_1x \le 1, \nonumber \\ \Vert x\Vert= & {} 1. \end{aligned}$$
(1)

When \(\Vert x\Vert =1\) in (1) is replaced by \(x^TQ_2x \le 1,\) Polyak [23] showed that the strong duality holds for

$$\begin{aligned} \min q_0(x)= & {} x^TQ_0x \nonumber \\ q_1(x)= & {} x^TQ_1x \le 1, \nonumber \\ q_2(x)= & {} x^TQ_2x \le 1. \end{aligned}$$
(2)

provided \(n\ge 3\) and there exist \(\mu _1, \mu _2\in {\mathbb {R}}\) such that the dual Slater condition \(\mu _1Q_1+\mu _2Q_2\succ 0\) is satisfied. Under the same assumptions, Ye and Zhang [32] utilized the matrix rank-one decomposition procedure to show that (2) has a tight SDP relaxation and the optimal solutions of (2) can be obtained from the optimal solutions of its SDP relaxation.

Notice that (P) confines the feasible domain of (2) to a closed subset on the unit sphere. Then, (P) is always bounded and attainable whereas (2) may not. In this sense, (P) might be easier than (2). However, the participation of the unit sphere losses the important convexity of the joint numerical range under the condition \(\mu _1Q_1+\mu _2Q_2\succ 0\). It is known that, under the dual Slater condition \(\mu _1Q_1+\mu _2Q_2\succ 0,\) the following joint numerical range of \(Q_0, Q_1, Q_2:\)

$$\begin{aligned} {\mathcal {P}}=\{(x^TQ_0x, x^TQ_1x,x^TQ_2x)|x\in {\mathbb {R}}^n\}\subset {\mathbb {R}}^3 \end{aligned}$$

is convex in \({\mathbb {R}}^3,\) which was the key property for Polyak [23] and Ye and Zhang [32] to show their results. Unfortunately, our Example 1 in Sect. 3 shows that, even if \({\mathcal {P}}\) is convex, its restriction on the unit sphere

$$\begin{aligned} \varOmega =\{(x^TQ_0x, x^TQ_1x,x^TQ_2x)|x\in {\mathbb {R}}^n:\Vert x\Vert =1\}\subset {\mathbb {R}}^3 \end{aligned}$$

may not be convex again. As a consequence, \(\mu _1Q_1+\mu _2Q_2\succ 0\) cannot be a valid sufficient condition for (P) to adopt the strong duality. Even worse, the non-convex nature of \(\varOmega \) implies that the construction of a suitable S-lemma for solving (P) is doomed to failure. On the other hand, Ferreira et al. [10] showed that if both \(q_0(x)\) and the constraint set \({\mathcal {C}}\) are spherically convex, then (P) has a unique optimal solution, which is also the critical point of the Lagrangian function. Since (P) is in general not spherically convex without further assumptions on the matrices \(Q_0, Q_1, Q_2,\) the results in [2, 10, 11] do not help to solve (P).

Luckily, we observe that the SDP relaxations between (P) and the (CDT) problem [6] are similar to each other although (P) and the (CDT) problem look differently. Recall first that the CDT problem takes the following format

$$\begin{aligned} \mathrm{(CDT)} \begin{array}{lll} &{}\min &{}q_0(x)=x^TQ_0x-2b_0^Tx\\ &{}\mathrm{s.t.}&{}q_1(x)=x^Tx-1\le 0,\\ &{} &{} q_2(x)=x^TQ_2x-2b_2^Tx+c_2\le 0, \end{array} \end{aligned}$$

where \( Q_2\succeq 0.\) The SDP relaxation of (CDT) is

$$\begin{aligned} \mathrm{(SCDT)} \begin{array}{lll} &{}\min &{}\ M(q_0)\bullet X\\ &{}\mathrm{s.t.} &{} M(q_1)\bullet X\le 0,\\ &{} &{} M(q_2)\bullet X\le 0,\\ &{} &{}\ \ I_{00}\bullet X= 1,\\ &{} &{}\ \ \ \ \ \ X\succeq 0, \end{array} \end{aligned}$$

where \(M(q_0)=\left[ \begin{array}{lll} 0&{}-b_0^T\\ -b_0&{}Q_0 \end{array}\right] , M(q_1)=\left[ \begin{array}{lll} -1&{}0^T\\ 0&{}I \end{array}\right] , M(q_2)=\left[ \begin{array}{lll} c_2&{}-b_2^T\\ -b_2&{}Q_2 \end{array}\right] , I_{00}=\left[ \begin{array}{lll} 1&{}0^T\\ 0&{}O \end{array}\right] \) and I is the identity matrix, O is the zero matrix both are of size n.

For problem (P), its SDP relaxation can be written as

$$\begin{aligned} \mathrm{(SP)} \begin{array}{lll} &{}\min &{}\ Q_0\bullet X\\ &{}\mathrm{s.t.} &{} Q_1\bullet X\le 0,\\ &{} &{} Q_2\bullet X\le 0,\\ &{} &{}\ \ I\bullet X= 1,\\ &{} &{}\ \ \ \ \ \ X\succeq 0. \end{array} \end{aligned}$$

Then, one can easily see that (SCDT) and (SP) are very similar in structure. They only differ on the coefficient matrices. The resemblance enables us to use Ai and Zhang’s rank-one decomposition technique in [1] to prove a necessary and sufficient condition for (P) to have the strong duality, under the assumtion that (P) holds the Slater condition. The detail is provided in Sect. 3. When (P) does not have a Slater point, a direct analysis in Sect. 2 shows that (P) always admits the strong duality.

2 (P) with no Slater point

Recall that (P) is said to satisfy the Slater condition if there exists a point \({\bar{x}}\in {\mathbb {R}}^n\) such that \(\Vert {\bar{x}}\Vert =1\) and \({\bar{x}}^TQ_1{\bar{x}}<0, {\bar{x}}^TQ_2{\bar{x}}<0.\) Throughout this section, we assume that \(n\ge 3.\) Under this assumption, we show that (P) with no Slater point can be reduced to have one less constraint and then solved in polynomial time by the following extension of the S-Lemma [22]:

Lemma 1

[22, Theorem 5.17] Let \(n\ge 3,~\alpha \in {\mathbb {R}}\) and \(Q_0,~Q_1\in {\mathbb {R}}^{n\times n}\) be real symmetric matrices. Assume further that there exists a Slater point \({\bar{x}}\in {\mathbb {R}}^n\) such that \(\Vert {\bar{x}}\Vert =1\) and \({\bar{x}}^TQ_1{\bar{x}}<0.\) The following two statements are equivalent:

  1. (i)

    The system \(x^TQ_0x<\alpha ,~x^TQ_1x\le 0, ~\Vert x\Vert =1\) is not solvable.

  2. (ii)

    There is a nonnegative multiplier \(\mu \) such that

    $$\begin{aligned} Q_0-\alpha I+\mu Q_1\succeq 0. \end{aligned}$$

To begin our analysis, we divide (P) into four cases:

  1. (a)

    at least one of the two matrices \(Q_1\) and \(Q_2\) is positive semi-definite;

  2. (b)

    both \(Q_1\) and \(Q_2\) are indefinite;

  3. (c)

    both matrices \(Q_1\) and \(Q_2\) are negative definite;

  4. (d)

    one of \(Q_1\) and \(Q_2\) is negative definite and the other is indefinite.

Clearly, case (a) implies that (P) has no Slater point, while cases (c) and (d) imply the contrary. For case (b), it is possible to have no Slater point, so cases (a) and (b) are discussed below, while (c) and (d) are left for the next section.

  1. (a)

    Either \(Q_1\succeq 0\) or \(Q_2\succeq 0.\) We may assume that \(Q_1\not \succ 0\) and \(Q_2\not \succ 0.\) Otherwise, (P) is infeasible. Suppose that \(Q_1\succeq 0.\) Then, the constraint \(x^TQ_1x\le 0\) becomes \(x^TQ_1x=0,\) which implies that \(Q_1x=0\) due to \(Q_1\succeq 0.\) Let N be an orthonormal basis matrix of the null space of \(Q_1,\)\(y\in {\mathbb {R}}^{n-r}\) with \(r=\mathrm{rank}(Q_1).\) Substitute \(x=Ny\) into (P) to eliminate the constraint \(x^TQ_1x\le 0\) and obtain

    $$\begin{aligned} \begin{array}{lll} v\mathrm{(P)}=&{}\min &{}y^T(N^TQ_0N)y\\ &{}\mathrm{s.t.} &{} y^T(N^TQ_2N)y\le 0,\\ &{} &{} \Vert y\Vert = 1, \end{array} \end{aligned}$$
    (3)

    which becomes a problem type of format (1).

    • If (3) has no Slater point, i.e., \( y^T(N^TQ_2N)y\ge 0\) for all \(\Vert y\Vert = 1,\) then (3), and thus (P), is infeasible if \( y^T(N^TQ_2N)y> 0\) for all \(\Vert y\Vert = 1.\) Otherwise, \( N^T(Q_2)Ny=0\) due to semidefiniteness of \(N^TQ_2N.\) Solving this linear equation and substituting the solutions to (3), we have obtained an unconstrained quadratic problem, which can be solved easily.

    • On the other hand, if (3) has a Slater point, we can apply Lemma 1 to convert it to an SDP problem as follows.

      $$\begin{aligned} v\mathrm{(P)}= & {} \min _{y\in \mathbb {R}^{n-r}}\left\{ y^T(N^TQ_0N)y : ~y^T(N^TQ_2N)y\le 0,\Vert y\Vert =1\right\} \\= & {} \max \left\{ \nu : \{y\in \mathbb {R}^{n-r}|y^T(N^TQ_0N)y<\nu , y^T(N^TQ_2N)y\le 0,\Vert y\Vert =1\}=\emptyset \right\} \\= & {} \max \left\{ \nu : N^T(Q_0-\nu I)N+\mu N^T(Q_2)N\succeq 0, \mu \ge 0 \right\} \\= & {} \max \left\{ \nu : N^T(Q_0-\nu I +\mu Q_2)N\succeq 0, \mu \ge 0 \right\} . \end{aligned}$$

      The optimal value \(v\mathrm{(P)}\) of (3) is thus computed by solving the SDP problem

      $$\begin{aligned} \begin{array}{lll} &{}\min &{}(N^TQ_0N)\bullet Y\\ &{}\mathrm{s.t.} &{} (N^TQ_2N)\bullet Y\le 0,\\ &{} &{} I_{(n-r)}\bullet Y= 1, \end{array} \end{aligned}$$

      whereas the optimal solution to (3) can be found by a matrix rank-one decomposition procedure developed in [19, Theorem 3].

    The case \(Q_2\succeq 0\) is analyzed similarly.

  2. (b)

    Both \(Q_1\) and \(Q_2\) are indefinite. We first solve the following two problems, both of which are in the form of (1) with a Slater point:

    $$\begin{aligned} \begin{array}{lll} \beta _1=&{}\min &{}x^TQ_1x\\ &{}\mathrm{s.t.} &{} x^TQ_2x\le 0,\\ &{} &{} \Vert x\Vert = 1 \end{array} \end{aligned}$$
    (4)

    and

    $$\begin{aligned} \begin{array}{lll} \beta _2=&{}\min &{}x^TQ_2x\\ &{}\mathrm{s.t.} &{} x^TQ_1x\le 0,\\ &{} &{} \Vert x\Vert = 1. \end{array} \end{aligned}$$
    (5)

    By Lemma 1, \(\beta _1\) can be calculated by solving the following SDP:

    $$\begin{aligned} \beta _1= & {} \min _{x\in \mathbb {R}^n}\left\{ x^TQ_1x| ~x^TQ_2x\le 0,\Vert x\Vert =1\right\} \nonumber \\= & {} \max \left\{ \beta | ~ Q_1-\beta I+\mu Q_2 \succeq 0, \mu \ge 0\right\} . \end{aligned}$$
    (6)

    Since (4) satisfies the Slater condition and (6) is the Lagrangian dual problem of (4) [30], \(\beta _1\) is attained at some dual optimal solution, say, \((\beta _1,\bar{\mu })\in {\mathbb {R}}\times {\mathbb {R}}_+\) so that \(Q_1-\beta _1 I+\bar{\mu }Q_2 \succeq 0.\) By the saddle point theorem (for example, [3, Theorem 6.2.5]), the optimal solution of (4) can be completely characterized by the KKT conditions of (4) at the dual optimal solution \((\beta _1,\bar{\mu })\) as follows:

    $$\begin{aligned} \begin{array}{lll} &{}(Q_1-\beta _1 I+{\bar{\mu }}Q_2)x=0; \\ &{}{\bar{\mu }}{x}^TQ_2{x}=0;\\ &{}{x}^TQ_2{x}\le 0;\\ &{}\Vert {x}\Vert =1. \end{array} \end{aligned}$$
    (7)

    Notice that, (5) can be similarly treated. Now, after computing \(\beta _1\) and \(\beta _2,\) we consider the following possibilities:

    1. (i)

      either \(\beta _1>0\) or \(\beta _2>0;\)

    2. (ii)

      \(\beta _1=0\) and \( \beta _2=0;\)

    3. (iii)

      at least one of the inequalities \(\beta _1<0\) and \(\beta _2<0\) holds.

    When case (b)(i) happens, (P) is infeasible. When case (b)(iii) happens, the Slater condition holds for (P). Indeed, since \(Q_1\) and \(Q_2\) are both indefinite, \(S_1:=\mathrm{int}\{x:x^TQ_1x\le 0\}\ne \emptyset \) and \(S_2:=\mathrm{int}\{x:x^TQ_2x\le 0\}\ne \emptyset .\) Suppose \(\beta _1<0.\) Then there exists \(\Vert {\bar{x}}\Vert =1\) such that \({\bar{x}}^TQ_2{\bar{x}}\le 0\) and \({\bar{x}}^TQ_1{\bar{x}}<0,\) so \({\bar{x}}\in S_1.\) If \({\bar{x}}^TQ_2{\bar{x}}<0,\) then \({\bar{x}}\in S_1\cap S_2\) so that it is a Slater point of (P). If \({\bar{x}}^TQ_2{\bar{x}}=0,\) since \({\bar{x}}\in S_1,\) an open set, there exists a full-dimensional ball \(B({\bar{x}},\epsilon )\) centered at \({\bar{x}}\) with radius \(\epsilon >0\) such that \(B({\bar{x}},\epsilon )\subset S_1.\) On the other hand, \({\bar{x}}^TQ_2{\bar{x}}=0\) means that \({\bar{x}}\) is a boundary point of \(S_2.\) So \(B({\bar{x}},\epsilon )\) is an open ball centered on the boundary of \(S_2.\) It guarantees that \(B({\bar{x}},\epsilon )\cap S_2\ne \emptyset .\) Then there exists \(y\in B({\bar{x}},\epsilon )\cap S_2\) such that \(y^TQ_2y<0\) so \(y\in S_1\cap S_2\) and \(x=\dfrac{y}{\Vert y\Vert }\) is a Slater point of (P). A similar analysis is valid for the case \(\beta _2<0\) or both \(\beta _1<0\) and \(\beta _2<0.\) The case (P) with Slater point will be discussed in next section. Therefore, we only have to deal (b)(ii) here. Due to \(\beta _1=0\) and \( \beta _2=0\), the constraints of (P) become equalities \(x^TQ_1x=0,~x^TQ_2x=0.\) Therefore, the feasible set of (P) can be written as the optimal solution set of (4) satisfying \(x^TQ_2x=0,\) which by (7), is

    $$\begin{aligned} \begin{array}{lll} &{}(Q_1+{\bar{\mu }}Q_2)x=0; \\ &{}{x}^TQ_2{x}=0;\\ &{}\Vert {x}\Vert =1. \end{array} \end{aligned}$$

    Then, problem (P) becomes

    $$\begin{aligned} \begin{array}{lll} v\mathrm{(P)}=&{}\min &{}x^TQ_0x\\ &{}\mathrm{s.t.} &{} (Q_1+{\bar{\mu }}Q_2)x=0, \\ &{} &{} x^TQ_2x=0,\\ &{} &{} \Vert x\Vert = 1. \end{array} \end{aligned}$$
    (8)

    By replacing \((Q_1+{\bar{\mu }}Q_2)x=0\) in (8) with \(x=Wy\) where W is an orthonormal basis matrix of the null space of the matrix \(Q_1+{\bar{\mu }}Q_2,\) problem (P) becomes a homogeneous QCQP with \(m=2\) and the two constraints are of the equality form. Specifically,

    $$\begin{aligned} \begin{array}{lll} v\mathrm{(P)}=&{}\min &{}y^T{\bar{Q}}_0y\\ &{}\mathrm{s.t.}&{} y^T{\bar{Q}}_2y= 0,\\ &{}&{}\Vert y\Vert =1, \end{array} \end{aligned}$$
    (9)

    where \({\bar{Q}}_0=W^TQ_0W, {\bar{Q}}_2=W^TQ_2W.\) To solve (9), we first need the following version of S-lemma for a system of two homogeneous quadratic equalities. Its proof can be obtained either by Brickman’s result [5] together with the convexity of the set \({\mathcal {D}}=\{(u,v)| u<0, v=0\}\subset {\mathbb {R}}^2\); or by modifying the proof of Theorem 4.1 in [17].

Lemma 2

Let \(A_0\) and \(A_1\) be two \(n\times n\) symmetric matrices. Suppose that \(n\ge 3\) and there exist unit vectors \({\bar{x}},x'\) such that \({\bar{x}}^TA_1{\bar{x}}<\alpha _1\) and \({x'}^TA_1x'>\alpha _1.\) Then the following two statements are equivalent.

  1. (i)

    the system \({\left\{ \begin{array}{ll}x^TA_0x<\alpha _0\\ x^TA_1x=\alpha _1,\\ \Vert x\Vert =1 \end{array}\right. }\) is unsolvable,

  2. (ii)

    there exists \(\mu \in {\mathbb {R}}\) such that \(A_0-\alpha _0I+\mu (A_1-\alpha _1I)\succeq 0.\)

We now try to solve (9). Suppose \({\bar{Q}}_2 \succeq 0\) or \({\bar{Q}}_2 \preceq 0,\) the quadratic constraint \(y^T{\bar{Q}}_2y= 0\) becomes a linear system \( {\bar{Q}}_2y=0.\) Solving it and substituting the solution into (9), we can reduce  (9) to a trust region subproblem, which, as we have mentioned in Introduction, can be solved.

Otherwise, \({\bar{Q}}_2\) is indefinite and there will be some \(\Vert \bar{y}\Vert =1\) and \(\Vert y'\Vert =1\) satisfying \(\bar{y}^T{\bar{Q}}_2\bar{y}<0\) and \({y'}^T{\bar{Q}}_2y'>0.\) Applying Lemma 2, we get

$$\begin{aligned} v\mathrm{(P)}&=\min \left\{ y^T{\bar{Q}}_0y| y^T{\bar{Q}}_2y= 0,\Vert y\Vert =1\right\} \\&=\max \left\{ \nu :\{y|y^T{\bar{Q}}_0y-\nu <0, y^T{\bar{Q}}_2y= 0,\Vert y\Vert =1\}=\emptyset \right\} \\&=\max \{\nu : {\bar{Q}}_0-\nu I+\mu {\bar{Q}}_2\succeq 0, \mu \in {\mathbb {R}}\}. \end{aligned}$$

Problem (P) under case (b)(ii) is therefore solved.

3 (P) with the Slater condition

In this section we assume that problem (P) satisfies the Slater condition. Before proceeding, we first show an example that the joint numerical range of \(Q_0, Q_1, Q_2:\)

$$\begin{aligned} {\mathcal {P}}=\{(x^TQ_0x, x^TQ_1x,x^TQ_2x)|x\in {\mathbb {R}}^n\}\subset {\mathbb {R}}^3 \end{aligned}$$

is convex, whereas

$$\begin{aligned} \varOmega =\{(x^TQ_0x, x^TQ_1x,x^TQ_2x)|x\in {\mathbb {R}}^n:\Vert x\Vert =1\}\subset {\mathbb {R}}^3 \end{aligned}$$

is not. This example explains that Ye and Zhang’s approach [32] cannot be adopted to solve (P).

Example 1

Let \(n=3,\)\(Q_0=\left( \begin{array}{lll}1&{}1&{}0\\ 1&{}-2&{}0\\ 0&{}0&{}1\end{array}\right) , Q_1=\left( \begin{array}{lll}1&{}0&{}0\\ 0&{}1&{}0\\ 0&{}0&{}0\end{array}\right) \) and \(Q_2=\left( \begin{array}{lll}0&{}1&{}0\\ 1&{}0&{}0\\ 0&{}0&{}0\end{array}\right) .\)

Observe that \(Q_0+4Q_1 +Q_2=\left( \begin{array}{lll}5&{}2&{}0\\ 2&{}2&{}0\\ 0&{}0&{}1\end{array}\right) \succ 0.\) Applying Polyak’s result [23] we see that the set

$$\begin{aligned} {\mathcal {P}}= & {} \left\{ (x^TQ_0x,x^TQ_1x,x^TQ_2x)|x\in {\mathbb {R}}^3\right\} \nonumber \\= & {} \left\{ (x_1^2-2x_2^2+x_3^2+2x_1x_2, x_1^2+x_2^2,2x_1x_2)|x\in {\mathbb {R}}^3\right\} \subset {\mathbb {R}}^3 \end{aligned}$$
(11)

is convex. However, the projection image of

$$\begin{aligned} \varOmega =\left\{ (u,v,\omega )=(x_1^2-2x_2^2+x_3^2+2x_1x_2, x_1^2+x_2^2,2x_1x_2)|~ \Vert x\Vert =1\right\} \subset {\mathbb {R}}^3 \end{aligned}$$

on the hyperplane \(\omega =0\) is the union of two line segments: \(u=-3v+1, 0\le v\le 1\) and \(u=1, 0\le v\le 1.\) Such a union is not convex. The set \(\varOmega \) is therefore not convex.

Recall that the SDP relaxation of (P) adopts the following form

$$\begin{aligned} \text {(SP) } \begin{array}{lll} \gamma ^*= &{}\min &{}\ Q_0\bullet X\\ &{}\mathrm{s.t.} &{} Q_1\bullet X\le 0,\\ &{} &{} Q_2\bullet X\le 0,\\ &{} &{}\ \ I\bullet X= 1,\\ &{} &{}\ \ \ \ \ \ X\succeq 0, \end{array} \end{aligned}$$

and its conic dual is

$$\begin{aligned} \text {(SD) } \begin{array}{lll} \nu ^*= &{}\max &{}\ \nu \\ &{}\mathrm{s.t.} &{} Z=Q_0-\nu I+\mu _1Q_1+\mu _2Q_2,\\ &{} &{} Z\succeq 0,\\ &{} &{} \mu _1\ge 0, \mu _2\ge 0. \end{array} \end{aligned}$$

We now prove that (SP) also satisfies the Slater condition.

Lemma 3

If (P) satisfies the Slater condition so does its SDP relaxation (SP).

Proof

Suppose \({\bar{x}}\in {\mathbb {R}}^n\) satisfies \(\Vert {\bar{x}}\Vert =1\) and \({\bar{x}}^TQ_1{\bar{x}}<0, {\bar{x}}^TQ_2{\bar{x}}<0.\) Then for \(\epsilon >0\) we define \({\bar{X}}=\dfrac{1}{1+n\epsilon }\left( {\bar{x}}{\bar{x}}^T+\epsilon I\right) .\) Since \({\bar{x}}{\bar{x}}^T\succeq 0,\)\(\epsilon I\succ 0\) and \(\dfrac{1}{1+n\epsilon }>0,\) we have \({\bar{X}}\succ 0\) and

$$\begin{aligned} I\bullet {\bar{X}}=\dfrac{1}{1+n\epsilon }\left( I\bullet {\bar{x}}{\bar{x}}^T+\epsilon I\bullet I \right) =\dfrac{1+n\epsilon }{1+n\epsilon }=1. \end{aligned}$$

On the other hand,

$$\begin{aligned} Q_i\bullet {\bar{X}}=\dfrac{1}{1+n\epsilon }\bullet {\bar{x}}^TQ_i{\bar{x}}+\dfrac{\epsilon }{1+n\epsilon }Q_i\bullet I, \quad i=1,2. \end{aligned}$$

Observe that \(\lim _{\epsilon \rightarrow 0}Q_i\bullet {\bar{X}}={\bar{x}}^TQ_i{\bar{x}}<0, i=1,2.\) We can thus choose \(\epsilon \) small enough to have \(Q_i\bullet {\bar{X}}<0,~ i=1,2.\) Then \({\bar{X}}\) is a Slater point of (SP). \(\square \)

The dual (SD) is said to satisfy the Slater condition if there exists \(Z\succ 0\) for some \(\nu \) and \(\mu _1\ge 0, \mu _2\ge 0.\) By choosing \(-\nu \) large enough number, it is easily seen that (SD) satisfies the Slater condition. When both (SP) and (SD) satisfy the Slater condition, they have attainable optimal solutions [29], say \(X^*\) and \((Z^*,\nu ^*,\mu _1^*, \mu _2^*),\) respectively, such that the complementary conditions hold

$$\begin{aligned} Z^*X^*=0, \mu _1^*Q_1\bullet X^*=0, \mu _2^*Q_2\bullet X^*=0. \end{aligned}$$
(12)

Any optimal pair of \(X^*\) and \((Z^*,\nu ^*,\mu _1^*, \mu _2^*)\) satisfying (12) is called an optimal complementary pair. Let us denote the feasible set of (SP) and (SD), respectively, by

$$\begin{aligned} W=\{X\succeq 0\ |\ Q_1\bullet X \le 0, Q_2\bullet X \le 0,I\bullet X=1\} \end{aligned}$$

and

$$\begin{aligned} V=\{(Z,\nu ,\mu _1,\mu _2)~|~ Z\succeq 0, \mu _1,\mu _2\ge 0\}. \end{aligned}$$

Below we define a very special property, which we call Property J, for any optimal complementary pair of (SP) and (SD).

Definition 1

An optimal complementary pair \(X^*\in W\) and \((Z^*,\nu ^*,\mu _1^*,\mu _2^*)\in V\) is said to have Property J if the following conditions are simultaneously satisfied:

  1. 1.

    \( \mu _1^* \mu _2^*>0,\)

  2. 2.

    rank\((Z^*)=n-2,\)

  3. 3.

    rank\((X^*)=2,\) and there is a rank-one decomposition of \(X^*\) as \(X^*=x^1{x^1}^T+x^2{x^2}^T,\) such that

    1. 3.1.

      \(Q_1\bullet x^1{x^1}^T= Q_1\bullet x^2{x^2}^T=0,\)\([Q_2\bullet x^1{x^1}^T][Q_2\bullet x^2{x^2}^T]<0,\)

    2. 3.2.

      \({x^1}^TQ_1x^2\ne 0.\) That is, \(x^1\) and \(x^2\) are not \(Q_1-\)orthogonal.

To check whether an optimal complementary pair \(X^*\) and \((Z^*,\nu ^*,\mu _1^*,\mu _2^*)\) satisfy Property J, we note that conditions 1 and 2 can be easily verified. As for condition 3, we suppose that \(\mathrm{rank}(X^*)=2\) and, by the matrix rank-one decomposition procedure [28], Procedure 1], decompose \(X^*\) as \(X^*= x^1{x^1}^T+x^2{x^2}^T.\) If \(x^1\) and \(x^2\) satisfy conditions 3.1 and 3.2, then Property J holds for the pair \(X^*\) and \((Z^*,\nu ^*,\mu _1^*,\mu _2^*).\) Otherwise, we can find other decompositions of \(X^*\) by the following result.

Proposition 1

[1] Suppose \(X\in {\mathbb {R}}^{n\times n}, X\succeq 0\) with \(\mathrm{rank}(X)=r\) and \(X= x^1{x^1}^T+x^2{x^2}^T+\ldots +x^r{x^r}^T.\) Let \(X_r=[x^1, x^2,\ldots , x^r]\) be the matrix with columns \(x^1, x^2,\ldots , x^r.\) Then X is rank-one decomposable at \(y\in {\mathbb {R}}^n\) if and only if there is \(u\in {\mathbb {R}}^r\) with \(\Vert u\Vert =1\) and \(y=X_ru.\)

From Proposition 1, every rank one decomposition of \(X^*=y^1{y^1}^T+y^2{y^2}^T\) decomposable at \(y^1\in {\mathbb {R}}^n\) can be written as \(y^1=X_2u\) where \(u\in {\mathbb {R}}^2\) with \(\Vert u\Vert =1.\) Since u is on a 2-dimensional circle, it takes the form either \(u=\left[ \begin{array}{lll}t\\ \sqrt{1-t^2} \end{array}\right] \) or \(u=\left[ \begin{array}{lll}t\\ sqrt{1-t^2} \end{array}\right] \) for \(-1\le t \le 1\) so that \(y^1=X_2u\) can be expresed in terms of parameter \(t\in [-1,1].\) Similarly, from \(y^2{y^2}^T=X^*-y^1{y^1}^T,\)\(y^2\) can be easily found as a function of t. Conditions 3.1 and 3.2 are now checked by solving quadratic (in)equalities of one parameter \(t\in [-1,1].\) Please see Example 3 for illustration.

Definition 2

Under the Slater condition, (P) is said to satisfy Property J if every optimal complementary pair of \(X^*\in W\) and \((Z^*,\nu ^*,\mu _1^*,\mu _2^*)\in V\) has Property J.

As the main theorem of this paper, we give a necessary and sufficient condition for (P) to have the strong duality.

Theorem 1

Under the Slater condition, the SDP relaxation (SP) of (P) is tight if and only if (P) fails Property J. Then, an optimal solution \(x^*{x^*}^T\) of (P) can be obtained in the null space of \(Z^*.\)

In other words, (P) has the strong duality if and only if there exists an optimal complementary pair of \(X^*\in W\) and \((Z^*,\nu ^*,\mu _1^*,\mu _2^*)\in V\) that has “no Property J.” Or equivalently, there exists an optimal complementary pair that violates any of the conditions in Definition 1.

As we have mentioned in Introduction, our work has been motivated by Ai and Zhang’s “no Property I” condition for the CDT problem to adopt the strong duality. The key difference lies in Condition 3.2 of Definition 1. By removing Condition 3.2 of Definition 1, Property J becomes Property I. It is interesting to point out, for the CDT problem, Condition 3.2 becomes redundant when joined with Property I so it reasonably disappears from Property I. That is, for the CDT problem, any optimal complementary pair \(X^*=x^1{x^1}^T+x^2{x^2}^T\) and \((Z^*,\mu _1^*,\mu _2^*)\) satisfying Property I must automatically have \({x^1}^TM(q_1)x^2\not =0.\) This, however, is not the case for (P) as can be seen in Example 2 later.

In the next subsection, we deliver a complete proof for our main theorem. We need to borrow the rank-one decomposition from Ai and Zhang [1].

Lemma 4

[1] Let \(A_1, A_2\in S^{n\times n}\) and \(\delta _1, \delta _2\in {\mathbb {R}}.\) Suppose that \(X=x^1{x^1}^T+x^2{x^2}^T+\ldots +x^r{x^r}^T,\) with \(r\ge 3.\) If

$$\begin{aligned}&A_1\bullet x^1{x^1}^T=A_1\bullet x^2{x^2}^T=\delta _1,\\&\quad (A_2\bullet x^1{x^1}^T-\delta _2)(A_2\bullet x^2{x^2}^T-\delta _2)<0, \end{aligned}$$

then one can find in polynomial-time a vector \(y\in {\mathbb {R}}^n\) such that X is rank-one decomposable at y and

$$\begin{aligned} A_1\bullet yy^T= & {} \delta _1,\\ A_2\bullet yy^T= & {} \delta _2. \end{aligned}$$

Here, the matrix X of rank r is called rank-one decomposable at y if there exist other \(r-1\) vectors \(y^2, y^3,\ldots , y^r\) such that \(X=yy^T+y^2{y^2}^T+\ldots +y^r{y^r}^T.\)

3.1 The proof of Theorem 1

We first prove that if there exists an optimal complementary pair \(X^*\) and \((Z^*,\nu ^*,\mu _1^*, \mu _2^*)\) having no Property J, then (SP) is tight. In this case, we can find a rank-one matrix \(x^*{x^*}^T\in W\) such that \(x^*{x^*}^T\) is optimal to (SP). Let \(r=\mathrm{rank}(X^*).\) If \(r=1,\) the result is automatically true. We therefore proceed by considering all possible cases with \(r>1\) as follows.

Case 1:

Either \(Q_1\bullet X^*<0\) or \(Q_2\bullet X^*<0.\) Suppose that \(Q_2\bullet X^*<0.\) Then \(\mu _2^*=0\) by the complementarity condition (12). If \(\mu _1^*=0,\) by the matrix rank-one decomposition procedure [28], we decompose \(X^*\) as

$$\begin{aligned} X^*=\sum _{i=1}^rx^i{x^i}^T \end{aligned}$$
(13)

such that \(Q_1\bullet x^i{x^i}^T \le 0\) for \(i=1,2,\ldots ,r.\) We have

$$\begin{aligned} \sum _{i=1}^rQ_2\bullet x^i{x^i}^T=Q_2\bullet X^*< 0, \end{aligned}$$

so there must be some \(1\le k\le r\) such that

$$\begin{aligned} Q_2\bullet x^k{x^k}^T\le 0. \end{aligned}$$

Then we define \(x^*=\frac{x^k}{\Vert x^k\Vert }\) and have \(I\bullet x^*{x^*}^T=1, Q_1\bullet x^*{x^*}^T\le 0 \) and \(Q_2\bullet x^*{x^*}^T\le 0.\) It indicates that \(x^*{x^*}^T\in W.\) Moreover, since \(Z^*\succeq 0,\) we have

$$\begin{aligned} 0\le \Vert x^k\Vert ^2Z^*\bullet x^*{x^*}^T=Z^*\bullet x^k{x^k}^T\le Z^*\bullet X^*=0, \end{aligned}$$

so \(Z^*\bullet x^*{x^*}^T=0.\) The other two complementarities

$$\begin{aligned} \mu _1^*Q_1\bullet x^*{x^*}^T=0, ~ \mu _2^*Q_2\bullet x^*{x^*}^T=0 \end{aligned}$$
(14)

are trivially satisfied. The rank one matrix \(x^*{x^*}^T\) is therefore optimal to (SP) so that the SDP relaxation is tight. If \(\mu _1^*>0,\) then \(Q_1\bullet X^*=0.\) Decompose \(X^*=\sum _{i=1}^rx^i{x^i}^T\) such that \(Q_1\bullet x^i{x^i}^T = 0\) for \(i=1,2,\ldots ,r.\) By the same argument, there is \(1\le k\le r\) such that

$$\begin{aligned} Q_2\bullet x^k{x^k}^T\le 0. \end{aligned}$$

Define again \(x^*=\frac{x^k}{\Vert x^k\Vert }\) and one can verify that \(x^*{x^*}^T\) is optimal to (SP). The same analysis can be applied for the case \(Q_1\bullet X^*<0.\)

Case 2:

\(Q_1\bullet X^*=0\) and \(Q_2\bullet X^*=0.\) Suppose at least one of \(\mu _1^*\) and \(\mu _2^*\) is zero, say \(\mu _1^*=0.\) We then decompose \(X^*=\sum _{i=1}^rx^i{x^i}^T\) such that \(Q_2\bullet x^i{x^i}^T= 0\) for \(i=1,2,\ldots ,r.\) If there is some index \(1\le k\le r\) such that \(Q_1\bullet x^k{x^k}^T= 0,\) with \(x^*=\frac{x^k}{\Vert x^k\Vert }\) we can verify that \(x^*{x^*}^T\) is optimal to (SP). Otherwise, since \(\sum _{i=1}^rQ_1\bullet x^i{x^i}^T =0,\) there must be \(1\le k, j \le r\) such that \(Q_1\bullet x^k{x^k}^T >0\) and \(Q_1\bullet x^j{x^j}^T <0.\) By choosing \(x^*=\frac{x^j}{\Vert x^j\Vert }\), it can be seen that \(x^*{x^*}^T\) is optimal to (SP). If both \(\mu _1^*\) and \(\mu _2^*\) are positive (i.e. Condition 1 of Property J is satisfied), we decompose

$$\begin{aligned} X^*=\sum _{i=1}^rx^i{x^i}^T \end{aligned}$$

such that \(Q_1\bullet x^i{x^i}^T= 0\) for \(i=1,2,\ldots ,r,\) and \(\sum _{i=1}^rQ_2\bullet x^i{x^i}^T =0.\) If there exists \(1\le k\le r\) such that \(Q_2\bullet x^k{x^k}^T =0,\) we then choose \(x^*=\frac{x^k}{\Vert x^k\Vert }\) and \(x^*{x^*}^T\) is an optimal solution of (SP). Otherwise, there must be indexes \(1\le k,j\le r\) such that

$$\begin{aligned} Q_2\bullet x^k{x^k}^T>0, Q_2\bullet x^j{x^j}^T<0. \end{aligned}$$

We now consider the following subcases.

  • \(r\ge 3.\) We notice that \(Q_1\bullet x^k{x^k}^T= Q_1\bullet x^j{x^j}^T=0.\) By Lemma 4, \(X^*\) is decomposable at \(y\in {\mathbb {R}}^n\) such that \(Q_1\bullet yy^T=0, Q_2\bullet yy^T=0.\) Let \(x^*=\frac{y}{\Vert y\Vert },\) by the same argument as above, \(x^*{x^*}^T\) is an optimal solution of (SP).

  • \(r=2.\) Then \(X^*=x^1{x^1}^T+x^2{x^2}^T\) such that \(Q_1\bullet x^i{x^i}^T= 0\) for \(i=1,2,\) and \(Q_2\bullet x^1{x^1}^T>0, Q_2\bullet x^2{x^2}^T<0\) so that Property J 3.1 holds. In this case, the following equation of variable \(\lambda \)

    $$\begin{aligned} (x^1+\lambda x^2)^TQ_2(x^1+\lambda x^2) =\lambda ^2{x^2}^TQ_2x^2+2\lambda {x^2}^T Q_2x^1+{x^1}^TQ_2x^1=0 \end{aligned}$$

    has two distinguish roots, say \(\lambda _1, \lambda _2,\) and we let \(u^i=x^1+\lambda _ix^2, i=1,2.\) Suppose Property J 3.2 is violated that \({x^1}^TQ_1x^2=0.\) Then, \({u^i}^TQ_1u^i=0\) for \(i=1,2.\) Moreover, \(Z^*x^i{x^i}^T=0\) and \(Z^*\succeq 0\) imply \(Z^*x^i=0\) so that \(Z^*u^i{u^i}^T=0,~i=1,2.\) We now set \(x^*=\dfrac{u^1}{\Vert u^1\Vert }\) and easily see that \(x^*{x^*}^T\) is a rank-one optimal solution of (SP). Otherwise, \({x^1}^TQ_1x^2\ne 0.\) Namely, Property J 3.1 and 3.2 are both satisfied. In this case, since we already assume \(\mu _1^*>0,~\mu _2^*>0,\) no Property J implies that rank\((Z^*)\ne n-2.\) On the other hand, \(x^1, x^2\) are linearly independent vectors and they are in the null space of \(Z^*\) because \(Z^*x^1=0\) and \(Z^*x^2=0.\) So \(\mathrm{rank}(Z^*)< n-2\) and

    $$\begin{aligned} \mathrm{Range}(X^*) \varsubsetneqq \mathrm{Null}(Z^*). \end{aligned}$$

    It means that \(\mathrm{Null}(X^*)\cap \mathrm{Null}(Z^*)\ne \{0\}\) so we can choose \(0\ne \hat{x}\in \mathrm{Null}(X^*)\cap \mathrm{Null}(Z^*)\) and define

    $$\begin{aligned} {\hat{X}}=X^*+\hat{x}\hat{x}^T=x^1{x^1}^T+x^2{x^2}^T+\hat{x}\hat{x}^T. \end{aligned}$$

    Then rank\(({\hat{X}})=3\) and \(Z^*{\hat{X}}=0.\) We already have

    $$\begin{aligned} Q_1\bullet x^1{x^1}^T= Q_1\bullet x^2{x^2}^T=0 \end{aligned}$$

    and

    $$\begin{aligned}{}[Q_2\bullet x^1{x^1}^T][ Q_2\bullet x^2{x^2}^T]<0. \end{aligned}$$

    Applying Lemma 4 we can find \(y\in {\mathbb {R}}^n\) such that X is decomposable at y and

    $$\begin{aligned} Q_1\bullet yy^T=0, Q_2\bullet yy^T=0. \end{aligned}$$

    Note that \(Z^*\succeq 0\) and \(Z^*{\hat{X}}=0\) imply \(Z^*\bullet yy^T=0.\) Let \(x^*=\frac{y}{\Vert y\Vert },\) by the same argument as above, \(x^*{x^*}^T\) is then an optimal solution of (SP). This last case also completes the first part of the proof.

To prove the necessary part, we assume contrarily that (SP) has a rank-one optimal solution \(x^*{x^*}^T\) and there exists an optimal complementary pair \(X^*\) and \((Z^*, \nu ^*, \mu _1^*, \mu _2^*)\) having Property J. We note that \(Z^*X^*=0,\)\(\mathrm{rank}(Z^*)=n-2,\)\(\mathrm{rank}(X^*)=2, Z^*\succeq 0\) and \( X^*=x^1{x^1}^T+x^2{x^2}^T\) all together imply that \(\{x^1, x^2\}\) is a basis of \(\mathrm{Null}(Z^*).\) Moreover, since \(x^*{x^*}^T\) and \(Z^*\) are primal and dual optimal solutions, respectively, their complementarity \(Z^*x^*{x^*}^T=0\) implies that \(x^*\in \mathrm{Null}(Z^*)\) so that \(x^*=\gamma _1x^1+\gamma _2x^2\) for some \(\gamma _1,\gamma _2\in {\mathbb {R}}.\) By the assumption that \(\mu _i^*>0, i=1,2,\) we have \({x^*}^TQ_ix^*=0, i=1,2.\) Especially,

$$\begin{aligned} {x^*}^TQ_1x^* =\gamma _1^2 {x^1}^TQ_1x^1+2\gamma _1\gamma _2{x^1}^TQ_1x^2+\gamma _2^2 {x^2}^TQ_1x^2=0. \end{aligned}$$
(15)

By assumption Property J 3.1 that \({x^1}^TQ_1x^1=0, {x^2}^TQ_1x^2=0,\) there must be

$$\begin{aligned} \gamma _1\gamma _2{x^1}^TQ_1x^2=0. \end{aligned}$$
(16)

If \(\gamma _1=0,\) then \(x^*=\gamma _2 x^2\) and \({x^*}^TQ_2x^*= \gamma _2^2 {x^2}^TQ_2x^2=0.\) Again by Property J 3.1, \({x^2}^TQ_2x^2\ne 0,\) so \(\gamma _2=0\) and thus \(x^*=0,\) which contradicts to \(\Vert x^*\Vert =1.\) The same arguments imply that \(\gamma _2\ne 0.\) Then, from (16), we have \({x^1}^TQ_1x^2=0.\) This contradicts to our assumption that the pair \(X^*\) and \((Z^*, \mu _1^*, \mu _2^*)\) have Property J.

4 Examples

Example 2 below confirms that Property J implies a positive duality gap.

Example 2

Let \(n=3,\)\(Q_0=\left( \begin{array}{lll}2.5&{}1&{}0\\ 1&{}1&{}0\\ 0&{}0&{}3\end{array}\right) , Q_1=\left( \begin{array}{lll}0&{}-1&{}0\\ -1&{}0&{}0\\ 0&{}0&{}0\end{array}\right) ,\)\(Q_2=\left( \begin{array}{lll}-1&{}0&{}0\\ 0&{}1&{}0\\ 0&{}0&{}0\end{array}\right) ,\)\(\alpha _1=\alpha _2=0.\) Then, problem (P) with this data becomes

$$\begin{aligned} \mathrm{(P)} \begin{array}{llll} v\mathrm{(P)}= &{}\min &{} 2.5x_1^2+2x_1x_2+x_2^2+3x_3^2&{} \\ &{}\mathrm{s.t.}&{}-2x_1x_2&{}\le 0,\\ &{} &{} -x_1^2+x_2^2&{}\le 0,\\ &{} &{} x_1^2+x_2^2+x_3^2&{}=1. \end{array} \end{aligned}$$

Observe that \({\bar{x}}=\left( \frac{2}{\sqrt{5}}, \frac{1}{\sqrt{5}},0\right) ^T\) is a Slater point of (P). By Lemma 3, the SDP relaxation (SP) also satisfies the Slater condition.

Solving the SDP relaxation (SP) and its conic dual (SD), we find that (SP) has a unique optimal solution \(X^*=\left( \begin{array}{lll}\frac{1}{2}&{}0&{}0\\ 0&{}\frac{1}{2}&{}0\\ 0&{}0&{}0 \end{array}\right) \) with the optimal value \(v(SP)=1.75,\) while the unique optimal solution of (SD) is

$$\begin{aligned} \nu ^*=1.75,~ \mu _1^*=0.75,~\mu _2^*=1,~ Z^*=\left( \begin{array}{lll}0&{}0&{}0\\ 0&{}0&{}0\\ 0&{}0&{}1.25 \end{array}\right) . \end{aligned}$$
(17)

First of all, the rank condition in Property J: \(\mathrm{rank}(X^*)=2,\)\(\mathrm{rank}(Z^*)=1=n-2\) (since \(n=3\)) is easily seen to satisfied. Moreover, condition 1: \(\mu _1^*\mu _2^*=0.75>0\) is also valid. Finally, let us take \(X^*=x^1 {x^1}^T+x^2{x^2}^T\) with \(x^1 =\left( \frac{1}{\sqrt{2}}, 0,0\right) ^T,\)\(x^2=\left( 0,\frac{1}{\sqrt{2}}, 0\right) ^T\) satisfying

$$\begin{aligned} Q_1\bullet x^1{x^1}^T=Q_1\bullet x^2{x^2}^T=0;~ (Q_2\bullet x^1{x^1}^T) (Q_2\bullet x^2{x^2}^T)=-\dfrac{1}{4}<0 \end{aligned}$$

and

$$\begin{aligned} {x^1}^TQ_1x^2=-\frac{1}{2}\ne 0. \end{aligned}$$

So, the pair \(X^*\) and \((Z^*, \nu ^*,\mu _1^*, \mu _2^*)\) satisfy Property J. Theorem 1 thus asserts that the SDP relaxation (SP) is not tight. In fact, we can solve (P) directly as follows: First, we substitute \(x_3^2=1-x_1^2-x_2^2\) into the objective and reduce the example to a 2-dimensional nonlinear programming problem. By considering case by case that none of the constraints is active; one of the constraints is active; and both constraints are active, we obtain the optimal solutions of (P) are \(\left( 1,0,0\right) ^T, \left( -1,0,0\right) ^T, \left( \frac{1}{\sqrt{5}}, -\frac{1}{\sqrt{5}},\frac{\sqrt{3}}{\sqrt{5}}\right) ^T,\)\( \left( \frac{1}{\sqrt{5}}, -\frac{1}{\sqrt{5}},-\frac{\sqrt{3}}{\sqrt{5}}\right) ^T,\left( -\frac{1}{\sqrt{5}}, \frac{1}{\sqrt{5}},\frac{\sqrt{3}}{\sqrt{5}}\right) ^T,\) and \(\left( -\frac{1}{\sqrt{5}}, \frac{1}{\sqrt{5}},-\frac{\sqrt{3}}{\sqrt{5}}\right) ^T\) with the optimal value \(v\mathrm{(P)}=2.5.\) It is obvious that \(v\mathrm{(P)}=2.5>1.75=v\mathrm{(SP)}.\)

Example 3

Let \(Q_0=\left( \begin{array}{lll}0&{}0&{}0\\ 0&{}2&{}-1\\ 0&{}-1&{}20\end{array}\right) , Q_1=\left( \begin{array}{lll}0&{}0&{}0\\ 0&{}0&{}1\\ 0&{}1&{}1\end{array}\right) ,\)\(Q_2=\left( \begin{array}{lll}1&{}0&{}0\\ 0&{}-1&{}0\\ 0&{}0&{}0\end{array}\right) \) and \(\alpha _1=\alpha _2=0.\)

Problem (P) is then

$$\begin{aligned} \mathrm{(P)} \begin{array}{llll} v\mathrm{(P)}= &{}\min &{} 2x_2^2-2x_2x_3+20x_3^2&{} \\ &{}\mathrm{s.t.}&{}2x_2x_3+x_3^2&{}\le 0,\\ &{} &{} x_1^2-x_2^2&{}\le 0,\\ &{} &{} x_1^2+x_2^2+x_3^2&{}=1. \end{array} \end{aligned}$$

Note that \({\bar{x}}=\left( 0,-\frac{2}{\sqrt{5}}, \frac{1}{\sqrt{5}}\right) ^T\) is a Slater point of (P). By direct computation, we obtain an optimal complementary pair \(X^*=\left( \begin{array}{lll}\frac{1}{2}&{}0&{}0\\ 0&{}\frac{1}{2}&{}0\\ 0&{}0&{}0\end{array}\right) \) and \(Z^*=\left( \begin{array}{lll}0&{}0&{}0\\ 0&{}0&{}0\\ 0&{}0&{}20\end{array}\right) , \mu _1^*=\mu _2^*=1,\) and \(\gamma ^*=\nu ^*=1\). Again, the rank condition for this pair: \(\mathrm{rank}(X^*)=2\) and \(\mathrm{rank}(Z^*)=1=n-2\) (since \(n=3\)) is easily satisfied. Next, we pick up an arbitrary rank-one decomposition \(X^*=x^1 {x^1}^T+x^2{x^2}^T\) with \(x^1 =\left( \frac{1}{\sqrt{2}}, 0,0\right) ^T,\)\(x^2=\left( 0,\frac{1}{\sqrt{2}}, 0\right) ^T\) and check that

$$\begin{aligned} Q_1\bullet x^1{x^1}^T=Q_1\bullet x^2{x^2}^T=0;~ (Q_2\bullet x^1{x^1}^T) (Q_2\bullet x^2{x^2}^T)=-\dfrac{1}{4}<0 \end{aligned}$$

and \({x^1}^T(Q_1-\alpha _1I)x^2=0.\) That is, condition 3.1 is satisfied while condition 3.2 is not. To verify all other rank-one decompositions of \(X^*,\) say \(X^*=y^1 {y^1}^T+y^2{y^2}^T,\) by Proposition 1, we can write \(y^1=X_2u\) where \(X_2=\left( \begin{array}{lll}\frac{1}{\sqrt{2}}&{}0\\ 0&{}\frac{1}{\sqrt{2}}\\ 0&{}0 \end{array}\right) \) and \(u=\left( \begin{array}{lll}t\\ \pm \sqrt{1-t^2}\end{array}\right) , -1\le t\le 1.\) Then, \(y^1=\left( \frac{t}{\sqrt{2}}, \pm \frac{\sqrt{1-t^2}}{\sqrt{2}},0\right) ^T\) and

$$\begin{aligned} y^2{y^2}^T=X^*-y^1{y^1}^T=\left( \begin{array}{lll}\frac{1-t^2}{2}&{} \frac{1\mp t\sqrt{1-t^2}}{2}&{}0\\ \frac{1\mp t\sqrt{1-t^2}}{2}&{}\frac{t^2}{2}&{}0\\ 0&{}0&{}0 \end{array}\right) \end{aligned}$$

so that \(y^2=\left( \frac{\sqrt{1-t^2}}{\sqrt{2}}, \frac{t}{\sqrt{2}},0\right) ^T.\) It can be check easily that \({y^1}^TQ_1y^2=0,~\forall t\in [-1,1]\) which implies that condition 3.2 can never be satisfied by any rank-one decomposition of \(X^*\) so the pair \(X^*\) and \((Z^*, \mu _1^*, \mu _2^*)\) have no Property J. Solving the equation

$$\begin{aligned} (x^1+\lambda x^2)^T(Q_2-\alpha _2I)(x^1+\lambda x^2)=0, \end{aligned}$$

we have \(\lambda =1\) and return \(x^*=x^1+x^2=(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0)^T\) as an optimal solution of (P). In this example, \(\lambda ^*=\gamma ^*=\nu ^*=1\) and it adopts the strong duality.

5 Concluding remarks

By observing the structural similarity between the SDP relaxations (P) and (CDT), in this paper we have successfully extended “Property I” of Ai and Zhang to become “Property J” which can be used to give a necessary and sufficient condition for (P) to have the strong duality if the Slater condition holds. On the other hand, when a feasible (P) fails to satisfy the Slater condition, our analysis shows that (P) can be always solved in polynomial time. Nevertheless, when (P) under the Slater condition happens to satisfy Property J, we only know that there is a positive duality gap but are unable to either solve (P) directly or give an estimation for the gap. It appears to be an interesting future research topic.