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

Jing Zhou; Cheng Lu; Ye Tian; Xiaoying Tang

doi:10.3934/jimo.2019104

Previous Article
A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery
JIMO Home
This Issue
Next Article
Independent sales or bundling? Decisions under different market-dominant powers

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 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, 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]
Case name	$ n $	$ s $	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]
Case name	$ n $	$ s $	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
$ n $	$ m $	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
$ n $	$ m $	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
$ n $	$ m+p $	$ \delta $	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
$ n $	$ m+p $	$ \delta $	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]	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
[3]	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
[4]	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
[5]	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
[6]	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
[7]	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
[8]	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
[9]	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
[10]	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
[11]	Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019044
[12]	Jinling Zhao, Wei Chen, Su Zhang. Immediate schedule adjustment and semidefinite relaxation. Journal of Industrial & Management Optimization, 2019, 15 (2) : 633-645. doi: 10.3934/jimo.2018062
[13]	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
[14]	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
[15]	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
[16]	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
[17]	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
[18]	Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033
[19]	Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041
[20]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

2018 Impact Factor: 1.025

Tools

Metrics

Tools

Article outline

Figures and Tables

2018 Impact Factor: 1.025

Tools

Figures and Tables

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors