×

zbMATH — the first resource for mathematics

A second-order cone based approach for solving the trust-region subproblem and its variants. (English) Zbl 1370.90170

MSC:
90C20 Quadratic programming
90C25 Convex programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
Software:
HSL-VF05; GQTPAR
PDF BibTeX Cite
Full Text: DOI arXiv
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] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5 (1995), pp. 13–51, . · Zbl 0833.90087
[3] A. Beck, Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming, J. Optim. Theory Appl., 142 (2009), pp. 1–29, . · Zbl 1188.90190
[4] A. Beck and Y. C. Eldar, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim., 17 (2006), pp. 844–860, . · Zbl 1128.90044
[5] A. Ben-Tal and D. den Hertog, Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Math. Program., 143 (2014), pp. 1–29, . · Zbl 1295.90036
[6] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust Optimization, Princeton Ser. Appl. Math., Princeton University Press, Princeton, NJ, 2009. · Zbl 1221.90001
[7] A. Ben-Tal and A. Nemirovski, Lectures on modern convex optimization, Tech. report, August 2015, .
[8] A. Ben-Tal and M. Teboulle, Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program., 72 (1996), pp. 51–63, . · Zbl 0851.90087
[9] D. Bertsimas, D. B. Brown, and C. Caramanis, Theory and applications of robust optimization, SIAM Rev., 53 (2011), pp. 464–501, . · Zbl 1233.90259
[10] D. Bienstock, A note on polynomial solvability of the CDT problem, SIAM J. Optim., 26 (2016), pp. 488–498, . · Zbl 1382.90083
[11] D. Bienstock and A. Michalka, Cutting-planes for optimization of convex functions over nonconvex sets, SIAM J. Optim., 24 (2014), pp. 643–677, . · Zbl 1334.90130
[12] D. Bienstock and A. Michalka, Polynomial solvability of variants of the trust-region subproblem, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2014, pp. 380–390, . · Zbl 1334.90130
[13] C. Buchheim, M. De Santis, L. Palagi, and M. Piacentini, An exact algorithm for nonconvex quadratic integer minimization using ellipsoidal relaxations, SIAM J. Optim., 23 (2013), pp. 1867–1889, . · Zbl 1282.90104
[14] S. Burer, A gentle, geometric introduction to copositive optimization, Math. Program., 151 (2015), pp. 89–116. · Zbl 1327.90162
[15] 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
[16] S. Burer and F. K\il\inç-Karzan, How to convexify the intersection of a second order cone and a nonconvex quadratic, Math. Program., 162 (2017), pp. 393–429, . · Zbl 1358.90095
[17] S. Burer and B. Yang, The trust region subproblem with non-intersecting linear constraints, Math. Program., 149 (2015), pp. 253–264, . · Zbl 1308.90121
[18] M. Celis, J. Dennis, and R. Tapia, A trust region strategy for nonlinear equality constrained optimization, in Numerical Optimization 1984: Proceedings of the SIAM Conference on Numerical Optimization, SIAM Philadelphia, 1985, pp. 71–82. · Zbl 0566.65048
[19] A. R. Conn, N. I. M. Gould, and P. L. Toint, Trust Region Methods, MPS/SIAM Ser. Optim., SIAM, Philadelphia, 2000, .
[20] L. L. Dines, On the mapping of quadratic forms, Bull. Amer. Math. Soc., 47 (1941), pp. 494–498. · Zbl 0027.15004
[21] J. B. Erway and P. E. Gill, A subspace minimization method for the trust-region step, SIAM J. Optim., 20 (2010), pp. 1439–1461, . · Zbl 1195.49042
[22] J. B. Erway, P. E. Gill, and J. D. Griffin, Iterative methods for finding a trust-region step, SIAM J. Optim., 20 (2009), pp. 1110–1131, . · Zbl 1189.49049
[23] C. Fortin and H. Wolkowicz, The trust region subproblem and semidefinite programming, Optim. Methods Softw., 19 (2004), pp. 41–67, . · Zbl 1070.65041
[24] A. L. Fradkov and V. A. Yakubovich, The S-procedure and duality relations in nonconvex problems of quadratic programming, Vestn. LGU, Ser. Mat., Mekh., Astron, 6 (1979), pp. 101–109. · Zbl 0423.49016
[25] W. Gander, G. H. Golub, and U. von Matt, A constrained eigenvalue problem, Linear Algebra Appl., 114/115 (1989), pp. 815–839, . · Zbl 0666.15006
[26] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins Stud. Math. Sci., The Johns Hopkins University Press, Baltimore, 1996.
[27] 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
[28] N. I. M. Gould, D. P. Robinson, and H. S. Thorne, On solving trust-region and other regularized subproblems in optimization, Math. Prog. Comp., 2 (2010), pp. 21–57, . · Zbl 1193.65098
[29] E. Hazan and T. Koren, A linear-time algorithm for trust region problems, Math. Program., 158 (2016), pp. 363–381, . · Zbl 1346.90654
[30] N. Ho-Nguyen and F. K\il\inç-Karzan, Online first-order framework for robust convex optimization, Tech. report, July 2016, .
[31] N. Ho-Nguyen and F. K\il\inç-Karzan, A second-order cone based approach for solving the trust region subproblem and its variants, Tech. report, March 10, 2016, , . · Zbl 1370.90170
[32] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, New York, 2013. · Zbl 1267.15001
[33] 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), pp. 171–206, . · Zbl 1297.90105
[34] J. Kuczyński and H. Wozniakowski, Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1094–1122, . · Zbl 0759.65016
[35] M. Locatelli, Exactness conditions for an sdp relaxation of the extended trust region problem, Optim. Lett., 10 (2016), pp. 1141–1151, . · Zbl 1353.90102
[36] S. Modaresi and J. Vielma, Convex hull of two quadratic or a conic quadratic and a quadratic inequality, Math. Program., 2017, preprint, . · Zbl 1393.90074
[37] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Comput., 4 (1983), pp. 553–572, . · Zbl 0551.65042
[38] Y. Nesterov, A method for solving a convex programming problem with rate of convergence \(O(1/k^2)\), Soviet Math. Dokl., 27 (1983), pp. 372–376. · Zbl 0535.90071
[39] Y. Nesterov and A. Nemirovski, Interior-Point Polynomial Algorithms in Convex Programming, Studies in Applied and Numerical Mathematics, SIAM, Philadelphia, 1994, .
[40] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer Ser. Oper. Res. Financ. Eng., Springer, New York, 2006. · Zbl 1104.65059
[41] I. Pólik and T. Terlaky, A survey of the s-lemma, SIAM Rev., 49 (2007), pp. 371–418, .
[42] T. K. Pong and H. Wolkowicz, The generalized trust region subproblem, Comput. Optim. Appl., 58 (2014), pp. 273–322, . · Zbl 1329.90100
[43] F. Rendl and H. Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Programming, 77 (1997), pp. 273–299, . · Zbl 0888.90137
[44] M. Rojas, S. A. Santos, and D. C. Sorensen, A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11 (2001), pp. 611–646, . · Zbl 0994.65067
[45] M. Salahi and S. Fallahi, Trust region subproblem with an additional linear inequality constraint, Optim. Lett., 10 (2016), pp. 821–832, . · Zbl 1367.90077
[46] M. Salahi and A. Taati, A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality, Comp. Appl. Math., 2016, preprint, . · Zbl 1393.90097
[47] 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
[48] D. C. Sorensen, Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim., 7 (1997), pp. 141–161, . · Zbl 0878.65044
[49] R. J. Stern and H. Wolkowicz, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. Optim., 5 (1995), pp. 286–313, . · Zbl 0846.49017
[50] J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Math. Oper. Res., 28 (2003), pp. 246–267, . · Zbl 1082.90086
[51] J. Wang and Y. Xia, A linear-time algorithm for the trust region subproblem based on hidden convexity, Optim. Lett., preprint, . · Zbl 1410.90145
[52] B. Yang, K. Anstreicher, and S. Burer, Quadratic programs with hollows, Tech. report, January 2016, . · Zbl 1401.90147
[53] Y. Ye and S. Zhang, New results on quadratic minimization, SIAM J. Optim., 14 (2003), pp. 245–267, . · Zbl 1043.90064
[54] H. Zhang, A. R. Conn, and K. Scheinberg, A derivative-free algorithm for least-squares minimization, SIAM J. Optim., 20 (2010), pp. 3555–3576, . · Zbl 1213.65091
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.