American Institute of Mathematical Sciences

Advanced
January  2021, 17(1): 151-168. doi: 10.3934/jimo.2019104

A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem

Jing Zhou 1, , Cheng Lu 2, , Ye Tian 3,, and  Xiaoying Tang 4,

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

* Corresponding author: Ye Tian

Received  July 2018 Revised  May 2019 Published  January 2021 Early access  September 2019

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.

Keywords: Second order cone programming relaxation, semidefinite programming relaxation, branch-and-bound algorithm, trust-region problem, simultaneous diagonalization.
Mathematics Subject Classification: Primary: 90C20, 90C26, 90C57.
Citation: Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
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.  Google Scholar

[2]

A. I. Barvinok, Feasibility testing for systems of real quadratic equations, Discrete Comput. Geom., 10 (1993), 1-13.  doi: 10.1007/BF02573959.  Google Scholar

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

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

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

[6]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[2]

A. I. Barvinok, Feasibility testing for systems of real quadratic equations, Discrete Comput. Geom., 10 (1993), 1-13.  doi: 10.1007/BF02573959.  Google Scholar

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

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

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

[6]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Table 1.  The trust-region problem with linear inequality constraints
Case name $ n $ $ s $ 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
Table Options

Download as excel

Case name $ n $ $ s $ 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
Table 2.  The generalized Celis-Dennis-Tapia problem
$ n $ $ m $ 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
Table Options

Download as excel

$ n $ $ m $ 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
Table 3.  The subproblem of Sparse Source localization
$ n $ $ m+p $ $ \delta $ 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
Table Options

Download as excel

$ n $ $ m+p $ $ \delta $ 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 & 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 & Management Optimization, 2021  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 & 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 & 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 & 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]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033

2020 Impact Factor: 1.801

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy