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

Article Contents

2021, Volume 17, Issue 1: 151-168. Doi: 10.3934/jimo.2019104

This issue Previous Article Pricing power exchange options with hawkes jump diffusion processes Next Article Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods

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

^* Corresponding author: Ye Tian
^* Corresponding author: Ye Tian

Received: June 30, 2018

Revised: April 30, 2019

Early access: September 2019

Published: January 2021

Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

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:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.