×

A block Lanczos method for the extended trust-region subproblem. (English) Zbl 1412.90102

Summary: We present a block Lanczos method for solving the large-scale extended trust-region (ETR) subproblem. During the algorithm, the original ETR subproblem is projected to a small-scale one, and then the active-set method is employed to solve this small-scale ETR subproblem to get a solution that can be used to derive an approximate solution of the original ETR subproblem. Theoretical analysis of error bounds for the optimal value, the optimal solution, and the multipliers is also proposed. We compare the block Lanczos method with the TOMLAB solver. Numerical experiments demonstrate that the block Lanczos method is effective and can achieve high accuracy for large-scale ETR subproblems.

MSC:

90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Adachi, S. Iwata, Y. Nakatsukasa, and A. Takeda, {\it Solving the trust-region subproblem by a generalized eigenvalue problem}, SIAM J. Optim., 27 (2017), pp. 269-291. · Zbl 1359.49009
[2] W. Ai and S. Zhang, {\it Strong duality for the CDT subproblem: A necessary and sufficient condition}, SIAM J. Optim., 19 (2009), pp. 1735-1756. · Zbl 1187.90290
[3] J. Baglama, {\it Dealing with linear dependence during the iterations of the restarted block Lanczos methods}, Numer. Algorithms, 25 (2000), pp. 23-36. · Zbl 1012.65032
[4] H. H. Bauschke and J. M. Borwein, {\it On projection algorithms for solving convex feasibility problems}, SIAM Rev., 38 (1996), pp. 367-426. · Zbl 0865.47039
[5] H. H. Bauschke, J. M. Borwein, and W. Li, {\it Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization}, Math. Program., 86 (1999), pp. 135-160. · Zbl 0998.90088
[6] A. Beck and Y. C. Eldar, {\it Strong duality in nonconvex quadratic optimization with two quadratic constraints}, SIAM J. Optim., 17 (2006), pp. 844-860. · Zbl 1128.90044
[7] A. Ben-Tal, L. E. Ghaoui, and A. Nemirovski, {\it Robust Optimization}, Princeton University Press, Princeton, NJ, 2009. · Zbl 1221.90001
[8] D. P. Bertsekas, {\it Constrained Optimization and Lagrange Multiplier Methods}, Academic Press, New York, 1982. · Zbl 0572.90067
[9] D. Bertsimas, D. B. Brown, and C. Caramanis, {\it Theory and applications of robust optimization}, SIAM Rev., 53 (2011), pp. 464-501. · Zbl 1233.90259
[10] D. Bienstock and A. Michalka, {\it Polynomial solvability of variants of the trust-region subproblem}, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2014, pp. 380-390. · Zbl 1428.90109
[11] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, {\it Distributed optimization and statistical learning via the alternating direction method of multipliers}, Found. Trends Mach. Learning, 3 (2011), pp. 1-122. · Zbl 1229.90122
[12] S. Burer and K. M. Anstreicher, {\it Second-order-cone constraints for extended trust-region subproblems}, SIAM J. Optim., 23 (2013), pp. 432-451. · Zbl 1298.90062
[13] S. Burer and B. Yang, {\it The trust region subproblem with non-intersecting linear constraints}, Math. Program., 149 (2015), pp. 253-264. · Zbl 1308.90121
[14] J. V. Burke and S. Deng, {\it Weak sharp minima revisited, part II: Application to linear regularity and error bounds}, Math. Program., 104 (2005), pp. 235-261. · Zbl 1124.90349
[15] R. H. Byrd, R. B. Schnabel, and G. A. Shultz, {\it Approximate solution of the trust region problem by minimization over two-dimensional subspaces}, Math. Program., 40 (1988), pp. 247-263. · Zbl 0652.90082
[16] X. Cai, D. Han, and X. Yuan, {\it The direct extension of ADMM for three-block separable convex minimization models is convergent when one function is strongly convex}, Comput. Optim. Appl., 66 (2017), pp. 39-73. · Zbl 1372.90079
[17] A. R. Conn, N. I. M. Gould, and P. L. Toint, {\it Trust-Region Methods}, SIAM, Philadelphia, PA, 2000. · Zbl 0958.65071
[18] T. Davis and Y. Hu, {\it The University of Florida sparse matrix collection}, ACM Trans. Math. Software, 38 (2011), pp. 1-25. · Zbl 1365.65123
[19] J. B. Erway and P. E. Gill, {\it A subspace minimization method for the trust-region step}, SIAM J. Optim., 20 (2010), pp. 1439-1461. · Zbl 1195.49042
[20] N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint, {\it Solving the trust-region subproblem using the Lanczos method}, SIAM J. Optim., 9 (1999), pp. 504-525. · Zbl 1047.90510
[21] A. Greenbaum, {\it Iterative Methods for Solving Linear Systems}, SIAM, Philadelphia, PA, 1997. · Zbl 0883.65022
[22] K. Guo, D. Han, Z. W. Wang, and T. Wu, {\it Convergence of ADMM for multi-block nonconvex separable optimization models}, Front. Math. China, 12 (2017), pp. 1139-1162. · Zbl 1386.90114
[23] N. Ho-Nguyen and F. Kilinc-Karzan, {\it A second-order cone based approach for solving the trust-region subproblem and its variants}, SIAM J. Optim., 27 (2017), pp. 1485-1512. · Zbl 1370.90170
[24] K. Holmstrom, A. O. Goran, and M. M. Edvall, {\it User’s Guide for TOMLAB/SOL}1, TOMLAB Optimization Inc., San Diego, CA, 2008.
[25] V. Jeyakumar and G. Y. Li, {\it Strong duality in robust convex programming: Complete characterizations}, SIAM J. Optim., 20 (2010), pp. 3384-3407. · Zbl 1228.90075
[26] V. Jeyakumar and G. Y. Li, {\it Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization}, Math. Program., 147 (2014), pp. 171-206. · Zbl 1297.90105
[27] S. Lu and S. M. Robinson, {\it Normal fans of polyhedral convex sets: Structures and connections}, Set-Valued Anal., 16 (2008), pp. 281-305. · Zbl 1144.52008
[28] K. F. Ng and W. H. Yang, {\it Regularities and their relations to error bounds}, Math. Program., 99 (2004), pp. 521-538. · Zbl 1077.90050
[29] J. Nocedal and S. J. Writht, {\it Numerical Optimization}, 2nd ed., Springer, Berlin, 2006.
[30] T. K. Pong and H. Wolkowicz, {\it The generalized trust region subproblem}, Comput. Optim. Appl., 58 (2014), pp. 273-322. · Zbl 1329.90100
[31] F. Rendl and H. Wolkowicz, {\it A semidefinite framework for trust region subproblems with applications to large scale minimization}, Math. Program., 77 (1997), pp. 273-299. · Zbl 0888.90137
[32] A. Ruhe, {\it Implementation aspects of band Lanczos algorithms for computation of eigenvalues of large sparse symmetric matrices}, Math. Comp., 33 (1979), pp. 680-687. · Zbl 0443.65022
[33] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, Philadelphia, PA, 2003. · Zbl 1031.65046
[34] M. Salahi, A. Taati, and H. Wolkowicz, {\it Local nonglobal minima for solving large-scale extended trust-region subproblems}, Comput. Optim. Appl., 66 (2017), pp. 223-244. · Zbl 1391.90496
[35] J. F. Sturm and S. Zhang, {\it On cones of nonnegative quadratic functions}, Math. Oper. Res., 28 (2003), pp. 246-267. · Zbl 1082.90086
[36] Z. Wang and Y. Yuan, {\it A subspace implementation of quasi-Newton trust region methods for unconstrained optimization}, Numer. Math., 104 (2006), pp. 241-269. · Zbl 1101.65066
[37] Y. Ye and S. Zhang, {\it New results on quadratic minimization}, SIAM J. Optim., 14 (2003), pp. 245-267. · Zbl 1043.90064
[38] J. Yuan, M. Wang, W. Ai, and T. Shuai, {\it A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts}, Sci. China Math., 59 (2016), pp. 1127-1140. · Zbl 1344.49040
[39] Y. Yuan, {\it A review on subspace methods for nonlinear optimization}, in Proceedings of the International Congress of Mathematicians 2014, Vol. IV, Kyung Moon, Seoul, 2014, pp. 807-827; available at . · Zbl 1388.65040
[40] Y. Yuan, {\it Recent advances in trust region algorithms}, Math. Program., 151 (2015), pp. 249-281. · Zbl 1317.65141
[41] L. Zhang, C. Shen, and R. Li, {\it On the generalized Lanczos trust-region method}, SIAM J. Optim., 27 (2017), pp. 2110-2142. · Zbl 1380.90210
[42] X. Y. Zheng and K. F. Ng, {\it Metric regularity and constraint qualifications for convex inequalities on Banach spaces}, SIAM J. Optim., 14 (2003), pp. 757-772. · Zbl 1079.90103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.