Abstract
In this paper, we study the strong duality for an optimization problem to minimize a homogeneous quadratic function subject to two homogeneous quadratic constraints over the unit sphere, called Problem (P) in this paper. When a feasible (P) fails to have a Slater point, we show that (P) always adopts the strong duality. When (P) has a Slater point, we propose a set of conditions, called “Property J”, on an SDP relaxation of (P) and its conical dual. We show that (P) has the strong duality if and only if there exists at least one optimal solution to the SDP relaxation of (P) which fails Property J. Our techniques are based on various extensions of S-lemma as well as the matrix rank-one decomposition procedure introduced by Ai and Zhang. Many nontrivial examples are constructed to help understand the mechanism.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
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
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:
Due to the unit sphere constraint \(\Vert x\Vert = 1,\) (P) can be written as
Therefore, we may assume that \(\delta _1= \delta _2=0\) and denote the constraint set of (P) by
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\):
When \(\Vert x\Vert =1\) in (1) is replaced by \(x^TQ_2x \le 1,\) Polyak [23] showed that the strong duality holds for
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:\)
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
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
where \( Q_2\succeq 0.\) The SDP relaxation of (CDT) is
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
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:
- (i)
The system \(x^TQ_0x<\alpha ,~x^TQ_1x\le 0, ~\Vert x\Vert =1\) is not solvable.
- (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:
- (a)
at least one of the two matrices \(Q_1\) and \(Q_2\) is positive semi-definite;
- (b)
both \(Q_1\) and \(Q_2\) are indefinite;
- (c)
both matrices \(Q_1\) and \(Q_2\) are negative definite;
- (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.
- (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.
- (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:
- (i)
either \(\beta _1>0\) or \(\beta _2>0;\)
- (ii)
\(\beta _1=0\) and \( \beta _2=0;\)
- (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].
- (i)
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.
- (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,
- (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
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:\)
is convex, whereas
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
is convex. However, the projection image of
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
and its conic dual is
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
On the other hand,
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
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
and
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.
\( \mu _1^* \mu _2^*>0,\)
- 2.
rank\((Z^*)=n-2,\)
- 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
- 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,\)
- 3.2.
\({x^1}^TQ_1x^2\ne 0.\) That is, \(x^1\) and \(x^2\) are not \(Q_1-\)orthogonal.
- 3.1.
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
then one can find in polynomial-time a vector \(y\in {\mathbb {R}}^n\) such that X is rank-one decomposable at y and
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,
By assumption Property J 3.1 that \({x^1}^TQ_1x^1=0, {x^2}^TQ_1x^2=0,\) there must be
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
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
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
and
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
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
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
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
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.
References
Ai, W., Zhang, S.Z.: Strong duality for the CDT subproblem: a necessary and sufficient condition. SIAM J. Optim. 19(4), 1735–1756 (2009)
Andreani, R., Martinez, J.M., Ramos, A., Silva, P.J.S.: Strict constraint qualifications and sequential optimality conditions for constrained optimization. Math. Oper. Res. 43(3), 693–717 (2018)
Bazarra, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming Theory and Algorithms. Wiley, New York (1993)
Boggs, P.T., Tolle, J.W.: Sequential quadratic programming. Acta Numer. 4, 1–51 (1995)
Brickman, L.: On the field of values of a matrix. Proc. Am. Math. Soc. 12, 61–66 (1961)
Celis, M.R., Dennis, J.E., Tapia, R.A.: A trust region algorithm for nonlinear equality constrained optimization. In: Boggs, R.T., Byrd, R.H., Schnabel, R.B. (eds.) Numerical Optimization, pp. 71–82. SIAM, Philadelphia (1984)
Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2000)
De Angelis, P.L., Toraldo, G.: Quadratic programming with bound constraints. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 3161–3166. Springer, New York (2009)
Fallahi, S., Salahi, M.: On the indefinite quadratic fractional optimization with two quadratic constraints. J. Optim. Theory Appl. 162, 249–256 (2014)
Ferreira, O.P., Nemeth, S.Z., Xiao, L.: On the spherical quasi-convexity of quadratic functions. Linear Algebra Its Appl. 562, 205–222 (2019)
Ferreira, O.P., Nemeth, S.Z., Xiao, L.: On the spherical quasi-convexity of quadratic functions. Linear Algebra Appl. 562, 205–222 (2019)
Gould, N.I.M., Lucidi, S., Roma, M., Toint, P.L.: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2), 504–525 (1999)
Hao, P.H.: Quadratically Constrained quadratic programming: some applications and a method for solution. Z. Oper. Res. 26, 105–119 (1982)
Hsia, Y., Lin, G.X., Sheu, R.L.: A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil. Pac. J. Optim. 10(3), 461–481 (2014)
Jeyakumar, V., Li, G.Y.: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Program. 147(1–2), 171–206 (2014)
Locatelli, M.: Some results for quadratic problems with one or two quadratic constraints. Oper. Res. Lett. 43(2), 126–131 (2015)
Moré, J.J.: Generalization of the trust region problem. Optim. Methods Softw. 2, 189–209 (1993)
Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4(3), 553–572 (1983)
Nguyen, V.B., Sheu, R.L., Xia, Y.: Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming. J. Glob. Optim. 64, 399–416 (2016)
Pardalos, P.M., Resende, M. (eds.): Handbook of Applied Optimization. Oxford University Press, New York (2002)
Pitsoulis, L.: Quadratic programming with bound constraints. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 3170–3171. Springer, New York (2009)
Pólik, I., Terlaky, T.: A survey of the S-lemma. SIAM Rev. 49(3), 371–418 (2007)
Polyak, B.T.: Convexity of quadratic transformations and its use in control and optimization. J. Optim. Theory Appl. 99, 553–583 (1998)
Pong, T.K., Wolkowicz, H.: The generalized trust region subproblem. Comput. Optim. Appl. 58, 273–322 (2014)
Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Program. 77(2, Ser. B), 273–299 (1997)
Sakaue, S., Nakatsukasa, Y., Takeda, A., Iwata, S.: Solving generalized CDT problems via two-parameter eigenvalues. SIAM J. Optim. 26(3), 1669–1694 (2016)
Solodov, M.V.: On the sequential quadratically constrained quadratic programming methods. Math. Oper. Res. 29(1), 64–79 (2004)
Sturm, J.F., Zhang, S.Z.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28, 246–267 (2003)
Vanderberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1995)
Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook on Semidefinite Programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht (2000)
Yakubovich, V.A.: S-procedure in nonlinear control theory. Vestnik Leningr. Univ. 4, 73–93 (1977)
Ye, Y.: A new complexity result on minimization of a quadratic function with a sphere constraint. In: Floudas, C., Pardalos, P. (eds.) Recent Advances in Global Optimization. Princeton University Press, Princeton (1992)
Yuan, Y.: Recent advances in trust region algorithms. Math. Program. 151(1), 249–281 (2015)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Nguyen, VB., Nguyen, T.N. & Sheu, RL. Strong duality in minimizing a quadratic form subject to two homogeneous quadratic inequalities over the unit sphere. J Glob Optim 76, 121–135 (2020). https://doi.org/10.1007/s10898-019-00835-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-019-00835-5
Keywords
- Quadratically constrained quadratic programming
- CDT problem
- S-lemma
- Slater condition
- Joint numerical range