# A New Spatial Branch and Bound Algorithm for Quadratic Program with One Quadratic Constraint and Linear Constraints

Authors: Jing Zhou
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper proposes a novel second-order cone programming (SOCP) relaxation for a quadratic program with one quadratic constraint and several linear constraints (QCQP) that arises in various real-life fields. This new SOCP relaxation fully exploits the simultaneous matrix diagonalization technique which has become an attractive tool in the area of quadratic programming in the literature. We first demonstrate that the new SOCP relaxation is as tight as the semidefinite programming (SDP) relaxation for the QCQP when the objective matrix and constraint matrix are simultaneously diagonalizable. We further derive a spatial branch-and-bound algorithm based on the new SOCP relaxation in order to obtain the global optimal solution. Extensive numerical experiments are conducted between the new SOCP relaxation-based branch-and-bound algorithm and the SDP relaxation-based branch-and-bound algorithm. The computational results illustrate that the new SOCP relaxation achieves a good balance between the bound quality and computational efficiency and thus leads to a high-efficiency global algorithm.


---

## Body

## 1. Introduction

In this paper, we consider a quadratic program with one quadratic constraint and several linear constraints in the following form:(1)minfx=xTQ0x+q0Tx,s.t.xTQ1x+q1Tx≤c,Dx≤d,where x∈ℝn is the decision variable, Qi∈ℝn×n is a symmetric matrix, and qi∈ℝn for i=0,1, D∈ℝm×n, d∈ℝm and c∈ℝ. (1) covers many important combinatorial optimization problems and engineering problems, such as the binary quadratic programming problem [1], the max-cut problem [2], the quadratic knapsack problem [3,4], the binary least-square problem [5], the image processing problem [6], the multiuser detection problem [7], the project selection and resource distribution problems [8], the multisensor beamforming problem [9], and the system equilibrium problem [10]. It is known that if Q0 and Q1 are all positive semidefinite, then the problem becomes convex and can be solved efficiently by using SOCP methods [11]. In this paper, we assume that Q0 is positive semidefinite while Q1 is not, and the feasible region of (1) is bounded with nonempty relative interior points.As a quadratically constrained quadratic programming problem, a typical approach to solve (1) is to exploit the branch-and-bound methods [12,13]. Note that the tightness and the computing efficiency of solving the convex relaxation problem of (1) at each node are critical factors that can affect the performance of the branch-and-bound algorithm. Thus, designing an effective convex relaxation of (1) is a hot topic in the literature. To the best of my knowledge, the SDP relaxation has become an attractive approach for obtaining good convex relaxations [14,15]. Though the SDP relaxation is tighter, it would also tremendously enlarge the dimension of the problem by lifting the original n-dimensional variable vector x to an n+1×n+1 variable matrix. Consequently, solving the SDP relaxation of a huge-size problem should take a very long computational time. Hence, designing a convex relaxation which can be efficiently solved even for huge-size problem while maintaining the strength of the convex relaxation are investigated in the literatures [16,17].In this paper, we will develop a new SOCP relaxation for (1) employing the simultaneous matrix diagonalization technique. We first give the following definition.Definition 1.
M
∈
ℝ
n
×
n and N∈ℝn×n are called simultaneously diagonalizable (SD) if there exists a nonsingular matrix F∈ℝn×n such that FTMF and FTNF are both diagonal matrices.
In the past few years, many researches have shown that for some quadratically constrained quadratic programming problems, the simultaneous matrix diagonalization technique that is embedded into a convex relaxation may result in a tighter convex relaxation than that is not. Ben-Tal and Den Hertog [18] showed that a quadratic program with one or two quadratic constraints has a hidden conic quadratic representation if the matrices in the quadratic forms are simultaneously diagonalizable. Jiang and Li [19] also applied the simultaneous diagonalization techniques to solve a quadratic programming problem. Zhou and Xu [20] proposed a simultaneous diagonalization-based SOCP relaxation for convex quadratic program with linear complementarity constraints. They also designed a new SOCP relaxation for the generalized trust-region problem and provided a sufficient condition under which the proposed SOCP relaxation is exact [21].
The main contributions of this paper are twofold.(1)
We first decompose the matrixQ1 according to the signs of its eigenvalues such that Q1=A−B, where A and B are both positive semidefinite. Then, we propose a new SOCP relaxation via simultaneous diagonalization of the two positive semidefinite matrices Q0 and B. We further show that the new SOCP relaxation is as tight as the SDP relaxation when Q0 is positive definite or Q1 is negative semidefinite.(2)
We derive a spatial branch-and-bound algorithm based on the new SOCP relaxation, and the following extensive numerical results show that the proposed algorithm outperforms the branch-and-bound algorithm as derived from the SDP relaxation. It implies that the new SOCP relaxation balances the bound tightness and computing efficiency better than that of the SDP relaxation.
The rest of the paper is organized as follows. In Section2, a new SOCP relaxation for (1) is introduced. We also show that the new SOCP relaxation is as tight as SDP relaxation in certain cases. In Section 3, we propose a spatial branch-and-bound algorithm based on the new SOCP relaxation. Some numerical experiments are conducted to illustrate the effectiveness of the proposed algorithm in Section 4. Finally, some concluding remarks are provided in Section 5.
Notations. For two n by n real matrices A=Aij and B=Bij, A−1 represents the inverse of A and A⋅B=traceATB=∑i,j=1nAijBij. For a real symmetric matrix X, X≽0 and X≻0 mean that X is positive semidefinite and positive definite, respectively. In denotes the n-dimensional identity matrix, and e is a unit vector with all elements being 1. Given a vector a∈ℝn, diaga corresponds to an n×n diagonal matrix with its diagonal elements equal to a.


## 2. A Simultaneous Diagonalization-Based SOCP Relaxation

In this section, we derive a new SOCP relaxation exploiting the techniques of difference of convex (DC) decomposition, and two positive semidefinite matrices are simultaneously diagonalizable. First of all, we present two lemmas concerning simultaneous matrix diagonalization that appear to play a central role in this paper.Lemma 1 (see [22, 23]).
IfM∈ℝh×h and N∈ℝh×h are two symmetric matrices and M≻0, then there exists a nonsingular matrix F∈ℝh×h such that FTMF and FTNF are both diagonal matrices.Lemma 2 (see [22, 23]).
IfM∈ℝh×h and N∈ℝh×h are two positive semidefinite matrices, then there exists a nonsingular matrix F∈ℝh×h such that FTMF and FTNF are both diagonal matrices.Letr be the number of negative eigenvalues of Q1, and without loss of generality, the first r eigenvalues of Q1 are supposed to be negative. Thus, Q1=A−B where A=∑i=r+1nσiηiηiT and B=∑i=1rσiηiηiT in which σi≥0, −σ1,…,−σr, σr+1,…,σn are eigenvalues and ηi, i=1,…,n, are corresponding eigenvectors of Q1.SinceQ0≽0, B≽0 and rankB=r, the proof of Lemma 2 [20] provides a method to find a nonsingular matrix F∈ℝn×n such that FTQ0F=diagμ1,…,μn and FTBF=diagλ1,…,λr,0,…,0 with λi>0, i=1,…,r and μj≥0, j=1,…,n.Letx=Fy, p0=FTq0, and p1=FTq1; then, (1) can be reformulated as(2)min∑j=1nμjyj2+p0Ty,s.t.yTFTAFy−∑j=1rλjyj2+p1Ty≤c,DFy≤d.Equation (2) still cannot be solved in polynomial time as the quadratic constraint remains nonconvex. Then, we derive a new SOCP relaxation for (1) by introducing auxiliary variables ti for i=1,…,r,:(3)min∑j=1rμjtj+∑j=r+1nμjyj2+p0Ty,s.t.yTFTAFy−∑j=1rλjtj+p1Ty≤c,DFy≤d,yj2≤tj,j=1,…,r.In general, the new SOCP relaxation provides a weaker lower bound than the SDP relaxation. Compared with the fact that the SDP relaxation lifts the originaln-dimensional variable vector to an n+1×n+1 variable matrix, the new SOCP relaxation only lifts the original n-dimensional variable vector to an n+r-dimensional variable vector, which implies that (3) can be solved more quickly than (4). Therefore, the SOCP relaxation presents greater potential in some real-life applications.Next, we will show that (3) is as tight as the SDP relaxation under certain circumstances. The SDP relaxation of (1) is [14]:(4)minQ0⋅X+q0Tx,s.t.Q1⋅X+q1Tx≤c,Dx≤d,X≽xxT.Suppose that the nonsingular matrixF from (3) also diagonalizes A. In fact, it implies that Q0 and Q1 are simultaneously diagonalizable. In such a case, we have FTQ0F=diagμ1,…,μn and FTQ1F=diag−λ1,…,−λr,λr+1,…,λn with λi>0 for i=1,…,r, λi≥0 for i=r+1,…,n, and μi≥0 for i=1,…,n according to Lemmas 1 and 2. Consequently, (3) can be reformulated as(5)min∑j=1rμjtj+∑j=r+1nμjyj2+p0Ty,s.t.∑j=r+1nλjyj2−∑j=1rλjtj+p1Ty≤c,DFy≤d,yj2≤tj,j=1,…,r.Theorem 1.
WhenQ0 and Q1 are simultaneously diagonalizable, (5) is as tight as (4).Proof.
On one hand, ify,t is a feasible solution of (5), then let x=Fy and X=FyyT+diagt1−y12,…,tr−yr2,0,…,0FT. It is easy to see that X≽xxT and(6)1Q1⋅X+q1Tx=Q1⋅FyyT+diagt1−y12,…,tr−yr2,0,…,0FT+q1Tx,=FTQ1F⋅yyT+diagt1−y12,…,tr−yr2,0,…,0+q1Tx,=diag−λ1,…,−λr,λr+1,…,λn⋅yyT+diagt1−y12,…,tr−yr2,0,…,0+q1Tx,=∑j=r+1nλjyj2−∑j=1rλjtj+p1Ty≤c,2Dx=DFy≤d,3Q0⋅X+q0Tx=Q0⋅FyyT+diagt1−y12,…,tr−yr2,0,…,0FT+q0Tx,=diagμ1,…,μn⋅yyT+diagt1−y12,…,tr−yr2,0,…,0+q0Tx,=∑j=1rμjtj+∑j=r+1nμjyj2+p0Ty.
It implies thatx,X is a feasible solution of (4), and the optimal objective function value of (4) is no more than the one of (5).
On the other hand, ifx,X is a feasible solution of (4), then we define y=F−1x, G=F−1XFT−1 and ti=Gii for i=1,…,r. G≽yyT implies ti≥yi2 for i=1,…,r. Also,(7)4∑j=r+1nλjyj2−∑j=1rλjtj+p1Ty=diag−λ1,…,−λr,λr+1,…,λn⋅diagt1,…,tr,yr+12,…,yn2+p1Ty≤diag−λ1,…,−λr,λr+1,…,λn⋅G+q1Tx=FT−1diag−λ1,…,−λr,λr+1,…,λnF−1⋅FGFT+q1Tx,=Q1⋅X+q1Tx≤c,5DFy=Dx≤d,6∑j=1rμjtj+∑j=r+1nμjyj2+p0Ty=diagμ1,…,μn⋅diagt1,…,tr,yr+12,…,yn2+p0Ty,≤diagμ1,…,μn⋅G+q0Tx=Q0⋅X+q0Tx.
It implies thaty,t is a feasible solution of (5) and the optimal objective function value of (5) is no more than that of (4).
Therefore, (5) is as tight as (4).Proposition 1.
WhenQ0 is positive definite or Q1 is negative semidefinite, (5) is as tight as (4).Proof.
IfQ0 is positive definite or Q1 is negative semidefinite, then Q0 and Q1 are simultaneously diagonalizable according to Lemmas 1 and 2. Hence, (5) is as tight as (4) according to Theorem 1.In what follows, we will use two simple examples to show that (5) is as tight as (4) under the conditions of Proposition 1, but (5) can be solved faster than (4).Example 1.
Consider the problem withn=3 and m=6:(8)minxT321844189314441482x+614−6Tx,s.t.xT−50−27−14−78−493−43−37x+1883Tx≤−49,0≤xi≤1,i=1,2,3.
The optimal objective function value of (4) is 7.9022, and the CPU time is 0.0448 seconds. Since Q0 is positive definite, we can find F=0.3509−0.0183−0.1260−0.0056−0.00630.1133−0.1954−0.09900.0418, FTQ1F=diag−6.1233,−0.4227,0.1347, and FTQ0F=diag1,1,1. The optimal value of (5) is 7.9022, and the CPU time is 0.0196 seconds.Example 2.
Consider the problem withn=3 and m=6:(9)minxT00002−10−11x+−114Tx,s.t.−xTx≤−1,0≤xi≤1,i=1,2,3.
The optimal objective function value of (4) is −1, and the CPU time is 0.1364 seconds. Since Q1 is negative definite, we can find F=1.0000000−0.5257−0.85070−0.85070.5257, FTQ1F=diag−1,−1,−1, and FTQ0F=diag0,0.3820,2.6180. The optimal value of (5) is −1, and the CPU time is 0.0196 seconds.


## 3. A Spatial Branch-and-Bound Algorithm

In this section, we develop a spatial branch-and-bound algorithm based on (3) for (1). Kim and Kojima [24] pointed out that it is necessary to add some appropriate constraints to the auxiliary variables to improve the lower bound. In order to enhance the relaxation effect and design a branch-and-bound algorithm, we introduce reformulation-linearization technique (RLT) constraints to (3). (1) is bounded, and thus there must exist a lower bound lj and an upper bound uj for each yj, j=1,…,r. Therefore, we can add r RLT constraints tj≤lj+ujyj−ljuj for j=1,…,r into (3).The new SOCP relaxation with RLT constraints is in the form(10)min∑j=1rμjtj+∑j=r+1nμjyj2+p0Ty,s.t.yTFTAFy−∑j=1rλjtj+p1Ty≤c,DFy≤d,yj2≤tj,tj≤lj+ujyj−ljuj,j=1,…,r.The initial lower boundlj0 and upper bound uj0 of yj, j=1,…,r are solved by the following 2r linear programming problems:(11)lj0/uj0=min/maxyj,s.t.DFy≤d.Taking Example 1 as an instance, the optimal value of (10) is 15.3976, which is better than the optimal value 7.9022 of (3).Lemma 3.
Lety,t be an optimal solution of (10) over the initial box l0,u0. If yj2=tj for j=1,…,r, then x=Fy is an optimal solution of (3).Proof.
Ifyj2=tj for j=1,…,r, then y is a feasible solution of (2). Consequently, x=Fy is an optimal solution of (1).According to Lemma3, we can see that if y,t is not an optimal solution, then there must exist some j∈1,…,r satisfying tj>yj2. Thus, we can select the index j∗ and split the initial box l0,u0 into two new boxes la,ua and lb,ub with la=l0, ua=u0, uj∗a=lj∗0+uj∗0/2, lb=l0, ub=u0, and lj∗b=lj∗0+uj∗0/2. Consequently, we generate two new nodes over la,ua and lb,ub, respectively, in the branch-and-bound tree.Before describing the spatial branch-and-bound algorithm, we give the following definition.Definition 2.
For a givenε>0 and a vector y∈ℝn, let x=Fy. If xTQ1x+q1Tx≤c+ε, then x is called an ε-feasible solution of (1). Let VQCQP be the optimal objective function value of (1), if the ε-feasible solution x also satisfies xTQ0x+q0Tx≤VQCQP+ε; then, x is called an ε-optimal solution of (1). Define the function(12)fεx=xTQ0x+q0Tx,ifxisε−feasible,+∞,otherwise.
The proposed algorithm is presented in Algorithm1.
Although the branch-and-bound algorithm based on (5) is not detailed here, it can be easily obtained by changing (3) with (5) in the proposed algorithm.
Next, we will prove that Algorithm1 converges after exploring finite nodes and returns an ε-optimal solution.Algorithm 1: A spatial branch-and-bound algorithm (SOCP_BB) for solving (1).
Require: An instance of (1) and a given error tolerance ε>0. Set iteration step k=1, the upper bound V∗=+∞ and x∗=∅.
(1)
Solve (11) for l0 and u0.
(2)
If (11) is infeasible, then
(3)
(1) is infeasible and terminate.
(4)
end if
(5)
Solve (10) over l0,u0 for its optimal objective function value lb0 and optimal solution y0,t0. Let x∗=Uy0 and V∗=fϵy0.
(6)
Construct a setD and insert y0,t0,lb0,l0,u0 into it.
(7)
loop
(8)
if D=∅ then
(9)
returnx∗,V∗ and terminate.
(10)
end if
(11)
Choose a node fromD, denoted as yk,tk,lbk,lk,uk such that lbk=minlbilbi∈D and remove it from D.
(12)
if V∗−lbk≤ε, then
(13)
returnx∗,V∗ and terminate.
(14)
end if
(15)
Setk⟵k+1.
(16)
Choosej∗=argmaxj∈1,…,rλjtjk−yjk2.
(17)
Construct the boxla,ua by setting la=lk, ua=uk, uj∗a=lj∗k+uj∗k/2 and construct the box lb,ub by setting lb=lk, ub=uk, lj∗b=lj∗k+uj∗k/2.
(18)
if (10) over la,ua is feasible, then
(19)
Solve (10) over la,ua for its optimal objective function value lba and optimal solution ya,ta. Denote uba=fεFya.
(20)
if uba<V∗, then
(21)
V∗=uba and x∗=Fya.
(22)
end if
(23)
if V∗−lba>ε, then
(24)
insertya,ta,lba,la,ua into D.
(25)
end if
(26)
end if
(27)
if (10) over lb,ub is feasible, then
(28)
Solve (10) over lb,ub for its optimal objective function value lbb and optimal solution yb,tb. Denote ubb=fεyb.
(29)
if ubb<V∗, then
(30)
V∗=ubb and x∗=Fyb.
(31)
end if
(32)
if V∗−lbb>ε, then
(33)
insertyb,tb,lbb,lb,ub into D.
(34)
end if
(35)
end if
(36)
end loopLemma 4.
Suppose that the nodeyk,tk,lbk,lk,uk is chosen from D in Line 11 of Algorithm 1 such that lbk=minlbilbi∈D and j∗=argmaxj∈1,…,rλjtjk−yjk2. For any ϵ>0, there exists a δ>0 such that if uj∗k−lj∗k≤δ, then Algorithm 1 terminates in Line 13.Proof.
Letxk=Fyk; then,(13)xkTQ1xk+q1Txk=ykTFTAFyk−∑j=1rλjyjk2+p1Tyk,=ykTFTAFyk−∑j=1rλjtjk+p1Tyk+∑j=1rλjtjk−yjk2≤c+∑j=1rλjtjk−yjk2≤c+∑j=1rλjujk−ljk24≤c+rδ24maxλjj=1,…,r.
For anyε>0, set δ=2ε/rmaxλjj=1,…,r, and then xk is an ε-feasible solution. Besides,(14)xkTQ0xk+q0Txk−VQCQP=∑j=1nμjyjk2+p0Tyk−VQCQP≤∑j=1nμjyjk2+p0Tyk−lbk=∑j=1rμjyjk2−tjk≤0.
Therefore,xk is an ε-optimal solution from Definition 2 and Algorithm 1 terminates in Line 13.The proof of Lemma4 implies that if ∑j=1rλjtjk−yjk2≤ϵ, then xk=Fyk is an ε-feasible solution. Thus, we aim to reduce ∑j=1rλjtjk−yjk2 in the branch-and-bound algorithm. Hence, we choose argmaxj∈1,…,rλjtjk−yjk2 as the variable selection strategy.Theorem 2.
Algorithm1 returns an ε-optimal solution after exploring atmost nodes.(15)Nε=∏j=1ruj0−lj0rmaxλjj=1,…,rε.Proof.
Algorithm1 shows that if the algorithm does not terminate in line 13, then a chosen box is split in half and two new boxes are generated. After exploring k nodes, the initial box l0,u0 would be split into k+1 boxes. If Algorithm 1 does not obtain an ε-optimal solution in line 13, it is easy to check that for each box lk,uk among those k+1 boxes, ujk−ljk≥minδ/2,uj0−lj0 with δ=2ε/rmaxλj,j=1,…,r for j=1,…,r. Otherwise, if there exists a j∗ such that uj∗k−lj∗k≤δ, and the j∗-th edge has been selected as a branching direction, then following from Lemma 4, we conclude that xk=Fyk is an ε-optimal solution. It contradicts with the assumption that Algorithm 1 does not obtain an ε-optimal solution in line 13 at node k. Hence, the volume of each box is no smaller than ∏j=1rminδ/2,uj0−lj0. Due to the fact that the total volume of all the k+1 boxes is no more than the one of the initial box l0,u0, it is easy to check that, after exploring Nε=∏j=1r2uj0−lj0/δ=∏j=1ruj0−lj0rmaxλjj=1,…,r/ε nodes, Algorithm 1 returns an ε-optimal solution.


## 4. Numerical Experiments

In this section, we compare the proposed algorithm with Algorithm1 in [25] which is a SDP relaxation-based branch-and-bound algorithm (SDP_BB). These algorithms are implemented in MATLAB R2013b on a PC with Window 7, 2.50 GHz Inter Dual Core CPU processors and 8 GB RAM. The SDP relaxations are solved by SeDuMi 1.02 [26] and the SOCP relaxations are solved by Cplex solver 12.6.3. The error tolerance is set to be ε=5e−4.The instances for the experiments are generated as follows. The entries ofqi are integers uniformly drawn at random from intervals −8,18 for each j=0,1. The elements of matrices Qj are integers uniformly drawn at random from intervals −100,10 (reference [17]). Then, Q0 and Q1 are replaced by their real symmetric parts. Q0 is decomposed as Q0=VDVT where D is the diagonal matrix of eigenvalues, and V is the orthogonal matrix whose columns are the corresponding eigenvectors. Let Q0=VDVT. We generate a vector a∈ℝn with the entries of a uniformly drawn at random from intervals 0,1. Then, we let c=ceilaTq1+aTQ1a, Q0=Q0/aTq0+aTQ0a, q0=q0/aTq0+aTQ0a, D=I−I, and d=e0. Five instances are generated for each given problem size in Table 1. The explored nodes (exp nodes) and CPU time in seconds (CPU time) are displayed for each algorithm in Table 1. The symbol “—” means the instance cannot be solved within the given maximum computing time of 10000 seconds.Table 1
Comparisons between SOCP_BB and SDP_BB.
n
SOCP_BB
SDP_BB
Exp nodes
CPU time
Exp nodes
CPU time
10
109
4.4539
208
50.0983
10
1
0.0240
1
0.0698
10
128
5.1209
230
41.2431
10
92
3.4678
75
11.5937
10
1
0.0228
2
0.1881
20
125
8.3562
176
69.9982
20
1664
115.1088
3114
1067.7725
20
566
38.1457
991
330.2524
20
30
1.9629
54
13.2143
20
55
3.5615
134
31.8341
30
1
0.08702
2
0.5089
30
114
9.6467
272
179.0759
30
4389
419.0829
3910
1431.4212
30
70
5.9402
92
34.3371
30
2983
260.3418
7523
4909.2678
40
21
2.8233
52
29.3877
40
54
6.5244
214
121.6062
40
74
8.3827
185
110.2765
40
136
15.4152
252
156.2269
40
31
3.3112
200
119.5072
50
152
24.5512
483
456.7316
50
139
21.9021
445
411.3182
50
1
0.3228
1
0.4154
50
150
23.5961
210
187.4114
50
19
3.9621
107
104.7606
60
13
2.3786
59
82.2647
60
5
1.1534
35
54.2444
60
103
18.7057
305
426.8943
60
18
4.1163
63
93.2252
60
19
4.2133
79
113.4004
70
5434
1332.6043
—
—
70
32
7.8642
203
432.7264
70
3677
891.9838
—
—
70
60
14.3761
111
250.3169
70
258
57.3409
724
1556.7962
80
11
4.1058
27
78.7600
80
69
17.6592
306
948.1594
80
136
45.5027
607
1896.2123
80
12634
4315.1516
—
—
80
81
24.2367
626
1829.0213
90
1979
820.2060
758
3708.4941
90
13148
4698.9012
—
—
90
3563
1322.3103
—
—
90
13469
4953.5129
—
—
90
151
54.3170
1814
8381.2107
100
23
12.6613
161
964.7115
100
337
153.4485
—
—
100
9
6.2885
47
264.1438
100
5454
2783.0369
—
—
100
102
48.8754
313
1859.7320Table1 shows that(1)
It is easy to observe that the average time cost for each explored node, i.e.,CPU time/exp nodes of the proposed algorithm SOCP_BB, is much lower than that of the algorithm SDP_BB for each instance. Also, this evidence is deepened when n becomes larger. The observation further illustrates that the computing efficiency of solving the SOCP relaxation is higher than that of solving the SDP relaxation.(2)
For most of the instances, both the number of explored nodes and the CPU time of the proposed algorithm SOCP_BB are smaller than those of the algorithm SDP_BB. It implies that the proposed SOCP relaxation offers a good trade-off between the computing efficiency and bound quality for (1).


## 5. Conclusion

By exploiting the simultaneous diagonalization technique, we derive a new SOCP relaxation for (1). Then, we prove that the SOCP relaxation is as tight as the well-known SDP relaxation in certain cases. Furthermore, we design a spatial branch-and-bound algorithm based on the new SOCP relaxation. Finally, numerical experiments are conducted to demonstrate the efficiency of the proposed method by comparing with the SDP relaxation-based branch-and-bound algorithm, and the promising results illustrates that the simultaneous diagonalization-based SOCP relaxation indeed well balance the bound quality and computing time.



---

*Source: 5717301-2020-02-25.xml*