-
Previous Article
Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods
- JIMO Home
- This Issue
-
Next Article
Pricing power exchange options with hawkes jump diffusion processes
A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem
1. | Department of Applied Mathematics, College of Science, Zhejiang University of Technology, Hangzhou, Zhejiang, 310032, China |
2. | School of Economics and Management, North China Electric Power University, Beijing, 102206, China |
3. | School of Business Administration, and Collaborative Innovation Center of Financial Security, Southwestern University of Finance and Economics, Chengdu, 611130, China |
4. | Department of Information Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong |
This paper proposes a second-order cone programming (SOCP) relaxation for the generalized trust-region problem by exploiting the property that any symmetric matrix and identity matrix can be simultaneously diagonalizable. We show that our proposed SOCP relaxation can provide a lower bound as tight as that of the standard semidefinite programming (SDP) relaxation. Moreover, we provide a sufficient condition under which the proposed SOCP relaxation is exact. Since the standard SDP relaxation suffers from a much heavier computing burden, the proposed SOCP relaxation has a much higher efficiency in solving process. Then we design a branch-and-bound algorithm based on this SOCP relaxation to obtain the global optimal solution for a general problem. Three types of numerical experiments are carried out to demonstrate the effectiveness and efficiency of our proposed SOCP relaxation.
References:
[1] |
W. Ai and S. Zhang,
Strong duality for the CDT subproblem: A necessary and sufficient condition, SIAM J. Optim., 19 (2009), 1735-1756.
doi: 10.1137/07070601X. |
[2] |
A. I. Barvinok,
Feasibility testing for systems of real quadratic equations, Discrete Comput. Geom., 10 (1993), 1-13.
doi: 10.1007/BF02573959. |
[3] |
A. Beck and D. Pan,
A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints, J. Global Optim., 69 (2017), 309-342.
doi: 10.1007/s10898-017-0521-1. |
[4] |
A. Ben-Tal and D. Den Hertog,
Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Math. Program., 143 (2014), 1-29.
doi: 10.1007/s10107-013-0710-8. |
[5] |
D. Bienstock and A. Michalka, Polynomial solvability of variants of the trust-region subproblem, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics, New York, 2014,380–390.
doi: 10.1137/1.9781611973402.28. |
[6] |
D. Bienstock,
A note on polynomial solvability of the CDT problem, SIAM J. Optim., 26 (2016), 488-498.
doi: 10.1137/15M1009871. |
[7] |
I. M. Bomze and M. L. Overton,
Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Math. Program., 151 (2015), 459-476.
doi: 10.1007/s10107-014-0836-3. |
[8] |
I. M. Bomze, V. Jeyakumar and G. Li,
Extended trust-region problems with one or two balls: Exact copositive and Lagrangian relaxations, J. Global Optim., 71 (2018), 551-569.
doi: 10.1007/s10898-018-0607-4. |
[9] |
S. Burer and K. M. Anstreicher,
Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23 (2013), 432-451.
doi: 10.1137/110826862. |
[10] |
M. R. Celis, J. E. Dennis and R. A. Tapia,
A trust region strategy for nonlinear equality constrained optimization, Numerical Optimization, 1984 (1985), 71-82.
|
[11] |
M. Grant and S. Boyed, CVX: Matlab Software for Disciplined Convex Programming, version 2.1, (2014). Available at: http://cvxr.com/cvx. Google Scholar |
[12] |
N. Ho-Nguyen and F. Kilinc-Karzan,
A second-order cone based approach for solving the trust-region subproblem and its variants, SIAM J. Optim., 27 (2017), 1485-1512.
doi: 10.1137/16M1065197. |
[13] |
R. Jiang and D. Li,
Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming, SIAM J. Optim., 26 (2016), 1649-1668.
doi: 10.1137/15M1023920. |
[14] |
V. Jeyakumar and G. Y. Li,
Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization, Math. Program., 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, Optim. Methods Softw., 15 (2001), 201-224.
doi: 10.1080/10556780108805819. |
[16] |
C. Lu, Z. Deng and Q. Jin,
An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints, J. Global Optim., 67 (2017), 475-493.
doi: 10.1007/s10898-016-0436-2. |
[17] |
C. Lu, Z. Deng, J. Zhou and X. Guo,
A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming, J. Global Optim., 73 (2019), 371-388.
doi: 10.1007/s10898-018-0726-y. |
[18] |
Z. Q. Luo, W. K. Ma, A. M. C. So, Y. Ye and S. Zhang,
Semidefinite relaxation of quadratic optimization problems, IEEE Signal Processing Magazine, 27 (2010), 20-34.
doi: 10.1109/MSP.2010.936019. |
[19] |
D. R. Morrison, S. H. Jacobson, J. J. Sauppe and E. C. Sewell,
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning, Discrete Optim., 19 (2016), 79-102.
doi: 10.1016/j.disopt.2016.01.005. |
[20] |
K. B. Petersen and M. S. Pedersen, The matrix cookbook, Technical University of Denmark, 7 (2008), 510pp. Google Scholar |
[21] |
N. Sagara and M. Fukushima,
A trust region method for nonsmooth convex optimization, J. Ind. Manag. Optim., 1 (2005), 171-180.
doi: 10.3934/jimo.2005.1.171. |
[22] |
Z. Sheng, G. Yuan, Z. Cui, X. Duan and X. Wang,
An adaptive trust region algorithm for large-residual nonsmooth least squares problems, J. Ind. Manag. Optim., 14 (2018), 707-718.
doi: 10.3934/jimo.2017070. |
[23] |
J. F. Sturm,
Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11 (1999), 625-653.
doi: 10.1080/10556789908805766. |
[24] |
J. F. Sturm and S. Zhang,
On cones of nonnegative quadratic functions, Math. Oper. Res., 28 (2003), 246-267.
doi: 10.1287/moor.28.2.246.14485. |
[25] |
Y. Tian, Z. Deng, J. Luo and Y. Li,
An intuitionistic fuzzy set based S3VM model for binary classification with mislabeled information, Fuzzy Optim. Decis. Mak., 17 (2018), 475-494.
doi: 10.1007/s10700-017-9282-z. |
[26] |
J. Zhou, S.-C. Fang and W. Xing,
Conic approximation to quadratic optimization with linear complementarity constraints, Comput. Optim. Appl., 66 (2017), 97-122.
doi: 10.1007/s10589-016-9855-8. |
[27] |
J. Zhou and Z. Xu,
A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints, Optim. Letters, 13 (2019), 1615-1630.
doi: 10.1007/s11590-018-1337-8. |
show all references
References:
[1] |
W. Ai and S. Zhang,
Strong duality for the CDT subproblem: A necessary and sufficient condition, SIAM J. Optim., 19 (2009), 1735-1756.
doi: 10.1137/07070601X. |
[2] |
A. I. Barvinok,
Feasibility testing for systems of real quadratic equations, Discrete Comput. Geom., 10 (1993), 1-13.
doi: 10.1007/BF02573959. |
[3] |
A. Beck and D. Pan,
A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints, J. Global Optim., 69 (2017), 309-342.
doi: 10.1007/s10898-017-0521-1. |
[4] |
A. Ben-Tal and D. Den Hertog,
Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Math. Program., 143 (2014), 1-29.
doi: 10.1007/s10107-013-0710-8. |
[5] |
D. Bienstock and A. Michalka, Polynomial solvability of variants of the trust-region subproblem, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics, New York, 2014,380–390.
doi: 10.1137/1.9781611973402.28. |
[6] |
D. Bienstock,
A note on polynomial solvability of the CDT problem, SIAM J. Optim., 26 (2016), 488-498.
doi: 10.1137/15M1009871. |
[7] |
I. M. Bomze and M. L. Overton,
Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Math. Program., 151 (2015), 459-476.
doi: 10.1007/s10107-014-0836-3. |
[8] |
I. M. Bomze, V. Jeyakumar and G. Li,
Extended trust-region problems with one or two balls: Exact copositive and Lagrangian relaxations, J. Global Optim., 71 (2018), 551-569.
doi: 10.1007/s10898-018-0607-4. |
[9] |
S. Burer and K. M. Anstreicher,
Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23 (2013), 432-451.
doi: 10.1137/110826862. |
[10] |
M. R. Celis, J. E. Dennis and R. A. Tapia,
A trust region strategy for nonlinear equality constrained optimization, Numerical Optimization, 1984 (1985), 71-82.
|
[11] |
M. Grant and S. Boyed, CVX: Matlab Software for Disciplined Convex Programming, version 2.1, (2014). Available at: http://cvxr.com/cvx. Google Scholar |
[12] |
N. Ho-Nguyen and F. Kilinc-Karzan,
A second-order cone based approach for solving the trust-region subproblem and its variants, SIAM J. Optim., 27 (2017), 1485-1512.
doi: 10.1137/16M1065197. |
[13] |
R. Jiang and D. Li,
Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming, SIAM J. Optim., 26 (2016), 1649-1668.
doi: 10.1137/15M1023920. |
[14] |
V. Jeyakumar and G. Y. Li,
Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization, Math. Program., 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, Optim. Methods Softw., 15 (2001), 201-224.
doi: 10.1080/10556780108805819. |
[16] |
C. Lu, Z. Deng and Q. Jin,
An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints, J. Global Optim., 67 (2017), 475-493.
doi: 10.1007/s10898-016-0436-2. |
[17] |
C. Lu, Z. Deng, J. Zhou and X. Guo,
A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming, J. Global Optim., 73 (2019), 371-388.
doi: 10.1007/s10898-018-0726-y. |
[18] |
Z. Q. Luo, W. K. Ma, A. M. C. So, Y. Ye and S. Zhang,
Semidefinite relaxation of quadratic optimization problems, IEEE Signal Processing Magazine, 27 (2010), 20-34.
doi: 10.1109/MSP.2010.936019. |
[19] |
D. R. Morrison, S. H. Jacobson, J. J. Sauppe and E. C. Sewell,
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning, Discrete Optim., 19 (2016), 79-102.
doi: 10.1016/j.disopt.2016.01.005. |
[20] |
K. B. Petersen and M. S. Pedersen, The matrix cookbook, Technical University of Denmark, 7 (2008), 510pp. Google Scholar |
[21] |
N. Sagara and M. Fukushima,
A trust region method for nonsmooth convex optimization, J. Ind. Manag. Optim., 1 (2005), 171-180.
doi: 10.3934/jimo.2005.1.171. |
[22] |
Z. Sheng, G. Yuan, Z. Cui, X. Duan and X. Wang,
An adaptive trust region algorithm for large-residual nonsmooth least squares problems, J. Ind. Manag. Optim., 14 (2018), 707-718.
doi: 10.3934/jimo.2017070. |
[23] |
J. F. Sturm,
Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11 (1999), 625-653.
doi: 10.1080/10556789908805766. |
[24] |
J. F. Sturm and S. Zhang,
On cones of nonnegative quadratic functions, Math. Oper. Res., 28 (2003), 246-267.
doi: 10.1287/moor.28.2.246.14485. |
[25] |
Y. Tian, Z. Deng, J. Luo and Y. Li,
An intuitionistic fuzzy set based S3VM model for binary classification with mislabeled information, Fuzzy Optim. Decis. Mak., 17 (2018), 475-494.
doi: 10.1007/s10700-017-9282-z. |
[26] |
J. Zhou, S.-C. Fang and W. Xing,
Conic approximation to quadratic optimization with linear complementarity constraints, Comput. Optim. Appl., 66 (2017), 97-122.
doi: 10.1007/s10589-016-9855-8. |
[27] |
J. Zhou and Z. Xu,
A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints, Optim. Letters, 13 (2019), 1615-1630.
doi: 10.1007/s11590-018-1337-8. |
Case name | NSOCP_BB | ED | BFS [3] | |||||
nodes | CPU(sec) | nodes | CPU(sec) | nodes | CPU(sec) | |||
Data_lin_8_20 | 8 | 20 | 19 | 0.5483 | 19 | 2.0817 | 3471 | 3.56 |
Data_lin_10_11 | 10 | 11 | 5 | 0.3004 | 1 | 0.4391 | 155 | 0.238 |
Data_30of90 | 90 | 60 | 1 | 0.6515 | 1 | 0.7701 | 3 | 0.0341 |
Data3_100_10 | 100 | 10 | 11 | 6.5704 | 15 | 113.0250 | 93 | 0.29 |
Data3_100_15 | 100 | 15 | 11 | 7.3087 | 33 | 281.2684 | 6439 | 21.11 |
Data_200_10 | 200 | 10 | 2 | 9.6405 | 1 | 11.7755 | 255 | 0.96 |
Data_200_15 | 200 | 15 | 10 | 27.6235 | 8 | 81.9576 | 2047 | 7.93 |
Data3_300_10 | 300 | 10 | 22 | 31.8774 | 21 | 304.4157 | 287 | 3.75 |
Data_300_15 | 300 | 15 | 29 | 40.7551 | 22 | 426.1334 | 8959 | 128.03 |
Case name | NSOCP_BB | ED | BFS [3] | |||||
nodes | CPU(sec) | nodes | CPU(sec) | nodes | CPU(sec) | |||
Data_lin_8_20 | 8 | 20 | 19 | 0.5483 | 19 | 2.0817 | 3471 | 3.56 |
Data_lin_10_11 | 10 | 11 | 5 | 0.3004 | 1 | 0.4391 | 155 | 0.238 |
Data_30of90 | 90 | 60 | 1 | 0.6515 | 1 | 0.7701 | 3 | 0.0341 |
Data3_100_10 | 100 | 10 | 11 | 6.5704 | 15 | 113.0250 | 93 | 0.29 |
Data3_100_15 | 100 | 15 | 11 | 7.3087 | 33 | 281.2684 | 6439 | 21.11 |
Data_200_10 | 200 | 10 | 2 | 9.6405 | 1 | 11.7755 | 255 | 0.96 |
Data_200_15 | 200 | 15 | 10 | 27.6235 | 8 | 81.9576 | 2047 | 7.93 |
Data3_300_10 | 300 | 10 | 22 | 31.8774 | 21 | 304.4157 | 287 | 3.75 |
Data_300_15 | 300 | 15 | 29 | 40.7551 | 22 | 426.1334 | 8959 | 128.03 |
NSOCP_BB | ED | ||||
ave nodes | ave CPU(sec) | ave nodes | ave CPU(sec) | ||
100 | 4 | 4.0 | 3.4839 | 2.1 | 12.0705 |
150 | 4 | 3.8 | 5.6403 | 2.1 | 35.2577 |
200 | 4 | 4.4 | 9.9031 | 2.7 | 110.9290 |
250 | 4 | 3.5 | 15.3188 | 2.7 | 244.2893 |
300 | 4 | 4.1 | 23.9567 | 3.3 | 594.1906 |
350 | 4 | 6.8 | 44.4904 | 2.7 | 818.5657 |
400 | 4 | 4.7 | 56.4051 | 3.0 | 1670.5532 |
100 | 7 | 3.8 | 5.5790 | 2.9 | 19.0970 |
150 | 7 | 3.7 | 10.1234 | 2.7 | 49.3179 |
200 | 7 | 5.1 | 19.0962 | 3.0 | 141.8477 |
250 | 7 | 4.3 | 29.4947 | 2.6 | 254.5980 |
300 | 7 | 4.8 | 45.4383 | 2.7 | 554.2895 |
350 | 7 | 3.3 | 64.0829 | 2.9 | 1336.9454 |
400 | 7 | 4.0 | 91.8627 | 4.2 | 2551.6678 |
100 | 10 | 4.9 | 9.3095 | 3.1 | 22.9624 |
150 | 10 | 5.6 | 21.4694 | 2.3 | 53.6741 |
200 | 10 | 5.3 | 32.4885 | 3.3 | 169.8376 |
250 | 10 | 3.6 | 52.2134 | 3.0 | 317.0527 |
300 | 10 | 5.3 | 80.7183 | 2.7 | 554.8825 |
350 | 10 | 6.3 | 123.4788 | 2.4 | 884.3760 |
400 | 10 | 8.3 | 181.5320 | 2.8 | 1584.7842 |
100 | 20 | 7.9 | 93.9798 | 3.2 | 99.6843 |
150 | 20 | 6.9 | 86.4431 | 2.8 | 120.1224 |
200 | 20 | 5.6 | 140.9858 | 3.4 | 286.7472 |
250 | 20 | 6.3 | 218.4065 | 2.5 | 430.6950 |
300 | 20 | 6.2 | 326.3330 | 3.3 | 913.2317 |
350 | 20 | 9.5 | 497.2161 | 3.8 | 1747.1609 |
400 | 20 | 7.8 | 672.3612 | 3.0 | 2350.9039 |
NSOCP_BB | ED | ||||
ave nodes | ave CPU(sec) | ave nodes | ave CPU(sec) | ||
100 | 4 | 4.0 | 3.4839 | 2.1 | 12.0705 |
150 | 4 | 3.8 | 5.6403 | 2.1 | 35.2577 |
200 | 4 | 4.4 | 9.9031 | 2.7 | 110.9290 |
250 | 4 | 3.5 | 15.3188 | 2.7 | 244.2893 |
300 | 4 | 4.1 | 23.9567 | 3.3 | 594.1906 |
350 | 4 | 6.8 | 44.4904 | 2.7 | 818.5657 |
400 | 4 | 4.7 | 56.4051 | 3.0 | 1670.5532 |
100 | 7 | 3.8 | 5.5790 | 2.9 | 19.0970 |
150 | 7 | 3.7 | 10.1234 | 2.7 | 49.3179 |
200 | 7 | 5.1 | 19.0962 | 3.0 | 141.8477 |
250 | 7 | 4.3 | 29.4947 | 2.6 | 254.5980 |
300 | 7 | 4.8 | 45.4383 | 2.7 | 554.2895 |
350 | 7 | 3.3 | 64.0829 | 2.9 | 1336.9454 |
400 | 7 | 4.0 | 91.8627 | 4.2 | 2551.6678 |
100 | 10 | 4.9 | 9.3095 | 3.1 | 22.9624 |
150 | 10 | 5.6 | 21.4694 | 2.3 | 53.6741 |
200 | 10 | 5.3 | 32.4885 | 3.3 | 169.8376 |
250 | 10 | 3.6 | 52.2134 | 3.0 | 317.0527 |
300 | 10 | 5.3 | 80.7183 | 2.7 | 554.8825 |
350 | 10 | 6.3 | 123.4788 | 2.4 | 884.3760 |
400 | 10 | 8.3 | 181.5320 | 2.8 | 1584.7842 |
100 | 20 | 7.9 | 93.9798 | 3.2 | 99.6843 |
150 | 20 | 6.9 | 86.4431 | 2.8 | 120.1224 |
200 | 20 | 5.6 | 140.9858 | 3.4 | 286.7472 |
250 | 20 | 6.3 | 218.4065 | 2.5 | 430.6950 |
300 | 20 | 6.2 | 326.3330 | 3.3 | 913.2317 |
350 | 20 | 9.5 | 497.2161 | 3.8 | 1747.1609 |
400 | 20 | 7.8 | 672.3612 | 3.0 | 2350.9039 |
NSOCP1_BB | NSOCP_BB | ACS | ||||||
ave nodes | ave CPU(sec) | ave nodes | ave CPU(sec) | ave nodes | ave CPU(sec) | |||
3 | 6 | 0.1 | 6.7 | 0.2681 | 10.1 | 0.3792 | 12.2 | 2.4176 |
3 | 6 | 1 | 10.7 | 0.3737 | 13.0 | 0.4631 | 15.3 | 3.1461 |
3 | 10 | 0.1 | 9.1 | 0.3344 | 8.3 | 0.3251 | 13.2 | 2.6044 |
3 | 10 | 1 | 13.2 | 0.4549 | 13.5 | 0.4847 | 17.3 | 2.9758 |
3 | 13 | 0.1 | 7.5 | 0.2794 | 7.6 | 0.3015 | 15.5 | 3.1541 |
3 | 13 | 1 | 22 | 0.6727 | 28.3 | 0.8975 | 18.1 | 3.2863 |
4 | 6 | 0.1 | 13.6 | 0.4461 | 16.4 | 0.5690 | 12.6 | 2.7129 |
4 | 6 | 1 | 22.9 | 0.6834 | 23.5 | 0.7513 | 13.9 | 2.8062 |
4 | 10 | 0.1 | 15.5 | 0.5079 | 17.4 | 0.6016 | 24.1 | 6.3445 |
4 | 10 | 1 | 21.1 | 0.6255 | 27.3 | 0.8490 | 25.3 | 5.1821 |
4 | 13 | 0.1 | 13.4 | 0.4803 | 12.7 | 0.4958 | 17.1 | 4.1885 |
4 | 13 | 1 | 25.1 | 0.8896 | 32.8 | 1.1869 | 25.3 | 7.1386 |
5 | 6 | 0.1 | 37.1 | 1.0944 | 44.4 | 1.4771 | 22.6 | 5.2888 |
5 | 6 | 1 | 33.7 | 0.8846 | 31.8 | 0.9472 | 42.2 | 10.4813 |
5 | 10 | 0.1 | 20.5 | 0.6051 | 19.3 | 0.6300 | 26.3 | 7.5633 |
5 | 10 | 1 | 25.5 | 0.7560 | 23.9 | 0.7938 | 20.5 | 5.4657 |
5 | 13 | 0.1 | 16.1 | 0.6268 | 15.8 | 0.6625 | 24.2 | 6.8016 |
5 | 13 | 1 | 36.0 | 1.1874 | 35.2 | 1.2666 | 26.6 | 8.3991 |
6 | 6 | 0.1 | 49.6 | 1.6442 | 48.7 | 1.8016 | 24.6 | 4.5381 |
6 | 6 | 1 | 9.6 | 0.4971 | 50.3 | 1.9330 | 236.8 | 23.6982 |
6 | 10 | 0.1 | 25.4 | 0.9164 | 45.9 | 1.6842 | 57.0 | 13.6420 |
6 | 10 | 1 | 48.3 | 1.5468 | 48.3 | 1.7473 | 63.8 | 16.7940 |
7 | 6 | 0.1 | 99.0 | 2.8795 | 166.6 | 5.7123 | 189.2 | 46.6260 |
7 | 6 | 1 | 53.6 | 1.6242 | 93.6 | 3.1935 | 174.2 | 53.2129 |
7 | 10 | 0.1 | 76.1 | 2.3453 | 79.3 | 2.8579 | 78.7 | 20.8093 |
7 | 10 | 1 | 342.6 | 9.6811 | 527.2 | 17.8453 | 58.8 | 14.7023 |
8 | 6 | 0.1 | 186.2 | 5.2471 | 203.3 | 7.3216 | 602.2 | 72.8406 |
8 | 6 | 1 | 60.9 | 1.8836 | 62.4 | 2.3540 | 202.9 | 47.0604 |
8 | 10 | 0.1 | 51.5 | 1.7470 | 48.7 | 1.9087 | 17.4 | 3.5242 |
8 | 10 | 1 | 117.0 | 3.4416 | 100.1 | 3.6475 | 62.0 | 16.2960 |
NSOCP1_BB | NSOCP_BB | ACS | ||||||
ave nodes | ave CPU(sec) | ave nodes | ave CPU(sec) | ave nodes | ave CPU(sec) | |||
3 | 6 | 0.1 | 6.7 | 0.2681 | 10.1 | 0.3792 | 12.2 | 2.4176 |
3 | 6 | 1 | 10.7 | 0.3737 | 13.0 | 0.4631 | 15.3 | 3.1461 |
3 | 10 | 0.1 | 9.1 | 0.3344 | 8.3 | 0.3251 | 13.2 | 2.6044 |
3 | 10 | 1 | 13.2 | 0.4549 | 13.5 | 0.4847 | 17.3 | 2.9758 |
3 | 13 | 0.1 | 7.5 | 0.2794 | 7.6 | 0.3015 | 15.5 | 3.1541 |
3 | 13 | 1 | 22 | 0.6727 | 28.3 | 0.8975 | 18.1 | 3.2863 |
4 | 6 | 0.1 | 13.6 | 0.4461 | 16.4 | 0.5690 | 12.6 | 2.7129 |
4 | 6 | 1 | 22.9 | 0.6834 | 23.5 | 0.7513 | 13.9 | 2.8062 |
4 | 10 | 0.1 | 15.5 | 0.5079 | 17.4 | 0.6016 | 24.1 | 6.3445 |
4 | 10 | 1 | 21.1 | 0.6255 | 27.3 | 0.8490 | 25.3 | 5.1821 |
4 | 13 | 0.1 | 13.4 | 0.4803 | 12.7 | 0.4958 | 17.1 | 4.1885 |
4 | 13 | 1 | 25.1 | 0.8896 | 32.8 | 1.1869 | 25.3 | 7.1386 |
5 | 6 | 0.1 | 37.1 | 1.0944 | 44.4 | 1.4771 | 22.6 | 5.2888 |
5 | 6 | 1 | 33.7 | 0.8846 | 31.8 | 0.9472 | 42.2 | 10.4813 |
5 | 10 | 0.1 | 20.5 | 0.6051 | 19.3 | 0.6300 | 26.3 | 7.5633 |
5 | 10 | 1 | 25.5 | 0.7560 | 23.9 | 0.7938 | 20.5 | 5.4657 |
5 | 13 | 0.1 | 16.1 | 0.6268 | 15.8 | 0.6625 | 24.2 | 6.8016 |
5 | 13 | 1 | 36.0 | 1.1874 | 35.2 | 1.2666 | 26.6 | 8.3991 |
6 | 6 | 0.1 | 49.6 | 1.6442 | 48.7 | 1.8016 | 24.6 | 4.5381 |
6 | 6 | 1 | 9.6 | 0.4971 | 50.3 | 1.9330 | 236.8 | 23.6982 |
6 | 10 | 0.1 | 25.4 | 0.9164 | 45.9 | 1.6842 | 57.0 | 13.6420 |
6 | 10 | 1 | 48.3 | 1.5468 | 48.3 | 1.7473 | 63.8 | 16.7940 |
7 | 6 | 0.1 | 99.0 | 2.8795 | 166.6 | 5.7123 | 189.2 | 46.6260 |
7 | 6 | 1 | 53.6 | 1.6242 | 93.6 | 3.1935 | 174.2 | 53.2129 |
7 | 10 | 0.1 | 76.1 | 2.3453 | 79.3 | 2.8579 | 78.7 | 20.8093 |
7 | 10 | 1 | 342.6 | 9.6811 | 527.2 | 17.8453 | 58.8 | 14.7023 |
8 | 6 | 0.1 | 186.2 | 5.2471 | 203.3 | 7.3216 | 602.2 | 72.8406 |
8 | 6 | 1 | 60.9 | 1.8836 | 62.4 | 2.3540 | 202.9 | 47.0604 |
8 | 10 | 0.1 | 51.5 | 1.7470 | 48.7 | 1.9087 | 17.4 | 3.5242 |
8 | 10 | 1 | 117.0 | 3.4416 | 100.1 | 3.6475 | 62.0 | 16.2960 |
[1] |
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 |
[2] |
Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020162 |
[3] |
Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020340 |
[4] |
Yi-Ming Tai, Zhengyang Zhang. Relaxation oscillations in a spruce-budworm interaction model with Holling's type II functional response. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021027 |
[5] |
Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020054 |
[6] |
Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020 doi: 10.3934/jdg.2021001 |
[7] |
Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021012 |
[8] |
Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136 |
[9] |
Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021013 |
[10] |
Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020377 |
[11] |
Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020164 |
[12] |
Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020 doi: 10.3934/eect.2020103 |
[13] |
Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089 |
[14] |
Elimhan N. Mahmudov. Infimal convolution and duality in convex optimal control problems with second order evolution differential inclusions. Evolution Equations & Control Theory, 2021, 10 (1) : 37-59. doi: 10.3934/eect.2020051 |
[15] |
Ying Lv, Yan-Fang Xue, Chun-Lei Tang. Ground state homoclinic orbits for a class of asymptotically periodic second-order Hamiltonian systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1627-1652. doi: 10.3934/dcdsb.2020176 |
[16] |
Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 |
[17] |
Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 |
[18] |
Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134 |
[19] |
Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272 |
[20] |
Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020168 |
2019 Impact Factor: 1.366
Tools
Article outline
Figures and Tables
[Back to Top]