Article Contents
Article Contents

# A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs

• * Corresponding author: Zhibin Deng
• In this paper, we propose a novel low-dimensional semidefinite programming (SDP) relaxation for convex quadratically constrained nonconvex quadratic programming problems. This new relaxation is derived by simultaneous matrix diagonalization method under the difference of convex decomposition scheme. The highlight of the relaxation is the low dimensionality of the positive semidefinite constraint, which only depends on the number of negative eigenvalues in the objective function. We prove that a mixed SOCP and SDP relaxation appeared in the literature is equivalent to the proposed relaxation, while the proposed relaxation has fewer constraints. We also provide conditions under which the proposed relaxation is as tight as the classical SDP relaxation and provides an optimal value for the original problem. For general cases, a spatial branch-and-bound algorithm is designed for finding a global optimal solution. Extensive numerical experiments support that the proposed algorithm outperforms two cutting-edge algorithms when the problem size is medium or large and the number of negative eigenvalues in the nonconvex objective function is relatively small.

Mathematics Subject Classification: Primary: 90C26, 90C34.

 Citation:

•  Algorithm 1 A Spatial Branch-and-Bound Algorithm for Solving (QCQP) Require: An instance of (QCQP) and a given error tolerance $\epsilon>0$. Set iteration step $p=1$.  1: Solve (wj-Bound}) for $l^0$ and $u^0$.  2: If (wj-Bound) is infeasible, then  3:      (QCQP) is infeasible and terminate.  4: end if  5: Solve (LowSDP) with $[l^0, u^0]$ for its optimal value ${lb}^0$ and optimal solution $(w^0,v^0,W^0)$. Let $U^*=f\Big(F \begin{bmatrix} {w^{0}} \\ {v^{0}} \end{bmatrix}\Big)$ and $x^*=F \begin{bmatrix} {w^{0}} \\{v^{0}} \end{bmatrix}$.  6: Construct a set $\mathcal{D}$ and insert $\{w^0,v^0,W^0,lb^0,l^0,u^0\}$ into it.  7: loop  8:      If $\mathcal{D}= \emptyset$, then  9:          return $(x^*,U^*)$ and terminate. 10:      end if 11:      Choose a problem from $\mathcal{D}$ using the node selection strategy, denoted as $\{w^p,v^p,W^p,lb^p,l^p,u^p\}$ such that $lb^p=\min\{lb^k|lb^k \in \mathcal{D}\}$. Delete it from $\mathcal{D}$. 12:      if $U^*-lb^p \leq \varepsilon$, then 13:          return $(x^*,U^*)$ and terminate. 14:      end if 15:      Set $p\leftarrow p+1$. 16:      Choose $j^*$ by the variable selection strategy. 17:      Set $l^a=l^p$, $u^a=u^p$, $u_{j^*}^a=\frac{l_{j^*}^p+u_{j^*}^p}{2}$, $l^b=l^p$, $u^b=u^p$, $l_{j^*}^b=\frac{l_{j^*}^p+u_{j^*}^p}{2}.$ 18:      if (LowSDP) with $[l^a, u^a]$ is feasible, then 19:          Solve (LowSDP) with $[l^a, u^a]$ for its optimal value ${lb}^a$ and optimal solution $(w^a,v^a,W^a)$ and denote $ub^a=f\Big(F \begin{bmatrix} {w^{a}} \\{v^{a}} \end{bmatrix}\Big)$. 20:        if $ub^a < U^*$, then 21:            $U^*=ub^a$ and $x^*=F \begin{bmatrix}{w^{a}} \\{v^{a}} \end{bmatrix}$. 22:        end if 23:        if $U^*-lb^a > \varepsilon$, then 24:            insert $\{w^a,v^a,W^a,{lb}^a,l^a,u^a\}$ into $\mathcal{D}$. 25:        end if 26:      end if 27:      if (LowSDP) with $[l^b, u^b]$ is feasible, then 28:          Solve (LowSDP) with $[l^b, u^b]$ for its optimal value ${lb}^b$ and optimal solution $(w^b,v^b,W^b)$ and denote $ub^b=f\Big(F \begin{bmatrix} {w^{b}} \\ {v^{b}} \end{bmatrix}\Big)$. 29:        If $ub^b < U^*$, then 30:            $U^*=ub^b$ and $x^*=F \begin{bmatrix}{w^{b}} \\ {v^{b}} \end{bmatrix}$. 31:        end if 32:        if $U^*-lb^b > \varepsilon$, then 33:            insert $\{w^b,v^b,W^b,{lb}^b,l^b,u^b\}$ into $\mathcal{D}$. 34:        end if 35:      end if 36: end loop

Table 1.  Comparison of lower bounds and CPU times for solving (LowSDP) and (SOCP-SDP)

 (LowSDP) (SOCP-SDP) ($n$, $m$, $r$) lower bound CPU(sec) lower bound CPU(sec) (100, 5, 33) -17.2771 0.8881 -17.2771 2.5127 (200, 5, 66) -24.3489 5.3022 -24.3489 20.3933 (300, 5,100) -28.5893 15.4098 -28.5893 74.1433 (400, 5,133) -34.9650 39.3298 -34.9650 211.8385 (500, 5,166) -38.3098 64.6529 -38.3098 549.5897 (100, 10, 33) -17.4904 1.5154 -17.4904 2.7576 (200, 10, 66) -23.9473 8.8909 -23.9473 16.6288 (300, 10,100) -30.1268 29.9709 -30.1268 57.2365 (400, 10,133) -34.3719 69.1769 -34.3719 315.4569 (100, 10, 25) -16.7852 1.2385 -16.7852 2.1822 (200, 10, 50) -23.2197 8.2397 -23.2220 15.3132 (300, 10, 75) -28.7501 22.8818 -28.7501 48.2711 (400, 10,100) -32.9298 53.9278 -32.9697 279.6444

Table 2.  Comparisons on trust-region problems with linear inequality constraints

 Proposed Algorithm ED Algorithm BW Algorithm ($n$, $m$, $r$) aver iter aver CPU std aver iter aver CPU std aver iter aver CPU std (100, 2, 33) 9.7 6.6 0.6 9.5 21.2 3.5 17.1 14.8 4.6 (150, 2, 50) 10.5 16.1 1.5 10.5 81.3 13.7 44.2 86.5 175.0 (200, 2, 66) 9.6 37.3 2.2 9.0 213.0 62.7 36.5 133.2 190.6 (100, 6, 33) 10.2 6.8 0.6 10.1 24.5 3.4 182.1 200.2 270.6 $r=\lfloor \frac{n}{3}\rfloor$ (150, 6, 50) 8.8 17.2 1.7 8.4 70.9 20.3 67.4 158.5 184.0 (200, 6, 66) 9.3 36.5 2.7 9.3 237.1 52.4 76.2 426.2 1077.7 (100, 10, 33) 10.1 7.1 0.9 10.0 22.3 4.5 124.6 113.7 119.7 (150, 10, 50) 10.4 17.7 2.0 10.1 78.1 17.5 569.7 1583.9 4553.0 (200, 10, 66) 9.5 36.2 6.1 9.3 186.4 69.3 308.0 1336.0 2984.3 (100, 2, 50) 8.9 8.7 1.6 8.8 27.0 9.6 36.2 33.6 63.8 (150, 2, 75) 9.6 24.5 2.7 9.7 117.6 15.7 58.6 143.4 229.4 (200, 2,100) 8.6 43.7 7.8 8.0 266.4 120.1 96.6 449.7 1238.3 (100, 6, 50) 9.8 9.7 2.5 10.0 36.6 13.7 148.3 168.2 209.7 $r=\lfloor \frac{n}{2}\rfloor$ (150, 6, 75) 9.6 22.0 3.7 9.7 108.7 29.5 98.2 198.4 308.4 (200, 6,100) 9.3 53.1 5.2 9.3 273.1 35.1 41.8 185.7 343.4 (100, 10, 50) 10.2 9.9 0.3 10.2 35.1 2.5 81.9 82.0 114.5 (150, 10, 75) 9.0 23.4 4.2 8.9 108.7 38.4 82.5 181.1 341.5 (200, 10,100) 9.3 46.3 8.0 9.1 297.4 105.6 150.4 833.7 2204.1 (100, 2, 66) 9.5 11.8 0.9 9.4 38.6 5.0 15.3 12.3 4.5 (150, 2,100) 6.3 21.8 6.5 6.4 94.3 56.5 12.8 23.0 12.5 (200, 2,133) 9.3 56.3 4.1 9.4 374.6 69.7 81.3 308.6 483.7 (100, 6, 66) 9.8 12.6 0.9 9.8 39.9 3.6 64.8 62.5 144.1 $r=\lfloor \frac{2n}{3}\rfloor$ (150, 6,100) 9.8 30.1 2.5 9.7 152.7 22.0 21.4 40.3 24.2 (200, 6,133) 9.6 61.4 5.0 9.6 399.9 44.8 64.5 241.5 527.6 (100, 10, 66) 9.8 13.5 1.0 9.8 41.5 4.2 92.8 94.0 131.4 (150, 10,100) 8.9 30.4 5.2 9.0 143.2 45.6 15.4 30.0 13.0 (200, 10,133) 8.1 61.1 9.2 8.1 351.0 121.1 23.4 84.4 40.4

Table 3.  Comparisons on generalized CDT problem

 Proposed algorithm ED Algorithm BW Algorithm ($n$, $m$, $r$) aver iter aver CPU std aver iter aver CPU std aver iter aver CPU std (100, 2, 33) 10.8 10.8 1.1 10.7 24.8 3.8 132.8 154.0 102.2 (150, 2, 50) 9.5 29.0 1.6 9.5 81.9 6.7 55.9 163.1 197.1 (200, 2, 66) 9.4 62.1 6.2 9.3 199.4 32.9 52.5 235.3 227.5 (100, 3, 33) 10.9 17.3 2.0 9.6 24.3 6.9 86.1 114.0 187.5 (150, 3, 50) 11.8 60.5 5.6 10.5 99.9 14.9 65.8 221.9 244.6 (200, 3, 66) 12.1 125.0 42.8 11.6 257.0 131.5 125.3 637.5 1103.2 $r = \lfloor \frac{n}{3}\rfloor$ (100, 4, 33) 12.1 28.2 7.2 11.7 32.8 9.5 270.1 355.3 431.9 (150, 4, 50) 9.9 76.2 6.6 9.2 90.6 12.5 34.6 175.9 168.3 (200, 4, 66) 11.1 233.4 36.8 10.3 284.6 69.4 345.1 2594.1 6676.9 (100, 5, 33) 11.0 41.6 4.7 10.3 42.0 4.9 72.7 117.9 139.5 (150, 5, 50) 10.9 138.3 21.5 10.5 129.8 10.5 74.8 371.2 507.1 (200, 5, 66) 10.9 345.3 60.5 10.8 344.1 68.4 96.8 904.7 1064.0 (100, 2, 50) 10.4 14.5 2.3 10.3 36.1 7.9 129.5 181.4 147.0 (150, 2, 75) 10.0 41.0 3.8 10.0 130.9 18.4 52.0 153.9 218.3 (200, 2,100) 10.6 89.9 11.6 10.2 331.4 73.7 30.2 146.6 55.8 (100, 3, 50) 9.8 22.7 1.2 9.8 40.4 2.9 22.8 35.1 34.9 (150, 3, 75) 9.9 65.4 6.4 9.8 131.6 22.7 33.2 112.5 142.5 (200, 3,100) 9.9 158.1 4.9 9.9 366.5 32.1 48.6 371.6 393.2 $r = \lfloor \frac{n}{2}\rfloor$ (100, 4, 50) 9.4 36.3 5.0 9.0 40.0 5.9 48.0 75.1 103.9 (150, 4, 75) 12.5 131.6 33.0 10.4 153.7 46.8 211.4 841.7 1729.6 (200, 4,100) 10.2 249.1 17.8 9.7 398.9 56.8 139.2 1049.6 1096.1 (100, 5, 50) 9.7 49.0 5.7 9.4 47.3 6.0 42.7 72.3 96.1 (150, 5, 75) 10.4 148.4 11.5 9.6 174.1 15.9 107.0 434.8 427.6 (200, 5,100) 10.3 479.0 38.6 9.8 550.5 59.2 101.1 931.0 830.7 (100, 2, 66) 10.3 19.3 2.5 10.1 42.9 8.7 146.1 168.6 181.7 (150, 2,100) 13.4 60.1 28.1 10.0 157.0 28.9 76.8 198.9 264.0 (200, 2,133) 10.6 110.6 7.4 10.6 465.5 53.3 105.0 519.6 876.1 (100, 3, 66) 9.7 25.9 2.5 9.2 42.7 6.6 146.4 179.5 399.1 (150, 3,100) 9.6 77.3 8.8 9.5 166.7 37.3 60.4 198.0 287.0 (200, 3,133) 10.0 181.9 9.0 9.3 453.2 67.2 114.1 658.1 1102.6 $r = \lfloor \frac{2n}{3}\rfloor$ (100, 4, 66) 10.1 39.1 3.5 9.5 50.2 5.0 59.0 101.3 132.1 (150, 4,100) 10.2 128.5 10.3 9.8 204.7 26.5 91.3 337.7 430.5 (200, 4,133) 10.7 341.6 45.8 10.4 575.1 95.7 243.8 1497.5 1597.9 (100, 5, 66) 11.1 59.2 9.5 10.7 62.9 11.6 400.7 523.1 862.5 (150, 5,100) 9.6 181.1 12.0 9.5 224.3 27.6 113.2 443.2 546.9 (200, 5,133) 9.7 476.0 30.9 9.6 612.3 72.8 75.2 699.2 589.2

Tables(4)