Journal of Global Optimization https://doi.org/10.1007/s10898-018-0676-4

Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems N. Ito1 · S. Kim2 · M. Kojima3 · A. Takeda4 · K.-C. Toh5 Received: 10 July 2017 / Accepted: 12 June 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018

Abstract Various conic relaxations of quadratic optimization problems in nonnegative variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combinatorial optimization problems can be expressed in several ways, each of which results in different conic relaxations. For the completely positive, doubly nonnegative and semidefinite relaxations of the combinatorial optimization problems, we discuss the equivalences and differences among the relaxations by investigating the feasible regions obtained from different representations of the combinatorial condition which we propose as a generalization of the binary and complementarity condition. We also study theoretically the issue of the primal and dual nondegeneracy, the existence of an interior solution and the size of the relaxations, as a result of different representations of the combinatorial condition. These characteristics of the conic relaxations affect the numerical efficiency and stability of the solver used to solve them. We illustrate the theoretical results with numerical experiments on QAP instances solved by SDPT3, SDPNAL+ and the bisection and projection method. Keywords Combinatorial quadratic optimization problems · Binary and complementarity condition · Completely positive relaxations · Doubly nonnegative relaxations · Semidefinite relaxations · Equivalence of feasible regions · Nondegeneracy Mathematics Subject Classification 90C20 · 90C22 · 90C25 · 90C26

N. Ito: This work was supported by Grant-in-Aid for JSPS Research Fellowship JP17J07365. S. Kim: The research was supported by 2017-R1A2B2005119. M. Kojima: This research was supported by Grant-in-Aid for Scientific Research (A) 26242027 and the Japan Science and Technology Agency (JST), the Core Research of Evolutionary Science and Technology (CREST) research project. A. Takeda: The work of this author was supported by Grant-in-Aid for Scientific Research (C), 15K00031. Extended author information available on the last page of the article

123

Journal of Global Optimization

1 Introduction We consider a general nonconvex quadratic optimization problem (abbreviated as QOP) with quadratic equality and inequality constraints. As the quadratic equalities can model the binary and complementarity conditions, QOPs have been studied for formulating various combinatorial optimization problems. More precisely, the binary condition xi ∈ {a, b} can be represented as a quadratic equality (xi − a)(b − xi ) = 0 and the complementarity condition can be written as xi x j = 0. As a result, various combinatorial optimization problems arising from important applications, such as the binary integer quadratic problem (BIQP), maximum stable set problem, max-cut problem, and quadratic assignment problem (QAP) have been dealt with in the framework of QOPs. The optimal value of the nonconvex QOP in general cannot be exactly found efficiently by a computational method. Instead, it is often approximated by a lower bound obtained from a conic relaxation of the problem. A conic relaxation problem is a (linear) conic optimization problem (COP) that minimizes a linear function in a symmetric matrix variable subject to linear equalities and inequalities and a cone constraint. When the cone consists of the positive semidefinite matrices, the doubly nonnegative matrices or the completely positive matrices, the COP is called a semidefinite programming (SDP) problem, a doubly nonnegative programming (DNN) problem or a completely positive programming (CPP) problem, respectively. Two fundamental approaches have been known for constructing a conic relaxation problem from a given QOP. Shor [25] derived an SDP relaxation problem from the Lagrangian dual of a QOP. The other primal-based approach is called the lifting (procedure). Based on these two approaches, Poljak et al. [20] presented a general method for constructing an SDP relaxation problem from a given QOP. The lifting and the Lagrangian dual may be regarded as the most fundamental principles in conic relaxations. Recent developments on CPP reformulations of QOPs, which have shown to attain the exact optimal values of QOPs under rather mild assumptions, have given rise to extensive studies of CPP reformulations of combinatorial QOPs. In particular, QOPs over the standard simplex [8,9], maximum stable set problems [11], graph partitioning problems [21], and quadratic assignment problems [22] are equivalently expressed as CPPs. Burer’s CPP reformulations [10] of a class of linearly constrained QOPs in nonnegative and binary variables generalizes the problems referred above. However, these CPP reformulations of QOPs are mainly of theoretical interest as CPPs are known to be numerically intractable [19]. Numerically tractable DNN relaxations are preferred over SDP relaxations as the former can generally provide a much higher lower bound. But the computational burden of solving a DNN problem increases very rapidly with the matrix size. Numerical methods to mitigate this difficulty have been proposed, for instance, the bisection and projection method [6,16,17] and SDPNAL+ [27]. They both reported numerical results on large-scale DNN problems that could not be solved by primal-dual interior-point methods. Many conic relaxations have been proposed for various QOP instances over the years. In theory, two conic relaxations are determined to be equivalent if they have a common optimal value. This theoretical equivalence, however, never guarantees their computational equivalence. That is, when they are solved by a numerical method, one conic relaxation problem may provide a better approximate optimal value in less execution time than the other. This difference is often caused by the difference in the size of the problem, the existence of primal/dual interior feasible solutions and the primal/dual nondegeneracy. Thus two conic relaxations can be equivalent in some aspects but different in some others.

123

Journal of Global Optimization

The purpose of this paper is, first, to present a theoretical basis that reveals the underlying connections of various conic relaxations of QOPs arising from combinatorial optimization problems, in particular, their equivalences and differences with respect to the optimal value, the sizes of the conic relaxation problems, the existence of primal/dual interior feasible solutions, and the primal/dual nondegeneracy. Second, to further investigate the simplification technique by Burer [10] for reducing the size of matrix variable for numerical efficiency. We show that the technique has the potential to reduce possible primal/dual degeneracy.

1.1 Our framework We briefly explain how various conic relaxations can be generated in a systematic manner from a QOP with a combinatorial condition. Our QOP model is   ζ ∗ = min f 0 (x) : x ∈ Rn+ , f j (x) = 0 (1 ≤ j ≤ ) ,

(1)

x

where Rn denotes the n-dimensional Euclidean space, Rn+ the nonnegative orthant of Rn , f j : Rn → R are defined as f j (x) = x T Q j x + 2cTj x − d j , Q j is a symmetric matrix, c j ∈ Rn , d j ∈ R (0 ≤ j ≤ ). As a combinatorial condition, we consider: (G) Exactly one of x j ( j ∈ J p ) is 1 and all others are 0 (1 ≤ p ≤ m), where J p (1 ≤ p ≤ m) denote distinct subsets of {1, . . . , n} with at least two elements. Condition (G) can be represented as quadratic equalities, thus, (G) can be embedded as the equalities f j (x) = 0 ( j = 1, . . . , ) of QOP (1). It is important to note that the representation is not unique. Condition (G) is an extension of the 0–1 condition x ∈ {0, 1} with a slack variable: x + u = 1 and x, u ∈ {0, 1}, which can be written as (x + u − 1)2 = 0, x(1 − x) = 0 and u(1 − u) = 0. This is the well-known quadratic equality representation of 0–1 variable. Alternatively, the first equality can be replaced by the two equalities (x + u)2 = 1 and x + u = 1, and the last two by the complementarity condition x, u ≥ 0 and xu = 0. Consequently, at least four different combinations of quadratic equality constraints can be obtained in this simple example. The number of quadratic equality representations increases in general cases. Thus, we consider (G) separately from the equalities as   ζ ∗ (G) = min f 0 (x) : x ∈ Rn+ , f j (x) = 0 (1 ≤ j ≤ 0 ), (G) ,

(2)

x

where 0 ≤ 0 ≤  and f j (x) = 0 (1 ≤ j ≤ 0 ) are given quadratic equality constraints. For a conic relaxation of QOP (2), we apply the following two procedures to (2): (Q) Replace Condition (G) with an equivalent set of quadratic equalities f j (x) = 0 (0 +1 ≤ j ≤ 0 + 1 ) for some 1 to obtain a QOP of the form (1) with  = 0 + 1 . (L) Apply the standard lifting to QOP (1) with a closed convex cone, chosen among the PSD (positive semidefinite), DNN and CPP cones. As a result of Procedure (L) applied to QOP (1), we obtain a COP, which depends on the choices of quadratic equalities to represent Condition (G) in (Q) and the closed convex cone in (L). Although some of the COPs with a common closed convex cone, say the DNN cone, have an equivalent optimal value, they may be different in other issues related to the numerical efficiency and stability.

123

Journal of Global Optimization

1.2 Related work and our contribution This paper is related to Bomze et al. [7] in that both aim to investigate connections of existing and new conic relaxations for QOPs in nonnegative variables and binary variables. While the original version of this paper and theirs were written independently, there exist some common results as well as different ones. Among the differences between the two papers, we should mention that • our framework of the quadratically constrained QOP with the combinatorial constraint (G) is more general than their framework of the linearly constrained QOP, • our paper considers the complementarity condition, another fundamental condition to formulate various combinatorial optimization problems beside the binary condition; the complementary condition was not treated in [7]. • a necessary and sufficient condition is given for the class of QOPs with linear equality, binary and complementarity constraints in nonnegative variables, which is a subclass of the quadratically constrained QOP with the combinatorial constraint (G), to be equivalent to their CPP relaxations. Such a necessary and sufficient condition was not discussed in [7] We also investigate in detail • how Burer’s simplification technique [10] affects the existence of primal/dual interior feasible solutions and the primal/dual nondegeneracy, • how various existing and new conic relaxations of QAPs can be derived based on our main theoretical results. In addition, we present • extensive numerical results to see how different DNN relaxations of QAPs affect the numerical behavior of two methods: SDPNAL+ [27] which is designed under the validity of Slater’s and primal/dual nondegeneracy conditions; and the BP (bisection and projection) method which is a robust first order method recently proposed by [17] (see also [6,16]). For some common results, our treatment of linear constraints and binary (zero-one) constraints in the construction of conic relaxations are essentially the same as those in [7]. To make our presentation complete, we have quoted Theorem 6 of [7] on the existence of a dual interior feasible solution and the strong duality for a fairly general conic optimization problem.

1.3 Outline of the paper This paper is organized as follows: in Sect. 2, we introduce a primal-dual pair of general COPs over a closed pointed (not necessarily convex) cone, which are used to represent both QOPs and their various conic relaxations throughout the paper. We present fundamental results on the nonexistence of a primal interior feasible solution of the COP from Lemma 2.4 of [5], the existence of a dual interior feasible solution and the strong duality from Theorem 6 of [7], and the convexfication of the primal COP from Theorem 3.1 of [5]. In the subsequent sections, we apply these results to a class of conic relaxations of the combinatorial QOP (2) and their

123

Journal of Global Optimization

simplifications [10]. We then explain Procedure (L) to lift QOP (1) to the general COP. The main results of this paper are included in Sects. 3, 4 and 5. Specifically, Sect. 3 is devoted to Procedure (Q) in detail. We also show fundamental relations among the liftings of quadratic equality constraints for representing Condition (G). Although some of the theoretical results there were shown in [7] as mentioned above, we will give their proofs for the paper to be selfcontained. In Sect. 4, we investigate issues related to the numerical efficiency and stability among the conic relaxation problems of QOP (2) generated in Sect. 3. Section 5 extends Burer’s simplification technique [10] to COPs over positive semidefinite, DNN and CPP cones. In particular, we discuss the effectiveness of the technique to resolve the primal/dual degeneracy in the conic relaxation. In Sect. 6, our main theoretical results in Sects. 3, 4 and 5 are applied to two classes of QOP instances, the BIQP and the QAP. Relations among the existing conic relaxations of these instances and the newly presented conic relaxations in Sect. 3 are shown. In Sect. 7, numerical results on QAP instances are presented to partially illustrate the theoretical results in Sects. 3, 4 and 5.

2 Preliminaries 2.1 Notation and symbols Let Rn denote the n-dimensional Euclidean space. We assume that each x ∈ Rn is a column vector of elements xi (1 ≤ i ≤ n), and x T denotes the transpose of x ∈ Rn . Let Rn+ denote the nonnegative orthant {x ∈ Rn : x ≥ 0} of Rn . Let Sm denote the linear space of m × m real symmetric matrices. We introduce cones of matrices in Sm as follows:   m T m Sm + = A ∈ S : z Az ≥ 0 for all z ∈ R   (the positive semidefinite (PSD) cone), = the convex hull of zz T : z ∈ Rm    m = zz T : z ∈ Rm + ,    (1 ≤ i ≤ r ) B = ri=1 z i z iT , z i ∈ Rm m m + CPP = B ∈ S : for some positive integer r = co m , the convex hull of  m (the completely positive (CPP) cone),   N = A ∈ Sm : Ai j ≥ 0 (1 ≤ i ≤ m, 1 ≤ j ≤ m) m

(the cone of nonnegative matrices), Dm NN

m = Sm (the doubly nonnegative (DNN) cone). +∩N

Note that  m is a closed nonconvex cone in Sm if m ≥ 2 and that all others are closed convex pointed cones with nonempty interior in Sm . For the aforementioned cones and their dual m m m ∗ m ∗ m )∗ hold. cones, the relations  m ⊂ Cm PP ⊂ DNN ⊂ S+ ⊂ (DNN ) ⊂ (CPP ) = ( m m m Given matrices A, B ∈ S , A • B stands for the inner product i=1 j=1 Ai j Bi j . Given Q ∈ Sm , we often write the quadratic form x T Qx in a vector variable x ∈ Rm as Q • x x T , which is relaxed into a linear form Q • Y in the matrix variable Y ∈ Sm + by replacing m x x T ∈ Sm + with Y ∈ S+ . The notation diag(Y ) means the m-dimensional column vector consisting of the diagonal elements Yii (1 ≤ i ≤ m) of Y ∈ Sm . With this notation, the 0–1 condition xi ∈ {0, 1} (1 ≤ i ≤ m) for x ∈ Rm can be written as x = diag(x x T ).

123

Journal of Global Optimization

2.2 A class of conic optimization problems Let H 0 , F 0 ∈ Sm . The descriptions of H 0 and F 0 are given in the next subsection. Given a closed (not necessarily convex) cone J ⊂ Sm and a linear subspace L = {Z ∈ Sm : F j • Z = 0 (1 ≤ j ≤ )} Sm

(3)

Sm

of generated by some given F j ∈ (1 ≤ j ≤ ), we consider a primal-dual pair of conic optimization problem (COP)   P(J, L) : ζp (J, L) = min F 0 • Z : Z ∈ J, H 0 • Z = 1, Z ∈ L , Z   D(J, L) : ζd (J, L) = max y0 : F 0 − H 0 y0 − W = S ∈ J∗ , W ∈ L ⊥ , y0 ,W ,S

L⊥

is the orthogonal complement of L. Notice that three types of constraints exist where in P(J, L): a cone constraint Z ∈ J, a single inhomogeneous linear equality H 0 • Z = 1, and a linear space constraint Z ∈ L (or homogeneous linear equality constraints). In the subsequent discussion, we frequently represent a QOP and its conic relaxations in terms of P(J, L) with some closed cone J ⊃  m and some linear subspace L of Sm with m = 1 + n or m = n. We will impose the following conditions in the lemma below. (0) (I) (II) (III) (IV) (V)

The feasible region of P(J, L) is nonempty and H 0 ∈ (J ∩ L)∗ . The feasible region of P(J, L) is nonempty, H 0 ∈ J∗ and F j ∈ J∗ (1 ≤ j ≤ ). J is a pointed closed convex cone with nonempty interior. F 0 • D > 0 for every nonzero D ∈ J ∩ L such that H 0 • D = 0. F 0 • D ≥ 0 for every nonzero D ∈ J ∩ L such that H 0 • D = 0. O  = F j ∈ J∗ for some j ∈ {1, . . . , }.

Conditions (I), (II), (III) and (IV) correspond to Conditions (I), (II), (III) and (IV) of [5], respectively. Condition (II) above is strengthened from the original one in [5] by imposing ‘pointed’ and ‘nonempty interior’ on a closed convex cone J. It ensures that the dual cone J∗ is also a pointed closed convex cone with nonempty interior. This change is to avoid the discussion on relative interior points of J and J∗ . The other closed convex cones considered k , D k , C k with k ∈ {n, 1 + n}, which all satisfy (II). Condition (III) in this paper are S+ NN PP from Theorem 6 of Bomze et al. [7] is described differently from the original one in [5], but they are equivalent under the assumption that the feasible region of P(J, L) is nonempty. Condition (0) is from [7]. It is interesting to note that Condition (IV) for the convexification is slightly weaker than Condition (III) for the strong duality in Lemma 2.1. Lemma 2.1 (i) (Nonexistence of an interior feasible solution in P(J, L), Lemma 2.4 of [5]) Assume that (II) and (V) hold. Then there is no feasible solution Z of P(J, L) which lies in the interior of J. (ii) (Existence of an interior feasible solution in D(J, L) and the strong duality, Theorem 6 of [7]) Assume that Conditions (0) and (II) hold. Then there is a feasible solution (y0 , W , S) of D(J, L) such that S lies in the interior of J∗ if and only if Condition (III) holds. In such a case, ζp (J, L) = ζd (J, L). (iii) (Convexification, Theorem 3.1 of [5]) Assume that (I) holds. Then ζp (J, L) = ζp (coJ, L) if and only if (IV) holds or ζp (J, L) = −∞. Here coJ denotes the convex hull of J. Proof Since (ii) and (iii) follow directly from Theorem 6 of [7] and Theorem 3.1 of [5], respectively, we only give a proof of (i), which is also a slight modification of the proof

123

Journal of Global Optimization

of Lemma 2.4 of [5]. Let Z be an arbitrary interior point of J. By (V), O  = F j ∈ J∗ for some j ∈ {1, . . . , }. Then

Z − F  j ∈ J for some  > 0. It follows that F j • Z > F j • Z −  F j • F j = F j • Z −  F j ≥ 0. Hence F j • Z > 0. Thus we have shown that any interior point Z of J can not be a feasible solution of P(J, L). 

Remark 2.1 Suppose that Conditions (0) and (II) are satisfied. Then (III) ensures the strong duality between P(J, L) and D(J, L) by (ii). However, (III) is not necessary for the strong duality. In fact, if we take L = Sm , F 0 = O and a nonzero H 0 lying on the boundary of J∗ , the dual interior feasible region is empty, but the strong duality holds since the primal interior feasible region is nonempty. For a more important example, we briefly mention the Lagrangian-dual method [5,6,17].  Suppose that Conditions (I) and (II) hold. Let H 1 = j=1 F j and L sum = {Z : H 1 • Z = 0}. Then Z ∈ J ∩ L is equivalent to Z ∈ J ∩ L sum . We consider the primal-dual pair of COPs: η p (λ) = min {F 0 • Z + λH 1 • Z : Z ∈ J, H 0 • Z = 1} , Z   ηd (λ) = max y0 : F 0 + λH 1 − H 0 y0 = S ∈ J∗ . y0 ,S

Here λ ∈ R is a Lagrangian multiplier and the term λH 1 • Z serves as a penalty for the violation of Z ∈ L sum . It was shown in Lemma 2.3 of [5] that η p (λ) = ηd (λ) for every λ ∈ R and that ηd (λ) converges to ζd (J, L) as λ → ∞. If in addition Condition (III) holds, then η p (λ) converges to ζ p (J, L) as λ → ∞; hence ζ p (J, L) = ζd (J, L) follows. See Sect. 2 of [5] for more details.

2.3 A general QOP and its conic relaxations To derive a conic relaxation of QOP (1) by applying the lifting procedure in a systematic manner, we introduce some constant and variable matrices. Let H 0 = the (1 + n) × (1 + n) matrix with 1 at the upper-left corner and 0 elsewhere,



− d j cTj x xT ∈ S1+n . Fj = ∈ S1+n (0 ≤ j ≤ ), Z = 0 x Y cj Qj

1 xT Then each quadratic function f j is written as f j (x) = F j • , and the function f j x x xT in x ∈ Rn is lifted to a linear function f¯j in Z ∈ S1+n as follows: f¯j (Z) = F j • Z with H 0 • Z = x0 = 1. If we compare f j (x) with f¯j (Z), we see that x x T is replaced by Y ∈ Sn . Define L by (3) for the F j ∈ S1+n (1 ≤ j ≤ ) given above. Since Z ∈  1+n and H 0 • Z = 1 if and only if x ∈ Rn+ and Y = x x T , P( 1+n , L) coincides with QOP (1); hence 1+n 1+n ζp ( 1+n , L) = ζ ∗ . By letting K1+n = S1+n + , DNN and CPP , we get the SDP, DNN, and CPP 1+n 1+n 1+n 1+n ⊃ relaxations P(K , L) of QOP (1), respectively. Since S1+n + ⊃ DNN ⊃ CPP = co 1+n 1+n 1+n 1+n 1+n ∗  , it follows that ζp (S+ , L) ≤ ζp (DNN , L) ≤ ζp (CPP , L) ≤ ζp ( , L) = ζ .

3 Lifted constraints of equivalent quadratic constraints In this section, we discuss Procedure (Q) in detail to derive QOP (1) from QOP (2) by representing Condition (G) in QOP (2) with a set of quadratic equalities. Many combinatorial optimization problems, such as BIQPs, QAPs, and maximum stable set problems, (implicitly)

123

Journal of Global Optimization

 include (G) as constraints. Notice that the equality i∈J p xi = 1 holds if (G) is satisfied. In particular, when J p consists of two distinct i and j, x j serves a slack variable for xi and vice versa. This special case will be further studied in Sect. 6.1. A more general case where J p includes more than two elements is applied to QAPs in Sect. 6.2. Let e J p ∈ Rn be a 0–1 vector whose ith element is 1 if i ∈ J p and 0 otherwise. Define   1 − eTJp + T and E Jp = E Jp = e Jp e Jp (1 ≤ p ≤ m). − e Jp E Jp Condition (G) can be interpreted as two different sets of constraints. First, linear equalities and 0–1 conditions: eTJp x − 1 = 0 and x 2j − x j = 0 ( j ∈ J p ) (1 ≤ p ≤ m).

(4)

Second, linear equalities and complementarity conditions: eTJp x − 1 = 0 and xi x j = 0 (i, j ∈ J p , i  = j) (1 ≤ p ≤ m).

(5)

Moreover, several reformulations of the linear equality constraint eTJp x−1 = 0 as quadratic equalities can be induced. This motivates us to examine the differences and equivalences among them. In Sect. 3.1, we first state three equivalent reformulations of the linear constraints in quadratic equalities, and show the equivalence between their lifted constraints. Then the differences of the lifted constraints of the 0–1 and complementarity conditions are discussed in Sect. 3.2. In Sect. 3.3, we describe a general COP.

3.1 Linear constraints We present three different representations of linear constraints in quadratic equalities and their lifted equalities. First, eTJp x − 1 = 0 is simply squared to obtain the quadratic equality

x0 x T + T 2 = 0 and x0 = H 0 • Z = 1. (e J p x − 1) = 0, which can be written as E J p • x x xT Thus, its lifted constraint is as follows:   • Z = 0 (1 ≤ p ≤ m) and H 0 • Z = 1. (E1) Z ∈ L E1 ≡ Z ∈ S1+n : E + Jp In [3], a CPP reformulation of a class of QOPs using (E1) is proposed by Arima, Kim, and Kojima; See also [5]. Second, consider a pair of the linear constraint eTJp x = 1 and the redundant quadratic constraint x = x x T e J p , which are lifted to the following constraints:   (E2) Z ∈ L E2 ≡ Z ∈ S1+n : eTJp x = x0 and x = Y e J p (1 ≤ p ≤ m) and H 0 • Z = 1. Condition (E2) was used in [23] for SDP and DNN relaxations of QAPs (denoted by QAPR0 , QAPR2 and QAPR3 ). These relaxations are presented in detail in Sect. 6.2.1. Finally, by lifting the linear constraint eTJp x = 1 and the redundant quadratic constraint (eTJp x)2 = 1, we obtain the following condition:   (E3) Z ∈ L E3 ≡ Z ∈ S1+n : eTJp x = x0 and eTJp Y e J p = x0 (1 ≤ p ≤ m) and H 0 • Z = 1.

123

Journal of Global Optimization

The following lemma shows that

(E1), (E2), and (E3) are equivalent under the semix0 x T ∈ S1+n definite constraints Z = + , but the equivalence does not hold in general. x Y Lemma 3.1 (i) L E2 ⊂ L E3 ⊂ L E1 . 1+n 1+n (ii) L E2 ∩ S1+n + = L E3 ∩ S+ = L E1 ∩ S+ . Proof (i) Let Z ∈ L E2 . Then eTJp x = x0 and x = Y e J p (1 ≤ p ≤ m). By multiplying eTJp to x = Y e J p (1 ≤ p ≤ m), we obtain eTJp Y e J p = x0 (1 ≤ p ≤ m). Thus, Z ∈ L E3 . To show L E3 ⊂ L E1 , we rewrite the two equalities (with each p) characterizing L E3 as    

2 − eTJp −1 0T x0 x T x0 x T = 0 and = 0, • • 0 e J p eTJp x Y x Y − e Jp O respectively. Then, we obtain E + J p • Z = 0 by adding these equalities. As a result, L E3 ⊂ L E1 . 1+n (ii) In view of (i), it suffices to show that L E1 ∩ S1+n + ⊂ L E2 ∩ S+ . The

equality (for each   T 1 x0 x T p) characterizing L E1 is equivalent to 1 − e J p = 0, which implies −e J p x Y



1 x0 x T x0 x T ∈ S1+n = 0 if 

+ . −e J p x Y x Y

Remark 3.1 The discussions in this section are valid for the lifting of any system of general linear equalities b p − a Tp x = 0 (1 ≤ p ≤ m) with a slight modification, where b p ∈ R and a p ∈ Rn (1 ≤ p ≤ m). In this general case, Conditions (E1), (E2) and (E3) turn out to be

  − b p a Tp b2p ¯ Z ∈ L¯ E1 ≡ Z ∈ S1+n : • Z = 0 (1 ≤ p ≤ m) and H 0 • (E1) − a pbp apap Z = 1.   ¯ (E2) Z ∈ L¯ E2 ≡ Z ∈ S1+n : a Tp x = b p x0 , b p x = Y a p (1 ≤ p ≤ m) and H 0 • Z = 1.   ¯ Z ∈ L¯ E3 ≡ Z ∈ S1+n : a Tp x = b p x0 , b2p x0 = a Tp Y a p (1 ≤ p ≤ m) and H 0 • (E3) Z = 1. ¯ to Lemma 3.1 remains valid with this modification. Burer [10] employed Condition (E3) derive a CPP reformulation of a class of linearly constrained QOPs in binary and continuous variables. The linear spaces L¯ E2 and L¯ E3 coincide with L2 and L3 in [7], respectively. The relations for L E2 and L E3 in Lemma 3.1 also follow from Theorem 1 of [7]. For the linear spaces L1 and L4 introduced in [7], we note that L4 corresponds to an extension of L E1sum defined in the subsequent discussion by (8) to the system of general linear equalities. But it seems difficult to adapt L1 for QOP (2) with quadratic equalities.

3.2 Representing a combinatorial constraint with 0–1 or complementarity condition Condition (G) has been expressed by using linear and 0–1 constraints as in (4). Alternatively, it has been expressed by using the linear and complementarity constraints as in (5). We now focus on the liftings of the 0–1 and the complementarity constraints to S1+n , which are stated as Conditions (Z) and (C) respectively as follows:   (Z) Z ∈ L Z ≡ Z ∈ S1+n : x j = Y j j ( j ∈ J p , 1 ≤ p ≤ m) .

123

Journal of Global Optimization

  (C) Z ∈ L C ≡ Z ∈ S1+n : Yi j = 0 (i, j ∈ J p , i  = j, 1 ≤ p ≤ m) . The following lemma shows the relation of (Z) and (C). Lemma 3.2 (i) L C ∩ L E2 ⊂ L Z ∩ L E2 . (ii) L C ∩ L E2 ∩ N1+n = L Z ∩ L E2 ∩ N1+n . (iii) If J p consists of two elements i and j, then the three conditions xi = Yii , x j = Y j j and Yi j = 0 are equivalent (i, j ∈ J p , i  = j). Hence L C ∩ L E2 = L Z ∩ L E2 in this case. 1+n 1+n 1+n (iv) L C ∩ L E1 ∩ D1+n NN = L C ∩ L E2 ∩ DNN = L C ∩ L E3 ∩ DNN = L Z ∩ L E1 ∩ DNN = 1+n L Z ∩ L E2 ∩ D1+n NN = L Z ∩ L E3 ∩ DNN . = L C ∩ L E2 ∩ S1+n = (v) If J p consists of two elements i and j, then L C ∩ L E1 ∩ S1+n + + 1+n 1+n 1+n . L C ∩ L E3 ∩ S+ = L Z ∩ L E1 ∩ S+ = L Z ∩ L E2 ∩ S+ = L Z ∩ L E3 ∩ S1+n +  Proof To prove assertion (i), (ii) and (iii), assume that Z ∈ L E2 . Then, Y j j + k∈J p \{ j} Y jk =  x j ( j ∈ J p , 1 ≤ p ≤ m). If, in addition, Z ∈ L C , then k∈J p \{ j} Y jk = 0 ( j ∈ J p , 1 ≤  p ≤ m). Thus, (i) follows. Now if Z ∈ N1+n , then Z ∈ L C iff k∈J p \{ j} Y jk = 0 ( j ∈ J p , 1 ≤ p ≤ m). Hence (ii) holds. Next, if J p consists of two elements i and j, then we have the identities Yii + Yi j = xi and Y j j + Y ji = x j (i, j ∈ J p , i  = j, 1 ≤ p ≤ m). Since Yi j = Y ji (1 ≤ i < j ≤ n), (iii) follows. (iv) follows from (ii) and Lemma 3.1, and (v) from (iii) and Lemma 3.1. 

Remark 3.2 The linear space L Z is essentially equivalent to B1 in Bomze et al. [7], and the last equality in (iv) of Lemma 3.2 was stated in Proposition 1 of [7]. In addition, they introduced the linear space B2 induced from an aggregation of binary constraints, and showed some relations involving B1 and B2 in Proposition 1 of [7]. But note that the linear spaces L C and its aggregation L Csum defined in Sect. 4.1 were not dealt with in [7].

3.3 Representation of COP The linear subspace L in P(K1+n , L) is expressed as L 0 ∩ L a ∩ L b using each (L a , L b ) ∈ {L E1 , L E2 , L E3 } × {L C , L Z }, and the linear space L 0 constructed by the remaining homogeneous linear equalities lifted from the quadratic equalities of QOP (2) is defined by:   L 0 = Z ∈ S1+n : F j • Z = 0 (1 ≤ j ≤ 0 ) . (6) For simplicity of notation, we write the feasible region of P(K1+n , L) as Feas(K1+n , L). Thus P(K1+n , L 0 ∩ L a ∩ L b ) can be rewritten as   ζp (K1+n , L 0 ∩ L a ∩ L b ) = min F 0 • Z : Z ∈ Feas(K1+n , L 0 ∩ L a ∩ L b ) . Z

Since Z ∈  1+n and H 0 • Z = 1 iff x ∈ Rn+ and Y = x x T , for any L a ∈ {L E1 , L E2 , L E3 }, Z ∈ L a ∩ L Z ∩  1+n iff (4) holds, and Z ∈ L a ∩ L C ∩  1+n iff (5) holds. Therefore, for any (L a , L b ) ∈ {L E1 , L E2 , L E3 } × {L C , L Z }, P( 1+n , L 0 ∩ L a ∩ L b ) is equivalent to QOP (2). 1+n 1+n By letting K1+n = S1+n + , DNN and CPP , we obtain respectively the SDP, DNN and CPP relaxations of QOP (2). The following theorem, obtained as a corollary of Lemmas 3.1 and 3.2, shows their relations. Theorem 3.1 For any (L a , L b ) and (L a¯ , L b¯ ) in {L E1 , L E2 , L E3 } × {L Z , L C }, we have

123

Journal of Global Optimization 1+n Feas(S1+n + , L 0 ∩ L a ∩ L Z ) = Feas(S+ , L 0 ∩ L a¯ ∩ L Z ) 1+n ⊃ Feas(S1+n + , L 0 ∩ L a ∩ L C ) = Feas(S+ , L 0 ∩ L a¯ ∩ L C ) 1+n ⊃ Feas(D1+n NN , L 0 ∩ L a ∩ L b ) = Feas(DNN , L 0 ∩ L a¯ ∩ L b¯ ) 1+n ⊃ Feas(C1+n PP , L 0 ∩ L a ∩ L b ) = Feas(CPP , L 0 ∩ L a¯ ∩ L b¯ )

⊃ Feas( 1+n , L 0 ∩ L a ∩ L b ) = Feas( 1+n , L 0 ∩ L a¯ ∩ L b¯ ), 1+n Feas(S1+n + , L 0 ∩ L a ∩ L b ) = Feas(S+ , L 0 ∩ L a¯ ∩ L b¯ ) if |J p | = 2 (1 ≤ p ≤ m).

  1+n 1+n . The following theorem shows that all P(K1+n , L 0 ∩ Let K1+n ∈ S1+n + , DNN , CPP L a ∩ L b ) ((L a , L b ) ∈ {L E1 , L E2 , L E3 } × {L Z , L C }) are equivalent with respect to the nonexistence of a primal interior feasible solution, the existence of a dual interior feasible solution, and the strong duality.   1+n 1+n and (L a , L b ) ∈ {L E1 , L E2 , L E3 }×{L Z , L C }. Theorem 3.2 Let K1+n ∈ S1+n + , DNN , CPP (i) (No primal interior feasible solution) If m ≥ 1 (i.e., Condition (G) is not empty), then Feas(K1+n , L 0 ∩ L a ∩ L b ) contains no interior point of K1+n . (ii) (Existence of a dual interior feasible solution and strong duality) There is a feasible solution (y0 , W , S) of D(K1+n , L 0 ∩ L a ∩ L b ) such that S lies in the interior of (K1+n )∗ if and only if Condition (III) holds with J = K1+n and L = L 0 ∩ L a ∩ L b . In such a case, ζp (K1+n , L 0 ∩ L a ∩ L b ) = ζd (K1+n , L 0 ∩ L a ∩ L b ). (iii) (CPP reformulation) Assume QOP (2) is feasible and that ∗  1+n F j ∈ D1+n = S1+n (1 ≤ j ≤ 0 ) (7) + +N NN ∗ holds. Then, for the optimal value ζ ∗ of QOP (2), ζ p (C1+n PP , L 0 ∩ L a ∩ L b ) = ζ if and 1+n 1+n ∗ only if Condition (IV) holds with K = and L = L 0 ∩ L a ∩ L b or ζ = −∞.

Proof (i) Consider the COP P(K1+n , L 0 ∩ L E1 ∩ L Z ). Then E + J p • Z = 0 with

1+n 1+n )∗ is a linear equality that defines L . By (i) of Lemma 2.1, O = E + E1 J p ∈ S+ ⊂ (K

Feas(K1+n , L 0 ∩ L E1 ∩ L Z ) contains no interior point of K1+n . Since Feas(K1+n , L 0 ∩ L a ∩ L b ) ⊂ Feas(K1+n , L 0 ∩ L E1 ∩ L Z ) for all (L a , L b ) ∈ {L E1 , L E2 , L E3 } × {L Z , L C }, (i) follows. 1+n ∩ L ∩ L ∩ L )∗ , (ii) follows from (ii) of Lemma 2.1. (ii) Since H 0 ∈ S1+n 0 a b + ⊂ (K 1+n (iii) Consider the COP P( , L 0 ∩ L E1 ∩ L C ), which is equivalent to QOP (2) with the optimal value ζ ∗ . From the assumption, we see that ∅  = Feas( 1+n , L 0 ∩ L E1 ∩ L C ). We 1+n )∗ . By representing L also see that H 0 ∈ S1+n E1 and L C as + ⊂ (   L E1 = Z ∈ S1+n : F j • Z = 0 (0 + 1 ≤ j ≤ 1 ) ,   L C = Z ∈ S1+n : F k • Z = 0 (1 + 1 ≤ k ≤ ) , where each F j corresponds to some E + J p in Condition (E1), and each F k • Z = 0 to some identity Yi j = 0 in Condition (C), it follows that F j ∈ S1+n + (0 + 1 ≤ j ≤ 1 ) and  ∗ 1+n 1+n (1 + 1 ≤ k ≤ ). Thus, we have F j ∈ DNN ⊂ ( 1+n )∗ (1 ≤ j ≤ ). Fk ∈ N Hence Condition (I) holds with J =  1+n and L = L 0 ∩ L E1 ∩ L C . By (iii) of Lemma 2.1, 1+n , L 0 ∩ L E1 ∩ L C ) = ζ ∗ ζp (C1+n PP , L 0 ∩ L E1 ∩ L C ) = ζp (

123

Journal of Global Optimization

if and only if Condition (IV) with J =  1+n and L = L 0 ∩L E1 ∩L C holds or ζ ∗ = −∞. Since  1+n ∩ L 0 ∩ L a ∩ L b =  1+n ∩ L 0 ∩ L E1 ∩ L C for all (L a , L b ) ∈ {L E1 , L E2 , L E3 }×{L Z , L C } by (iv) of Lemma 3.2, Assertion (iii) follows. 

As a special case, we obtain the following corollary, which will be used in Sect. 6.   1+n 1+n Corollary 3.1 Let K1+n ∈ S1+n and (L a , L b ) ∈ {L E1 , L E2 , L E3 }×{L Z , L C } , D , C + NN PP be arbitrarily fixed. Assume that QOP (2) is feasible, and one of the two conditions (a)  m ≥ 1 and Feas(K1+n , L 0 ∩ L a ∩ L b ) is bounded, (b) mp=1 J p = {1, . . . , n}, holds. Then, (i) Feas(K1+n , L 0 ∩ L a ∩ L b ) contains no interior point of K1+n . (ii) There is a feasible solution (y0 , W , S) of D(K1+n , L 0 ∩ L a ∩ L b ) such that S lies in the interior of (K1+n )∗ and ζp (K1+n , L 0 ∩ L a ∩ L b ) = ζd (K1+n , L 0 ∩ L a ∩ L b ). ∗ (iii) Assume that (7) holds. Then ζ p (C1+n PP , L 0 ∩ L a ∩ L b ) = ζ . Proof (i) follows directly from (i) of Theorem 3.2. To prove (ii) and (iii), we first show that (b) implies (a). P(S1+n ∈ Feas(S1+n + , L E2 ∩ L Z ). For all Z  + , L E2 mConsider ∩n L Z ), (b) implies  n n T x ≤ nm; hence trace(Z) = 1 + x ≤ e i=1 i p=1 J p i=1 Yii = 1 + i=1 x i ≤ 1 + nm. Therefore Feas(K1+n , L 0 ∩L a ∩L b ) ⊂ Feas(S1+n + , L 0 ∩L E2 ∩L Z ) is contained in the bounded : trace(Z) ≤ 1 + nm}, where the inclusion follows from Theorem 3.1. Now set {Z ∈ S1+n + we prove (ii) and (iii) under the assumption (a). Since QOP (2) is feasible, Feas(K1+n , L 0 ∩ L a ∩ L b ) is nonempty and bounded. Hence there is no nonzero D ∈ K1+n ∩ L 0 ∩ L a ∩ L b such that H 0 • D = 0, and (III) and (IV) hold with J ∈ { 1+n , K1+n } and L = L 0 ∩ L a ∩ L b . Therefore (ii) and (iii) follow from (ii) and (iii) of Theorem 3.2, respectively. 

3.4 Decomposing the constraint F j • Z = 0 with H 0 • Z = 1 and Z ∈ 01+n under the condition (7) Throughout this subsection, we assume (7), and show

that each single constraint F j • Z = x0 x T 0 with x0 = H 0 • Z = 1 and Z = ∈  1+n can be decomposed into an x x xT equivalent family of linear equality and complementarity constraints in nonnegative variables x1 , . . . , xn . Let j ∈ {1, . . . , 0 } be arbitrarily fixed, and let F = F j for simplicity of notation. It follows from (7) that F can be represented as F = G + C for some G ∈ S1+n and + C ∈ N1+n . We may assume that all the diagonal elements of C are zero since any positive value on the diagonal of C can be eliminated and added to the diagonal of G. Furthermore, p T G ∈ S1+n is decomposed into the sum of rank 1 matrices such that G = + i=1 gi gi , 1+n and C∈ N into the sum of matrices with two off-diagonal positive elements such that C = (i, j)∈E C i j , where C i j denotes a matrix in N1+n with a positive value at (i, j)th and ( j, i)th elements and 0 elsewhere, and E is a subset of {(i, j) :T 1 ≤ i < j ≤ 1 + n}. Thus, x x the constraints F • Z = 0, x0 = H 0 • Z = 1 and Z = 0 ∈  1+n can be rewritten x x xT

p  1 xT 1 xT as x ≥ 0, i=1 giT gi + (i, j)∈E C i j • = 0, or equivalently, T x xx x x xT 1 = 0 (1 ≤ i ≤ p) (linear equality constraints), x ≥ 0, giT x

123

Journal of Global Optimization



1 xT 1

xT





= 0 ((i, j) ∈ E , 1 < i < j) (complementarity constraints),

i

1 xT

j

= 0, or, x j−1 = 0 ((1, j) ∈ E ).



j

If the last constraint exists, the variable x j−1 can be eliminated from QOP (2). Therefore, we have shown that each constraint F j • Z = 0 with H 0 • Z = 1 and Z ∈  1+n can be converted to an equivalent family of linear equality constraints and complementarity constraints. It should be noted that (iii) of Theorem 3.2 provides a necessary and sufficient condition for the equivalence of QOP (2) with such constraints to its CPP relaxation.

4 Issues on computational efficiency and stability in DNN relaxations When we consider DNN relaxations for computation, we realize that various equivalent DNN relaxations are available from the theoretical point of view. For instance, P(D1+n NN , L 0 ∩ L a ∩ L b ) with each (L a , L b ) ∈ {L E1 , L E2 , L E3 } × {L Z , L C } are equivalent to each other in theory. The same statement also holds true for the relaxations to be defined in Sect. 5, namely, P (DnNN , L 0 ∩ L a ∩ L b ) with each (L a , L b ) ∈ {L E1 , L E2 , L E3 } × {L Z , L C }. The size of conic relaxations, the existence of primal/dual interior feasible solutions and the primal/dual nondegeneracy are three most important factors for an efficient and stable implementation of conic relaxations. The size of a conic relaxation means the dimension of the variable matrix and the number of linear equality constraints. The size (1 + n) of the variable matrix Z will be reduced to n by the simplification technique in Sect. 5. In Sect. 4.1, we compare the numbers of linear equalities involved in L E1 through L C , and discuss how to reduce the number of linear equalities in P(D1+n NN , L 0 ∩ L E1 ∩ L C ). The technique to reduce the number of linear equalities can also be applied to L E1 through L C . The existence of primal/dual interior feasible solutions and the primal/dual nondegeneracy in the conic relaxation problems of QOP (2) are crucial to the successful execution of a primal-dual interior-point method and SDPNAL+, which were designed by assuming these conditions for their stable and fast convergence. They are discussed in Sects. 4.2 and 4.3, respectively.

4.1 The number of linear equalities Consider the DNN relaxation P(D1+n NN , L 0 ∩L a ∩L b ) with some (L a , L b ) ∈ {L E1 , L E2 , L E3 }× {L Z , L C } for computing a lower bound for QOP (2). As L E1 , L E2 and L E3 involve m, m +mn and 2m linear equalities, respectively, L E2 may not be the best choice for computational efficiency. From the positive semidefiniteness of the coefficient matrix E + J p of each linear 1+n equality in L E1 (1 ≤ p ≤ m), we see that E + J p • Z ≥ 0 for every Z ∈ S+ . Thus, by defining ⎫ ⎧ ⎞ ⎛ m ⎬ ⎨  ⎠• Z =0 , L E1sum ≡ Z ∈ S1+n : ⎝ (8) E+ Jp ⎭ ⎩ p=1

we obtain L E1 ∩ S1+n = L E1sum ∩ S1+n + + . We note that L E1sum contains only one linear equality. This can be regarded as a clear advantage of Condition  (E1). Now, we compare Conditions (Z) and (C). As L Z involves mp=1 |J p | linear equalities and  L C involves mp=1 (|J p | − 1)|J p |/2 linear equalities Yi j = Y ji (1 ≤ i, j ≤ n) for Y ∈ Sn ,

123

Journal of Global Optimization

(Z) may seem more efficient than (C). Since Yi j ≥ 0 (1 ≤ i, j ≤ n) for every Z ∈ N1+n , however, we see that L C ∩ N1+n = L Csum ∩ N1+n , where ⎧ ⎫ m  ⎨ ⎬   L Csum = Z ∈ S1+n : Yi j = 0 . ⎩ ⎭ p=1 i∈J p j∈J p , j>i

As L Csum involves only one equality, it is more efficient to employ L Csum than L Z or L C for the DNN relaxation. When (7) holds, all the homogeneous constraints in Feas(D1+n NN , L 0 ∩ L E1 ∩ L C ) can be further combined into a single constraint. This was presented in [4] for a class of linearly constrained QOPs in binary variables. See also Remark 2.1 We note that the constraints Z ∈ L Z ∩ N1+n and Z ∈ L C ∩ N1+n can be treated as cone constraints. In fact, both L Z ∩ N1+n and L C ∩ N1+n are polyhedral cones in S1+n . The metric projection of Z ∈ S1+n onto L Z ∩ N1+n was presented for the bisection and projection algorithm in [16]. Computing the metric projection of Z ∈ S1+n onto L C ∩ N1+n is trivial as the elements Yi j are replaced by 0 if i ∈ J p , j ∈ J p , i  = j and 1 ≤ p ≤ m, and max{0, Yi j } otherwise. Both computations have been used for the bisection and projection algorithm [17], and they can also be incorporated directly in SDPNAL+ [27].

4.2 The existence of interior feasible solutions of COPs and their dual We first discuss the existence of interior feasible solutions of the primal-dual pair of COPs P(J, L) and D(J, L) given in Sect. 2.2. Suppose that two distinct linear subspaces L = L 1 and L = L 2 ⊂ L 1 provide an equivalent feasible region for P(J, L). Obviously, Z is an interior feasible solution of P(J, L 1 ) if and only if it is an interior feasible solution of P(J, L 2 ). In the dual side, however, the feasible region of D(J, L 1 ) can be a proper subset of the feasible region of D(J, L 2 ). Hence, D(J, L 1 ) may not have an interior feasible solution even when D(J, L 2 ) has one. As the dimension of the subspace L becomes smaller, the possibility of the existence of a dual interior feasible solution increases. Next, we focus our attention to the class of conic relaxations of the combinatorial QOP (2) discussed in Sect. 3. Suppose that m ≥ 1 (i.e., Condition (G) is not empty). We have shown in Theorem 3.2 that 1+n • there is no Z ∈ Feas(D1+n NN , L 0 ∩ L a ∩ L b ) which lies in the interior of DNN , 1+n • there is a feasible solution (y0 , W , S) of D(DNN , L 0 ∩ L a ∩ L b ) such that S lies in the ∗ interior of (D1+n NN ) if and only if Condition (III) holds with L = L 0 ∩ L a ∩ L b

for any (L a , L b ) ∈ {L E1 , L E2 , L E3 } × {L Z , L C }. Thus, all DNN relaxations discussed so far are equivalent with respect to the existence of interior feasible solutions.

4.3 Nondegeneracy For SDPs, the primal and dual nondegeneracy was studied in [1]. (See [18] for the local convergence of the primal-dual interior point method under the nondegeneracy assumption.) The definition in [1] can be extended to the primal-dual pair, P(K1+n , L) and D(K1+n , L), in a straightforward manner. Let J be a closed convex cone in Sk . For every U ∈ J, let FU (J) denote the minimal face of J containing U, and TU (J) the subspace of Sk spanned by FU (J) (the tangent subspace of J at U ∈ J). Let L¯ = {Z ∈ L : H 0 • Z = 0} . Then a feasible (or optimal) solution Z of P(K1+n , L) is called (primal) nondegenerate if S1+n = L¯ + T Z (K1+n ),

123

Journal of Global Optimization

and a feasible (or optimal) solution (y0 , W , S) of D(K1+n , L) (dual) nondegenerate if S1+n = L¯ ⊥ + T S ((K1+n )∗ ). This definition may be regarded as a special case of the nondegeneracy for a feasible solution of a general nonlinear optimization problem in [24]. For solving a DNN problem, P(D1+n NN , L), a primal-dual interior-point method and SDPNAL+ would in fact solve the following SDP that is equivalent P(D1+n NN , L):   1+n , H 0 • Z = 1, (Z, U) ∈ M . (9) min F 0 • Z : (Z, U) ∈ S1+n + ×N Z,U

Here M = {(Z, U) ∈ S1+n ×S1+n : Z ∈ L, Z−U = O}. Z is a feasible (or optimal) solution of P(D1+n NN , L) iff (Z, Z) is a feasible (or optimal) solution of SDP (9). The definition of the primal and dual nondegeneracy can be applied to SDP (9). More precisely, a feasible solution 1+n ), (Z, Z) of SDP (9) is (primal) nondegenerate if S1+n × S1+n = M¯ + T Z (S1+n + ) × T Z (N where M¯ = {(Z, U) ∈ M : H 0 • Z = 0} = {(Z, Z) : Z ∈ L, H 0 • Z = 0}. It can be proved that if (Z, Z) is a nondegenerate feasible solution of SDP (9) then Z is a nondegenerate feasible solution of P(D1+n NN , L). The dual problem of (9) can be shown to be given by: 

max

y0 ,V ,W ,S,T

1+n y0 : (F 0 , O) − (H 0 , O)y0 − (V , W ) = (S, T ) ∈ S1+n , (V , W ) ∈ M ⊥ + ×N

  1+n , = max y0 : F 0 − H 0 y0 − S − T ∈ L ⊥ , (S, T ) ∈ S1+n + ×N y0 ,S,T



(10)

where we used the fact that M ⊥ = {(V , W ) ∈ S1+n × S1+n : V + W ∈ L ⊥ }. A feasible solution (y0 , S, T ) is said to be (dual) nondegenerate for the dual problem (10) if S1+n × 1+n ). It can be shown that the above condition is equivalent S1+n = M¯ ⊥ + T S (S1+n + ) × T T (N to 1+n S1+n = L¯ ⊥ + T S (S1+n ). + ) + T T (N

(11)

With larger (or smaller) L, the possibility of the primal nondegeneracy (or the dual nondegeneracy) can be expected to increase by both definitions of nondegeneracy for P(K1+n , L) and SDP (9).

5 Eliminating x from conic relaxation problems Burer [10] presented a simplification technique to eliminate the variable x of a QOP in binary and nonnegative variables from its CPP reformulation under the assumption of the existence of a special valid constraint, i.e., an equality h T x = 1 with h ≥ 0 satisfied by every feasible solution of the QOP. The same technique can be applied to the conic relaxation problem 1+n 1+n P(K1+n , L) of QOP (1) (= P( 1+n , L)) with K1+n ∈ {S1+n + , DNN , CPP } and L defined by T (3). Suppose that h ≥ 0 and that h x = 1 is valid for every feasible solution x of QOP (1). Then the equalities x = x x T h and h T x x T h = 1 are valid constraints for QOP (1). As a result, their lifted equalities x = Y h and h T Y h = 1 can be added to the constraints of P(K1+n , L) or L can be replaced with L ∩ L S , where

  x0 x T T : h Y h = x0 , x = Y h . LS = Z = (12) x Y Throughout this section, we assume that   Kk ∈ Sk+ , DkNN , CkPP (k ∈ {n, 1 + n}),

123

Journal of Global Optimization

  L = Z ∈ K1+n : F j • Z = 0 (1 ≤ j ≤ ) ⊂ L S . For simplicity of notation, we introduce linear maps  : Sn → S1+n ,  : S1+n → Sn and  : S1+n → Sn such that

T T

 h Y h hT Y h ∈ S1+n for every Y ∈ Sn , Y h I = (Y ) = Yh Y I

T

 x0 x T h n ∈ S1+n , ∈ S for every Z = (Z) = h I Z x Y I

x0 x T n ∈ S1+n , (Z) = Y ∈ S for every Z = x Y where I is the n × n identity matrix. Then L S can be rewritten as L S = (Sn ). Some properties of these mappings are listed as follows: A • (B) = ( A) • B for every A ∈ S1+n and B ∈ Sn ,

x0 x T −1 ∈ (Sn ),  (Z) = (Z) = Y for every Z = x Y

0 0T (Z) = (Z) = Y for every Z = ∈ S1+n , 0 Y  



  Kn ⊂ K1+n ,  K1+n = Kn and  K1+n = Kn .

(13) (14) (15)

The first three identities are straightforward. For the last property, recall that Kk ∈ {CkPP , DkNN , Sk+ } (k ∈ {n, 1 + n}). The identity (13) means that  is an extension of −1 : (Sn ) → Sn to the entire space S1+n . Let     L  = −1 (L) = Y ∈ Sn : (Y ) ∈ L = Y ∈ Sn : F  • Y = 0 (1 ≤ j ≤ ) , F j = (F j ) (0 ≤ j ≤ ), H 0 = (H 0 ). In the remainder of the paper, we use the prime symbol for functions, linear subspaces of Sn , feasible regions of COPs, matrices in Sn , and the conditions induced from the original ones in S1+n by the simplification.

5.1 Equivalence of P(K1+n , L) and D(K1+n , L) to their simplifications We show that P(K1+n , L) is equivalent to its simplified COP, denoted as P (Kn , L  ):   ζp (Kn , L  ) = min F 0 • Y : Y ∈ Kn , H 0 • Y = 1, Y ∈ L  . Y

x0 x T is a feasible solution of P(K1+n , L). Then, x Y Y = (Z) is a feasible solution of P(Kn , L  ) and F 0 • Y = F 0 • Z. If in addition Z lies in the interior of K1+n , then Y lies in the interior of Kn . (ii) Suppose that Y is a feasible solution of P(Kn , L  ). Then Z = (Y ) is a feasible solution of P(K1+n , L) and F 0 • Z = F 0 • Y .

Theorem 5.1 (i) Suppose that Z =

Proof (i) By the assumption L ⊂ L S , we know that

T x xT h Yh = K1+n ∩ L  Z = 0 x Y Yh

123

(Y h)T Y

= (Y ).

Journal of Global Optimization

It follows that Y ∈ Kn ∩ L  and 1 = H 0 • Z = H 0 • (Y ) = (H 0 ) • Y = H 0 • Y . Hence Y is a feasible solution of P (Kn , L  ). By the definition of F 0 , we also see that F 0 • Z = F 0 • (Y ) = (F 0 ) • Y = F 0 • Y . The second assertion of (i) is apparent. (ii) By (15), Z = (Y ) ∈ K1+n . By Y ∈ L  and the definition of L  , we see that Z ∈ L. Furthermore, 1 = H 0 • Y = (H 0 ) • Y = H 0 • (Y ) = H 0 • Z holds. Hence Z is a feasible solution of P(K1+n , L). Similarly, the equality F 0 • Z = F 0 • Y follows as in (i).  We now consider the dual of the simplified P (Kn , L  ), denoted by D (Kn , L  ):   ζd (Kn , L  ) = max  y0 : F 0 − H 0 y0 − W  = S ∈ (Kn )∗ , W  ∈ (L  )⊥ . y0 ,W  ,S

Lemma 5.1 (i) (L  )⊥ = (L ⊥ ). (ii) ((K1+n )∗ ) ⊂ (Kn )∗ and (int((K1+n )∗ )) ⊂ int((Kn )∗ ). Here int((Kk )∗ ) denotes the interior of (Kk )∗ (k ∈ {n, 1 + n}). Proof To prove (i), we observe that Y ∈ L  iff (Y ) ∈ L iff 0 = (Y ) • W = Y • (W ) for all W ∈ L ⊥ iff Y ∈ (L ⊥ )⊥ . Hence W  ∈ (L  )⊥ iff W  ∈ (L ⊥ ), which implies (i). To prove (ii), suppose that S ∈ (K1+n )∗ and S = (S). We note that S ∈ (Kn )∗ iff S • Y ≥ 0 for every nonzero Y ∈ Kn and that S ∈ int((Kn )∗ ) iff S • Y > 0 for every nonzero Y ∈ Kn . Choose a nonzero Y ∈ Kn arbitrarily. Then O  = (Y ) ∈ K1+n by the definition of  and (15). Hence S • Y = (S) • Y = S • (Y ) ≥ 0. If S ∈ int((K1+n )∗ ), then the inequality is strict. Thus we have shown (ii). 

Theorem 5.2 Assume that (y0 , W , S) ∈ R × S1+n × S1+n is a feasible solution of D(K1+n , L). Let W  = (W ) and S = (S). Then (y0 , W  , S ) is a feasible solution of D (Kn , L  ). If S lies in the interior of (K1+n )∗ , then S lies in the interior of (Kn )∗ . Proof From the assumption, F 0 − H 0 y0 − W = S, W ∈ L ⊥ , S ∈ (K1+n )∗ . By applying the linear map  : S1+n → Sn to these relations, we obtain F 0 − H 0 y0 − W  = S , W  ∈ (L ⊥ ), S ∈ ((K1+n )∗ ). By Lemma 5.1, we know that W  ∈ (L  )⊥ and S ∈ (Kn )∗ . Hence (y0 , W  , S ) is a feasible solution of D (Kn , L  ). The second assertion also follows from Lemma 5.1. 

Now we discuss how Conditions (0) through (V) are adapted to the simplified COP. Define

 1 − hT −1

∈ S1+n FS = − 1 hT = + . h − h hh T   Lemma 5.2 (i) K1+n ∩ L S = Z ∈ K1+n : F S • Z = 0 . 1+n ∗ 1+n . Then (F) = O if and only if F ∈ {λF : λ ≥ 0}. (ii) Let F ∈ (D1+n S NN ) = S+ + N

123

Journal of Global Optimization

Proof (i) Suppose that Z ∈ K1+n ∩ L S . Then

1 − hT x0 x T = x0 − 2h T x + h T Y h = 0. • FS • Z = x Y − h hh T   Hence Z ∈ Z ∈ K1+n : F S • Z = 0 . Now, suppose that Z ∈ K1+n ⊂ S1+n + and F S • Z =



1 x0 x T 0. Then = 0, which implies x0 = h T x, x = Y h and h T Y h = x0 . Hence −h x Y Z ∈ K1+n ∩ L S . (ii) The ‘if’ part is straightforward. To prove the ‘only if’ part, assume that F = F 1 + F 2 , 1 1 2 1 2 F ∈ N1+n , F 2 ∈ S1+n + and (F + F ) = O. Then (F ) ≥ O, diag((F )) ≥ 0, and 1 2 2 2 (F ) + (F ) = O. As a result, diag((F )) = 0, which implies (F ) = O. We also 1 have (F 1 ) = O, which implies By applying the eigenvalue decomposition to kF = O. 1+n 2 2 2 F ∈ S+ , we have that F = i=1 d i d iT for some eigenvectors k ≤ n.

F and   d i of

 −1 2 : μ ∈ R (1 ≤ i ≤ From (F ) = 0, h I d i = 0 follows. In other word, d i ∈ μ h k). Thus, F = F 2 ∈ {λF S : λ ≥ 0}. 

Lemma 5.2 shows that a constraint F j • Z = 0 with F j ∈ (K1+n )∗ in P(K1+n , L) becomes a trivial one by the simplification to derive P (Kn , L  ) if and only if F j ∈ {λF S : λ ≥ 0}. Taking this fact into account, we strengthen Condition (V) to ( V) {λF S : λ ≥ 0}   F j ∈ (D1+n )∗ ∩ (K1+n )∗ for some j ∈ {1, . . . , }. NN

K1+n

Lemma 5.3 Let J = in Conditions (0) through (IV). Then Conditions (0), (I), (II), (III), (IV) and ( V) imply the following Conditions (0) , (I) , (II) , (III) , (IV) and (V) , respectively. (0) The feasible region of P (Kn , L  ) is nonempty and H 0 ∈ (Kn ∩ L  )∗ . (I) The feasible region of P (Kn , L  ) is nonempty, H 0 ∈ (Kn )∗ and F j ∈ (Kn )∗ (1 ≤ j ≤ ). (II) Kn is a pointed closed convex cone with nonempty interior. (III) F 0 • D > 0 for every nonzero D ∈ Kn ∩ L  such that H 0 • D = 0. (IV) F 0 • D ≥ 0 for every nonzero D ∈ Kn ∩ L  such that H 0 • D = 0. (V) O  = F j ∈ (Kn )∗ for some j ∈ {1, . . . , }. Proof (0) ⇒ (0) and (I) ⇒ (I) follow from Theorem  (15) and the defini 5.1, Lemma 5.1, tions of , L  , H 0 . (II) ⇒ (II) follows from Kk ∈ Sk+ , DkNN , CkPP (k ∈ {n, 1 + n}). To prove (III) ⇒ (III) , assume that O  = D ∈ Kn ∩ L  and H 0 • D = 0. Let D = ( D ). By the definitions of  and L  , we have that O  = D ∈ K1+n ∩ L and H 0 • D = 0. Therefore F 0 • D = F 0 • D > 0 by (III). (IV) ⇒ (IV) can be shown similarly. Finally, ( V) ⇒ (V) follows from Lemma 5.2. 

Using Lemma 5.3, we can extend (i) and (ii) of Lemma 2.1 to the simplified COPs P (Kn , L  ) and D (Kn , L  ). But the details are omitted here. In Sect. 5.3, we will state Corollary 5.1 as extensions of (i) and (ii) of Theorem 3.2 on the class of conic relaxations of QOP (2) with Condition (G) to their simplifications.

5.2 Nondegeneracy of the simplified COPs P (Kn , L ) and D (Kn , L ) We show that is effective for increasing the possibility of the nondegeneracy. the simplification

T ¯ 1 x ¯ is a Let Z¯ = be a feasible solution of P(K1+n , L). By Theorem 5.1, Y¯ = ( Z) x¯ Y¯

123

Journal of Global Optimization

feasible solution of P (Kn , L  ). Let L¯ = {Z ∈ L : H 0 • Z = 0}, and ¯ = ( L). ¯ L¯  = {Y ∈ L  : H 0 • Y = 0} = −1 ( L) By definition, Z¯ is nondegenerate in generate in P (Kn , L  ) if Sn = L¯  + TY¯ (Kn ).

P(K1+n , L)

if

S1+n

= L¯ + T Z¯

(K1+n ),

(16) and Y¯ is nonde-

¯ is nondegenerate. Theorem 5.3 Assume that Z¯ is nondegenerate. Then Y¯ = ( Z) Proof It suffices to prove that Sn ⊂ L¯  + TY¯ (Kn ) because the converse inclusion is obvious. 1+n n We will show that Sn ⊂ L¯  + (T Z¯ (K1+n

(i), and (T Z¯ (K )) ⊂ TY¯ (K ) in (iii). )) in T 00 ∈ S1+n . By the nondegeneracy assumption (i) Take an arbitrary Y ∈ Sn . Let Z = 0 Y ¯ there exist Z 1 ∈ L¯ and Z 2 ∈ T ¯ (K1+n ) such that Z = Z 1 + Z 2 . Since  : S1+n → on the Z, Z n ¯ + (T ¯ (K1+n )). S is linear, we see that Y = (Z) = (Z 1 ) + (Z 2 ). Thus Sn ⊂ ( L) Z  n  1+n ¯ ¯ ¯ Using ( L) = L by (16), we obtain that S ⊂ L + (T Z¯ (K )). n ¯ (ii) Next we show that (F Z¯ (K1+n )) ⊂ FY¯ (Kn ). Obviously, FY¯ (K ) T Y . Let x x 0 ¯  = Z. (F Z¯ (K1+n ))  Y  = Y¯ . Then, there is a Z ∈ F Z¯ (K1+n ) such that Z = x Y Since Z¯ lies in the relative interior of F Z¯ (K1+n ), Z¯ can be represented as a convex combi¯ Z¯ = λZ + (1 − λ)U for some nation of Z and some U ∈ F Z¯ (K1+n ) such that U  = Z; ¯ = λY + (1 − λ)(U), Y¯  = Y ∈ Kn and λ ∈ (0, 1). It follows that FY¯ (Kn )  Y¯ = ( Z) (U) ∈ Kn . Since FY¯ (Kn ) is a face of Kn , we obtain that Y ∈ FY¯ (Kn ). Thus, we have shown (F Z¯ (K1+n )) ⊂ FY¯ (Kn ). (iii) Let Z 1 , . . . , Zq be a basis of T Z¯ (K1+n ). They can be taken from F Z¯ (K1+n ). Then we know by (ii) that (Z 1 ), . . . , (Zq ) ∈ FY¯ (Kn ). Therefore we see that

 (T Z¯ (K1+n )) =  lin{Z 1 , . . . , Zq } = lin{(Z 1 ), . . . , (Zq )} ⊂ TY¯ (Kn ), where lin(A) denotes the smallest linear subspace of Sk that contains A ⊂ Sk . Consequently, we have shown that (T Z¯ (K1+n )) ⊂ TY¯ (Kn ). 

¯ is a feasible solution of D(K1+n , L). Let W¯  = ( W ¯ , S) ¯ ) and Suppose that ( y¯0 , W S = (S). By Theorem 5.2, ( y¯0 , W¯  , S¯ ) is a feasible solution of D (Kn , L  ). By definition, ¯ is nondegenerate in D(K1+n , L) if S1+n = L¯ ⊥ + T ¯ ((K1+n )∗ ), and ( y¯0 , W¯  , S¯ ) ¯ , S) ( y¯0 , W S ⊥ is nondegenerate in D (Kn , L  ) if Sn = L¯  + T S¯  ((Kn )∗ ). We can prove the following theorem similarly to Theorem 5.3, and the proof is omitted. ¯

¯ is nondegenerate, then ( y¯0 , W¯  , S¯ ) is nondegenerate. ¯ , S) Theorem 5.4 If ( y¯0 , W

5.3 Eliminating x from conditions (E1), (E2), (E3), (Z) and (C)  Let h be an arbitrary convex combination of e J p (1 ≤ p ≤ m), i.e., h = mp=1 λ p e J p , 1 = m T p=1 λ p and λi ≥ 0 (1 ≤ p ≤ m). Then the common equalities e J p x = 1 (1 ≤ p ≤ m), which have been lifted to homogeneous linear equalities in Z in Conditions (E1), (E2) and (E3) with H 0 • Z = 1, imply that h T x = 1, x = x x T h and h T x x T h = 1. Hence we can apply Burer’s simplification technique to the conditions by adding their lifted equalities x = Y h and h T Y h = 1. Define L S by (12). The following lemma shows that adding the lifted equalities themselves explicitly is redundant.

123

Journal of Global Optimization

Lemma 5.4 (i) L E2 ⊂ L S . 1+n (ii) L S ∩ L a ∩ S1+n + = L a ∩ S+ for any L a ∈ {L E1 , L E2 , L E3 }. T   m x = mp=1 λ p eTJp x = x0 and x = Proof Let Z ∈ L E2 . Then, h T x = p=1 λ p e J p m m T T p=1 λ p x = p=1 λ p Y e J p = Y h. As a result, h Y h = h x = x 0 . Thus we have shown (i). (ii) follows from (ii) of Lemma 3.1. 

Note that each of (E1), (E2), (E3), (Z) and (C) consists of Z ∈ M and H 0 • Z = 1 for some linear subspace M of S1+n . Thus, the corresponding simplified condition is obtained by replacing them with M  = −1 (M) = {Y ∈ Sn : (Y ) ∈ M} and H 0 • Y = 1, where H 0 = (H 0 ) = hh T . If M is represented as M =  n  Z ∈ S1+n : H j • Z = 0 (1 ≤ j ≤ k) for some  H j ∈ S (1 ≤ j ≤ k), then M turns out to be Y ∈ Sn : (H j ) • Y = 0 (1 ≤ j ≤ k) . M  is also obtained by substituting x = Y h and x0 = h T Y h into the homogeneous linear equalities in Z ∈ S1+n describing M. As a result, (E1), (E2), (E3), (Z) and (C) are simplified as follows:    (E1) Y ∈ L E1 ≡ Y ∈ Sn : (E + J p ) • Y = 0 (1 ≤ p ≤ m) and H 0 • Y = 1 .   h T Y e J p = H 0 • Y , and H 0 • Y = 1 . (E2) Y ∈ L E2 ≡ Y ∈ Sn : Y h = Y e J p (1 ≤ p ≤ m)   T  • Y, h Y e = H J p 0 and H 0 • Y = 1 . (E3) Y ∈ L E3 ≡ Y ∈ Sn : T e J p Y e J p = H 0 • Y (1 ≤ p ≤ m)   (Z) Y ∈ L Z ≡ Y ∈ Sn : [Y h] j = Y j j ( j ∈ J p , 1 ≤ p ≤ m) .  (C) Y ∈ L C ≡ Y ∈ Sn : Yi j = 0 (i, j ∈ J p , i  = j, 1 ≤ p ≤ m) . In the remainder of this section,we impose an additional restriction that h is the barycenter of e J p (1 ≤ p ≤ m), i.e., h = m1 mp=1 e J p , and further simplify (E3)’ to   (E3) Y ∈ L E3 ≡ Y ∈ Sn : eTJp Y e J p = H 0 • Y (1 ≤ p ≤ m) and H 0 • Y = 1 . We need the following lemmas to show the equivalence between (E3) and (E3) when Y ∈ Sn+ . Lemma 5.5 [22, Lemma 2] Let A ∈ Sm + and A pq = A pp Aqq (1 ≤ p, q ≤ m).

m

m

p=1

q=1

A pq =

m p=1

2 A pp . Then,

Lemma 5.6 Suppose that Y ∈ Sn+ and eTJp Y e J p = 1 (1 ≤ p ≤ m). Then, H 0 • Y = 1 if and only if eTJp Y e Jq = 1 (1 ≤ p, q ≤ m). Proof Since we know that

⎛

⎞T ⎛ ⎞ m m m m   1 1 1  T e Jp ⎠ Y ⎝ e Jp ⎠ = 2 e J p Y e Jq , H 0 • Y = h T Y h = ⎝ m m m p=1

q=1

p=1 q=1

the ‘if part’ follows. Assume that H 0 • Y = 1 holds. Consider the m × m matrix ⎞ ⎛ eT ⎞ ⎛ T J1 e J1 Y e J1 . . . eTJ1 Y e Jm  ⎜ ⎟

... . . . ⎠ = ⎝ ... ⎠ Y e J1 . . . e Jm ∈ Sm A = ⎝ ... +. T eTJm Y e J1 . . . eTJm Y e Jm e Jm

123

(17)

Journal of Global Optimization

By the assumption, A pp = eTJp Y e J p = 1 (1 ≤ p ≤ m). Thus, we see from (17) 2

m m m   A pq = mp=1 q=1 eTJp Y e Jq = m 2 = A pp . Therefore, by that mp=1 q=1 p=1 Lemma 5.5, eTJp Y e Jq = A pq =

A pp Aqq = 1 (1 ≤ p, q ≤ m).



Theorem 5.5 L E3 ∩ {Y ∈ Kn : H 0 • Y = 1} = L E3 ∩ {Y ∈ Kn : H 0 • Y = 1}. Proof Since Kn ⊂ Sn+ , it suffices to show the identity for Kn = Sn+ . From L E3 ⊂ L E3 , we see that L E3 ∩ {Y ∈ Sn+ : H 0 • Y = 1} ⊂ L E3 ∩ {Y ∈ Sn+ : H 0 • Y = 1}. Now assume that Y ∈ L E3 ∩ {Y ∈ Sn+ : H 0 • Y = 1} holds. By Lemma 5.6, we see that eTJp Y e Jq = A pq = 1 (1 ≤ p, q ≤ m). Thus, ⎞T ⎛ m m  1  T 1 hT Y e J p = ⎝ e Jq ⎠ Y e J p = e Jq Y e J p = 1 (1 ≤ p ≤ m). m m q=1

Therefore, Y ∈

L E3

∩ {Y ∈

Sn+

q=1

:

H 0

• Y = 1} holds.



Burer [10] conjectured that the simplification technique applied to his CPP reformulation of a class of QOPs in binary and continuous variables could increase the possibility of the existence of interior feasible solutions. The theorem below negates the conjecture except cases where the assumption (a) is violated.   Corollary 5.1 Let Kn ∈ Sn+ , DnNN , CnPP and (L a , L b ) ∈ {L E1 , L E2 , L E3 , L E3 } × {L Z , L C } be arbitrarily fixed. Assume that (a) Feas(S1+n + , L 0 ∩ L E1 ∩ L Z ) is nonempty and bounded, (b) m ≥ 2 hold. Then (i) Feas(Kn , L 0 ∩ L a ∩ L b ) contains no interior point of Kn . (ii) There is a feasible solution (y0 , W  , S ) of D(Kn , L 0 ∩ L a ∩ L b ) such that S lies in the interior of (Kn )∗ and ζp (Kn , L 0 ∩ L a ∩ L b ) = ζd (Kn , L 0 ∩ L a ∩ L b ). 1+n Proof We will apply Lemmas 5.3 and 2.1. Conditions (0) and (II) with J ∈ {S1+m + , DNN , 1+n 1+n 1+n 1+n CPP } clearly hold, and (III) holds with J ∈ {S+ , DNN , CPP } and L = L 0 ∩ L a ∩ L b by the assumption (a) , (i) of Lemma 3.1 and (i) of Lemma 3.2. Thus, Assertion (ii) follows from Lemmas 5.3 and 2.1. By the assumption (b) , there is a p ∈ {1, . . . , } such that E Jp ∈ / {λF S : λ ≥ 0}, and we can include E J p • Z = 0 in the homogeneous equalities F j • Z = 0 (1 ≤ j ≤ ) to represent L = L 0 ∩ L E1 ∩ L Z as in (3). By Lemma 5.3 and Lemma 2.1, Feas(Sn+ , L 0 ∩ L E1 ∩ L Z ) contains no interior point of Sn+ . Since Feas(Sn+ , L 0 ∩ L a ∩ L b ) ⊂ Feas(Sn+ , L 0 ∩ L E1 ∩ L Z ) by (i) of Lemma 3.1 and (i) of Lemma 3.2, Assertion (i) follows. 

6 Applications We consider two well-known combinatorial QOPs, the simple BIQP in Sect. 6.1, and the QAP, which is widely known as one of the most difficult combinatorial QOPs, in Sect. 6.2. For their importance in applications, many conic relaxations of both QOPs have been extensively studied. We investigate some of them in terms of P(K1+n , L a ∩L b ) with L a ∈ {L E1 , L E2 , L E3 } and L b ∈ {L C , L Z }, and P (Kn , L a ∩ L b ) with L a ∈ {L E1 , L E2 , L E3 , L E3 } and L b ∈ {L C , L Z }.

123

Journal of Global Optimization

6.1 The binary integer quadratic problem Let Q ∈ Sr . The BIQP is given by   ∗ ζBIQP = min Q • uu T : u j ∈ {0, 1} (1 ≤ j ≤ r )   = min Q • uu T : u = diag(uu T ) . By the definition of  1+r , U = uu T with u ∈ Rr+ iff

1 uT u U

(18)

∈  1+r . Hence we can

rewrite BIQP (18) as

  1 uT ∈ K1+r , u = diag(U) η(K1+r ) = min Q • U : u U

(19)

with K1+r =  1+r . Then, the standard SDP, DNN and CPP relaxations are obtained if 1+r 1+r 1+r K1+r =  1+r is replaced by S1+r ⊃ D1+r + , DNN and CPP , respectively. Since S+ NN ⊃ 1+r 1+r 1+r 1+r ∗ CPP ⊃  1+r , it follows that η(S+ ) ≤ η(DNN ) ≤ η(CPP ) ≤ η( 1+r ) = ζBIQP . To strengthen the DNN relaxation and derive the CPP reformulation [4,10] of BIQP (18), we transform BIQP (18) to the following problem by introducing slack variables v j = 1 − u j ≥ 0 (1 ≤ i ≤ r ).   ∗ = min (20) ζBIQP f 0 (x) : 1 = u j + v j , x j ∈ {0, 1} (1 ≤ j ≤ r ) , x=[u;v]∈R2r

where f 0 (x) = Q • uu T for every n-dimensional column vector x = [u; v] formed by concatenating u and v vertically. Let n = 2r , m = r and J p = { p, p + r } (1 ≤ p ≤ m). ∗ Then, the constraint of the problem (20) is stated as (G), and (20) is written as ζBIQP = min x∈Rn { f 0 (x) : (G)}, which is a special case of QOP (2) with 0 = 0. Therefore, the discussions in Sects. 3, 4 and 5 can be applied for deriving various conic relaxations of BIQP (20) as special cases of P(K1+n , L a ∩ L b ) and P (Kn , L a ∩ L b ). Note that L 0 = S1+n and L 0 = Sn since 0 = 0. In particular, each J p consists of two elements (1 ≤ p ≤ m). Applying (iii) of Lemma 3.2, we may replace Condition (Z) with (Zu) Z ∈ L Zu ≡ {Z ∈ S1+n : xi = Yii (1 ≤ i ≤ r )}. We see that (Zu) is different from (Z) in that xi = Yii (r + 1 ≤ i ≤ n) are not imposed in (Zu). 1+n 1+n 1+n , L ∩ L ) (L , L ) ∈ {L , L , Let K1+n ∈ {S1+n a b a b E1 E2 + , DNN , CPP }. All problems P(K L E3 } × {L Z , L Zu , L C }) share a common optimal value by Theorem 3.1. Furthermore, Assertions (i), (ii) and (iii) of Corollary 3.1 hold since the assumption (b) there is satisfied and BIQP (20) is feasible. If Burer’s CPP reformulation [10] of a class of linearly constrained QOPs in binary and continuous variables is applied to BIQP (20), then P(C1+n PP , L E3 ∩ L Zu ) is obtained. On the other hand, the application of the CPP reformulation proposed in [3] (see also [5,17]) for a class of quadratically constrained QOPs to BIQP (20) would result in P(C1+n PP , L E1 ∩ L C ). The 0–1 condition (Zu) is utilized in Burer’s reformulation while the complementarity condition (C) is employed in the reformulation in [3]. As both of them are equivalent to (20), the equivalence of their reformulations follows. Lemmas 3.1 and 3.2 ensure not only their equivalence but also the equivalence of their DNN and SDP relaxations. The DNN relaxation (with optimal value η(D1+r NN )) of BIQP (18) and the DNN relaxation 1+2r , L ∩ L ) (with the optimal value ζ P(D1+2r E1 C p (DNN , L E1 ∩ L C )) of BIQP (20) were NN

123

Journal of Global Optimization Table 1 A sketch of the correspondence of some existing relaxations of the QAP to P(K1+n , L a ∩ L b ) with 1+n 1+n n n n   n  n K1+n ∈ {S1+n + , DNN , CPP }, and P (K , L a ∩ L b ) with K ∈ {S+ , DNN , CPP } Lb LZ L E1 La

LZ ∩ LC

LC AKKT

L E2

QAPR0

L E3

Burer

− QAP− R , QAPR 2

QAPR2 , QAPR3

3

↓ via the simplification in [10] L b

L Z

L C

L Z ∩ L C

L E1 L E2

L a

L E3

sBurer

L E3

QAPCP , QAPK0∗ , QAPAW+ , QAPZKRW1 n

AKKT means the conic relaxation presented in [3,5], QAPR0 , QAP R2 and QAP R3 the ones in [23], and Burer the one in [10]. QAP−R and QAP− R3 mean the conic relaxations obtained from QAPR2 and QAPR3 by 2 eliminating the redundant constraint (Z), respectively. sBurer corresponds to Burer’s simplified conic relaxation applied to the QAP. QAPCP , QAPK0∗ , QAPAW+ and QAPZKRW1 are from [22], but their correspondence n

to P (Kn , L E3 ∩ L C ) is not exact. More precisely, their optimal values are the same, but the descriptions of the feasible regions are different. The details are shown in Theorem 6.1. No existing conic relaxations, to the authors’ best knowledge, correspond to the remaining COPs. Detailed explanations are included in Sects. 6.2.1 and 6.2.2

compared in detail in [16, Section 6] by Kim, Kojima and Toh. They showed that the second 1+2r relaxation is at least as effective as the first, i.e., η(D1+r NN ) ≤ ζ p (DNN ) in theory, and provided randomly generated numerical instances for which strict inequalities hold. Moreover, [15] presented a numerical instance of BIQP (18) with r = 3 such that its DNN relaxation (19) ∗ ˆ with K1+r = D1+3 NN attained only a strict lower bound ζ for the optimal value ζBIQP . Since it is known in [12] that Dn = Cn if n ≤ 4, we also have η(C1+3 ) = η(D1+3 ) = ζˆ < ζ ∗ NN

PP

PP

NN

BIQP

in that instance. In other words, the CPP relaxation (19) with K1+r = C1+3 PP attains only the ∗ strict lower bound ζˆ < ζBIQP . In that instance, they also illustrated that ζ p (D1+6 NN , L E1 ∩L C ) = ˆζ < ζ ∗ . In theory, however, ζ p (C1+6 , L E1 ∩ L C ) = ζ ∗ is guaranteed. BIQP

PP

BIQP

6.2 The quadratic assignment problem Based on the results of Sects. 3 and 5, we investigate the relations among several existing conic relaxations [2,10,22,23,28] of the QAP, which are summarized in Table 1. In addition to the existing conic relaxations in Table 1, there can be other conic relaxations of the QAP, which are obtained by combining the conditions in the rows and columns of Table 1. Let A and B be given r × r matrices. Then the QAP is described as   ∗ ζQAP = min X • ( AX B T ) : X is a permutation matrix .

(21)

123

Journal of Global Optimization

QAP can be regarded as a QOP in an r × r matrix variable X subject to the following combinatorial conditions: (GC) All elements of each pth column of X are 0 except one with the value 1. (GR) All elements of each ith row of X are 0 except one with the value 1. To derive the conic relaxation using the systematic method presented in Sect. 3, we need to transform the problem (21) in the matrix variable X ∈ Rr ×r to a QOP in an n-dimensional column vector variable x, where n = r 2 . For every X = (x 1 , . . . , x r ) ∈ Rr ×r , where x p denotes the p-th column vector of X, we consider the n-dimensional vector x = [x 1 ; . . . ; x r ] by arranging x p (1 ≤ p ≤ r ) vertically. Then the objective function can be rewritten as X • ( AX B T ) = x T (B ⊗ A)x. The conditions (GC) and (GR) on X can also be restated as the condition (G) on x with m = 2r and J p = {( p − 1)r + 1, ( p − 1)r + 2, . . . , ( p − 1)r + r } (1 ≤ p ≤ r ), Jr +i = {i, i + r , . . . , i + (r − 1)r } (1 ≤ i ≤ r ), where J p and Jr +i correspond to (GC) and (GR), respectively. Hence, QAP (21) is equivalently formulated as follows:   ∗ ζQAP = min x T (B ⊗ A)x : (G) , (22) which is a special case of QOP (2) with 0 = 0. Thus, various conic relaxations of QAP (22) can be derived from P(K1+n , L a ∩ L b ) and P (Kn , L a ∩ L b ) as stated in Sect. 3. Note that L 0 = S1+n and L 0 = Sn since 0 = 0. Let Y pq = the ( p, q)th r × r block submatrix of Y corresponding to x p (x q )T , C p = J p (1 ≤ p ≤ r ), Ri = Jr +i (1 ≤ i ≤ r ), E J = e J eTJ ∈  n . We note that both {C p : 1 ≤ p ≤ r } and {Ri : 1 ≤ i ≤ r } form partitions of the index set {1, . . . , n}. This is an important feature of QOP (22) derived from QAP (21), which is utilized in Sect. 6.2.2. Some of Conditions (E1) through (C), which are mainly considered in Sect. 6.2.2, are rewritten as follows: ⎧ ⎫ eCT p x = x0 , E C p • Y = x0 , ⎬ ⎨ (E3) Z ∈ L E3 = Z ∈ S1+n : eTR p x = x0 , E R p • Y = x0 and H 0 • Z = 1. ⎩ ⎭ (1 ≤ p ≤ r )   p pp (Z) Z ∈ L Z = Z ∈ S1+n : xi = Yii (1 ≤ i ≤ r , 1 ≤ p ≤ r ) .   pp pq (C) Z ∈ L C = Z ∈ S1+n : Yi j = 0 (i = j, 1 ≤ p ≤ r ), Yii = 0 ( p = q, 1 ≤ i ≤ r ) . Other conditions appear in Sects. 6.2.1 and 6.2.2 but their precise forms are not relevant to the discussions there.

6.2.1 Conic relaxations in the space S1+n 1+n 1+n , L ∩L ) with ((L , L ) ∈ {L , L , L } For K1+n ∈ {D1+n a b a b E1 E2 E3 NN , CPP }, all problems P(K , L ∩ L × {L Z , L Zu , L C }) share a common optimal value. In particular, all P(C1+n a b) PP ((L a , L b ) ∈ {L E1 , L E2 , L E3 } × {L Z , L C }) provide CPP reformulations of QAP (22) such 1+n ∗ that ζ p (C1+n PP , L a ∩ L b ) = ζQA P . We also see that all problems P(S+ , L a ∩ L Z ) (L a ∈ {L E1 , L E2 , L E3 }) have a common optimal value, and that the optimal values of all prob1+n lems P(S+ , L a ∩ L C ) (L a ∈ {L E1 , L E2 , L E3 }) are the same. However, only the inequality

123

Journal of Global Optimization 1+n ζ p (S1+n + , L a ∩ L Z ) ≤ ζ p (S+ , L a ∩ L C ) is guaranteed for each L a ∈ {L E1 , L E2 , L E3 }. These facts follow from Theorem 3.1. Furthermore, Assertions (i), (ii) and (iii) of Corollary 3.1 hold since the assumption (b) there is satisfied and QOP (2) induced from QAP (22) is feasible. The CPP reformulation of Arima–Kim–Kojima–Toh [3,5] applied to QAP (22) is given by P(C1+n PP , L E1 ∩ L C ), while Burer’s CPP reformulation [10] applied to QAP (22) is 1+n 1+n P(CPP , L E3 ∩ L Z ). Replacing the CPP cone C1+n PP with the DNN cone DNN , DNN relax1+n ations P(D1+n NN , L E1 ∩ L C ) and P(DNN , L E3 ∩ L Z ) are obtained, respectively. They are 1+n 1+n equivalent. Replacing DNN with S+ leads to SDP relaxations P(S1+n + , L E1 ∩ L C ) and 1+n , L ∩ L ), respectively, which satisfy ζ (S , L ∩ L ) ≤ ζ p (S1+n P(S1+n E3 Z p + E3 Z + + , L E1 ∩ L C ) as mentioned above. 1+n = S1+n also provides DNN and P(K1+n , L E2 ∩ L C ) with K1+n = D1+n + NN and K SDP relaxations of QAP (22). These two relaxations coincide with the relaxations QAP R3 and QAPR2 presented in [23] except that for the latter two relaxations, the 0–1 condition (Z) is imposed in addition to the complementarity condition (C). But (Z) is redundant by Lemma 3.2. On the other hand, P(S1+n + , L E2 ∩ L Z ) coincides with the relaxations QAPR0 presented in [23]. See also Section 4 of [22].

6.2.2 Conic relaxations in the space Sn  e J p /2r . As both {C p : 1 ≤ p ≤ r } and {Ri : 1 ≤ i ≤ r } form partitions  

r  r of the index set {1, . . . , n}, we see that h = p=1 eC p /r = i=1 e Ri /r = e/r . Thus,   hh T = E/r 2 , where E denotes the n × n matrix of 1’s. Let Kn ∈ Sn+ , DnNN , CnPP . Then, P (Kn , L a ∩ L b ) with each (L a , L b ) ∈ {L E1 , L E2 , L E3 , L E3 } × {L Z , L C } entails an SDP, DNN or CPP relaxation of QAP (22) in the space Sn , respectively. We can adapt what we have observed in the beginning of Sect. 6.2.1 to the simplified COPs P (Kn , L  ∩ L a ∩ L b ) and D (Kn , L  ∩ L a ∩ L b ) (Kn ∈ {Sn+ , DnNN , CnPP }, (L a , L b ) ∈ {L E1 , L E2 , L E3 , L E3 }×{L Z , L C }). In particular, Assertions (i) and (ii) of Corollary 5.1 hold. The details are omitted. In the rest of this section, we examine and compare some existing CPP, DNN and SDP relaxations [2,22,23,28] in view of the discussion in Sect. 5. Our main focus is on P (Kn , L E3 ∩ L C ) among the relaxations, which will be related to some existing conic relaxations [2,22, 23,28] of QAPs. First, we rewrite Conditions (E3)” and (C)’ as follows:   E • Y = (E/r 2 ) • Y (1 ≤ p ≤ r ), and E • Y = r 2 . (E3)” Y ∈ L E3 ≡ Y ∈ Sn : C p E Ri • Y = (E/r 2 ) • Y (1 ≤ i ≤ r )   pp pq (C)’ Y ∈ L C ≡ Y ∈ Sn : Yi j = 0 (i = j, 1 ≤ p ≤ r ), Yii = 0 ( p = q, 1 ≤ i ≤ r ) . Let h =

 2r

p=1

The permutation matrix X is characterized by the conditions X ≥ O and X T X = I. Based on this characterization, Povh and Rendl [22] reformulated QAP (21) by adding the 2   r r redundant constraints X X T = I and = r 2 as follows: i=1 p=1 X i p ∗ ζQAP

⎧ ⎨

⎫ ⎞2 ⎛ r r  ⎬  = min X • ( AX B T ) : X ≥ O, X T X = I, X X T = I, ⎝ Xi p⎠ = r 2 , ⎭ X ⎩ i=1 p=1

and derived its conic relaxations: 

Y ∈ Kn , I • Y pq = δ pq (1 ≤ p, q ≤ r ),  r ζPR (K ) = min (B ⊗ A) • Y : Y pp = I, E • Y = r 2 n

 .

(23)

p=1

123

Journal of Global Optimization

Here Kn = CnPP , DnNN or Sn+ with n = r 2 , δ pq denotes the Kronecker delta such that δ pq = 1 pq = δ if pq (1 ≤ p, q ≤ r ) and rp = qpp and δ pq = 0 otherwise. We note that TI • Y = I are the liftings of the equalities X X = I and X X T = I in the variable p=1 Y matrix X ∈ Rr ×r to the equalities in the variable matrix Y ∈ Sn×n , respectively. The CPP relaxation QAPCP , DNN relaxation QAPKn0∗ and SDP relaxation QAPAW+ , which are all from Povh and Rendl [22], are obtained by setting Kn = CnPP , DnNN and Sn+ , respectively. In particular, Povh and Rendl showed that QAPCP provided a CPP reformulation of QAP (21), ∗ . The SDP relaxation QAP i.e., ζPR (CnPP ) = ζQAP AW+ corresponds to a slight variation of the Anstreicher–Wolkowicz relaxation [2]. As a stronger SDP relaxation than QAPAW+ , Povh and Rendl in [22] also presented the SDP relaxation QAPZRKW1 , which was shown to be equivalent to the ‘gangster-model’ from [28]. The SDP relaxation QAPZRKW1 is naturally extended to a general conic relaxation of QAP by replacing the PSD cone Sn+ with a closed convex cone Kn ⊃  n . ⎧ ⎫ Y ∈ Kn , I • Y pp = 1 (1 ≤ p ≤ n), ⎪ ⎪ ⎨ ⎬ r qq Yii = 1 (1 ≤ i ≤ n), (24) ζZRKW1 (Kn ) = min (B ⊗ A) • Y : q=1 ⎪ Y ⎪ ⎩ ⎭ ]Y ∈ L C , E • Y = r 2 We will relate QAPCP , QAPKn0∗ , QAPAW+ and COP (24) to P (Kn , L E3 ∩ L C ). Lemma 6.1 Let Kn ⊂ Sn+ . Suppose that Y ∈ L C holds. Then r  

pp

Yi j = 0 (1 ≤ p ≤ r ),

r  

pq

Yii = 0 (1 ≤ i ≤ r ),

p=1 q= p

i=1 j =i

EC p • Y = I • Y

pp

(1 ≤ p ≤ r ), E Ri • Y =

r p=1

pp

Yii (1 ≤ i ≤ r ).

(25)

 Proof Z ∈ L C implies the first two equalities. The last two equalities follow from them.  r Lemma 6.2 Let Y ∈ Nn . Suppose that I • Y pq = δ pq (1 ≤ p, q ≤ r ) and p=1 Y pp = I. Then Y ∈ L C holds.   pq Proof Let p  = q. Then ri=1 Yii = I • Y pq = 0. From rp=1 Y pp = I, we see that r pp  n 

p=1 Yi j = 0 (i  = j). Since Y ∈ N , these identities imply Z ∈ L C . Theorem 6.1 Let Kn ⊂ Sn+ . (i) Y ∈ Kn is a feasible solution of COP (24) iff it satisfies (E3)” and (C)’. (ii) If Y ∈ Kn satisfies (E3)” and (C)’, then it is a feasible solution of COP (23). (iii) Assume that Kn ⊂ DnNN . Then Y ∈ Kn is a feasible solution of COP (23) iff it satisfies (E3)” and (C)’. Proof (i) By Lemma 6.1, (25) holds under (C)’ which is assumed both in the ‘if’ and ‘only if’ parts. Hence assertion (i) follows. (ii) Assume that Y ∈ Kn satisfies (E3)” and (C)’. Then E • Y = r 2 . By Lemma 6.1 and (C)’, we see that  if p = q, EC p • Y = 1 pq I • Y = r i.e., I • Y pq = δ pq (1 ≤ p, q ≤ r ), pq Yii = 0 otherwise, i=1  r r  E •Y =1 if i = j, R i pp i.e., Yi j = r Y pp = I. pp Yi j = 0 otherwise p=1 p=1

123

p=1

Journal of Global Optimization

Therefore, Y ∈ Kn is a feasible solution of COP (23). (iii) Since the ‘if’ part is proved in (ii), it suffices to show the ‘only if’ part. Assume that Y ∈ Kn is a feasible solution of COP (23) with Kn ⊂ DnNN . By Lemma 6.2, (C)’ holds. Hence, (25) holds by Lemma 6.1. The equality E • Y = r 2 follows directly from the assumption.  Corollary 6.1 Suppose  n ⊂ Kn ⊂ Sn+ . Then ζPR (Kn ) ≤ ζZRKW1 (Kn ) = ζ  (Kn , L E3 , L C ) n ∗ . If, in addition, Kn ⊂ Dn , then ζ (Kn ) = ζ n n ≤ ζQAP PR ZRKW1 (K ) holds. If K = CPP , then NN ∗   ∗ n n n  n ζPR (K ) = ζQAP ; hence ζPR (K ) = ζZRKW1 (K ) = ζ (K , L E3 , L C ) = ζQAP . Proof The first and second assertions follow from Theorem 6.1, and the last from [22, Corollary 4]. 

7 Numerical results on SDP and DNN relaxations of QAP In Sect. 6.2, the QAP has been discussed as a special case of QOP (2), and some of existing conic relaxations have been related to P(K1+n , L a ∩ L b ) with (L a , L b ) ∈ {L E1 , L E2 , L E3 } ×{L C , L Z } and P (K1+n , L a ∩ L b ) with (L a , L b ) ∈ {L E1 , L E2 , L E3 }×{L C , L Z }. The purpose of the numerical experiments here is to compare the numerical results obtained by solving those COPs with SDPT3 [26], SDPNAL+ [27] and the bisection and projection method (BP) [6,16,17]. Specifically, we want to see whether the numerical results are in line with the theoretical results on the following issues: (a) For every L a ∈ {L E1sum , L E1 , L E2 , L E3 } and L a ∈ {L E1sum , L E1 , L E2 , L E3 }, the relations 1+n n   n   ζ p (S1+n + , L a ∩ L Z ) = ζ p (S+ , L a ∩ L Z ) ≤ ζ p (S+ , L a ∩ L C ) = ζ p (S+ , L a ∩ L C ), n   ≤ ζ p (D1+n NN , L a ∩ L Z ) = ζ p (DNN , L a ∩ L Z ) n   = ζ p (D1+n NN , L a ∩ L C ) = ζ p (DNN , L a ∩ L C )

hold. (Theorems 3.1, 5.1 and 5.2). Recall that L E1sum has been defined by (8), and that its simplification L E1sum is given by −1 (L E1sum ). n       (b) P(D1+n NN , L E2 ∩ L b ) with L b ∈ {L C , L Z } and P (DNN , L E2 ∩ L b ) with L b ∈ {L C , L Z } are more time-consuming than the other COPs. (Sect. 4.1). (c) The efficiency and effectiveness of solving a COP depend on numerical methods. For (c), we experimented with SDPNAL+ and BP. The solver SDPNAL+ can be applied to solve all COPs in (a), although its fast local convergence and stable execution are considerably affected by the existence of interior feasible solutions and nondegeneracy. The BP method, on the other hand, is a first-order method which is designed to be robust for ill-conditioned problems having empty primal or dual interior feasible regions. However, it works on only n    P(D1+n NN , L E1sum ∩ L b ) (L b ∈ {L C , L Z }) and P (DNN , L E1sum ∩ L C ) (see [6,16,17] for more details). We should note that DNN relaxations of the tested QAP instances are too large for SDPT3 to solve within reasonable CPU time. QAP instances for the experiments are obtained from QAPLIB [13]. The default parameters were used for SDPT3. For SDPNAL+, ‘tol’ was set to 10−6 and ‘stopoptions’ to 2 so that the solver continues to run even if it encounters some stagnations. For BP, the stopping criterion for the length of the target search interval was set to δ = 0.1. SDPNAL+ and BP were terminated in 10,000 s or 20,000 iterations even if their stopping criteria were not satisfied. Linearly dependent equality constraints were removed from each COP before SDPT3

123

Journal of Global Optimization

and SDPNAL+ were applied. All the computations were performed in Matlab on a Mac Pro with Intel Xeon E5 CPU (2.7 GHZ) and 64 GB memory. Table 2 shows the numerical results on two small-sized QAP instances from QAPLIB [13]. Note that we used the procedure in [6] to modify all computed bounds to be valid lower bounds. It is clear that the results in Table 2 are consistent with the inequalities in (a). For the equalities in (a), we observe that the lower bounds in bold fonts, which were obtained from DNN relaxations with (L a , L b ) ∈ {L E1sum , L E1 }×{L C }, are smaller than the ones from DNN relaxations with other (L a , L b ), which suggests that the first pair of DNN relaxations do not work well with SDPNAL+ as they are ill-conditioned in the sense that we shall explain next. ⊥ ⊂ L ⊥ ⊂ L ⊥ . In particular, dim(L ⊥ By Lemma 3.1, we know that L ⊥ E1sum ⊂ L E1 E3 E2  E1sum ) = 1.

Recall that n = r 2 . The small value of dim (L E1sum ∩ L C )⊥ , which is at most 1 + r 2 (r − 1), relative to the dimension (r 2 + 1)(r 2 + 2)/2 of the linear space S1+n implies that the dual nondegeneracy condition (11) is very likely to fail. We also know that the primal problems have no interior feasible solutions as stated in Sect. 6.2.1. All the issues just discussed have a negative impact on the numerical performance of SDPNAL+. The same observation can be made on the simplified DNN relaxations with (L a , L b ) ∈ {L E1sum , L E1 } × {L C }. Table 3 shows a summary of the numerical results on SDPNAL+ and BP applied to three sets of QAP instances. More precisely, QAP instances of small to large size from QAPLIB [13] are categorized into Sets 1, 2 and 3. Set 1, for instance, includes QAPs such as had12, nug12, rou12, scr12, chr12a, chr12b, chr12c, tai10a, and tai10b. Although we solved the same set of 16 DNN relaxations of each instance as in Table 2, detailed results are omitted here to save space. We refer the reader to [14] for the results in detail. For a summary of the results, we introduce the following symbols and notation. Let ζˆ (L a ∩ L b ) and ζˆ  (L a ∩ L b ) n    denote the approximate optimal values of P(Dn+1 NN , L a ∩ L b ) and P (DNN , L a ∩ L b ) solved by    SDPNAL+ and BP, and let τ (L a ∩ L b ) and τ (L a ∩ L b ) be the corresponding execution time of SDPNAL+ and BP. These values are converted to differences in relative lower bounds with respect to the maximum lower bound, and the ratio of the execution time to the minimum execution time. More precisely, we computed ζˆmax ≡ τmin ≡

max

{ζˆ (L a ∩ L b ), ζˆ  (L a ∩ L b )} (the maximum lower bound),

min

{τ (L a ∩ L b ), τ  (L a ∩ L b )} (the minimum execution time),

L a ,L b ,L a ,L b ,SDPNAL+,BP L a ,L b ,L a ,L b ,SDPNAL+,BP

η(L a ∩ L b ) ≡ (ζˆmax − ζˆ (L a ∩ L b ))/ζˆmax , η (L a ∩ L b ) ≡ (ζˆmax − ζˆ  (L a ∩ L b ))/ζˆmax ,

σ (L a ∩ L b ) ≡ τ (L a ∩ L b )/τmin , σ  (L a ∩, L b ) ≡ τ  (L a ∩ L b )/τmin . Then, the computed means are denoted by

 (L a ∩ L b ), σm (L a ∩ L b ), σm (L a ∩ L b ), ηm (L a ∩ L b ), ηm

and the worst-case values by  (L a ∩ L b ), σw (L a ∩ L b ), σw (L a ∩ L b ) ηw (L a ∩ L b ), ηw

over the numerical results from a set of QAP instances for each L a , L b , L a , L b . We also compute their means and worst-case values over all of L a , L b , L a , and L b , respectively (the rows with ‘all L a ’ and ‘all L a ’, the columns with ‘all L b ’ and ‘all L b ’ in Table 3.) The mean and the worst-case value were computed over the numerical results of each set of QAPs obtained by SDPNAL+ and BP. In Table 3, we first focus on the numerical results by SDPNAL+. For Set 1 of small-sized QAPs, the values of ηm and ηw are smaller as shown in the rows L E2 and L E2 , which means

123

Journal of Global Optimization Table 2 Approximate optimal values of P(K1+n , L a ∩ L b ) and P (Kn , L a ∩ L b ) for small size QAP instances, tai10 and chr12a tai10a SDP solved by SDPT3

DNN solved by SDPNAL+

K1+n = S1+n + La

Lb

K1+n = D1+n NN

Lb

LZ

LC

La

LZ

LC

L E1sum L E1

32,224.7

128,738.6

L E1sum

135,027.9

134,972.8

32,224.8

128,701.6

L E1

135,022.7

134,955.1

L E2

32,227.4

128,739.9

L E2

135,028.0

135,024.8

L E3

32,225.1

128,734.5

L E3

135,028.0

135,028.0

Kn = Sn+ L a

L b

L Z

L C

L E1sum

32,226.4

128,739.3

32,227.1

128,738.9

32,227.5

128,739.9

32,226.8

128,722.4

L E1 L E2 L E3

Kn = DnNN

L b

L Z

L C

L E1sum

135,028.0

134,996.0

135,027.7

134,994.0

135,023.4

135,022.9

135,028.0

135,024.1

L a

L E1 L E2 L E3

chr12a K1+n = S1+n + La

Lb LZ

L E1sum L E1 L E2 L E3 Kn = Sn+ L a

L b L Z

L E1sum

L E1 L E2 L E3

K1+n = D1+n NN

Lb

LC

La

LZ

LC

− 103,846.8

− 4840.5

L E1sum

9551.4

9544.5

− 103,849.2

− 4842.2

L E1

9551.6

9542.9

− 103,846.8

− 4840.6

L E2

9552.0

9552.0

− 103,847.9

− 4840.6

L E3

9552.0

9550.4

L C

Kn = DnNN L a

L b L Z

L C

− 103,846.7

− 4840.6

L E1sum

9552.0

9546.7

− 103,846.9

− 4840.9

− 103,846.7

− 4840.5

− 103,846.9

− 4840.6

L E1 L E2 L E3

9548.6

9542.3

9552.0

9552.0

9552.0

9548.5

that lower bounds of higher quality are obtained for these particular cases in the rows L E2 and L E2 . The large number m + mn (which equals to dim(L ⊥ E2 )) of linear equalities in L E2 may have contributed to the positive result as dual nondegeneracy is more likely to hold as discussed in Sect. 4. But σm (σw ) in the rows L E2 and L E2 are much larger than the ones in the other rows, which indicates that solving DNN relaxations with L a = L E2 and L b = L E2 by SDPNAL+ are much more expensive than the other cases as mentioned in (b). We omit these two time-consuming cases for the sets of larger QAPs. The DNN relaxations with L a ∈ {L E1sum , L E1 }, which have only 1 or m linear equalities, on the other hands, are inferior to the others with regard to lower bounds and execution time. The performance of SDPNAL+ could have been affected by the failure of dual nondegeneracy as a result of the small dimension of L ⊥ a . The DNN relaxations with L a = L E3 , which have

123

123

all L a

L E3

L E2

L E1

4.78e−5 (3.58e−4)

3.50e−5 (1.58e−4)

2.10e−5 (1.31e−4)

1.07e−4 (3.58e−4)

2.78e−5 (1.25e−4)

N/A

L Z  (η ) ηm w

L E1sum

4.17e−5 (2.30e−4)

all L a

L E1sum

3.37e−5 (1.31e−4)

L E3

SDPNAL+

 (σ  ) σm w

2.11e−5 (1.36e−4)

L E2

BP

3.25e1 (2.30e2)

6.46e−5 (2.17e−4)

L E1

3.33e0 (5.30e0)

3.75e1 (2.22e2)

5.77e0 (1.22e1)

1.35e2 (2.22e2)

4.90e0 (1.04e1)

4.44e0 (7.78e0)

N/A

3.70e0 (7.02e0)

1.16e2 (2.30e2)

4.89e0 (8.43e0)

5.75e0 (1.17e1)

4.72e−5 (2.30e−4)

L E1sum

SDPNAL+

3.99e−3 (1.37e−2)

L E1sum

BP

2.33e−4 (1.01e−3)

1.43e−4 (3.68e−4)

1.08e-4 (3.36e−4)

3.86e−4 (1.01e−3)

2.93e−4 (6.62e−4)

3.61e−5 (1.33e−4)

L C  (η ) ηm w

3.60e−4 (1.16e−3)

6.16e−5 (3.13e−4)

7.64e−5 (3.48e−4)

6.99e−4 (1.01e−3)

6.04e−4 (1.16e−3)

3.50e−5 (1.34e−4)

LC ηm (ηw )

σm (σw )

LZ

ηm (ηw )

Set 1 of small size QAP instances (had12, nug12, rou12, scr12, chr12a, chr12b, chr12c, tai10a, tai10b)

4.59e1 (2.97e2)

4.67e0 (1.12e1)

1.63e2 (2.97e2)

8.16e0 (1.66e1)

7.46e0 (1.48e1)

1.31e0 (3.08e0)

 (σ  ) σm w

2.80e1 (1.72e2)

2.89e0 (7.06e0)

8.45e1 (1.72e2)

1.27e1 (2.62e1)

1.17e1 (2.09e1)

2.06e0 (3.82e0)

σm (σw )

Table 3 The mean and worst-case values of relative lower bound differences η and ratios of the execution time σ

1.40e−4 (1.01e−3)

8.92e−5 (3.68e−4)

6.46e−5 (3.36e−4)

2.47e−4 (1.01e−3)

1.60e−4 (6.62e−4)

N/A

all L b  (η ) ηm w

2.01e−4 (1.16e−3)

4.77e−5 (3.13e−4)

4.87e−5 (3.48e−4)

3.82e−4 (1.01e−3)

3.26e−4 (1.16e−3)

2.01e-3 (1.37e-2)

ηm (ηw )

all L b

4.17e1 (2.97e2)

5.22e0 (1.22e1)

1.49e2 (2.97e2)

6.53e0 (1.66e1)

5.95e0 (1.48e1)

N/A

 (σ  ) σm w

3.02e1 (2.30e2)

3.30e0 (7.06e0)

1.00e2 (2.30e2)

8.80e0 (2.62e1)

8.73e0 (2.09e1)

2.70e0(5.30e0)

σm (σw )

Journal of Global Optimization

 (η ) ηm w

L Z  (σ  ) σm w

 (η ) ηm w

L C  (σ  ) σm w

SDPNAL+

1.13e−4 (6.89e−4)

1.39e−4 (8.68e−4)

all L a

1.76e−4 (8.68e−4)

1.28e−4 (7.02e−4)

N/A

 (η ) ηm w

L E3

L E1

L E1sum

1.20e−4 (6.64e−4)

all L a

L E1sum

1.06e−4 (4.05e−4)

L E3

BP

1.12e−4 (4.67e−4)

L E1

L Z

1.42e−4 (6.64e−4)

L E1sum

SDPNAL+

8.71e−3 (4.54e−2)

L E1sum

BP

7.40e0 (2.40e1)

7.63e0 (2.40e1)

8.10e0 (2.20e1)

6.48e0 (1.68e1)

N/A

 (σ  ) σm w

4.60e0 (2.04e1)

3.28e0 (1.17e1)

4.47e0 (1.52e1)

6.04e0 (2.04e1)

2.44e0 (3.82e0)

2.72e−4 (1.24e−3)

1.54e−4 (7.31e−4)

3.68e−4 (9.50e−4)

2.94e−4 (1.24e−3)

6.83e−5 (4.56e−4)

 (η ) ηm w

L C

6.65e−4 (3.97e−3)

2.21e−4 (7.87e−4)

8.08e−4 (1.24e−3)

9.67e−4 (3.97e−3)

7.87e−5 (4.58e−4)

LC ηm (ηw )

σm (σw )

LZ

ηm (ηw )

9.41e0 (4.27e1)

7.92e0 (1.98e1)

1.08e1 (3.30e1)

9.45e0 (4.27e1)

1.73e0 (3.86e0)

 (σ  ) σm w

1.23e1 (7.80e1)

3.39e0 (8.85e0)

1.46e1 (6.15e1)

1.90e1 (7.80e1)

2.21e0 (5.37e0)

σm (σw )

Set 2 of medium size QAP instances (chr20a, chr20b, chr20c, had20, lipa20a, lipa20b, nug20, rou20, scr20, tai20a, tai20b)

Table 3 continued

2.06e−4 (1.24e−3)

1.34e−4 (7.31e−4)

2.72e−4 (9.50e−4)

2.11e−4 (1.24e−3)

N/A

 (η ) ηm w

all L b

3.93e−4 (3.97e−3)

1.63e−4 (7.87e−4)

4.60e−4 (1.24e−3)

5.54e−4 (3.97e−3)

4.40e−3 (4.54e−2)

ηm (ηw )

all L b

 (η ) ηm w

all L b

8.40e0 (4.27e1)

7.77e0 (2.40e1)

9.47e0 (3.30e1)

7.97e0 (4.27e1)

N/A

 (σ  ) σm w

8.46e0 (7.80e1)

3.34e0 (1.17e1)

9.55e0 (6.15e1)

1.25e1 (7.80e1)

2.33e0 (5.37e0)

σm (σw )

 (σ  ) σm w

Journal of Global Optimization

123

123

all L a

L E3

L E1

4.33e−5 (3.87e−4)

2.50e−5 (7.58e−5)

4.92e−5 (1.22e−4)

5.56e−5 (3.87e−4)

8.31e0 (2.49e1)

1.01e1 (2.49e1)

9.15e0 (2.17e1)

5.70e0 (1.32e1)

N/A

3.57e0 (5.65e0)

5.61e0 (1.18e1)

The subscript ‘m’ stands for the mean and ‘w’ worst-case values

SDPNAL+

N/A

L Z  (η ) ηm w

L E1sum

3.84e−5 (1.01e−4)

all L a

L E1sum

 (σ  ) σm w

4.97e−5 (9.98e−5)

L E3

BP

4.69e0 (1.18e1)

5.26e−5 (1.01e−4)

L E1

1.81e0 (4.13e0) 4.88e0 (1.07e1)

1.30e−5 (5.30e−5)

L E1sum

SDPNAL+

5.15e−3 (3.88e−2)

L E1sum

BP

2.22e−4 (1.85e−3)

1.50e−4 (1.03e−3)

2.96e−4 (1.85e−3)

2.20e−4 (8.99e−4)

1.15e−4 (1.69e−4)

L C  (η ) ηm w

3.30e−4 (1.38e−3)

1.31e−4 (7.46e−4)

4.44e−4 (1.38e−3)

4.15e−4 (1.04e−3)

1.31e−4 (1.78e−4)

LC ηm (ηw )

σm (σw )

LZ

ηm (ηw )

7.27e0 (2.49e1)

8.60e0 (2.49e1)

9.02e0 (2.49e1)

4.18e0 (1.06e1)

1.26e0 (1.98e0)

 (σ  ) σm w

4.10e0 (1.29e1)

2.37e0 (3.58e0)

5.34e0 (1.29e1)

4.59e0 (1.06e1)

1.51e0 (2.56e0)

σm (σw )

Set 3 of medium size QAP instances (bur26a, bur26b, bur26c, bur26d, bur26e, bur26f, bur26g, bur26h, nug25, chr25a)

Table 3 continued

1.33e−4 (1.85e−3)

8.73e−5 (1.03e−3)

1.72e−4 (1.85e−3)

1.38e−4 (8.99e−4)

N/A

all L b  (η ) ηm w

1.84e−4 (1.38e−3)

9.02e−5 (7.46e−4)

2.48e−4 (1.38e−3)

2.14e−4 (1.04e−3)

2.64e−3 (3.88e−2)

ηm (ηw )

all L b

7.79e0 (2.49e1)

9.33e0 (2.49e1)

9.09e0 (2.49e1)

4.94e0 (1.32e1)

N/A

 (σ  ) σm w

4.40e0 (1.29e1)

2.97e0 (5.65e0)

5.48e0 (1.29e1)

4.74e0 (1.07e1)

1.66e0 (4.13e0)

σm (σw )

Journal of Global Optimization

Journal of Global Optimization

intermediate numbers of linear equalities, show relatively good results for Sets 1, 2 and 3 of QAPs as far as lower bounds and execution time are concerned. The similar observation can be made for L a ∈ {L E1sum , L E1 } and L a = L E3 cases. When the DNN relaxation with L b = L C and L b = L C were solved by SDPNAL+, the mean and worst lower bounds (ηm and ηw ) obtained were significantly inferior to the other cases of L b = L Z and L b = L Z , especially when they are combined with L a ∈ {L E1sum , L E1 } and L a ∈ {L E1sum , L E1 }. This shows that SDPNAL+ works more effectively and stably on the DNN relaxations with L b = L Z and L b = L Z (see the numbers in bold fonts). In contrast to SDPNAL+, BP was able to stably solve the DNN relaxations with L b = L C and L b = L C . In particular, BP has superior performance in solving the DNN relaxations with L b = L C in each set of QAP instances. This demonstrates the robustness of BP for solving degenerate DNN problems, and the effectiveness of the simplification technique when it is combined with BP. However, BP solved the COPs with L b = L Z less efficiently (see the numbers in bold fonts). Since the stability of BP depends on the stability of the numerical algorithm used to check the dual feasibility of a given matrix, simple Condition (C) which imposes constraints on each element independently would be numerically more preferable than Condition (Z). In all cases, the simplification technique did not shorten the execution time much as expected in Sect. 3.3. This is because the simplification with h = e/r destroyed the sparsity of the original DNN relaxations. We note that all the coefficient matrices involved in Conditions (E1) through (E3) are sparse while many of those in the simplified Conditions (E1)’ through (E3)” (including hh T ) are fully dense. With regard to the issue (c) mentioned at the beginning of this section, we can conclude from the numerical results in Tables 2 and 3 that the DNN relaxation with (L a , L b ) = (L E3 , L Z ) and the one (L a , L b ) = (L E3 , L Z ) give better results when solved by SDPNAL+, while the DNN relaxation with (L a , L b ) = (L E1sum , L C ) is better solved with BP.

8 Concluding remarks We have shown how various conic relaxations can be generated in a systematic manner for a QOP with lifted linear constraints generated from different quadratic equality representations of the combinatorial condition. The equivalences and differences of a class of DNN relaxations proposed for a general combinatorial optimization problem and their simplification have been studied. They are equivalent not only in the quality of the optimal values they provide, but also in the nonexistence of a primal interior feasible solution and the existence of a dual interior feasible solution as we have established in Theorems 3.1, 5.1, 5.2, Corollaries 3.1 and 5.1. However, the differences lie on the size of the matrix variable, the number of linear equality and inequality constraints and the primal/dual degeneracy. As applications of these results, we have presented some connections among existing DNN relaxations as well as derived new ones. Moreover, we have provided new relaxations for the QAP as shown in Table 1. Through numerical results on QAP instances, we have demonstrated that the aforementioned differences often cause critical differences on the performance of the numerical methods, SDPNAL+ and BP, which were recently developed for solving large-scale COPs. We have also observed that SDPNAL+ and BP work effectively on different DNN relaxation formulations. For the combinatorial optimization problems that are not dealt with in this paper, for instance, the quadratic multiple knapsack problem, maximum stable set problem and graph

123

Journal of Global Optimization

partitioning problem, the same approach presented in this paper can be applied to show the equivalence and difference in their conic relaxations.

References 1. Alizadeh, F., Pierre, J., Haeberly, A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77(1), 111–128 (1997) 2. Anstreicher, K., Wolkowicz, H.: On Lagrangian relaxation of quadratic matrix constraints. SIAM J. Matrix Anal. Appl. 22, 41–55 (2000) 3. Arima, N., Kim, S., Kojima, M.: A quadratically constrained quadratic optimization model for completely positive cone programming. SIAM J. Optim. 23(4), 2320–2340 (2013) 4. Arima, N., Kim, S., Kojima, M.: Simplified copositive and Lagrangian relaxations for linearly constrained quadratic optimization problems in continuous and binary variables. Pac. J. Optim. 10, 437–451 (2014) 5. Arima, N., Kim, S., Kojima, M., Toh, K.C.: Lagrangian-conic relaxations, Part I: a unified framework and its applications to quadratic optimization problems. Pac. J. Optim. 14, 161–192 (2018) 6. Arima, N., Kim, S., Kojima, M., Toh, K.C.: A robust Lagrangian-DNN method for a class of quadratic optimization problems. Comput. Optim. Appl. 66(3), 453–479 (2017) 7. Bomze, I.M., Cheng, J., Dickinson, P.J.C., Lisser, A.: A fresh CP look at mixed-binary QPs: new formulations and relaxations. Math. Program. 166, 159–184 (2017) 8. Bomze, I.M., Dür, M., de Klerk, E., Roos, C., Quist, A., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000) 9. Bomze, I.M., de Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24, 163–185 (2002) 10. Burer, S.: On the copositive representation of binary and continuous non-convex quadratic programs. Math. Program. 120, 479–495 (2009) 11. de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002) 12. Diananda, P.H.: On non-negative forms in real variables some or all of which are non-negative. Proc. Camb. Philos. Soc. 58, 17–25 (1962) 13. Hahn, P., Anjos, M.: QAPLIB—a quadratic assignment problem library. http://www.seas.upenn.edu/ qaplib 14. Ito, N., Kim, S., Kojima, M., Takeda, A., Toh, K.C.: Numerical results on QAPs. https://napinoco.github. io/papers/IKKTT2017a_full_table.pdf (2017) 15. Kim, S., Kojima, M.: Binary quadratic optimization problems that are difficult to solve by conic relaxations. Discrete Optim. 24, 170–183 (2017) 16. Kim, S., Kojima, M., Toh, K.C.: Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints. Research report B-483, Tokyo Institute of Technology, Department of Mathematical and Computing Sciences, Oh-Okayama, Meguro-ku, Tokyo 152-8552 (2016) 17. Kim, S., Kojima, M., Toh, K.C.: A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems. Math. Program. 156, 161–187 (2016) 18. Kojima, M., Shida, M., Shindoh, S.: Local convergence of predictor-corrector infeasible-interior-point method for sdps and sdlcps. Math. Program. 80, 129–160 (1998) 19. Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and non-linear programming. Math. Program. 39, 117–129 (1987) 20. Poljak, S., Rendl, F., Wolkowicz, H.: A recipe for semidefinite relaxation for (0,1)-quadratic programming. J. Glob.Optim. 7, 51–73 (1995) 21. Povh, J., Rendl, F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18, 223– 241 (2007) 22. Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6, 231–241 (2009) 23. Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. Ser. B 109(2–3), 505–524 (2007) 24. Robinson, S.M.: Local structure of feasible sets in nonlinear programming, part ii: nondegeneracy. Math. Program. Study 22, 217–230 (1984) 25. Shor, N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1–11 (1987) 26. Tütüncü, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. 95, 189–217 (2003)

123

Journal of Global Optimization 27. Yang, L.Q., Sun, D.F., Toh, K.C.: SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Prog. Comput. 7, 331–366 (2015) 28. Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2, 71–109 (1998)

Affiliations N. Ito1 · S. Kim2 · M. Kojima3 · A. Takeda4 · K.-C. Toh5

B

S. Kim [email protected] N. Ito [email protected] M. Kojima [email protected] A. Takeda [email protected] K.-C. Toh [email protected]

1

FAST RETAILING CO., LTD., 6F UNIQLO CITY TOKYO, 1-6-7 Ariake, Koto-ku, Tokyo 135-0063, Japan

2

Department of Mathematics, Ewha W. University, 52 Ewhayeodae-gil, Sudaemoon-gu, Seoul 03760, Korea

3

Department of Industrial and Systems Engineering, Chuo University, Tokyo 112-8551, Japan

4

Department of Creative Informatics, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan

5

Department of Mathematics and Institute of Operations Research and Analytics, National University of Singapore, 10 Lower Kent Ridge Road, Singapore, Singapore 119076

123