×

A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality. (English) Zbl 1393.90097

Summary: In this paper, we study the extended trust region subproblem (eTRS) in which the trust region intersects the Euclidean ball with a single linear inequality constraint. By reformulating the Lagrangian dual of eTRS as a two-parameter linear eigenvalue problem, we state a necessary and sufficient condition for its strong duality in terms of an optimal solution of a linearly constrained bivariate concave maximization problem. This results in an efficient algorithm for solving eTRS of large size whenever the strong duality is detected. Finally, some numerical experiments are given to show the effectiveness of the proposed method.

MSC:

90C26 Nonconvex programming, global optimization
90C22 Semidefinite programming
65F15 Numerical computation of eigenvalues and eigenvectors of matrices

Software:

HSL-VF05
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ai, W; Zhang, S, Strong duality for the CDT subproblem: a necessary and sufficient condition, SIAM J Optim, 19, 1735-1756, (2009) · Zbl 1187.90290 · doi:10.1137/07070601X
[2] Beck, A; Eldar, YC, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J Optim, 17, 844-860, (2006) · Zbl 1128.90044 · doi:10.1137/050644471
[3] Ben-Tal A, Ghaoui LE, Nemirovski A (2009) Robust Optimization, Princeton Series in Applied Mathematics · Zbl 1221.90001
[4] Bertsimas, D; Pachamanova, D; Sim, M, Robust linear optimization under general norms, Oper Res Lett, 32, 510-516, (2004) · Zbl 1054.90046 · doi:10.1016/j.orl.2003.12.007
[5] Bertsimas, D; Brown, D; Caramanis, C, Theory and applications of robust optimization, SIAM Rev, 53, 464-501, (2011) · Zbl 1233.90259 · doi:10.1137/080734510
[6] Burer, S; Anstreicher, KM, Second-order-cone constraints for extended trust-region subproblems, SIAM J Optim, 23, 432-451, (2013) · Zbl 1298.90062 · doi:10.1137/110826862
[7] Burer, S; Yang, B, The trust region subproblem with non-intersecting linear constraints, Math Program, 149, 253-264, (2015) · Zbl 1308.90121 · doi:10.1007/s10107-014-0749-1
[8] Coleman, TF; Liao, A, An efficient trust region method for unconstrained discrete-time optimal control problems, Comput Optim Appl, 4, 47-66, (1995) · Zbl 0876.49025 · doi:10.1007/BF01299158
[9] Conn AR, Gould NI, Toint PL (2000) Trust region methods. SIAM, Philadelphia · Zbl 0958.65071 · doi:10.1137/1.9780898719857
[10] Fukushima, M; Yamamoto, Y, A second-order algorithm for continuous-time nonlinear optimal control problems, IEEE Trans Automat Contr, 31, 673-676, (1986) · Zbl 0608.49021 · doi:10.1109/TAC.1986.1104364
[11] Fortin, C; Wolkowicz, H, The trust region subproblem and semidefinite programming, Optim Methods Softw, 19, 41-67, (2004) · Zbl 1070.65041 · doi:10.1080/10556780410001647186
[12] Gould, NI; Lucidi, S; Roma, M; Toint, PL, Solving the trust-region subproblem using the Lanczos method, SIAM J Optim, 9, 504-525, (1999) · Zbl 1047.90510 · doi:10.1137/S1052623497322735
[13] Gould, NI; Robinson, DP; Thorne, HS, On solving trust-region and other regularised subproblems in optimization, Math Program Comput, 2, 21-57, (2010) · Zbl 1193.65098 · doi:10.1007/s12532-010-0011-7
[14] Hsia Y, Sheu RL (2013) Trust region subproblem with a fixed number of additional linear inequality constraints has polynomial complexity, arXiv preprint. arXiv:1312.1398 · Zbl 1128.90044
[15] Jeyakumar, V; Li, GY, Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization, Math Program, 147, 171-206, (2014) · Zbl 1297.90105 · doi:10.1007/s10107-013-0716-2
[16] Martinez JM (1994) Local minimizers of quadratic functions on Euclidean balls and spheres. SIAM J Optim 4(1):159-176 · Zbl 0801.65057
[17] Niesen, U; Devavrat, S; Gregory, W, Adaptive alternating minimization algorithms, IEEE Trans Inf Theory, 55, 1423-1429, (2009) · Zbl 1367.94128 · doi:10.1109/TIT.2008.2011442
[18] Overton, ML, Large-scale optimization of eigenvalues, SIAM J Optim, 2, 88-120, (1992) · Zbl 0757.65072 · doi:10.1137/0802007
[19] Pardalos P, Romeijn H (2002) Handbook of Global Optimization, vol 2. Kluwer Academic Publishers, Dordrecht · Zbl 0991.00017 · doi:10.1007/978-1-4757-5362-2
[20] Rendl, F; Wolkowicz, H, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math Program, 77, 273-299, (1997) · Zbl 0888.90137 · doi:10.1007/BF02614438
[21] Salahi M, Fallahi S (2016) Trust region subproblem with an additional linear inequality constraint. Optim Lett. 10:821-832 · Zbl 1367.90077
[22] Sturm, JF; Zhang, S, On cones of nonnegative quadratic functions, Math Oper Res, 28, 246-267, (2003) · Zbl 1082.90086 · doi:10.1287/moor.28.2.246.14485
[23] Ye, Y; Zhang, S, New results on quadratic minimization, SIAM J Optim, 14, 245-267, (2003) · Zbl 1043.90064 · doi:10.1137/S105262340139001X
[24] Ye H (2011) Efficient Trust Region Subproblem Algorithms, Master thesis, Department of Combinatorics and Optimization, University of Waterloo · Zbl 1233.90259
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.