• Previous Article
    Differential equation approximation and enhancing control method for finding the PID gain of a quarter-car suspension model with state-dependent ODE
  • JIMO Home
  • This Issue
  • Next Article
    Financing strategies for a capital-constrained supplier under yield uncertainty
doi: 10.3934/jimo.2019044

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

1. 

Department of Applied Mathematics, College of Science, Zhejiang University of Technology, Hangzhou, Zhejiang, 310032, China

2. 

School of Economics and Management, University of Chinese Academy of Sciences, Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences, Beijing, 100190, China

* Corresponding author: Zhibin Deng

Received  October 2018 Revised  December 2018 Published  May 2019

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.

Citation: Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019044
References:
[1]

K. Anstreicher, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, Journal of Global Optimization, 43 (2009), 471-484. doi: 10.1007/s10898-008-9372-0.

[2]

A. Ben-Tal and D. Hertog, Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Mathematical Programming, 143 (2014), 1-29. doi: 10.1007/s10107-013-0710-8.

[3]

Ø Bergmann and T. Steihaug, Solving trust-region subproblem augmented with linear inequality constraints, Optimization Methods and Software, 28 (2013), 26-36. doi: 10.1080/10556788.2011.582501.

[4]

D. Bienstock, A note on polynomial solvability of the CDT problem, SIAM Journal on Optimization, 26 (2016), 488-498. doi: 10.1137/15M1009871.

[5]

I. M. BomzeM. Locatelli and F. Tardella, New and old bounds for standard quadratic optimization: Dominance, equivalence and incomparability, Mathematical Programming, 115 (2008), 31-64. doi: 10.1007/s10107-007-0138-0.

[6]

I. M. Bomze and M. L. Overton, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Mathematical Programming, 151 (2015), 459-476. doi: 10.1007/s10107-014-0836-3.

[7]

C. Buchheim and A. Wiegele, Semidefinite relaxations for non-convex quadratic mixed-integer programming, Mathematical Programming, 141 (2013), 435-452. doi: 10.1007/s10107-012-0534-y.

[8]

S. BurerS. Kim and M. Kojima, Faster, but weaker, relaxations for quadratically constrained quadratic programs, Computational Optimization and Applications, 59 (2014), 27-45. doi: 10.1007/s10589-013-9618-8.

[9]

S. Burer and B. Yang, The trust region subproblem with non-intersecting linear constraints, Mathematical Programming, 149 (2015), 253-264. doi: 10.1007/s10107-014-0749-1.

[10]

J. Chen and S. Burer, Globally solving nonconvex quadratic programming problems via completely positive programming, Mathematical Programming Computation, 4 (2012), 33-52. doi: 10.1007/s12532-011-0033-9.

[11]

J. Dai, S.-C. Fang and W. Xing, Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints, Journal of Industrial and Management Optimization, (2018). doi: 10.3934/jimo.2018117.

[12]

Z. DengS.-C. FangQ. Jin and C. Lu, Conic approximation to nonconvex quadratic programming with convex quadratic constraints, Journal of Global Optimization, 61 (2015), 459-478. doi: 10.1007/s10898-014-0195-x.

[13]

D. Y. Gao, Solutions and optimality criteria to box constrained nonconvex minimization problems, Journal of Industrial and Management Optimization, 3 (2007), 293-304. doi: 10.3934/jimo.2007.3.293.

[14]

V. Jeyakumar and G. Y. Li, Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization, Mathematical Programming, 147 (2014), 171-206. doi: 10.1007/s10107-013-0716-2.

[15]

S. Kim and M. Kojima, Second order cone programming relaxation of nonconvex quadratic optimization problems, Optimization Methods and Software, 15 (2001), 201-224. doi: 10.1080/10556780108805819.

[16]

C. LuZ. Deng and Q. Jin, An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints, Journal of Global Optimization, 67 (2017), 475-493. doi: 10.1007/s10898-016-0436-2.

[17]

Z. Q. LuoW. K. MaA. M. C. SoY. Ye and S. Zhang, Semidefinite relaxation of quadratic optimization problems, IEEE Signal Processing Magazine, 27 (2010), 20-34. doi: 10.1109/MSP.2010.936019.

[18]

P. M. Pardalos and S. A. Vavasis, Quadratic programming with one negative eigenvalue is NP-hard, Journal of Global Optimization, 1 (1991), 15-22. doi: 10.1007/BF00120662.

[19]

J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.

[20]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267. doi: 10.1287/moor.28.2.246.14485.

[21]

J. WangJ. Lu and Y. Feng, Congruence diagonalization of two Hermite matrices simultaneously, International Journal of Algebra, 4 (2010), 1119-1125.

[22]

X. ZhengX. Sun and D. Li, Nonconvex quadratically constrained quadratic programming: Best DC decompositions and their SDP representations, Journal of Global Optimization, 50 (2011), 695-712. doi: 10.1007/s10898-010-9630-9.

[23]

J. ZhouZ. DengS.-C. Fang and W. Xing, Detection of a copositive matrix over a p-th order cone, Pacific Journal of Optimization, 10 (2014), 593-611.

[24]

J. ZhouS.-C. Fang and W. Xing, Conic approximation to quadratic optimization with linear complementarity constraints, Computational Optimization and Applications, 66 (2017), 97-122. doi: 10.1007/s10589-016-9855-8.

[25]

J. Zhou and Z. Xu, A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints, Optimization Letters, (2018). doi: 10.1007/s11590-018-1337-8.

show all references

References:
[1]

K. Anstreicher, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, Journal of Global Optimization, 43 (2009), 471-484. doi: 10.1007/s10898-008-9372-0.

[2]

A. Ben-Tal and D. Hertog, Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Mathematical Programming, 143 (2014), 1-29. doi: 10.1007/s10107-013-0710-8.

[3]

Ø Bergmann and T. Steihaug, Solving trust-region subproblem augmented with linear inequality constraints, Optimization Methods and Software, 28 (2013), 26-36. doi: 10.1080/10556788.2011.582501.

[4]

D. Bienstock, A note on polynomial solvability of the CDT problem, SIAM Journal on Optimization, 26 (2016), 488-498. doi: 10.1137/15M1009871.

[5]

I. M. BomzeM. Locatelli and F. Tardella, New and old bounds for standard quadratic optimization: Dominance, equivalence and incomparability, Mathematical Programming, 115 (2008), 31-64. doi: 10.1007/s10107-007-0138-0.

[6]

I. M. Bomze and M. L. Overton, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Mathematical Programming, 151 (2015), 459-476. doi: 10.1007/s10107-014-0836-3.

[7]

C. Buchheim and A. Wiegele, Semidefinite relaxations for non-convex quadratic mixed-integer programming, Mathematical Programming, 141 (2013), 435-452. doi: 10.1007/s10107-012-0534-y.

[8]

S. BurerS. Kim and M. Kojima, Faster, but weaker, relaxations for quadratically constrained quadratic programs, Computational Optimization and Applications, 59 (2014), 27-45. doi: 10.1007/s10589-013-9618-8.

[9]

S. Burer and B. Yang, The trust region subproblem with non-intersecting linear constraints, Mathematical Programming, 149 (2015), 253-264. doi: 10.1007/s10107-014-0749-1.

[10]

J. Chen and S. Burer, Globally solving nonconvex quadratic programming problems via completely positive programming, Mathematical Programming Computation, 4 (2012), 33-52. doi: 10.1007/s12532-011-0033-9.

[11]

J. Dai, S.-C. Fang and W. Xing, Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints, Journal of Industrial and Management Optimization, (2018). doi: 10.3934/jimo.2018117.

[12]

Z. DengS.-C. FangQ. Jin and C. Lu, Conic approximation to nonconvex quadratic programming with convex quadratic constraints, Journal of Global Optimization, 61 (2015), 459-478. doi: 10.1007/s10898-014-0195-x.

[13]

D. Y. Gao, Solutions and optimality criteria to box constrained nonconvex minimization problems, Journal of Industrial and Management Optimization, 3 (2007), 293-304. doi: 10.3934/jimo.2007.3.293.

[14]

V. Jeyakumar and G. Y. Li, Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization, Mathematical Programming, 147 (2014), 171-206. doi: 10.1007/s10107-013-0716-2.

[15]

S. Kim and M. Kojima, Second order cone programming relaxation of nonconvex quadratic optimization problems, Optimization Methods and Software, 15 (2001), 201-224. doi: 10.1080/10556780108805819.

[16]

C. LuZ. Deng and Q. Jin, An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints, Journal of Global Optimization, 67 (2017), 475-493. doi: 10.1007/s10898-016-0436-2.

[17]

Z. Q. LuoW. K. MaA. M. C. SoY. Ye and S. Zhang, Semidefinite relaxation of quadratic optimization problems, IEEE Signal Processing Magazine, 27 (2010), 20-34. doi: 10.1109/MSP.2010.936019.

[18]

P. M. Pardalos and S. A. Vavasis, Quadratic programming with one negative eigenvalue is NP-hard, Journal of Global Optimization, 1 (1991), 15-22. doi: 10.1007/BF00120662.

[19]

J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.

[20]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267. doi: 10.1287/moor.28.2.246.14485.

[21]

J. WangJ. Lu and Y. Feng, Congruence diagonalization of two Hermite matrices simultaneously, International Journal of Algebra, 4 (2010), 1119-1125.

[22]

X. ZhengX. Sun and D. Li, Nonconvex quadratically constrained quadratic programming: Best DC decompositions and their SDP representations, Journal of Global Optimization, 50 (2011), 695-712. doi: 10.1007/s10898-010-9630-9.

[23]

J. ZhouZ. DengS.-C. Fang and W. Xing, Detection of a copositive matrix over a p-th order cone, Pacific Journal of Optimization, 10 (2014), 593-611.

[24]

J. ZhouS.-C. Fang and W. Xing, Conic approximation to quadratic optimization with linear complementarity constraints, Computational Optimization and Applications, 66 (2017), 97-122. doi: 10.1007/s10589-016-9855-8.

[25]

J. Zhou and Z. Xu, A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints, Optimization Letters, (2018). doi: 10.1007/s11590-018-1337-8.

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
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
(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
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
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
[1]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

[2]

Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871

[3]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543

[4]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703

[5]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171

[6]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965

[7]

Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647

[8]

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111

[9]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185

[10]

Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial & Management Optimization, 2019, 15 (2) : 893-908. doi: 10.3934/jimo.2018076

[11]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[12]

Jinling Zhao, Wei Chen, Su Zhang. Immediate schedule adjustment and semidefinite relaxation. Journal of Industrial & Management Optimization, 2019, 15 (2) : 633-645. doi: 10.3934/jimo.2018062

[13]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

[14]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65

[15]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651

[16]

Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697

[17]

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033

[18]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653

[19]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[20]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (15)
  • HTML views (95)
  • Cited by (0)

Other articles
by authors

[Back to Top]