×

zbMATH — the first resource for mathematics

Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem. (English) Zbl 07236496
MSC:
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
Software:
GQTPAR; HSL-VF05
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Adachi, S. Iwata, Y. Nakatsukasa, and A. Takeda, Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM J. Optim., 27 (2017), pp. 269-291. · Zbl 1359.49009
[2] A. Beck and D. Pan, A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints, J. Global Optim., 69 (2017), pp. 309-342. · Zbl 1382.90082
[3] D. Bienstock and A. Michalka, Polynomial solvability of variants of the trust-region subproblem, in Proceedings of SODA, 2014, pp. 380-390. · Zbl 1428.90109
[4] I. M. Bomze and M. L. Overton, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Math. Program. Ser. B., 151 (2015), pp. 459-476. · Zbl 1328.90095
[5] S. Burer and K. M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23 (2013), pp. 432-451. · Zbl 1298.90062
[6] S. Burer and B. Yang, The trust-region subproblem with non-intersecting linear constraints, Math. Program., 149 (2015), pp. 253-264. · Zbl 1308.90121
[7] M. R. Celis, J. E. Dennis, and R. A. Tapia, A trust region strategy for nonlinear equality constrained optimization, in Proceedings of the SIAM Conference on Numerical Optimization 1984, SIAM, Philadelphia, 1985, pp. 71-82. · Zbl 0566.65048
[8] A. R. Conn, N. I. M. Gould, and P. L. Toint, Trust-Region Methods, MOS-SIAM Ser. Optim., SIAM, Philadelphia, 2000.
[9] Z. B. Deng, C. Lu, Y. Tian, and J. Luo, Globally solving extended trust region subproblems with two intersecting cuts, Optim. Lett., 2019, https://doi.org/10.1007/s11590-019-01484-z.
[10] R. Fletcher, Practical Methods of Optimization, 2nd ed., John Wiley, New York, 1987. · Zbl 0905.65002
[11] D. M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. and Stat. Comput. 2 (2012), pp. 186-197. · Zbl 0467.65027
[12] G. H. Golub and C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, MD, 1989. · Zbl 0733.65016
[13] N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9 (1999), pp. 504-525. · Zbl 1047.90510
[14] E. Hazan and T. Koren, A linear-time algorithm for trust region problems, Math. Program., 158 (2016), pp. 363-381. · Zbl 1346.90654
[15] 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), pp. 1485-1512. · Zbl 1370.90170
[16] Y. Hsia and R. L. Sheu, Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity, https://arxiv.org/abs/1312.1398, 2013.
[17] D. G. Luenberger, Linear and Nonlinear Programming, 2nd ed., Addison-Wesley, Reading, MA, 1984. · Zbl 0571.90051
[18] J. M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4 (1994), pp. 159-176. · Zbl 0801.65057
[19] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM J. Sci. and Stat. Comput., 4 (1983), pp. 553-572. · Zbl 0551.65042
[20] K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39 (1987), pp. 117-129. · Zbl 0637.90078
[21] P. M. Pardalos and G. Schnitger, Checking local optimality in constrained quadratic programming is NP-hard, Oper. Res. Lett., 7 (1988), pp. 33-45. · Zbl 0644.90067
[22] P. M. Pardalos and S. A. Vavasis, Open questions in complexity theory for numerical optimization, Math. Program., 57 (1992), pp. 337-339. · Zbl 0784.90102
[23] K. B. Petersen and M. S. Pedersen, The Matrix Cookbook, Version 20121115, Technical report, Technical University of Denmark, Kongens Lyngby, Denmark, 2012.
[24] A. H. Phan, M. Yamagishi, D. Mandic, and A. Cichocki, Quadratic programming over ellipsoids with applications to constrained linear regression and tensor decomposition, Neural Comput. Appl., 32 (2020), pp. 7097-7120.
[25] F. Rendl and H. Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program. Ser. B., 77 (1997), pp. 273-299. · Zbl 0888.90137
[26] M. Salahi, A. Taati, and H. Wolkowicz, Local nonglobal minima for solving large-scale extended trust-region subproblems, Comput Optim Appl., 66 (2017), pp. 223-244. · Zbl 1391.90496
[27] D. C. Sorensen, Newton’s method with a model trust region modification, SIAM J. Numer. Anal., 19 (1982), pp. 409-426. · Zbl 0483.65039
[28] J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Math. Oper. Res., 28 (2003), pp. 246-267. · Zbl 1082.90086
[29] J. L. Wang and Y. Xia, A linear-time algorithm for the trust region subproblem based on hidden convexity, Optim. Lett., 11 (2017), pp. 1639-1646. · Zbl 1410.90145
[30] Y. Xia, A survey of hidden convex optimization, J. Oper. Res. Soc. China., 8 (2020), pp. 1-28. · Zbl 1449.90294
[31] Y. Ye, A new complexity result on minimization of a quadratic function with a sphere constraint, in Recent Advances in Global Optimization, C. Floudas and P. Pardalos, eds., Princeton University Press, Princeton, NJ, 1992.
[32] Y. Ye and S. Zhang, New results on quadratic minimization, SIAM J. Optim., 14 (2003), pp. 245-267. · Zbl 1043.90064
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.