• Previous Article
    Existence of solution of a microwave heating model and associated optimal frequency control problems
  • JIMO Home
  • This Issue
  • Next Article
    Optimal expansion timing decisions in multi-stage PPP projects involving dedicated asset and government subsidies
September  2020, 16(5): 2087-2102. 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, 2020, 16 (5) : 2087-2102. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

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

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

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

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[2]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[3]

Anton Schiela, Julian Ortiz. Second order directional shape derivatives of integrals on submanifolds. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021017

[4]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136

[5]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[6]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184

[7]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212

[8]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[9]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141

[10]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881

[11]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[12]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067

[13]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109

[14]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[15]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[16]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597

[17]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[18]

Lars Grüne, Luca Mechelli, Simon Pirkelmann, Stefan Volkwein. Performance estimates for economic model predictive control and their application in proper orthogonal decomposition-based implementations. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021013

[19]

Pavel I. Naumkin, Isahi Sánchez-Suárez. Asymptotics for the higher-order derivative nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021028

[20]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (165)
  • HTML views (689)
  • Cited by (1)

Other articles
by authors

[Back to Top]