-
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. |
[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. |
[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. |
[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. |
[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] |
Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 |
[2] |
Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030 |
[3] |
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 and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111 |
[4] |
Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223 |
[5] |
Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and 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 and Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965 |
[7] |
Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283 |
[8] |
Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117 |
[9] |
Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial and Management Optimization, 2019, 15 (2) : 893-908. doi: 10.3934/jimo.2018076 |
[10] |
Narges Torabi Golsefid, Maziar Salahi. Second order cone programming formulation of the fixed cost allocation in DEA based on Nash bargaining game. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021032 |
[11] |
Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117 |
[12] |
Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044 |
[13] |
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 and Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703 |
[14] |
Jinling Zhao, Wei Chen, Su Zhang. Immediate schedule adjustment and semidefinite relaxation. Journal of Industrial and Management Optimization, 2019, 15 (2) : 633-645. doi: 10.3934/jimo.2018062 |
[15] |
Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543 |
[16] |
Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881 |
[17] |
Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919 |
[18] |
Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial and Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321 |
[19] |
Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial and Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697 |
[20] |
Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]