Further Development in Convex Conic Reformulation of Geometric Nonconvex Conic Optimization Problems

Naohiko Arima nao

\_

[email protected]. Sunyoung Kim Department of Mathematics, Ewha W. University, 52 Ewhayeodae-gil, Sudaemoon-gu, Seoul 03760, Korea ([email protected]). The research was supported by NRF 2021-R1A2C1003810. Masakazu Kojima Department of Industrial and Systems Engineering, Chuo University, Tokyo 192-0393, Japan ([email protected]).

Abstract

A geometric nonconvex conic optimization problem (COP) was recently proposed by Kim, Kojima and Toh (SIOPT 30:1251-1273, 2020) as a unified framework for convex conic reformulation of a class of quadratic optimization problems and polynomial optimization problems. The nonconvex COP minimizes a linear function over the intersection of a nonconvex cone $\mathbb{K}$ , a convex subcone $\mathbb{J}$ of the convex hull co $\mathbb{K}$ of $\mathbb{K}$ , and an affine hyperplane with a normal vector $H$ . Under the assumption co $(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ , the original nonconvex COP in their paper was shown to be equivalently formulated as a convex conic program by replacing the constraint set with the intersection of $\mathbb{J}$ and the affine hyperplane. This paper further studies the key assumption co $(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ in their framework and provides three sets of necessary-sufficient conditions for the assumption. Based on the conditions, we propose a new wide class of quadratically constrained quadratic programs with multiple nonconvex equality and inequality constraints, which can be solved exactly by their semidefinite relaxation.

Key words. Convex conic reformulation, geometric conic optimization problem, quadratically constrained quadratic program, polynomial optimization problem, positive semidefinite cone, exact semidefinite relaxation.

AMS Classification. 90C20, 90C22, 90C25, 90C26,

1 Introduction

Convex conic reformulation of a geometric nonconvex conic optimization problem (COP) was studied by Kim, Kojima and Toh in [15] as a unified framework for completely positive programming reformulation of a wide class of nonconvex quadratic optimization problems (QOPs). This class includes a wide range of QOPs, such as QOPs over the standard simplex [6], maximum stable set problems [9], graph partitioning problems [20] and quadratic assignment problems [9], and its extension to polynomial optimization problems (POPs) [3, 4, 18]. The class of QOPs also covers Burer’s class of QOPs with linear equality and complementarity constraints in nonnegative and binary variables [8]. Their geometric nonconvex COP denoted by COP( $\mathbb{K}\cap\mathbb{J}$ ) below is quite simple, but it is powerful enough to capture the basic essentials to investigate convex conic reformulation of general nonconvex COPs. In fact, it minimizes a linear function in a finite dimensional vector space $\mathbb{V}$ over the intersection of three geometrically represented sets, a nonconvex cone $\mathbb{K}$ , a convex subcone $\mathbb{J}$ of the convex hull co $\mathbb{K}$ of $\mathbb{K}$ , and an affine hyperplane with a normal vector $H$ . The framework was also used in the recent paper [10] which proposed a large class of quadratically constrained quadratic programs with stochastic data. See also [7].

Throughout the paper, $\mathbb{V}$ denotes a finite dimensional vector space endowed with the inner product $\langle\mbox{\boldmath$A$},\,\mbox{\boldmath$B$}\rangle$ for every pair of $A$ and $B$ in $\mathbb{V}$ , and $\mbox{\boldmath$O$}\not=\mbox{\boldmath$H$}\in\mathbb{V}$ and $\mbox{\boldmath$Q$}\in\mathbb{V}$ are arbitrarily fixed, unless specified. For every cone $\mathbb{C}\subseteq\mathbb{V}$ , let COP( $\mathbb{C}$ ) denote the conic optimization problem (COP) of the form

\displaystyle\zeta_{p}(\mathbb{C})=\inf\left\{\langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}\rangle:\mbox{\boldmath$X$}\in\mathbb{C},\ \langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}\rangle=1\right\}.

(1)

Here we say that $\mathbb{C}\subseteq\mathbb{V}$ is a cone, which is not necessarily convex nor closed, if $\lambda\mbox{\boldmath$A$}\in\mathbb{C}$ for every $\mbox{\boldmath$A$}\in\mathbb{C}$ and $\lambda\geq 0$ . If COP( $\mathbb{C}$ ) is infeasible, we let $\zeta_{p}(\mathbb{C})=\infty$ . By replacing $\mathbb{C}$ by its convex hull co $\mathbb{C}$ , we obtain a convex relaxation COP(co $\mathbb{C}$ ) of the problem. When the original nonconvex COP( $\mathbb{C}$ ) and the relaxed convex COP(co $\mathbb{C}$ ) share a common optimal value, i.e., $\zeta_{p}(\mathbb{C})=\zeta_{p}(\mbox{co}\mathbb{C})$ , the convex COP is called a convex conic reformulation of the nonconvex COP.

A nonconvex COP introduced in [15] is described as

\displaystyle\mbox{COP($\mathbb{K}\cap\mathbb{J}$):}\quad\zeta_{p}(\mathbb{K}\cap\mathbb{J})=\inf\left\{\langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}\rangle:\mbox{\boldmath$X$}\in\mathbb{K}\cap\mathbb{J},\ \langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}\rangle=1\right\}

under the following conditions:
(A) $\mathbb{K}$ is a nonempty cone in $\mathbb{V}$ and $-\infty<\zeta_{p}(\mathbb{K}\cap\mathbb{J})<\infty$ (i.e., COP( $\mathbb{K}\cap\mathbb{J}$ ) is feasible and has a finite optimal value).
(B) $\mathbb{J}$ is a convex cone contained in co $\mathbb{K}$ such that co $(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ .
Among the theoretical results established in [15], we mention the following equivalence result (see [15, Theorem 3.1], [2, Theorem 5.1] for more details).

Theorem 1.1.

Assume that Conditions (A) and (B) are satisfied. Then,

\displaystyle\left.\begin{array}[]{c}-\infty<\zeta_{p}(\mathbb{J})<\infty,\\ \Updownarrow\\ -\infty<\zeta_{p}(\mathbb{K}\cap\mathbb{J})=\zeta_{p}(\mathbb{J})<\infty\\ \mbox{({\it i.e.}, COP($\mathbb{J}$) is a convex reformulation of COP($\mathbb{K}\cap\mathbb{J}$))}.\end{array}\right\}

(6)

First, we briefly discuss some remaining issues, which were not throughly studied in [15]:

: (a) The feasibility preserving property [27] (Section 2.1).
: (b) Strong duality of the reformulated convex COP (Section 2.2).
: (c) The existence of a common optimal solution of a nonconvex COP and the reformulated convex COP (Section 2.3).

If $\mathbb{J}$ is a face of co $\mathbb{K}$ , then co $(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ (Condition (B)) is satisfied. This case was throughly studied and played an essential role in convex conic reformulation of QOPs and POPs in [15]. Another case mentioned in [15, Lemma 2.1 (iv)] for Condition (B) is: $\mathbb{J}$ is the convex hull of the union of (possibly infinitely many) faces of co $\mathbb{K}$ . But neither its implication nor its application was discussed there. In Section 3 of this paper, we introduce the family $\widehat{\mbox{$\cal F$}}(\mathbb{K})$ of all $\mathbb{J}$ which satisfy co $(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ , and study its fundamental properties. In particular, we establish the following characterization of $\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .

Theorem 1.2.

: (i) $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ iff $\mathbb{J}=\mbox{co}\mathbb{K}^{\prime}$ for some cone $\mathbb{K}^{\prime}\subseteq\mathbb{K}$ .
: (ii) $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ iff $\mathbb{J}=\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ for some $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .
: (iii) Assume that $\mathbb{K}$ and $\mathbb{J}$ are closed and $\mbox{\boldmath$H$}\in\mbox{int}(\mathbb{K}^{*})$ , where $\mbox{int}(\mathbb{K}^{*})$ denotes the interior of $\mathbb{K}^{*}$ . Then $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ iff $\zeta_{p}(\mathbb{K}\cap\mathbb{J})=\zeta_{p}(\mathbb{J})$ for every $\mbox{\boldmath$Q$}\in\mathbb{V}$ .

A proof is given in Section 3.3. Based on assertion (ii), we discuss a decomposition of the convex reformulation COP $(\mbox{co}(\bigcup\mbox{$\cal F$}))$ of COP $(\mathbb{K}\cap\big{(}\mbox{co}(\bigcup\mbox{$\cal F$})\big{)})$ with $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ into the convex reformulations COP( $\mathbb{F}$ ) of COP( $\mathbb{K}\cap\mathbb{F}$ ) $(\mathbb{F}\in\mbox{$\cal F$})$ (Theorem 3.6).

In Section 4, we focus on the case where $\mathbb{K}$ is represented as $\mathbb{K}=\{\mbox{\boldmath$x$}\mbox{\boldmath$x$}^{T}:\mbox{\boldmath$x$}\in\mathbb{R}^{n}\}\subseteq\mathbb{S}^{n}$ (the space of $n\times n$ symmetric matrices) and $\mathbb{J}$ by multiple inequalities such that $\mathbb{J}=\mathbb{J}_{-}\equiv\{\mbox{\boldmath$X$}\in\mbox{co}\mathbb{K}:\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle\leq 0\ (1\leq k\leq m)\}$ for some $\mbox{\boldmath$B$}_{k}\in\mathbb{S}^{n}$ $(1\leq k\leq m)$ . In this case, co $\mathbb{K}$ forms the cone $\mathbb{S}^{n}_{+}$ of positive semidefinite matrices in $\mathbb{S}^{n}$ , and COP $(\mathbb{J}_{-})$ serves as a semidefinite programming (SDP) relaxation of COP $(\mathbb{K}\cap\mathbb{J}_{-})$ , which can be regarded as a quadratically constrained quadratic program (QCQP) with nonconvex inequality constraints $\mbox{\boldmath$x$}^{T}\mbox{\boldmath$B$}_{k}\mbox{\boldmath$x$}\leq 0$ $(1\leq k\leq m)$ and an equality constraint $\mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1$ . By using Theorem 1.2 (iii) and [26, Lemma 2.2], we establish that $\mathbb{J}_{-}\equiv\{\mbox{\boldmath$X$}\in\mbox{co}\mathbb{K}:\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle\leq 0\ (1\leq k\leq m)\}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ if condition

\displaystyle\mathbb{J}_{0}(\mbox{\boldmath$B$}_{k})\equiv\{\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}:\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle=0\}\subseteq\mathbb{J}_{-}\ (1\leq k\leq m)

(7)

is satisfied. This result leads to a wide class of QCQPs with multiple nonconvex constraints, COP $(\mathbb{K}\cap\mathbb{J}_{-})$ with $\mbox{\boldmath$B$}_{k}\in\mathbb{S}^{n}$ $(1\leq k\leq m)$ , which can be solved by their SDP relaxation COP $(\mathbb{J}_{-})$ . See Figure 1 for a geometrical image of condition (7). We know that if $X$ is a common optimal solution of COP $(\mathbb{K}\cap\mathbb{J}_{-})$ and its SDP relaxation COP $(\mathbb{J}_{-})$ , then rank $\mbox{\boldmath$X$}=1$ . In case (a), every extreme ray of $\mathbb{J}_{-}$ on which COP $(\mathbb{J}_{-})$ can attain an optimal solution $X$ lies on the boundary of $\mathbb{S}^{n}_{+}$ whose extreme rays are known to be generated by rank-1 matrices. In case (b), $\mathbb{J}_{-}$ includes an extreme ray not included on the boundary of $\mathbb{S}^{n}_{+}$ ; hence such an extreme ray may include a matrix with rank greater than $1$ . Thus, condition (7) is quite natural to ensure the equivalence of COP $(\mathbb{J}_{-})$ and its SDP relaxation COP $(\mathbb{K}\cap\mathbb{J}_{-})$ for any $\mbox{\boldmath$Q$}\in\mathbb{S}^{n}$ . We also see that $\mathbb{J}_{-}=\mbox{co}\mathbb{K}^{\prime}$ for some $\mathbb{K}^{\prime}\subseteq\mathbb{K}$ in case (a) but $\mathbb{J}_{-}\not=\mbox{co}\mathbb{K}^{\prime}$ for any $\mathbb{K}^{\prime}\subseteq\mathbb{K}$ in case (b). Therefore, by Theorem 1.2 (i), $\mathbb{J}_{-}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ in case (a) but $\mathbb{J}_{-}\not\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ in case (b). We note that if $n\geq 3$ then the intersection of the boundary of $\mathbb{S}^{n}_{+}$ with $\mathbb{J}_{0}(\mbox{\boldmath$B$})$ ( $\mbox{\boldmath$B$}\in\mathbb{S}^{n}$ ) generally includes matrices with rank in $\{0,1,\ldots,n-1\}$ , presenting a more complicated situation. The aforementioned explanation represents the case when $n=2$ .

Refer to caption — Figure 1: Geometrical illustrations for condition (7) with $m=3$ . (a) illustrates a case where (7) is satisfied, and (b) a case where (7) is not satisfied. Here $\mathbb{J}_{-}(\mbox{\boldmath$B$}_{k})=\{\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}:\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle\leq 0\}$ $(1\leq k\leq m)$ and $\mathbb{J}_{-}=\cap_{k=1}^{3}\mathbb{J}_{-}(\mbox{\boldmath$B$}_{k})$ .

1.1 Contribution of the paper and related literature

Our primary contribution lies in presenting a new and wide class of QCQPs with multiple nonconvex constraints that can be solved exactly by their SDP relaxation. The equivalence of QCQPs and their SDP relaxation was extensively studied in the literature, including [5, 11, 12, 19, 22, 23, 25, 26, 28]. The classes of QCQPs studied there can be classified into two categories. The first category requires particular sign patterns of the data matrices involved in QCQPs [5, 12, 22, 28]. The studies on the second category have focused on cases where the number of nonconvex constraints is limited at most two [26], and some additional assumption on the quadratic functions involved in the constraint [11, 19, 23, 25, 26]. Trust-region subproblems of nonlinear programs have been frequently studied in relation to the second category. Our class of QCQPs is also related to the second category, but represents a significantly wider class than them, in the sense that QCQPs can involve any finite number of nonconvex constraints. Condition (7) is both quite general and intuitively natural, ensuring the equivalence of QCQPs and their SDP relaxation (see Figure 1).

The second contribution is that we present more precise characterizations of Condition (B), which plays a central role in the theory of convex conic reformulation of geometric COPs, as shown in Theorem 1.2. This contribution, together with (a), (b) and (c) mentioned above, makes the theory solid and enhances its applicability to a wide range of problems. In particular, the discovery of the new class of QCQPs in the first contribution is based on them.

1.2 Outline of the paper

In Section 2, we discuss the three issues (a), (b) and (c) in detail. In Section 3, we present some fundamental properties on $\widehat{\mbox{$\cal F$}}(\mathbb{K})$ , and prove Theorem 1.2. We also discuss decompositions of a nonconvex COP and its convex conic reformulation based on Theorem 1.2 (ii). In Section 4, we present the class of QCQPs with multiple nonconvex inequality and equality constraints that can be reformulated as their SDP relaxation. Some representative QCQP examples in this class are presented. We conclude in Section 5 with remarks on the features of the geometric nonconvex COP $(\mathbb{K}\cap\mathbb{J})$ as a unified framework, and its possible application to the completely positive cone.

1.3 Remarks on notation and symbols

We note that a cone $\mathbb{C}$ is convex if $\mbox{\boldmath$X$}=\sum_{k=1}^{m}\mbox{\boldmath$X$}^{k}\in\mathbb{C}$ whenever $\mbox{\boldmath$X$}^{k}\in\mathbb{C}$ $(k=1,...,m)$ . The convex hull co $\mathbb{C}$ of a cone $\mathbb{C}$ is represented as co $\mathbb{C}=\{\sum_{k=1}^{m}\mbox{\boldmath$X$}^{k}:\mbox{\boldmath$X$}^{k}\in\mathbb{C}\ (k=1,\ldots,m)\ \mbox{for some }m\}$ . The dual $\mathbb{C}^{*}=\{\mbox{\boldmath$Y$}\in\mathbb{V}:\langle\mbox{\boldmath$X$},\,\mbox{\boldmath$Y$}\rangle\geq 0\ \mbox{for every }\mbox{\boldmath$X$}\in\mathbb{C}\}$ of a cone $\mathbb{C}$ always forms a closed convex cone in $\mathbb{V}$ . Let $\mathbb{C}$ be a convex cone in $\mathbb{V}$ . A convex cone $\mathbb{F}\subset\mathbb{C}$ is a face of $\mathbb{C}$ if $\mbox{\boldmath$X$}^{k}\in\mathbb{F}$ $(1\leq k\leq m)$ whenever $\mbox{\boldmath$X$}=\sum_{k=1}^{m}\mbox{\boldmath$X$}^{k}\in\mathbb{F}$ and $\mbox{\boldmath$X$}^{k}\in\mathbb{C}$ $(1\leq k\leq m)$ . An extreme ray of $\mathbb{C}$ is a face which spans a $1$ -dimensional linear subspace of $\mathbb{V}$ .

2 Some remaining issues

In this section, we discuss issues (a) and (b) and (c) mentioned in Section 1.

2.1 The feasibility preserving property - (a)

The property that the nonconvex problem is feasible iff its convex relaxation is feasible is called feasibility preserving. This property was fully studied in [27] for convex relaxation of nonconvex QOPs. We present a simple proof that our geometric framework is feasibility preserving.

Lemma 2.1.

Let $\mathbb{C}$ be a nonempty cone in $\mathbb{V}$ . COP $(\mathbb{C})$ is feasible (infeasible, respectively) iff COP $(\mbox{co}\mathbb{C})$ is feasible (infeasible, respectively).

Proof.

It suffices to show that if COP(co $\mathbb{C}$ ) is feasible, then COP( $\mathbb{C}$ ) is feasible. Let $\overline{\mbox{\boldmath$X$}}$ be a feasible solution of COP(co $\mathbb{C}$ ). Then, there exist $\mbox{\boldmath$X$}_{k}\in\mathbb{C}$ $(1\leq k\leq m)$ such that $\overline{\mbox{\boldmath$X$}}=\sum_{k=1}^{m}\mbox{\boldmath$X$}_{k}$ . Since $1=\langle\mbox{\boldmath$H$},\,\overline{\mbox{\boldmath$X$}}\rangle=\langle\mbox{\boldmath$H$},\,\sum_{k=1}^{m}\mbox{\boldmath$X$}_{k}\rangle$ , $\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}_{k}\rangle>0$ for some $k$ . Let $\widehat{\mbox{\boldmath$X$}}=\mbox{\boldmath$X$}_{k}/\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}_{k}\rangle$ . Then $\widehat{\mbox{\boldmath$X$}}\in\mathbb{C}$ and $\langle\mbox{\boldmath$H$},\,\widehat{\mbox{\boldmath$X$}}\rangle=1$ . Hence $\widehat{\mbox{\boldmath$X$}}$ is a feasible solution of COP( $\mathbb{C}$ ). ∎

By Lemma 2.1, we can weaken Condition (A).

(A)’: $\mathbb{K}$ is a nonempty (not necessarily convex) cone in $\mathbb{V}$ .

Corollary 2.2.

Assume Conditions (A)’ and (B). Then (6) holds.

Proof.

If $-\infty<\zeta_{p}(\mathbb{J})<\infty$ , then $-\infty<\zeta_{p}(\mathbb{J})\leq\zeta_{p}(\mathbb{K}\cap\mathbb{J})<\infty$ holds by Lemma 2.1. Hence Condition (A) is satisfied. Therefore, (6) holds by Theorem 1.1. ∎

By the corollary and the lemma above, we know under Conditions (A)’ and (B) that if COP $(\mathbb{J})$ attains the finite optimal value $\zeta_{p}(\mathbb{J})$ , then $\zeta_{p}(\mathbb{K}\cap\mathbb{J})=\zeta_{p}(\mathbb{J})$ , and that if COP $(\mathbb{J})$ is infeasible, then so is COP $(\mathbb{K}\cap\mathbb{J})$ .

2.2 Strong duality of COP( $\mathbb{J}$ ) - (b)

As a straightforward application of [14, Theorem 2.1] to the primal-dual pair COP( $\mathbb{J}$ ) and DCOP( $\mathbb{J}$ ) with $\mbox{\boldmath$H$}\in\mathbb{J}^{*}$ , we obtain Theorem 2.3 below. Here the dual of COP $(\mathbb{J})$ is given by

\displaystyle\mbox{DCOP$(\mathbb{J})$:}\ \zeta_{d}(\mathbb{J})=\sup\{t:\mbox{\boldmath$Q$}-\mbox{\boldmath$H$}t\in\mathbb{J}^{*}\}.

(8)

Theorem 2.3.

Assume that $\mathbb{J}$ is a closed convex cone in $\mathbb{V}$ , $\mbox{\boldmath$H$}\in\mathbb{J}^{*}$ and that $-\infty<\zeta_{p}(\mathbb{J})<\infty$ or $-\infty<\zeta_{d}(\mathbb{J})<\infty$ . Then the following assertions hold.

: (i) $-\infty<\zeta_{p}(\mathbb{J})=\zeta_{d}(\mathbb{J})<\infty$ holds.
: (ii) Dual DCOP( $\mathbb{J}$ ) has an optimal solution.
: (iii) The set of optimal solutions of primal COP( $\mathbb{J}$ ) is nonempty and bounded iff $\mbox{\boldmath$Q$}-\mbox{\boldmath$H$}t\in\mbox{int}\mathbb{J}^{*}$ for some $t\in\mathbb{R}$ .
: (iv) The set of optimal solutions of primal COP( $\mathbb{J}$ ) is nonempty and unbounded if $\mathbb{J}$ is not pointed and $\mbox{\boldmath$Q$}-\mbox{\boldmath$H$}t\in\mbox{relint}\mathbb{J}^{*}$ for some $t\in\mathbb{R}$ , where $\mbox{relint}\mathbb{J}^{*}$ denotes the relative interior of $\mathbb{J}^{*}$ with respect to the linear subspace of $\mathbb{V}$ spanned by $\mathbb{J}^{*}$ .

We note that the condition “ $\mathbb{J}$ is closed” is natural when the existence of an optimal solution of COP( $\mathbb{J}$ ) is discussed, and the condition $\mbox{\boldmath$H$}\in\mathbb{J}^{*}$ holds naturally when QCQPs and POPs are converted into COP( $\mathbb{K}\cap\mathbb{J}$ ). See [15, Sections 3.2, 4 and 5].

2.3 Existence of a common optimal solution of COP( $\mathbb{J}$ ) and COP( $\mathbb{K}\cap\mathbb{J}$ ) - (c)

If $X$ is an optimal solution of COP( $\mathbb{K}\cap\mathbb{J}$ ), then the identity $\zeta_{p}(\mathbb{K}\cap\mathbb{J})=\zeta_{p}(\mathbb{J})$ ensures that $X$ is also an optimal solution of COP( $\mathbb{J}$ ) since $\mathbb{K}\cap\mathbb{J}\subseteq\mathbb{J}$ . In general, however, a nonconvex (or even convex) COP may have no optimal solution even when it has a finite optimal value. See, for example, [13, Section 4]. The following theorem provides a sufficient condition for a common optimal solution of COP( $\mathbb{K}\cap\mathbb{J}$ ) and COP( $\mathbb{J}$ ).

Theorem 2.4.

Assume that $\mathbb{K}$ is a closed cone in $\mathbb{V}$ , $\mathbb{J}\subseteq\mbox{co}\mathbb{K}$ is a closed convex cone satisfying co $(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ , COP $(\mathbb{K}\cap\mathbb{J})$ is feasible, $\mbox{\boldmath$H$}\in\mathbb{J}^{*}$ , and that $\mbox{\boldmath$Q$}-\mbox{\boldmath$H$}t\in\mbox{int}\mathbb{J}^{*}$ (the interior of $\mathbb{J}^{*}$ ) for some $t\in\mathbb{R}$ . Then,

\displaystyle\left.\begin{array}[]{l}-\infty<\zeta_{d}(\mathbb{J})=\zeta_{p}(\mathbb{J})=\zeta_{p}(\mathbb{K}\cap\mathbb{J})<\infty,\\[3.0pt] \mbox{COP$(\mathbb{K}\cap\mathbb{J})$ and COP$(\mathbb{J})$ have a common optimal solution,}\\[3.0pt] \mbox{DCOP$(\mathbb{J})$ has an optimal solution.}\end{array}\right\}

(12)

The strict feasibility of DCOP $(\mathbb{J})$ (i.e., Slater’s constraint qualification $\mbox{\boldmath$Q$}-\mbox{\boldmath$H$}t\in\mbox{int}\mathbb{J}^{*}$ for some $t$ ) is assumed here for the existence of solutions of COP $(\mathbb{K}\cap\mathbb{J})$ and COP $(\mathbb{J})$ . It should be emphasized that none of the finite optimal values for COP $(\mathbb{K}\cap\mathbb{J})$ , COP $(\mathbb{J})$ and DCOP $(\mathbb{J})$ is assumed in advance.

Proof of Theorem 2.4. We prove that COP( $\mathbb{J}$ ) and COP( $\mathbb{K}\cap\mathbb{J}$ ) have a common optimal solution $\mbox{\boldmath$X$}^{*}$ . Choose a feasible solution $\overline{\mbox{\boldmath$X$}}\in\mathbb{K}\cap\mathbb{J}$ of COP( $\mathbb{K}\cap\mathbb{J}$ ). We consider the level sets of COP( $\mathbb{K}\cap\mathbb{J}$ ) and COP( $\mathbb{J}$ ) given by

	$\displaystyle S(\mathbb{K}\cap\mathbb{J})$	$\displaystyle\equiv$	$\displaystyle\left\{\mbox{\boldmath$X$}\in\mathbb{K}\cap\mathbb{J}:\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}\rangle=1,\ \langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}\rangle\leq\langle\mbox{\boldmath$Q$},\,\overline{\mbox{\boldmath$X$}}\rangle\right\},$
	$\displaystyle S(\mathbb{J})$	$\displaystyle\equiv$	$\displaystyle\left\{\mbox{\boldmath$X$}\in\mathbb{J}:\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}\rangle=1,\ \langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}\rangle\leq\langle\mbox{\boldmath$Q$},\,\overline{\mbox{\boldmath$X$}}\rangle\right\}.$

Then $\overline{\mbox{\boldmath$X$}}\in S(\mathbb{K}\cap\mathbb{J})\subseteq S(\mathbb{J})$ . Since $\mathbb{K}$ and $\mathbb{J}$ are closed, both $S(\mathbb{K}\cap\mathbb{J})$ and $S(\mathbb{J})$ are closed. We will show that $S(\mathbb{J})$ is bounded. Assume on the contrary that $S(\mathbb{J})$ is unbounded. Then, there exists a sequence $\{\mbox{\boldmath$X$}_{k}\in S(\mathbb{J})\}$ such that $\parallel\mbox{\boldmath$X$}_{k}\parallel\rightarrow\infty$ as $k\rightarrow\infty$ . We may assume without loss of generality that $\mbox{\boldmath$X$}_{k}/\parallel\mbox{\boldmath$X$}_{k}\parallel\in\mathbb{J}$ converges to $\Delta\mbox{\boldmath$X$}\in\mathbb{J}$ such that

\displaystyle\Delta\mbox{\boldmath$X$}\in\mathbb{J},\ \parallel\Delta\mbox{\boldmath$X$}\parallel=1,\ \langle\mbox{\boldmath$H$},\,\Delta\mbox{\boldmath$X$}\rangle=0,\ \langle\mbox{\boldmath$Q$},\,\Delta\mbox{\boldmath$X$}\rangle\leq 0.

By $O\not=\Delta\mbox{\boldmath$X$}\in\mathbb{J}$ and the assumption that $\mbox{\boldmath$Q$}-\mbox{\boldmath$H$}t\in\mbox{int}\mathbb{J}^{*}$ for some $t\in\mathbb{R}$ , we see that

\displaystyle 0

\displaystyle<

\displaystyle\langle\mbox{\boldmath$Q$}-\mbox{\boldmath$H$}t,\,\Delta\mbox{\boldmath$X$}\rangle=\langle\mbox{\boldmath$Q$},\,\Delta\mbox{\boldmath$X$}\rangle-\langle\mbox{\boldmath$H$},\,\Delta\mbox{\boldmath$X$}\rangle t\leq 0,

which is a contradiction. Hence we have shown that both $S(\mathbb{J})$ and $S(\mathbb{K}\cap\mathbb{J})$ are nonempty closed and bounded. Therefore, both COP( $\mathbb{J}$ ) and COP( $\mathbb{K}\cap\mathbb{J}$ ) have optimal solutions, say $\widehat{\mbox{\boldmath$X$}}$ and $\mbox{\boldmath$X$}^{*}$ , respectively. It follows that $-\infty<\zeta_{p}(\mathbb{J})\leq\zeta_{p}(\mathbb{K}\cap\mathbb{J})=\langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}^{*}\rangle<\infty$ . Since the equivalence relation (6) holds by Corollary 2.2, we see that $\zeta_{p}(\mathbb{J})=\zeta_{p}(\mathbb{K}\cap\mathbb{J})=\langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}^{*}\rangle.$ Therefore, $\mbox{\boldmath$X$}^{*}$ is a common optimal solution of COP( $\mathbb{J}$ ) and COP( $\mathbb{K}\cap\mathbb{J}$ ). All other assertions in (12) follow from Theorem 2.3. ∎

3 On Condition (B)

If $\mathbb{J}$ is a face of co $\mathbb{K}$ or the convex hull of the union of a family of faces of co $\mathbb{K}$ , then Condition (B) holds. The former case was studied throughly in [15] for its applications to convex conic reformulation of QOPs and POPs. In this section, we further investigate fundamental properties of Condition (B).

To characterize Condition (B), we define

\displaystyle\widehat{\mbox{$\cal F$}}(\mathbb{K})

\displaystyle=

\displaystyle\left\{\mathbb{J}:\begin{array}[]{l}\mathbb{J}\ \mbox{satisfies Condition (B)},\ {\it i.e.},\\ \mbox{$\mathbb{J}$ is a convex cone in co$\mathbb{K}$ satisfying co$(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$}\end{array}\right\}.

(15)

3.1 Illustrative examples

We show $4$ examples of $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K}_{r})$ for $\mathbb{K}_{r}$ $(r=1,2)$ whose convex hull forms a common semicircular cone in the $3$ -dimensional space in Figure 2, where a $2$ -dim. section of $\mathbb{K}_{r}$ is illustrated $(r=1,2)$ . We identify a set $S$ on the $2$ -dim. section of co $\mathbb{K}_{r}$ with the 3-dim. cone $S=\{(\lambda,\lambda\mbox{\boldmath$X$}):\mbox{\boldmath$X$}\in S,\ \lambda\geq 0\}$ (the cone generated by $S$ ). In particular, an extreme point (or a $1$ -dimensional face, respectively) of the section of co $\mathbb{K}_{r}$ corresponds to an extreme ray (or a $2$ -dimensional face, respectively) of the semicircular cone co $\mathbb{K}_{r}$ . $\mathbb{K}_{1}$ consists of all extreme rays of the semicircular cone, which correspond to the half circle. $\mathbb{K}_{2}$ includes the 2-dim. face of the semicircular cone, which corresponds to the line segment $[\mbox{\boldmath$e$},\mbox{\boldmath$f$}]$ , in addition to all extreme rays. Note that the common $\mathbb{K}=\mathbb{K}_{1}$ is used for Examples 3.1, 3.2 and 3.3, and $\mathbb{K}=\mathbb{K}_{2}$ for Example 3.4. In each example, it is easy to verify that assertions (i), (ii) and (iii) of Theorem 3.5 with $\mathbb{K}=\mathbb{K}_{r}$ hold.

Example 3.1.

If we choose $3$ distinct extreme points $\mbox{\boldmath$a$},\ \mbox{\boldmath$b$},\ \mbox{\boldmath$c$}$ on the half circle as in Figure 2 (a), their convex hull $\mathbb{J}_{1}\in\widehat{\mbox{$\cal F$}}(\mathbb{K}_{1})$ forms a closed polyhedral cone. Letting $\mathbb{C}_{1}=\mbox{cone}(\{\mbox{\boldmath$a$},\ \mbox{\boldmath$b$},\ \mbox{\boldmath$c$}\})$ , we can write $\mathbb{J}_{1}=\mbox{co}(\mathbb{C}_{1})$ .

Example 3.2.

Let $\mathbb{C}_{2}$ be the cone generated by the union of all extreme points contained in the arc $a$ to $b$ along the half circle and an extreme point $c$ (see Figure 2 (b)), their convex hull $\mathbb{J}_{2}=\mbox{co}(\mathbb{C}_{2})$ forms a non-polyhedral closed convex cone. We see that $\mathbb{J}_{2}\in\widehat{\mbox{$\cal F$}}(\mathbb{K}_{1})$ .

Example 3.3.

We modify Example 3.2 by letting $\mathbb{C}_{3}=\mathbb{C}_{2}\backslash\mbox{cone}(\{\mbox{\boldmath$b$}\})$ as in Figure 2 (c). Then $\mathbb{J}_{3}=\mbox{co}(\mathbb{C}_{3})\in\widehat{\mbox{$\cal F$}}(\mathbb{K}_{1})$ . In this case, $\mathbb{J}_{3}$ is not closed. Hence, this example shows that $\widehat{\mbox{$\cal F$}}(\mathbb{K}_{1})$ contains non-closed convex cone in general.

Example 3.4.

In this example, $\mathbb{K}_{2}$ includes the $2$ -dim. face of co $\mathbb{K}_{2}$ , which corresponds to the line segment $[\mbox{\boldmath$e$},\mbox{\boldmath$f$}]$ of its section as in Figure 2 (d). Let $\mathbb{C}_{4}$ be the cone generated by the union of all extreme points contained in the arc $a$ to $b$ along the half circle and the semi-closed interval $(\mbox{\boldmath$d$},\mbox{\boldmath$c$}]$ on $[\mbox{\boldmath$e$},\mbox{\boldmath$f$}]$ . Then $\mathbb{J}_{4}=\mbox{co}(\mathbb{C}_{4})\in\widehat{\mbox{$\cal F$}}(\mathbb{K}_{2})$ . It should be noted that $\mathbb{J}_{4}\in\widehat{\mbox{$\cal F$}}(\mathbb{K}_{2})$ cannot be generated in Examples 3.1, 3.2 and 3.3 since the $2$ -dim. face cone $([\mbox{\boldmath$e$},\mbox{\boldmath$f$}])$ is not included in $\mathbb{K}_{1}$ .

3.2 Basic properties on $\widehat{\mbox{$\cal F$}}(\mathbb{K})$

We now show some fundamental properties on $\widehat{\mbox{$\cal F$}}(\mathbb{K})$ including the ones observed in the examples above. For a family $\cal S$ of subsets of $\mathbb{V}$ and a subset $T$ of $\mathbb{V}$ , we use notation $\bigcup\mbox{$\cal S$}$ to denotes the union of all $U\in\mbox{$\cal S$}$ , i.e., $\bigcup\mbox{$\cal S$}=\bigcup_{U\in\mbox{\scriptsize$\mbox{$\cal S$}$}}U$ , and $T\cap\mbox{$\cal S$}$ to denote $\{T\cap U:U\in\mbox{$\cal S$}\}$ .

Theorem 3.5.

The following assertions hold.

: (i) $\mathbb{F}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ for every face $\mathbb{F}$ of $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .
: (ii) $\mathbb{J}\cap\mathbb{F}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ for every face $\mathbb{F}$ of co $\mathbb{K}$ and $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .
: (iii) $\mathbb{F}\subseteq\mathbb{K}$ for every extreme ray $\mathbb{F}$ of $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .
: (iv) $\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\subseteq\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}\subseteq\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ for every $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .
: (v) $\mbox{co}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))=\mbox{co}(\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})=\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ (hence $\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ ) for every $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .

Proof of Theorem 3.5 (i): Let $\mathbb{F}$ be a face of $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . co $(\mathbb{K}\cap\mathbb{F})\subseteq\mathbb{F}$ is obvious. To show the converse inclusion relation, let $\mbox{\boldmath$X$}\in\mathbb{F}\subseteq\mathbb{J}=\mbox{co}(\mathbb{K}\cap\mathbb{J})$ . Then $\mbox{\boldmath$X$}=\sum_{k=1}^{m}\mbox{\boldmath$X$}_{k}$ for some $\mbox{\boldmath$X$}_{k}\in\mathbb{K}\cap\mathbb{J}$ $(1\leq k\leq m)$ . Since $\mathbb{F}$ is a face of $\mathbb{J}$ , $\mbox{\boldmath$X$}_{k}\in\mathbb{F}$ $(1\leq k\leq m)$ . Hence, $\mbox{\boldmath$X$}\in\mbox{co}(\mathbb{K}\cap\mathbb{F})$ , and we have shown that co $(\mathbb{K}\cap\mathbb{F})\supset\mathbb{F}$ . ∎

Obviously co $\mathbb{K}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Taking $\mathbb{J}=\mbox{co}\mathbb{K}$ in (i), we see that $\mathbb{F}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ for every face $\mathbb{F}$ of co $\mathbb{K}$ . In particular, every extreme ray of co $\mathbb{K}$ is in $\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .

Proof of Theorem 3.5 (ii): Assume that $\mathbb{F}$ is a face of co $\mathbb{K}$ and $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Then $\mathbb{J}\cap\mathbb{F}$ is a convex cone and $\mathbb{K}\cap\mathbb{J}\cap\mathbb{F}\subseteq\mathbb{J}\cap\mathbb{F}$ . Hence co $(\mathbb{K}\cap\mathbb{J}\cap\mathbb{F})\subseteq\mathbb{J}\cap\mathbb{F}$ follows. To show the converse inclusion co $(\mathbb{K}\cap\mathbb{J}\cap\mathbb{F})\supset\mathbb{J}\cap\mathbb{F}$ , suppose that $\mbox{\boldmath$X$}\in\mathbb{J}\cap\mathbb{F}$ . Since $\mathbb{J}=\mbox{co}(\mathbb{K}\cap\mathbb{J})$ by assumption, $\mathbb{F}\ni\mbox{\boldmath$X$}=\sum_{k=1}^{m}\mbox{\boldmath$X$}_{k}$ for some $\mbox{\boldmath$X$}_{k}\in\mathbb{K}\cap\mathbb{J}\subseteq\mbox{co}\mathbb{K}$ $(1\leq k\leq m)$ . Since $\mathbb{F}$ is a face of co $\mathbb{K}$ , $\mbox{\boldmath$X$}_{k}\in\mathbb{F}$ $(1\leq k\leq m)$ . Hence $\mbox{\boldmath$X$}=\sum_{k=1}^{m}\mbox{\boldmath$X$}_{k}\in\mbox{co}(\mathbb{K}\cap\mathbb{J}\cap\mathbb{F})$ . Thus, we have shown co $(\mathbb{K}\cap\mathbb{J}\cap\mathbb{F})=\mathbb{J}\cap\mathbb{F}$ and $\mathbb{J}\cap\mathbb{F}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .∎

Proof of Theorem 3.5 (iii): Assume that $\mathbb{F}$ is an extreme ray of $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . To show $\mathbb{F}\subseteq\mathbb{K}$ , choose an arbitrary nonzero $\mbox{\boldmath$X$}\in\mathbb{F}$ . Then, $\mbox{\boldmath$X$}\in\mathbb{F}\subseteq\mathbb{J}=\mbox{co}(\mathbb{K}\cap\mathbb{J})$ is represented as $\mbox{\boldmath$X$}=\sum_{k=1}^{m}\mbox{\boldmath$X$}_{k}$ for some nonzero $\mbox{\boldmath$X$}_{k}\in\mathbb{K}\cap\mathbb{J}$ $(k=1,\ldots,m)$ . Since $\mathbb{F}$ is an extreme ray of $\mathbb{J}$ , nonzero $\mbox{\boldmath$X$}_{k}$ $(1\leq k\leq m)$ all lie in the extreme ray $\mathbb{F}$ . Hence, $\mbox{\boldmath$X$}=\lambda_{k}\mbox{\boldmath$X$}_{k}$ for some $\lambda_{k}>0$ $(1\leq k\leq m)$ . Let $k$ be arbitrarily fixed. Since $\mathbb{K}$ is a cone and $\mbox{\boldmath$X$}_{k}\in\mathbb{K}$ , $\mbox{\boldmath$X$}=\lambda_{k}\mbox{\boldmath$X$}_{k}\in\mathbb{K}$ . Thus, we have shown $\mathbb{F}\subseteq\mathbb{K}$ . ∎

Proof of Theorem 3.5 (iv): Assume that $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Let $\mbox{\boldmath$X$}\in\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ . Then, there exists a $\mathbb{J}\in\mbox{$\cal F$}$ such that $\mbox{\boldmath$X$}\in\mathbb{K}\cap\mathbb{J}$ , which implies that $\mbox{\boldmath$X$}\in\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ . Hence, $\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\subseteq\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ holds. The second inclusion relation is straightforward. ∎

Proof of Theorem 3.5 (v): Assume that $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . By (iv), it suffices to show that co $(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))\supset\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ . By assumption, $\mbox{co}\big{(}\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\big{)}\supset\mbox{co}(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ for every $\mathbb{J}\in\mbox{$\cal F$}$ . Hence, $\mbox{co}\big{(}\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\big{)}\supset\bigcup\mbox{$\cal F$}$ follows. Since $\mbox{co}\big{(}\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\big{)}$ is a convex cone, we obtain that $\mbox{co}\big{(}\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\big{)}\supset\mbox{co}(\bigcup\mbox{$\cal F$})$ . ∎

3.3 Proof of Theorem 1.2

‘only if part’ of (i): Assume that $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Let $\mathbb{K}^{\prime}=\mathbb{K}\cap\mathbb{J}$ . Then, $\mathbb{K}^{\prime}$ is a cone in $\mathbb{K}$ and $\mathbb{J}=\mbox{co}\big{(}\mathbb{K}\cap\mathbb{J}\big{)}=\mbox{co}\mathbb{K}^{\prime}$ .

‘if part’ of (i): Assume that $\mathbb{J}=\mbox{co}\mathbb{K}^{\prime}$ for some cone $\mathbb{K}^{\prime}\subseteq\mathbb{K}$ . Since $\mathbb{J}$ is convex, we obviously see that $\mbox{co}\big{(}\mathbb{K}\cap\mathbb{J}\big{)}\subseteq\mathbb{J}$ . We also see from $\mathbb{K}^{\prime}\subseteq\mathbb{K}$ and $\mbox{co}\mathbb{K}^{\prime}=\mathbb{J}$ that $\mathbb{K}^{\prime}=\mathbb{K}^{\prime}\cap\mbox{co}\mathbb{K}^{\prime}\subseteq\mathbb{K}\cap\mathbb{J}$ . Hence $\mathbb{J}=\mbox{co}\mathbb{K}^{\prime}\subseteq\mbox{co}\big{(}\mathbb{K}\cap\mathbb{J}\big{)}$ . Therefore, we have shown $\mbox{co}\big{(}\mathbb{K}\cap\mathbb{J}\big{)}=\mathbb{J}$ and $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .

‘only if part’ of (ii): Assume that $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Let $\mbox{$\cal F$}=\{\mathbb{J}\}$ . Then, $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ and $\mathbb{J}=\mbox{co}\mathbb{J}=\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ holds since $\mathbb{J}$ is convex.

‘if part’ of (ii): Assume that $\mathbb{J}=\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ for some $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Then, $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ follows from Theorem 3.5 (v).

Since $\mathbb{J}\subseteq\mbox{co}\mathbb{K}$ and $\mbox{\boldmath$H$}\in\mbox{int}\mathbb{K}^{*}$ by the assumption, the feasible region $\{\mbox{\boldmath$X$}\in\mathbb{K}\cap\mathbb{J}:\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}\rangle=1\}$ of COP( $\mathbb{K}\cap\mathbb{J}$ ), the feasible region $\{\mbox{\boldmath$X$}\in\mathbb{J}:\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}\rangle=1\}$ of COP( $\mathbb{J}$ ) and the feasible region $S\equiv\{\mbox{\boldmath$X$}\in\mbox{co}(\mathbb{K}\cap\mathbb{J}):\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}\rangle=1\}$ of COP( $\mbox{co}(\mathbb{K}\cap\mathbb{J})$ ) are all bounded and closed.

‘only if part’ of (iii): Assume that $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Let $Q$ , arbitrarily chosen from $\mathbb{V}$ , be fixed. The feasible region of COP $(\mathbb{J})$ is either empty, or closed and bounded. If it is empty, then $\zeta_{p}(\mathbb{J})=\zeta_{p}(\mathbb{K}\cap\mathbb{J})=\infty$ . Otherwise, it is nonempty, closed and bounded. Hence, $-\infty<\zeta_{p}(\mathbb{J})<\infty$ . Therefore, Conditions (A)’ and (B) hold, and $\zeta_{p}(\mathbb{K}\cap\mathbb{J})=\zeta_{p}(\mathbb{J})$ follows from Corollary 2.2.

‘if part’ of (iii): Assuming $\mathbb{J}\not\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ , we show that $-\infty<\zeta_{p}(\mathbb{J})<\zeta_{p}(\mathbb{K}\cap\mathbb{J})<\infty$ for some $\mbox{\boldmath$Q$}\in\mathbb{V}$ . It follows from $\mathbb{J}\not\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ that the convex cone $\mbox{co}(\mathbb{K}\cap\mathbb{J})$ is a proper subset of the closed convex cone $\mathbb{J}$ . Hence, there exists a nonzero $\overline{\mbox{\boldmath$X$}}\in\mathbb{J}\backslash\big{(}\mbox{co}(\mathbb{K}\cap\mathbb{J})\big{)}\subseteq\mbox{co}\mathbb{K}$ . Let $\widetilde{\mbox{\boldmath$X$}}=\overline{\mbox{\boldmath$X$}}/\langle\mbox{\boldmath$H$},\,\overline{\mbox{\boldmath$X$}}\rangle\in\mathbb{J}\backslash\big{(}\mbox{co}(\mathbb{K}\cap\mathbb{J})\big{)}\subseteq\mbox{co}\mathbb{K}$ . Then, $\widetilde{\mbox{\boldmath$X$}}$ is a feasible solution of COP $(\mathbb{J})$ but not in the bounded and closed feasible region $S=\{\mbox{\boldmath$X$}\in\mbox{co}\big{(}\mathbb{K}\cap\mathbb{J}):\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}\rangle=1\}$ of COP( $\mbox{co}(\mathbb{K}\cap\mathbb{J})$ ). By the separation theorem of convex sets (see, for example, [21, Theorem 11.4.1]), there exist $\mbox{\boldmath$Q$}\in\mathbb{V}$ such that $\langle\mbox{\boldmath$Q$},\,\widetilde{\mbox{\boldmath$X$}}\rangle<\inf\{\langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}\rangle:\mbox{\boldmath$X$}\in S\}=\zeta_{p}(\mbox{co}(\mathbb{K}\cap\mathbb{J}))$ . Therefore, we obtain that

\displaystyle-\infty<\zeta_{p}(\mathbb{J})\leq\langle\mbox{\boldmath$Q$},\,\widetilde{\mbox{\boldmath$X$}}\rangle<\zeta_{p}(\mbox{co}(\mathbb{K}\cap\mathbb{J}))\leq\zeta_{p}(\mathbb{K}\cap\mathbb{J}).

∎

Given a convex cone $\mathbb{C}$ , there are various ways to represent $\mathbb{C}$ as the convex hull of a nonconvex cone. For example, when the convex cone $\mathbb{C}$ is closed and pointed, $\mathbb{C}$ can be represented as the convex hull of the nonconvex cone consisting of the extreme rays of $\mathbb{C}$ [21, Theorem 18.5]. However, any face of $\mathbb{C}$ can be added to the nonconvex cone. Thus, the representation of $\mathbb{C}$ in terms of the convex hull of a nonconvex cone $\mathbb{K}$ is not unique. Theorem 1.2 (i) shows the possibility of the ‘finest’ representation of $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ , and (ii) the possibility of various coarse representations of $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . A similar observation can be applied to co $\mathbb{K}$ ; two distinct nonconvex cones $\mathbb{K}_{1}\subseteq\mathbb{V}$ and $\mathbb{K}_{2}\subseteq\mathbb{V}$ induce a common convex cone as their convex hull, co $\mathbb{K}_{1}=\mbox{co}\mathbb{K}_{2}$ , such that $\widehat{\mbox{$\cal F$}}(\mathbb{K}_{1})\not=\widehat{\mbox{$\cal F$}}(\mathbb{K}_{2})$ . This fact has been observed in Examples 3.4.

3.4 Decompositions of COP $(\mathbb{K}\cap\mathbb{J})$

We now focus on Theorems 3.5 (v) and 1.2 (ii). Let $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Assume that $\mathbb{J}$ is decomposed into $\mathbb{F}\in\mbox{$\cal F$}\subseteq$ for some $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ such that $\mathbb{J}=\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ as in Theorem 1.2 (ii). In general, $\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ could be a proper subset of $\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ by Theorem 3.5 (iv). By Theorem 3.5 (v), however, their convex hulls coincide with each other, and COP(co $(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))$ ) and COP(co $(\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})$ ) both induce a common convex relaxation, COP( $\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ ). We also know that each $\mathbb{F}\in\mbox{$\cal F$}$ satisfies co $(\mathbb{K}\cap\mathbb{F})=\mathbb{F}$ ; hence COP $(\mathbb{F})$ is a convex relaxation of COP $(\mathbb{K}\cap\mathbb{F})$ . The following theorem summarizes the relations of the three pairs of COPs and their convex conic relaxation, COP( $\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ ) and COP( $\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ ), COP( $\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ ) and COP( $\mbox{co}\big{(}\bigcup\mbox{$\cal F$})$ ), and COP( $\mathbb{K}\cap\mathbb{F}$ ) and COP( $\mathbb{F}$ ) ( $\mathbb{F}\in\mbox{$\cal F$}$ ). In particular, assertion (iii) of the theorem means that COP $(\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})$ can be decomposed into the family of subproblems COP $(\mathbb{K}\cap\mathbb{F})$ , which is reformulated by COP $(\mathbb{F})$ , $(\mathbb{F}\in\mbox{$\cal F$})$ .

Theorem 3.6.

Assume that $\mbox{$\cal F$}\subseteq\widehat{\mbox{$\cal F$}}(\mathbb{K})$ and that $-\infty<\zeta_{p}(\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})<\infty$ . Then, the following assertions hold.

: (i) $\zeta_{p}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))=\zeta_{p}(\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})=\zeta_{p}(\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})$ .
: (ii) $\zeta_{p}(\mathbb{K}\cap\mathbb{F})=\zeta_{p}(\mathbb{F})$ $(\mathbb{F}\in\mbox{$\cal F$})$ .
: (iii) $\zeta_{p}(\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})=\inf\{\zeta_{p}(\mathbb{K}\cap\mathbb{F}):\mathbb{F}\in\mbox{$\cal F$}\}=\inf\{\zeta_{p}(\mathbb{F}):\mathbb{F}\in\mbox{$\cal F$}\}$ .

Proof.

(i) The pair of $\mathbb{K}$ and $\mathbb{J}=\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ satisfies Condition (A) by Lemma 2.1, and Condition (B) by Theorem 3.5 (v). Hence $-\infty<\zeta_{p}(\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})=\zeta_{p}(\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})<\infty$ by Theorem 1.1. We now prove the identity $\zeta_{p}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))=\zeta_{p}(\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})$ . First, we show that $-\infty<\zeta_{p}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))<\infty$ . Since $\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\subseteq\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ by Theorem 3.5 (iv), we see that $-\infty<\zeta_{p}(\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})\leq\zeta_{p}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))$ . It remains to show that COP( $\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ ) is feasible. By Condition (A), there exists a feasible solution $\overline{\mbox{\boldmath$X$}}$ of COP( $\mathbb{K}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ ), which satisfies $\overline{\mbox{\boldmath$X$}}\in\mathbb{K}$ , $\overline{\mbox{\boldmath$X$}}\in\mbox{co}(\bigcup\mbox{$\cal F$})$ and $\langle\mbox{\boldmath$H$},\,\overline{\mbox{\boldmath$X$}}\rangle=1$ . From $\overline{\mbox{\boldmath$X$}}\in\mbox{co}(\bigcup\mbox{$\cal F$})$ , there exist $\mbox{\boldmath$X$}^{k}\in\bigcup\mbox{$\cal F$}$ $(1\leq k\leq m)$ such that $\overline{\mbox{\boldmath$X$}}=\sum_{k=1}^{m}\mbox{\boldmath$X$}^{k}$ . Since $1=\langle\mbox{\boldmath$H$},\,\overline{\mbox{\boldmath$X$}}\rangle=\sum_{k=1}^{m}\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}^{k}\rangle$ , $\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}^{k}\rangle>0$ for some $k$ . Let $\widehat{\mbox{\boldmath$X$}}=\mbox{\boldmath$X$}^{k}/\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}^{k}\rangle$ . Then $\widehat{\mbox{\boldmath$X$}}\in\mathbb{K}\cap\mathbb{F}$ for some $\mathbb{F}\in\mbox{$\cal F$}$ and $\langle\mbox{\boldmath$H$},\,\widehat{\mbox{\boldmath$X$}}\rangle=1$ , which implies that $\widehat{\mbox{\boldmath$X$}}$ is a feasible solution of COP( $\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ ). Hence, we have shown that $-\infty<\zeta_{p}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))<\infty$ . Now, we observe that $\big{(}\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\big{)}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}=\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ and that co $\big{(}\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\big{)}\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}=\mbox{co}\big{(}\bigcup(\mathbb{K}\cap\mbox{$\cal F$})\big{)}=\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ by Theorem 3.5 (v). Therefore $\zeta_{p}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))=\zeta_{p}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))\cap\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})=\zeta_{p}(\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})$ follows from Theorem 1.1 with replacing $\mathbb{K}$ by $\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ and $\mathbb{J}$ by $\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ .

(ii) Let $\mathbb{F}\in\mbox{$\cal F$}$ be arbitrarily fixed. Then, co $(\mathbb{K}\cap\mathbb{F})=\mathbb{F}$ . By Lemma 2.1, if COP( $\mathbb{K}\cap\mathbb{F}$ ) is infeasible then $\zeta_{p}(\mathbb{K}\cap\mathbb{F})=\zeta_{p}(\mathbb{F})=\infty$ . Otherwise, COP( $\mathbb{F}$ ) is feasible; hence $\zeta_{p}(\mathbb{F})<\infty$ . We also see that $-\infty<\zeta_{p}(\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)})\leq\zeta_{p}(\mathbb{F})$ from $\mathbb{F}\subseteq\mbox{co}\big{(}\bigcup\mbox{$\cal F$}\big{)}$ . By applying Corollary 2.2 with replacing $\mathbb{J}$ by $\mathbb{F}$ , we obtain $\zeta_{p}(\mathbb{K}\cap\mathbb{F})=\zeta_{p}(\mathbb{F})$ .

(iii) By (i) and (ii), it suffices to show $\zeta_{p}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))=\inf\{\zeta_{p}(\mathbb{K}\cap\mathbb{F}):\mathbb{F}\in\mbox{$\cal F$}\}$ . Since $\mathbb{K}\cap\mathbb{F}\subseteq\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ for every $\mathbb{F}\in\mbox{$\cal F$}$ , we see $\zeta_{p}(\bigcup(\mathbb{K}\cap\mbox{$\cal F$}))\leq\inf\{\zeta_{p}(\mathbb{K}\cap\mathbb{F}):\mathbb{F}\in\mbox{$\cal F$}\}$ . To show the converse inequality, let $\overline{\mbox{\boldmath$X$}}$ be an arbitrary feasible solution of COP( $\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ ) with the objective value $\bar{\zeta}_{p}=\langle\mbox{\boldmath$Q$},\,\overline{\mbox{\boldmath$X$}}\rangle$ . Then $\langle\mbox{\boldmath$H$},\,\overline{\mbox{\boldmath$X$}}\rangle=1$ and $\overline{\mbox{\boldmath$X$}}\in\bigcup(\mathbb{K}\cap\mbox{$\cal F$})$ , i.e., $\overline{\mbox{\boldmath$X$}}\in\mathbb{K}\cap\overline{\mathbb{F}}$ for some $\overline{\mathbb{F}}\in\mbox{$\cal F$}$ . Hence $\overline{\mbox{\boldmath$X$}}$ is a feasible solution of COP( $\mathbb{K}\cap\overline{\mathbb{F}}$ ). Therefore, $\inf\{\zeta_{p}(\mathbb{K}\cap\mathbb{F}):\mathbb{F}\in\mbox{$\cal F$}\}\leq\zeta_{p}(\mathbb{K}\cap\overline{\mathbb{F}})\leq\bar{\zeta}_{p}.$ ∎

4 A class of quadratically constrained quadratic programs with multiple nonconvex constraints

Throughout this section, we assume that $\mathbb{K}=\{\mbox{\boldmath$x$}\mbox{\boldmath$x$}^{T}:\mbox{\boldmath$x$}\in\mathbb{R}^{n}\}$ , where $\mathbb{R}^{n}$ denotes the $n$ -dimensional linear space of column vectors $\mbox{\boldmath$x$}=(x_{1},\ldots,,x_{n})$ . Thus, co $\mathbb{K}$ forms the positive semidefinite cone $\mathbb{S}^{n}_{+}$ in the space $\mathbb{S}^{n}$ of $n\times n$ symmetric matrices. Let $\mathbb{J}\subseteq\mathbb{S}^{n}$ be a closed convex cone and $\mbox{\boldmath$Q$},\ \mbox{\boldmath$H$}\in\mathbb{S}^{n}$ . We use COP $(\mathbb{K}\cap\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ for COP $(\mathbb{K}\cap\mathbb{J})$ and $\zeta_{p}(\mathbb{K}\cap\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ for $\zeta_{p}(\mathbb{K}\cap\mathbb{J})$ to display their dependency on $\mbox{\boldmath$Q$}\in\mathbb{S}^{n}$ and $\mbox{\boldmath$H$}\in\mathbb{S}^{n}$ . Similarly, COP $(\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ for COP $(\mathbb{J})$ , $\zeta_{p}(\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ for $\zeta_{p}(\mathbb{J})$ , DCOP $(\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ for DCOP $(\mathbb{J})$ , and $\zeta_{d}(\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ for $\zeta_{d}(\mathbb{J})$ .

COP $(\mathbb{K}\cap\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ represents a general (or extended) quadratically constrained quadratic program (QCQP)

\displaystyle\zeta_{p}(\mathbb{K}\cap\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})

\displaystyle=

\displaystyle\inf\left\{\mbox{\boldmath$x$}^{T}\mbox{\boldmath$Q$}\mbox{\boldmath$x$}:\mbox{\boldmath$x$}\in\mathbb{R}^{n},\ \mbox{\boldmath$x$}\mbox{\boldmath$x$}^{T}\in\mathbb{J},\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1\right\},

and COP $(\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ its semidefinite programming (SDP) relaxation. Recall that Theorem 1.2 (i) states a necessary and sufficient condition

\mathbb{J}=\mbox{co}\mathbb{K}^{\prime}

for some cone

\mathbb{K}^{\prime}\subseteq\mathbb{K}=\cup\{\mbox{all extreme rays of }\mathbb{S}^{n}_{+}\}

for $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ , and Theorem 3.5 (iii) describes a necessary condition

every extreme ray of

\mathbb{J}

lies in

\mathbb{K}

for $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . See Figure 2 in Section 3. These two conditions are independent from the description of $\mathbb{J}$ . When applying to QCQPs, however, $\mathbb{J}$ is usually described in terms of inequalities $\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle\leq 0$ and/or equalities $\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle=0$ with $\mbox{\boldmath$B$}_{k}\in\mathbb{S}^{n}$ $(1\leq k\leq m)$ . In this section, we focus on the cases where $\mathbb{J}=\{\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}:\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle\leq 0\ (1\leq k\leq m)\}$ , and present a sufficient condition on $\mbox{\boldmath$B$}_{k}\in\mathbb{S}^{n}$ $(1\leq k\leq m)$ for $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . The condition should be sufficient for the above mentioned conditions to hold.

For each $\mbox{\boldmath$B$}\in\mathbb{S}^{n}$ , let

\displaystyle\mathbb{J}_{0}(\mbox{\boldmath$B$})=\{\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}:\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}\rangle=0\},\ \mathbb{J}_{-}(\mbox{\boldmath$B$})=\{\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}:\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}\rangle\leq 0\}.

Let $m$ be a nonnegative integer, $\mbox{\boldmath$Q$},\ \mbox{\boldmath$H$},\ \mbox{\boldmath$B$}_{1},\ldots,\mbox{\boldmath$B$}_{m}\in\mathbb{S}^{n}$ , and $\mathbb{J}_{-}=\cap_{k=1}^{m}\mathbb{J}_{-}(\mbox{\boldmath$B$}_{k})$ . We note that $\mathbb{J}_{-}=\mathbb{S}^{n}_{+}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ if $m=0$ . We consider COP $(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ and its convex relaxation COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ . We can rewrite COP $(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ as a QCQP:

\displaystyle\zeta_{p}(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})

\displaystyle=

\displaystyle\inf\left\{\mbox{\boldmath$x$}^{T}\mbox{\boldmath$Q$}\mbox{\boldmath$x$}:\begin{array}[]{l}\mbox{\boldmath$x$}\in\mathbb{R}^{n},\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$B$}_{k}\mbox{\boldmath$x$}\leq 0\ (1\leq k\leq m),\\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1\end{array}\right\}.

(18)

COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})$ serves as an SDP relaxation of the QCQP (18). We establish the following result.

Theorem 4.1.

Assume that

\displaystyle\mathbb{J}_{0}(\mbox{\boldmath$B$}_{k})\subseteq\mathbb{J}_{-}\equiv\cap_{\ell=1}^{m}\mathbb{J}_{-}(\mbox{\boldmath$B$}_{\ell})\ (1\leq k\leq m).

(19)

(Recall Figure 1 in Section 1). Then,

: (i) $\mathbb{J}_{-}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .
: (ii) Let $\mbox{\boldmath$Q$}\in\mathbb{S}^{n}$ and $\mbox{\boldmath$H$}\in\mathbb{S}^{n}$ . Then $-\infty<\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})=\zeta_{p}(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})<\infty$ iff $-\infty<\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})<\infty$ .

We provide some illustrative examples in Section 4.1, before presenting a proof of the theorem in Section 4.2. If $m=0$ or $1$ , then condition (19) obviously holds. The following proposition presents sufficient conditions for (19), which can be algebraically verified. In particular, condition (21) is used in the examples.

Proposition 4.2.

Suppose that $m\geq 2$ . If

\displaystyle-\mbox{\boldmath$B$}_{\ell}-\mbox{\boldmath$B$}_{k}\tau\in\mathbb{S}^{n}_{+}\ \mbox{for some }\tau\in\mathbb{R}\ (1\leq k,\ \ell\leq m,\ k\not=\ell),

(20)

where $\tau$ can depend on both $k$ and $\ell$ , or

\displaystyle\hskip 8.53581pt\;\;\;\langle\mbox{\boldmath$B$}_{k}+\mbox{\boldmath$B$}_{\ell},\,\mbox{\boldmath$X$}\rangle\leq 0\ \mbox{for every }\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}\ \mbox{or}-(\mbox{\boldmath$B$}_{k}+\mbox{\boldmath$B$}_{\ell})\in\mathbb{S}^{n}_{+}\ (1\leq k<\ell\leq m),

(21)

then (19) holds.

Proof.

Condition (20) can be rewritten as

\displaystyle-\mbox{\boldmath$B$}_{\ell}\in\mathbb{S}^{n}_{+}+\{\mbox{\boldmath$B$}_{k}\tau:\tau\in\mathbb{R}\}\ (1\leq k,\ \ell\leq m,\ k\not=\ell).

Also, condition (19) can be rewritten as

	$\displaystyle-\mbox{\boldmath$B$}_{\ell}\in\mathbb{J}_{0}(\mbox{\boldmath$B$}_{k})^{*}$	$\displaystyle=$	$\displaystyle\big{(}\mathbb{S}^{n}_{+}\cap\{\mbox{\boldmath$X$}\in\mathbb{S}^{n}:\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle=0\}\big{)}^{*}$
		$\displaystyle=$	$\displaystyle\mbox{cl}\big{(}\mathbb{S}^{n}_{+}+\{\mbox{\boldmath$B$}_{k}\tau:\tau\in\mathbb{R}\}\big{)}\ (1\leq k,\ \ell\leq m,\ k\not=\ell),$

where cl $C$ denotes the closure of $C\subseteq\mathbb{S}^{n}$ (see [17] for the second identity). Therefore (20) implies (19). Condition (21) is a special case of (20) with taking $\tau=1$ . Hence (21) implies (19). ∎

We note that (20) is not necessary for condition of (19). For example, take $n=m=2$ , $\mbox{\boldmath$B$}_{1}={\scriptsize\begin{pmatrix}1&1\\ 1&0\end{pmatrix}}$ and $\mbox{\boldmath$B$}_{2}={\scriptsize\begin{pmatrix}-1&0\\ 0&0\end{pmatrix}}$ . Then $-\mbox{\boldmath$B$}_{1}-\mbox{\boldmath$B$}_{2}\tau\not\in\mathbb{S}^{2}_{+}$ for any $\tau\in\mathbb{R}$ but

\displaystyle\mathbb{J}_{0}(\mbox{\boldmath$B$}_{1})\subseteq\mathbb{S}^{2}_{+}=\mathbb{J}_{-}(\mbox{\boldmath$B$}_{2}),\ \mathbb{J}_{0}(\mbox{\boldmath$B$}_{2})=\left\{\begin{pmatrix}0&0\\ 0&X_{22}\end{pmatrix}:X_{22}\geq 0\right\}\subseteq\mathbb{J}_{-}(\mbox{\boldmath$B$}_{1}).

Hence condition (19) holds. If $\tau\leq 0$ in (20), then $\langle\mbox{\boldmath$B$}_{\ell},\,\mbox{\boldmath$X$}\rangle\leq 0$ for every $\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}$ satisfying $\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle\leq 0$ ; hence the constraint $\langle\mbox{\boldmath$B$}_{\ell},\,\mbox{\boldmath$X$}\rangle\leq 0$ (or $\mathbb{J}_{-}(\mbox{\boldmath$B$}_{\ell})$ ) is redundant. If we assume that none of the constraints $\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle\leq 0$ $(1\leq k\leq m)$ is redundant, then we can take $\tau>0$ in (20)

In Section 4.3, we prove the following result.

Theorem 4.3.

Let $\mbox{\boldmath$B$}\in\mathbb{S}^{n}$ .

: (i) $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ and $\mathbb{J}_{-}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ are equivalent.
: (ii) $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .

In Section 4.4, we briefly discuss how multiple equality constraints can be added to QCQPs (18).

4.1 Some examples

We present six examples.

Example 4.4.

If $m=1$ , then (19) is satisfied for any $\mbox{\boldmath$B$}_{1}\in\mathbb{S}^{n}$ . Let $\mbox{\boldmath$Q$}_{0},\ \mbox{\boldmath$Q$}_{1},\ \mbox{\boldmath$Q$}_{2}\in\mathbb{S}^{\ell}$ . Consider the QCQP

\displaystyle\zeta_{\rm QCQP}

\displaystyle=

\displaystyle\inf\left\{\mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{0}\mbox{\boldmath$u$}:\mbox{\boldmath$u$}\in\mathbb{R}^{\ell},\mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{1}\mbox{\boldmath$u$}\leq 1,\ \mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{2}\mbox{\boldmath$u$}\leq 1\right\}.

(22)

This form of QCQP was studied in [19, 26]. They showed that QCQP (22) can be solved by its SDP relaxation under strong duality of its SDP relaxation, which is not assumed here. We can transform QCQP (22) into

$\displaystyle\eta_{\rm QCQP}$	$\displaystyle=$	$\displaystyle\inf\left\{\mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{0}\mbox{\boldmath$u$}:\begin{array}[]{l}\mbox{\boldmath$u$}\in\mathbb{R}^{\ell},\ u_{\ell+1}\in\mathbb{R},\\ \mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{1}\mbox{\boldmath$u$}\leq 1,\ \mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{2}\mbox{\boldmath$u$}+u_{\ell+1}^{2}=1\end{array}\right\}$
	$\displaystyle=$	$\displaystyle\inf\left\{\mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{0}\mbox{\boldmath$u$}:\begin{array}[]{l}\mbox{\boldmath$u$}\in\mathbb{R}^{\ell},\ u_{\ell+1}\in\mathbb{R},\\ \mbox{\boldmath$u$}^{T}(\mbox{\boldmath$Q$}_{1}-\mbox{\boldmath$Q$}_{2})\mbox{\boldmath$u$}-u_{\ell+1}^{2}\leq 0,\ \mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{2}\mbox{\boldmath$u$}+u_{\ell+1}^{2}=1\end{array}\right\}$
	$\displaystyle=$	$\displaystyle\inf\left\{\mbox{\boldmath$x$}^{T}\mbox{\boldmath$Q$}\mbox{\boldmath$x$}:\mbox{\boldmath$x$}\in\mathbb{R}^{n},\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$B$}_{1}\mbox{\boldmath$x$}\leq 0,\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1\right\}$
	$\displaystyle=$	$\displaystyle\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})\ \mbox{(with $m=1$)},$

where $n=\ell+1$ ,

\displaystyle\mbox{\boldmath$x$}=\begin{pmatrix}\mbox{\boldmath$u$}\\ u_{l+1}\end{pmatrix},\ \mbox{\boldmath$Q$}=\begin{pmatrix}\mbox{\boldmath$Q$}_{0}&\mbox{\bf 0}\\ \mbox{\bf 0}^{T}&0\end{pmatrix},\ \mbox{\boldmath$B$}_{1}=\begin{pmatrix}\mbox{\boldmath$Q$}_{1}-\mbox{\boldmath$Q$}_{2}&\mbox{\bf 0}\\ \mbox{\bf 0}^{T}&-1\end{pmatrix},\ \mbox{\boldmath$H$}=\begin{pmatrix}\mbox{\boldmath$Q$}_{2}&\mbox{\bf 0}\\ \mbox{\bf 0}^{T}&1\end{pmatrix}.

Thus, condition (19) is satisfied with $m=1$ .

Example 4.5.

Let $\mbox{\boldmath$Q$},\ \mbox{\boldmath$H$},\ \mbox{\boldmath$B$}\in\mathbb{S}^{n}$ . Consider a QCQP with two equality constraints.

	$\displaystyle\eta_{\rm QCQP}$	$\displaystyle=$	$\displaystyle\left\{\mbox{\boldmath$x$}^{T}\mbox{\boldmath$Q$}\mbox{\boldmath$x$}:\mbox{\boldmath$x$}^{T}\mbox{\boldmath$B$}\mbox{\boldmath$x$}=1,\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1\right\}$
		$\displaystyle=$	$\displaystyle\left\{\mbox{\boldmath$x$}^{T}\mbox{\boldmath$Q$}\mbox{\boldmath$x$}:\mbox{\boldmath$x$}^{T}(\mbox{\boldmath$B$}-\mbox{\boldmath$H$})\mbox{\boldmath$x$}=0,\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1\right\}\ =\ \zeta_{p}(\mathbb{J}_{0}(\mbox{\boldmath$B$}_{1}),\mbox{\boldmath$Q$},\mbox{\boldmath$H$}),$

where $\mbox{\boldmath$B$}_{1}=\mbox{\boldmath$B$}-\mbox{\boldmath$H$}$ . By Theorem 4.3 (ii), $\mathbb{J}_{0}(\mbox{\boldmath$B$}_{1})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . We can also rewrite the QCQP as

\displaystyle\eta_{\rm QCQP}

\displaystyle=

\displaystyle\left\{\mbox{\boldmath$x$}^{T}\mbox{\boldmath$Q$}\mbox{\boldmath$x$}:\mbox{\boldmath$x$}^{T}(\mbox{\boldmath$B$}_{1})\mbox{\boldmath$x$}\leq 0,\ \mbox{\boldmath$x$}^{T}(\mbox{\boldmath$B$}_{2})\mbox{\boldmath$x$}\leq 0,\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1\right\},

where $\mbox{\boldmath$B$}_{2}=-(\mbox{\boldmath$B$}-\mbox{\boldmath$H$})$ . Then $-(\mbox{\boldmath$B$}_{1}+\mbox{\boldmath$B$}_{2})=\mbox{\boldmath$O$}\in\mathbb{S}^{n}_{+}$ ; hence (21) holds with $m=2$ . This also shows that $\mathbb{J}_{0}(\mbox{\boldmath$B$}_{1})=\mathbb{J}_{-}(\mbox{\boldmath$B$}_{1})\cap\mathbb{J}_{-}(-\mbox{\boldmath$B$}_{1})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ for every $\mbox{\boldmath$B$}_{1}\in\mathbb{S}^{n}$ .

Example 4.6.

Let $q_{k}(\mbox{\boldmath$u$})=\mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{k}\mbox{\boldmath$u$}+2\mbox{\boldmath$b$}_{k}^{T}\mbox{\boldmath$u$}$ be a quadratic function in $\mbox{\boldmath$u$}\in\mathbb{R}^{\ell}$ , where $\mbox{\boldmath$Q$}_{k}\in\mathbb{S}^{\ell}$ , $\mbox{\boldmath$b$}_{k}\in\mathbb{R}^{\ell}$ $(k=0,1)$ . Consider a QCQP:

\displaystyle\zeta_{\rm QCQP}

\displaystyle=

\displaystyle\inf\left\{q_{0}(\mbox{\boldmath$u$}):\mbox{\boldmath$u$}\in\mathbb{R}^{\ell},-1\leq q_{1}(\mbox{\boldmath$u$})\leq 1\right\}.

(25)

This type of QCQP was studied in [23] in connection with indefinite trust region subproblems. See also [11, 26]. QCQP (25) can be rewritten as

$\displaystyle\eta_{\rm QCQP}$	$\displaystyle=$	$\displaystyle\inf\left\{\mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{0}\mbox{\boldmath$u$}+2\mbox{\boldmath$b$}_{0}^{T}\mbox{\boldmath$u$}u_{\ell+1}:\begin{array}[]{l}\mbox{\boldmath$u$}\in\mathbb{R}^{\ell},\ u_{\ell+1}\in\mathbb{R},\ u_{\ell+1}^{2}=1,\\ -\mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{1}\mbox{\boldmath$u$}-2\mbox{\boldmath$b$}_{1}^{T}\mbox{\boldmath$u$}u_{\ell+1}-u_{\ell+1}^{2}\leq 0,\\ \mbox{\boldmath$u$}^{T}\mbox{\boldmath$Q$}_{1}\mbox{\boldmath$u$}+2\mbox{\boldmath$b$}_{1}^{T}\mbox{\boldmath$u$}u_{\ell+1}-u_{\ell+1}^{2}\leq 0\end{array}\right\}$
	$\displaystyle=$	$\displaystyle\inf\left\{\mbox{\boldmath$x$}^{T}\mbox{\boldmath$Q$}\mbox{\boldmath$x$}:\mbox{\boldmath$x$}^{T}\mbox{\boldmath$B$}_{1}\mbox{\boldmath$x$}\leq 0,\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$B$}_{2}\mbox{\boldmath$x$}\leq 0,\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1\right\}$
	$\displaystyle=$	$\displaystyle\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})\ \mbox{(with $m=2$)},$

where $n=\ell+1$ ,

	$\displaystyle\mbox{\boldmath$x$}=\begin{pmatrix}\mbox{\boldmath$u$}\\ u_{l+1}\end{pmatrix}\in\mathbb{R}^{n},\ \mbox{\boldmath$Q$}=\begin{pmatrix}\mbox{\boldmath$Q$}_{0}&\mbox{\boldmath$b$}_{0}\\ \mbox{\boldmath$b$}_{0}^{T}&0\end{pmatrix}\in\mathbb{S}^{n},$
	$\displaystyle\mbox{\boldmath$B$}_{1}=\begin{pmatrix}-\mbox{\boldmath$Q$}_{1}&-\mbox{\boldmath$b$}_{1}\\ -\mbox{\boldmath$b$}_{1}^{T}&-1\end{pmatrix}\in\mathbb{S}^{n},\ \mbox{\boldmath$B$}_{2}=\begin{pmatrix}\mbox{\boldmath$Q$}_{1}&\mbox{\boldmath$b$}_{1}\\ \mbox{\boldmath$b$}_{1}^{T}&-1\end{pmatrix}\in\mathbb{S}^{n},\ \mbox{\boldmath$H$}=\begin{pmatrix}\mbox{\boldmath$O$}&\mbox{\bf 0}&\\ \mbox{\bf 0}^{T}&1\end{pmatrix}\in\mathbb{S}^{n}.$

It is easy to verify that

\displaystyle\langle\mbox{\boldmath$B$}_{1},\,\mbox{\boldmath$X$}\rangle+\langle\mbox{\boldmath$B$}_{2},\,\mbox{\boldmath$X$}\rangle=-2X_{nn}\leq 0\ \mbox{for every }\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}.

(27)

Therefore, condition (21) is satisfied with $m=2$ .

Example 4.7.

We add the constraint $\parallel\mbox{\boldmath$u$}\parallel^{2}/\gamma\geq\gamma$ to QCQP (25) in Example 4.6, where $\gamma>0$ is a parameter determined later. Then, the resulting QCQP can be written as

	$\displaystyle\eta_{\rm QCQP}$	$\displaystyle=$	$\displaystyle\inf\left\{q_{0}(\mbox{\boldmath$u$}):\mbox{\boldmath$u$}\in\mathbb{R}^{\ell},-1\leq q_{1}(\mbox{\boldmath$u$})\leq 1,\ \parallel\mbox{\boldmath$u$}\parallel^{2}/\gamma\geq\gamma\right\}$		(28)
		$\displaystyle=$	$\displaystyle\inf\left\{\mbox{\boldmath$x$}^{T}\mbox{\boldmath$Q$}\mbox{\boldmath$x$}:\mbox{\boldmath$x$}^{T}\mbox{\boldmath$B$}_{k}\mbox{\boldmath$x$}\leq 0\ (k=1,2,3),\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1\right\},$		(28)

where $n$ , $x$ , $Q$ , $\mbox{\boldmath$B$}_{1}$ , $\mbox{\boldmath$B$}_{2}$ and $H$ are the same as in Example 4.6 and $\mbox{\boldmath$B$}_{3}={\scriptsize\begin{pmatrix}-\mbox{\boldmath$I$}/\gamma&\mbox{\bf 0}\\ \mbox{\bf 0}^{T}&\gamma\end{pmatrix}}\in\mathbb{S}^{n}$ . In addition to (27),

\displaystyle\left.\begin{array}[]{lcl}\langle\mbox{\boldmath$B$}_{1},\,\mbox{\boldmath$X$}\rangle+\langle\mbox{\boldmath$B$}_{3},\,\mbox{\boldmath$X$}\rangle&=&\langle{\scriptsize\begin{pmatrix}-\mbox{\boldmath$Q$}_{1}-\mbox{\boldmath$I$}/\gamma&-\mbox{\boldmath$b$}_{1}\\ -\mbox{\boldmath$b$}_{1}^{T}&-1+\gamma\end{pmatrix}},\,\mbox{\boldmath$X$}\rangle\leq 0\ \mbox{for every }\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+},\\[3.0pt] \langle\mbox{\boldmath$B$}_{2},\,\mbox{\boldmath$X$}\rangle+\langle\mbox{\boldmath$B$}_{3},\,\mbox{\boldmath$X$}\rangle&=&\langle{\scriptsize\begin{pmatrix}\mbox{\boldmath$Q$}_{1}-\mbox{\boldmath$I$}/\gamma&\mbox{\boldmath$b$}_{1}\\ \mbox{\boldmath$b$}_{1}^{T}&-1+\gamma\end{pmatrix}},\,\mbox{\boldmath$X$}\rangle\leq 0\ \mbox{for every }\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}\end{array}\right\}

(31)

hold if we take a sufficiently small $\gamma>0$ . Therefore, condition (21) is satisfied with $m=3$ .

Adding the constraint $\parallel\mbox{\boldmath$u$}\parallel^{2}/\gamma\geq\gamma$ to QCQP (25) is interpreted as removing the ball $\{\mbox{\boldmath$u$}\in\mathbb{R}^{n}:\parallel\mbox{\boldmath$u$}\parallel/\gamma<\gamma\}$ with the center 0, which lies the interior of the feasible region, from the feasible region. The above result implies that if the size of the ball is sufficiently small then we can remove the ball from the feasible region without destroying $\mathbb{J}_{-}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . For example, suppose that $\mbox{\boldmath$Q$}_{1}=\mbox{\boldmath$O$}$ and $\mbox{\boldmath$b$}_{1}={\scriptsize\begin{pmatrix}\mbox{\bf 0}\\ 1/2\end{pmatrix}}\in\mathbb{R}^{\ell}$ . Then QCQP (28) turns out to be

\displaystyle\eta_{\rm QCQP}

\displaystyle=

\displaystyle\inf\left\{q_{0}(\mbox{\boldmath$u$}):\mbox{\boldmath$u$}\in\mathbb{R}^{\ell},\ -1\leq u_{\ell}\leq 1,\ \parallel\mbox{\boldmath$u$}\parallel^{2}/\gamma\geq\gamma\right\}.

In this case, if $0<\gamma\leq 4/5$ , then (31) is satisfied. It is interesting to note that the unit ball $\{\mbox{\boldmath$u$}\in\mathbb{R}^{\ell}:\parallel\mbox{\boldmath$u$}\parallel\leq 1\}$ is included in $\{\mbox{\boldmath$u$}\in\mathbb{R}^{\ell}:-1\leq u_{\ell}\leq 1\}$ , but we cannot take $\gamma=1$ to satisfy (31).

Example 4.8.

Let $\mbox{\boldmath$B$}_{k}$ be a matrix in $\mathbb{S}^{n}$ whose elements satisfy

\displaystyle[B_{k}]_{ij}=[B_{k}]_{ji}\in\left\{\begin{array}[]{ll}(-\infty,1]&\mbox{if $i=j=k$},\\ {(-\infty,-2]}&\mbox{if $i=j\not=k$},\\ {[-1/(2n),1/(2n)]}&\mbox{otherwise}.\end{array}\right.

$(k=1,\ldots,n)$ . Then,

\displaystyle-([B_{k}]_{ij}+[B_{\ell}]_{ij})=-([B_{k}]_{ji}+[B_{\ell}]_{ji})\in\left\{\begin{array}[]{ll}[1,\infty)&\mbox{if $i=j$},\\ {[-1/n,1/n]}&\mbox{otherwise},\end{array}\right.

which implies that $-(\mbox{\boldmath$B$}_{k}+\mbox{\boldmath$B$}_{\ell})$ is diagonally dominant; hence positive semidefinite $(1\leq k<\ell\leq n)$ . Therefore, condition (21) is satisfied with $m=n$ .

Example 4.9.

Let $A$ be an $r\times n$ matrix. Adding a homogeneous linear equality constraint $\mbox{\boldmath$A$}\mbox{\boldmath$x$}=\mbox{\bf 0}$ to QCQP (18), we have

	$\displaystyle\bar{\eta}_{\rm QCQP}$	$\displaystyle=$	$\displaystyle\inf\left\{\mbox{\boldmath$x$}^{T}\mbox{\boldmath$Q$}\mbox{\boldmath$x$}:\begin{array}[]{l}\mbox{\boldmath$x$}\in\mathbb{R}^{n},\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$B$}_{k}\mbox{\boldmath$x$}\leq 0\ (1\leq k\leq m),\\ \mbox{\boldmath$x$}^{T}\mbox{\boldmath$H$}\mbox{\boldmath$x$}=1,\ \mbox{\boldmath$A$}\mbox{\boldmath$x$}=\mbox{\bf 0}\end{array}\right\}$
		$\displaystyle=$	$\displaystyle\inf\left\{\langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}\rangle:\mbox{\boldmath$X$}\in\mathbb{K}\cap\mathbb{J}_{-}\cap\mathbb{F}\right\}\ =\ \zeta_{p}(\mathbb{K}\cap\mathbb{J}_{-}\cap\mathbb{F},\mbox{\boldmath$Q$},\mbox{\boldmath$H$}),$

where $\mathbb{F}\equiv\{\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}:\langle\mbox{\boldmath$A$}^{T}\mbox{\boldmath$A$},\,\mbox{\boldmath$X$}\rangle=0\}$ forms a face of $\mathbb{S}^{n}_{+}$ since $\mbox{\boldmath$A$}^{T}\mbox{\boldmath$A$}\in\mathbb{S}^{n}_{+}$ . By Theorem 3.5 (ii), $\mathbb{J}_{-}\cap\mathbb{F}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ if $\mathbb{J}_{-}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Therefore, we can add $\mbox{\boldmath$A$}\mbox{\boldmath$x$}=\mbox{\bf 0}$ to any of the examples above so that the resulting QCQP can still be solved exactly by its SDP relaxation as long as $-\infty<\zeta_{p}(\mathbb{J}_{-}\cap\mathbb{F},\mbox{\boldmath$Q$},\mbox{\boldmath$H$})<\infty$ .

4.2 Proof of Theorem 4.1

We need the following lemma.

Lemma 4.10.

([26, Lemma 2.2], see also [24, Proposition 3]) Let $\mbox{\boldmath$B$}\in\mathbb{S}^{n}$ and $\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}$ with rank $\mbox{\boldmath$X$}=r$ . Suppose that $\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}\rangle\leq 0$ . Then, there exists a rank-1 decomposition of $X$ such that $\mbox{\boldmath$X$}=\sum_{i=1}^{r}\mbox{\boldmath$x$}_{i}\mbox{\boldmath$x$}_{i}^{T}$ and $\mbox{\boldmath$x$}_{i}^{T}\mbox{\boldmath$B$}\mbox{\boldmath$x$}_{i}\leq 0$ $(1\leq i\leq r)$ . If, in particular, $\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}\rangle=0$ , then $\mbox{\boldmath$x$}_{i}^{T}\mbox{\boldmath$B$}\mbox{\boldmath$x$}_{i}=0$ $(1\leq i\leq r)$ .

Proof Theorem 4.1 (i): For the proof, we utilize Theorem 1.2 (iii) and Lemma 4.10. Choose a $\mbox{\boldmath$Q$}\in\mathbb{S}^{n}$ arbitrarily, and consider COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ . We first observe that the feasible region of COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ is either empty or bounded since every feasible $X$ satisfies $\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}$ and $\langle\mbox{\boldmath$I$},\,\mbox{\boldmath$X$}\rangle=1$ . If $\mathbb{J}_{-}=\{\mbox{\boldmath$O$}\}$ , then the feasible region of COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ is empty; hence $\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})=\zeta_{p}(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})=\infty$ . Otherwise, there exists a nonzero $\mbox{\boldmath$X$}\in\mathbb{J}_{-}\subseteq\mathbb{S}^{n}_{+}$ , and $\mbox{\boldmath$X$}/\langle\mbox{\boldmath$I$},\,\mbox{\boldmath$X$}\rangle$ lies in the feasible region. Hence, the feasible region is bounded, and COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ has a nonzero optimal solution with a finite optimal value $\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ . Obviously $\mbox{\boldmath$I$}\in\mathbb{S}^{n}_{+}\subseteq\mathbb{J}_{-}^{*}$ . By Theorem 2.3, DCOP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ has an optimal solution $(\bar{t},\overline{\mbox{\boldmath$Y$}})\in\mathbb{R}\times\mathbb{J}_{-}^{*}$ such that

\displaystyle 0

\displaystyle=

\displaystyle\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})-\zeta_{d}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})=\langle\mbox{\boldmath$X$},\,\overline{\mbox{\boldmath$Y$}}\rangle

for every optimal solutions $X$ of COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ . The following two cases occur. Case (a): there exists a nonzero optimal solution $X$ and a $k\in\{1,\ldots,m\}$ such that $\mbox{\boldmath$X$}\in\mathbb{J}_{0}(\mbox{\boldmath$B$}_{k})$ , i.e., $\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle=0$ . Case (b): $\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle<0$ for all optimal solutions of COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ and all $k\in\{1,\ldots,m\}$ .

Case (a): Let $r=\mbox{rank}\mbox{\boldmath$X$}$ . By Lemma 4.10, there exists a rank-1 decomposition of $X$ such that $\mbox{\boldmath$X$}=\sum_{i=1}^{r}\mbox{\boldmath$x$}_{i}\mbox{\boldmath$x$}_{i}^{T}$ and $\mbox{\boldmath$x$}_{i}^{T}\mbox{\boldmath$B$}_{k}\mbox{\boldmath$x$}_{i}=0$ (i.e., $\mbox{\boldmath$x$}_{i}\mbox{\boldmath$x$}_{i}^{T}\in\mathbb{J}_{0}(\mbox{\boldmath$B$}_{k})$ ) $(1\leq i\leq r)$ . By assumption (19), $\mbox{\boldmath$x$}_{i}\mbox{\boldmath$x$}_{i}^{T}\in\mathbb{J}_{-}\ (1\leq i\leq r)$ . Since $1=\langle\mbox{\boldmath$I$},\,\mbox{\boldmath$X$}\rangle=\sum_{i=1}^{r}\mbox{\boldmath$x$}_{i}^{T}\mbox{\boldmath$x$}_{i}$ , there exist a $\tau\in(0,1]$ and a $j\in\{1,\ldots,r\}$ such that $\mbox{\boldmath$x$}_{j}^{T}\mbox{\boldmath$x$}_{j}=\tau$ . Let $\overline{\mbox{\boldmath$X$}}=\mbox{\boldmath$x$}_{j}\mbox{\boldmath$x$}_{j}^{T}/\tau$ . Since $\mbox{\boldmath$x$}_{j}\mbox{\boldmath$x$}_{j}^{T}\in\mathbb{J}_{-}$ , $\overline{\mbox{\boldmath$X$}}\in\mathbb{J}_{-}$ . We also see that $\langle\mbox{\boldmath$I$},\,\overline{\mbox{\boldmath$X$}}\rangle=\langle\mbox{\boldmath$I$},\,\mbox{\boldmath$x$}_{j}\mbox{\boldmath$x$}_{j}^{T}/\tau\rangle=1$ . Hence $\overline{\mbox{\boldmath$X$}}$ is a rank- $1$ feasible solution of COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ . Furthermore, we see from $\overline{\mbox{\boldmath$Y$}}\in\mathbb{J}_{-}^{*}$ and $\mbox{\boldmath$x$}_{i}\mbox{\boldmath$x$}_{i}^{T}\in\mathbb{J}_{-}$ $(1\leq i\leq r)$ that

\displaystyle 0\leq\langle\overline{\mbox{\boldmath$Y$}},\,\overline{\mbox{\boldmath$X$}}\rangle=\frac{\langle\overline{\mbox{\boldmath$Y$}},\,\mbox{\boldmath$x$}_{j}\mbox{\boldmath$x$}_{j}^{T}\rangle}{\tau}\leq\frac{\langle\overline{\mbox{\boldmath$Y$}},\,\mbox{\boldmath$X$}\rangle}{\tau}=0.

Hence, $\overline{\mbox{\boldmath$X$}}$ is a rank-1 optimal solution of COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ , and it is an optimal solution of COP $(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ with the same objective value $\langle\mbox{\boldmath$Q$},\,\overline{\mbox{\boldmath$X$}}\rangle$ . Therefore, we have shown that $\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})=\zeta_{p}(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ .

Case (b): Let $S$ denote the optimal solution set of COP $(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ . By the assumption of this case, $\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle<0$ $(1\leq k\leq m)$ for all $\mbox{\boldmath$X$}\in S$ . Hence $S$ coincides with the optimal solution set of COP $(\mathbb{S}^{n}_{+},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ , an SDP of minimizing $\langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}\rangle$ subject to $\mbox{\boldmath$X$}\in\mathbb{S}^{n}_{+}$ and the single equality constraint $\langle\mbox{\boldmath$H$},\,\mbox{\boldmath$X$}\rangle=1$ . It is well-known that every solvable SDP with $r$ equality constraints has an optimal solution $X$ with rank $\leq\sqrt{2r}$ (see, for example, [16]). Hence, there exists an $\overline{\mbox{\boldmath$X$}}\in S$ such that rank $\overline{\mbox{\boldmath$X$}}=1$ , which is a common optimal solution of COP $(\mathbb{J},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ and COP $(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ . Therefore, $\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})=\zeta_{p}(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ .

In both Cases (a) and (b), we have shown that $\zeta_{p}(\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})=\zeta_{p}(\mathbb{K}\cap\mathbb{J}_{-},\mbox{\boldmath$Q$},\mbox{\boldmath$I$})$ . Since $Q$ is chosen arbitrarily from $\mathbb{S}^{n}$ , we can conclude by Theorem 1.2 (iii) that $\mathbb{J}_{-}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . ∎

Proof Theorem 4.1 (ii): The desired result follows from Corollary 2.2. ∎

4.3 Proof of Theorem 4.3

(i) We first show that $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ $\Rightarrow$ $\mathbb{J}_{-}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Since $\mathbb{J}_{-}(\mbox{\boldmath$B$})$ is a convex set containing $\mathbb{K}\cap\mathbb{J}_{-}(\mbox{\boldmath$B$})$ , co $(\mathbb{K}\cap\mathbb{J}_{-}(\mbox{\boldmath$B$}))\subseteq\mathbb{J}_{-}(\mbox{\boldmath$B$})$ is obvious. To show $\mathbb{J}_{-}(\mbox{\boldmath$B$})\subseteq\mbox{co}(\mathbb{K}\cap\mathbb{J}_{-}(\mbox{\boldmath$B$}))$ , let $\mbox{\boldmath$X$}\in\mathbb{J}_{-}(\mbox{\boldmath$B$})$ . Then there exists an $\mbox{\boldmath$X$}^{i}\in\mathbb{K}$ such that

\displaystyle\mbox{\boldmath$X$}=\sum_{i=1}^{m}\mbox{\boldmath$X$}^{i},\ 0\geq\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}\rangle=\sum_{i=1}^{m}\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{i}\rangle.

Let $I_{+}=\{i:\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{i}\rangle>0\}\ \mbox{and }\ I_{0}=\{i:\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{i}\rangle=0\},\ I_{-}=\{i:\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{i}\rangle<0\}.$ By definition, $\mbox{\boldmath$X$}^{i}\in\mathbb{K}\cap\mathbb{J}_{-}(\mbox{\boldmath$B$})\ (i\in I_{0}\cup I_{-})$ . Hence, if $I_{+}=\emptyset$ then $\mbox{\boldmath$X$}\in\mbox{co}(\mathbb{K}\cap\mathbb{J}_{-}(\mbox{\boldmath$B$}))$ . Now assume that $I_{+}\not=\emptyset$ . Then, $I_{-}\not=\emptyset$ since otherwise $\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}\rangle=\sum_{i=1}^{m}\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{i}\rangle>0$ , a contradiction. Let

\displaystyle\mbox{\boldmath$X$}^{+}=\sum_{i\in I_{+}}\mbox{\boldmath$X$}^{i}\in\mbox{co}\mathbb{K},\ \ \mbox{\boldmath$X$}^{0}=\left\{\begin{array}[]{ll}\displaystyle\sum_{i\in I_{0}}\mbox{\boldmath$X$}^{i}&\mbox{if }I_{0}\not=\emptyset,\\ \mbox{\bf 0}&\mbox{otherwise }\end{array},\right.\ \ \mbox{\boldmath$X$}^{-}=\sum_{i\in I_{-}}\mbox{\boldmath$X$}^{i}.

Then,

	$\displaystyle\mbox{\boldmath$X$}^{0}\in\mbox{co}(\mathbb{K}\cap\mathbb{J}_{0}(\mbox{\boldmath$B$})),\ \mbox{\boldmath$X$}^{-}\in\mbox{co}(\mathbb{K}\cap\mathbb{J}_{-}(\mbox{\boldmath$B$})),\ \mbox{\boldmath$X$}=\mbox{\boldmath$X$}^{+}+\mbox{\boldmath$X$}^{0}+\mbox{\boldmath$X$}^{-},$		(36)
	$\displaystyle\alpha^{+}\equiv\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{+}\rangle>0,\ \alpha^{0}\equiv\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{0}\rangle=0,\ \alpha^{-}\equiv-\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{-}\rangle>0,$
	$\displaystyle 0\geq\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}\rangle=\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{+}+\mbox{\boldmath$X$}^{0}+\mbox{\boldmath$X$}^{-}\rangle=\alpha^{+}-\alpha^{-}.$		(37)

Define

\displaystyle\overline{\mbox{\boldmath$X$}}

\displaystyle\equiv

\displaystyle\frac{\alpha^{-}\mbox{\boldmath$X$}^{+}+\alpha^{+}\mbox{\boldmath$X$}^{-}}{\alpha^{+}+\alpha^{-}},\ \mbox{which implies }\mbox{\boldmath$X$}^{+}=\frac{\alpha^{+}+\alpha^{-}}{\alpha^{-}}\overline{\mbox{\boldmath$X$}}-\frac{\alpha^{+}}{\alpha^{-}}\mbox{\boldmath$X$}^{-}.

(38)

Then,

\displaystyle\overline{\mbox{\boldmath$X$}}\in\mbox{co}\mathbb{K},\ \langle\mbox{\boldmath$B$},\,\overline{\mbox{\boldmath$X$}}\rangle=\frac{\alpha^{-}\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{+}\rangle+\alpha^{+}\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}^{-}\rangle}{\alpha^{+}+\alpha^{-}}=\frac{\alpha^{-}\alpha^{+}-\alpha^{+}\alpha^{-}}{\alpha^{+}+\alpha^{-}}=0.

Hence, $\overline{\mbox{\boldmath$X$}}\in\mathbb{J}_{0}(\mbox{\boldmath$B$})=\mbox{co}(\mathbb{K}\cap\mathbb{J}_{0}(\mbox{\boldmath$B$}))\subseteq\mbox{co}(\mathbb{K}\cap\mathbb{J}_{-}(\mbox{\boldmath$B$}))$ . It follows from (36) and (38) that

\displaystyle\mbox{\boldmath$X$}=\mbox{\boldmath$X$}^{+}+\mbox{\boldmath$X$}^{0}+\mbox{\boldmath$X$}^{-}=\frac{\alpha^{+}+\alpha^{-}}{\alpha^{-}}\overline{\mbox{\boldmath$X$}}+\frac{\alpha^{-}-\alpha^{+}}{\alpha^{-}}\mbox{\boldmath$X$}^{-}+\mbox{\boldmath$X$}^{0}.

Since we have already shown that the three points $\overline{\mbox{\boldmath$X$}},\mbox{\boldmath$X$}^{0}$ and $\mbox{\boldmath$X$}^{-}$ lies in co $(\mathbb{K}\cap\mathbb{J}_{-}(\mbox{\boldmath$B$}))$ and $\frac{\alpha^{+}+\alpha^{-}}{\alpha^{-}}\geq 0$ and $\frac{\alpha^{-}-\alpha^{+}}{\alpha^{-}}\geq 0$ (by (37)), we obtain $\mbox{\boldmath$X$}\in co(\mathbb{K}\cap\mathbb{J}_{-}(\mbox{\boldmath$B$}))$ . Thus we have shown that $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ $\Rightarrow$ $\mathbb{J}_{-}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ .

We show that $\mathbb{J}_{-}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ $\Rightarrow$ $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . It is easy to verify that $\mathbb{J}_{0}(\mbox{\boldmath$B$})$ is a face of $\mathbb{J}_{-}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Then $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ follows by Theorem 3.5 (i). Therefore, we have shown that $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ $\Leftrightarrow$ $\mathbb{J}_{-}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . ∎

(ii) Since $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ is equivalent to $\mathbb{J}_{-}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ by (i), $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ follows from Theorem 4.1 (i) with $m=1$ . ∎

Remark 4.11.

Assertion (i) of Theorem 4.3 holds for a more general case where $\mathbb{K}$ is a cone in a finite dimensional space $\mathbb{V}$ and $\mbox{\boldmath$B$}\in\mathbb{V}$ . Define

\displaystyle\mathbb{J}_{0}(\mbox{\boldmath$B$})=\{\mbox{\boldmath$X$}\in\mbox{co}\mathbb{K}:\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}\rangle=0\},\ \mathbb{J}_{-}(\mbox{\boldmath$B$})=\{\mbox{\boldmath$X$}\in\mbox{co}\mathbb{K}:\langle\mbox{\boldmath$B$},\,\mbox{\boldmath$X$}\rangle\leq 0\}.

Then, $\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ and $\mathbb{J}_{-}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ are equivalent. The proof of Theorem 4.3 (i) stated above remains valid for this general case without any change.

4.4 Adding equality constraints

Assume that, in general,

\displaystyle\mathbb{J}\equiv\left\{\mbox{\boldmath$X$}\in\mathbb{S}^{n}:\langle\mbox{\boldmath$B$}_{j},\,\mbox{\boldmath$X$}\rangle=0\ (j\in I_{0}),\ \langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle\leq 0\ (k\in I_{-})\right\}\in\widehat{\mbox{$\cal F$}}(\mathbb{K}),

(39)

where $I_{0}$ and $I_{-}$ denote a partition of $\{1,\ldots,m\}$ and $\mbox{\boldmath$Q$},\ \mbox{\boldmath$H$},\ \mbox{\boldmath$B$}_{k}\in\mathbb{S}^{n}$ $(k\in I_{0}\cup I_{-})$ . We present a method for adding an equality constraint $\langle\mbox{\boldmath$B$}_{m+1},\,\mbox{\boldmath$X$}\rangle=0$ to $\mathbb{J}$ so that $\mathbb{J}\cap\mathbb{J}_{0}(\mbox{\boldmath$B$}_{m+1})$ remains in $\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . The method can be used recursively by replacing $I_{0}$ with $I_{0}\cup\{m+1\}$ . Note that $I_{-}$ is not updated. Initially, we take $\mathbb{J}_{-}\equiv\cap_{k=1}^{m}\mathbb{J}_{-}(\mbox{\boldmath$B$}_{k})$ with $\mbox{\boldmath$B$}_{k}\in\mathbb{S}^{n}$ $(1\leq k\leq m)$ satisfying (19) or $\mathbb{J}_{0}(\mbox{\boldmath$B$}_{1})$ with $\mbox{\boldmath$B$}_{1}\in\mathbb{S}^{n}$ for $\mathbb{J}$ .

If $I_{0}=\emptyset$ , we can choose any $\mbox{\boldmath$B$}\in\mathbb{S}^{n}$ satisfying $\mathbb{J}_{0}(\mbox{\boldmath$B$})\subseteq\mathbb{J}_{-}(\mbox{\boldmath$B$}_{k})$ $(k\in I_{-})$ so that $\mathbb{J}_{-}\cap\mathbb{J}_{0}(\mbox{\boldmath$B$})=\mathbb{J}_{0}(\mbox{\boldmath$B$})\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ by Theorem 4.3 (i). As a result, all inequality constraints $\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle$ $(k\in I_{-})$ become redundant. We exclude this trivial choice in the subsequent discussion.

Let $\mathbb{K}^{\prime}=\mathbb{K}\cap\mathbb{J}$ , which is a cone in $\mathbb{S}^{n}$ . It follows from $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ that $\mbox{co}(\mathbb{K}^{\prime}\cap\mathbb{J})=\mbox{co}(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ . Hence $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K}^{\prime})$ . All the results in Section 3 is quite general so that the results can be applied even if $\mathbb{K}$ is replaced with $\mathbb{K}^{\prime}$ and $\mathbb{S}^{n}_{+}=\mbox{co}\mathbb{K}$ with co $\mathbb{K}^{\prime}$ . However, it is difficult to extend Theorems 4.1 and 4.3 to the general case where $\mathbb{S}^{n}_{+}$ is replaced with $\mathbb{J}=\mbox{co}\mathbb{K}^{\prime}$ defined by (39). The main reason is that Lemma 4.10 is no longer valid for the general case. Consequently, it becomes clear that adding an equality constraint to $\mathbb{J}$ is more restrictive than adding inequalities as only the general results in Section 3 can be used.

In general, $\mathbb{J}_{0}(\mbox{\boldmath$B$})$ is a face of $\mathbb{J}$ iff

\displaystyle\mbox{\boldmath$B$}\in\mathbb{J}^{*}=\mbox{cl}\left\{\mbox{\boldmath$Y$}+\sum_{j\in I_{-}\cup I_{0}}\mbox{\boldmath$B$}_{j}y_{j}:\mbox{\boldmath$Y$}\in\mathbb{S}^{n}_{+},\ y_{j}\in\mathbb{R}\ (j\in I_{0}),\ y_{k}\leq 0\ (k\in I_{-})\right\}.

(See [17] for the identity). Obviously, every $\mbox{\boldmath$B$}\in\mathbb{S}^{n}_{+}$ lies in $\mathbb{J}^{*}$ . In this case, $\mathbb{J}_{0}(\mbox{\boldmath$B$})$ forms a common face of $\mathbb{J}$ and $\mathbb{S}^{n}_{+}$ . It is also straightforward to see that $\mbox{\boldmath$B$}=-\mbox{\boldmath$B$}_{\ell}\in\mathbb{J}^{*}$ for every $\ell\in I_{-}$ . In this case, $\mathbb{J}\cap\mathbb{J}_{0}(-\mbox{\boldmath$B$}_{\ell})=\big{(}\cap_{j\in I_{0}}\mathbb{J}_{0}(\mbox{\boldmath$B$}_{j})\big{)}\cap\mathbb{J}_{0}(\mbox{\boldmath$B$}_{\ell})$ and all inequalities $\langle\mbox{\boldmath$B$}_{k},\,\mbox{\boldmath$X$}\rangle\leq 0$ $(k\in I_{-})$ become redundant. (Recall that assumption (19) holds if $I_{-}\not=\emptyset$ ). More generally, if $y_{k}\leq 0$ $(k\in I_{-})$ and $y_{j}\in\mathbb{R}$ $(j\in I_{0})$ , then then $\mbox{\boldmath$B$}=\sum_{j\in I_{-}\cup I_{0}}\mbox{\boldmath$B$}_{j}y_{j}\in\mathbb{J}^{*}$ .

5 Concluding discussion

By extending the condition co $(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ with a face $\mathbb{J}$ of co $\mathbb{K}$ in [15] to characterizations of the family $\widehat{\mbox{$\cal F$}}(\mathbb{K})$ of all convex cone $\mathbb{J}\subseteq\mbox{co}\mathbb{K}$ satisfying co $(\mathbb{K}\cap\mathbb{J})=\mathbb{J}$ , we have established the fundamental properties of $\widehat{\mbox{$\cal F$}}(\mathbb{K})$ in Section 3. In particular, by applying the properties to nonconvex QCQPs, we have shown that a new class of QCQP with multiple nonconvex inequality and equality constraints can be solved exactly by its SDP relaxation in Section 4.

The important and distinctive feature of the geometric nonconvex COP $(\mathbb{K}\cap\mathbb{J})$ and its convex conic reformulation COP $(\mathbb{J})$ is independence from the description of $\mathbb{K}$ and $\mathbb{J}$ . The required main assumption is that $\mathbb{K}$ is a cone in $\mathbb{V}$ and $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ , which indicates that the results presented in Sections 2 and 3 can be applied in various cases. It should be noted that the other assumption $-\infty<\zeta_{p}(\mathbb{J})<\infty$ is necessary and sufficient to ensure $\zeta_{p}(\mathbb{J})=\zeta_{p}(\mathbb{K}\cap\mathbb{J})$ under $\mathbb{J}\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . We have not imposed any assumption on the objective function $\langle\mbox{\boldmath$Q$},\,\mbox{\boldmath$X$}\rangle$ . See Corollary 2.2.

To the question of whether Theorem 4.1 can be applied to the completely positive relaxation of QCQPs, we should note that the answer is negative, as shown in the following simple example: Let $\mathbb{K}=\{\mbox{\boldmath$x$}\mbox{\boldmath$x$}^{T}:\mbox{\boldmath$x$}\in\mathbb{R}^{2}_{+}\}$ and $\mathbb{J}_{0}=\{\mbox{\boldmath$X$}\in\mbox{co}\mathbb{K}:X_{11}-X_{22}=0\}$ . Then $\mbox{co}(\mathbb{K}\cap\mathbb{J}_{0})=\left\{\lambda{\scriptsize\begin{pmatrix}1&1\\ 1&1\end{pmatrix}}:\lambda\geq 0\right\}$ is a proper subset of $\mathbb{J}_{0}$ ; hence $\mathbb{J}_{0}\not\in\widehat{\mbox{$\cal F$}}(\mathbb{K})$ . Thus assertion (ii) of Theorem 4.3 does not hold for this case. Or, at least, some modification is necessary on assumption (19). This example also shows that Lemma 4.10 is no longer valid if $\mathbb{S}^{n}_{+}$ is replaced with the completely positive cone.

We recently became aware of the results in the paper [1] by Argue et al., which investigated the equivalence between QCQPs and their SDP relaxations. Some results there including their Proposition 1 are related to our main result, Theorem 4.1. We should mention that our approach is different from theirs and our results were obtained independently from theirs. Our approach, originated from our previous paper [15] which discussed the equivalent convex relaxation of a geometric conic optimization problem in a finite dimensional space, is geometric in nature. In contrast, theirs is limited to QCQP in $\mathbb{R}^{n}$ and its SDP relaxation, and does not involve geometric considerations. Their paper [1] was also written independently from our earlier paper [15]. Both approaches should be useful for further development of the subject.

References

[1] C. J. Argue, F. Kilinç-Karzan, and A.L. Wang. Necessary and sufficient conditions for rank-one- generated cones, Math. Oper. Res., 48 (2023), pp. 100–126.
[2] N. Arima. A convex reformation of linear optimization problems on non-convex cones (in Japanese). PhD thesis, University of Tsukuba, Tsukuba, Ibaraki, Japan 305-8577, March 2022.
[3] N Arima, S. Kim, and M. Kojima. Extension of completely positive cone relaxation to polynomial optimization, J. Optim. Theory Appl., 168 (2016), pp. 884–900.
[4] N. Arima, S. Kim, M. Kojima, and K. C. Toh. Lagrangian-conic relaxations, Part II: Applications to polynomial optimization problems, Pacific J. Optim, 15 (2019), pp. 415–439.
[5] G. Azuma, Fukuda M., S. Kim, and M. Yamashita. Exact SDP relaxations for quadratic programs with bipartite graph structures, J. of Global Optim., 86 (2023), pp. 671-691.
[6] I. M. Bomze, M. D $\ddot{\mbox{u}}$ r, E. de Klerk, C. Roos, A. Quist, and T. Terlaky. On copositive programming and standard quadratic optimization problems, J. Global Optim., 18 (2000), pp. 301–320.
[7] I. M. Bomze and M. Gabl. Optimization under uncertainty and risk: Quadratic and copositive approaches, Eur. J. Oper. Res., 310 (2023), pp. 449–476.
[8] S. Burer. On the copositive representation of binary and continuous non-convex quadratic programs, Math. Program., 120 (2009), pp. 479–495.
[9] E. de Klerk and D. V. Pasechnik. Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12 (2002), pp. 875-892.
[10] M. Gabl. Sparse conic reformulation of structured QCQPs based on copositive optimization with applications in stochastic optimization, J. of Global Optim., 87 (2023), pp.1–34.
[11] V. Jeyakumar and Li. G. Y. Trust-region problems with linear inequality constraints: exact sdp relaxation, global optimality and robust optimization, Math. Program., 147 (2014), pp. 171–206.
[12] S. Kim and M. Kojima. Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations, Comput. Optim. Appl., 26 (2003), pp. 143–154.
[13] S. Kim and M. Kojima. Equivalent sufficient conditions for global optimality of quadratically constrained quadratic program, Technical Report arXiv:2303.05874, March 2023.
[14] S. Kim and M. Kojima. Strong duality of a conic optimization problem with a single hyperplane and two cone constraints strong duality of a conic optimization problem with a single hyperplane and two cone constraints, Optimization, To appear.
[15] S. Kim, M. Kojima, and K. C. Toh. A geometric analysis of a class of nonconvex conic programs for convex conic reformulations of quadratic and polynomial optimization problems, SIAM J. Optim., 30 (2020), pp. 1251–1273.
[16] G. Pataki. On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Math. Oper. Res., 23 (1998), pp. 339–358.
[17] G. Pataki. On the closedness of the linear image of a closed convex cone, Math. Oper. Res., 32 (2007), pp. 395–412.
[18] J. Pena, J. C. Vera, and L. F. Zuluaga. Completely positive reformulations for polynomial optimization, Math. Program., 151 (2015), pp. 405–431.
[19] B. T. Polyak. Convexity of quadratic transformations and its use in control and optimization, J. Optim. Theory Appl., 99 (1998), pp. 553–583.
[20] J. Povh and F. Rendl. A copositive programming approach to graph partitioning, SIAM J. Optim., 18 (2007), pp. 223–241.
[21] T. Rockafellar R. Convex Analysis. Princeton University Press, 1970.
[22] S. Sojoudi and J. Lavaei. Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure, SIAM J. Optim., 24 (2014), pp. 1746–1778.
[23] R. Stern and H. Wolkowicz. Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. Optim., 5 (1995), pp. 286–313.
[24] J. F. Sturm and S. Zhang. On cones of nonnegative quadratic functions, Math. Oper. Res., 28 (2003), pp. 246–267.
[25] A. L. Wang and F. Kilinc-Karzan. On the tightness of SDP relaxations of QCQPs, Math. Program., 193 (2022), pp. 33–73.
[26] Y. Ye and S. Zhang. New results on quadratic minimization, SIAM J. Optim., 14 (2003), pp. 245–267.
[27] E. A. Yildirim. An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs, J. Global Optim., 82 (2022), pp. 1–20.
[28] S. Zhang. Quadratic optimization and semidefinite relaxation, Math. Program., 87 (2000), pp. 453–465.

Further Development in Convex Conic Reformulation of Geometric Nonconvex Conic Optimization Problems

Abstract

1 Introduction

Theorem 1.1.

Theorem 1.2.

1.1 Contribution of the paper and related literature

1.2 Outline of the paper

1.3 Remarks on notation and symbols

2 Some remaining issues

2.1 The feasibility preserving property - (a)

Lemma 2.1.

Proof.

Corollary 2.2.

Proof.

2.2 Strong duality of COP(𝕁\mathbb{J}) - (b)

Theorem 2.3.

2.3 Existence of a common optimal solution of COP(𝕁\mathbb{J}) and COP(𝕂∩𝕁\mathbb{K}\cap\mathbb{J}) - (c)

Theorem 2.4.

3 On Condition (B)

3.1 Illustrative examples

Example 3.1.

Example 3.2.

Example 3.3.

Example 3.4.

3.2 Basic properties on ℱ^​(𝕂)\widehat{\mbox{$\cal F$}}(\mathbb{K})

Theorem 3.5.

3.3 Proof of Theorem 1.2

3.4 Decompositions of COP(𝕂∩𝕁)(\mathbb{K}\cap\mathbb{J})

Theorem 3.6.

Proof.

4 A class of quadratically constrained quadratic programs with multiple nonconvex constraints

Theorem 4.1.

Proposition 4.2.

Proof.

Theorem 4.3.

4.1 Some examples

Example 4.4.

Example 4.5.

Example 4.6.

Example 4.7.

Example 4.8.

Example 4.9.

4.2 Proof of Theorem 4.1

Lemma 4.10.

4.3 Proof of Theorem 4.3

Remark 4.11.

4.4 Adding equality constraints

5 Concluding discussion

References

2.2 Strong duality of COP( $\mathbb{J}$ ) - (b)

2.3 Existence of a common optimal solution of COP( $\mathbb{J}$ ) and COP( $\mathbb{K}\cap\mathbb{J}$ ) - (c)

3.2 Basic properties on $\widehat{\mbox{$\cal F$}}(\mathbb{K})$

3.4 Decompositions of COP $(\mathbb{K}\cap\mathbb{J})$