Abstract
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.
Similar content being viewed by others
Notes
We observed that, among the three classes of test problems, scaling had the most effect on the performance of new algorithm in handling third class (indeed the scaling improved the performance of RW algorithm).
References
Ai W, Zhang S (2009) Strong duality for the CDT subproblem: a necessary and sufficient condition. SIAM J Optim 19(4):1735–1756
Beck A, Eldar YC (2006) Strong duality in nonconvex quadratic optimization with two quadratic constraints. SIAM J Optim 17(3):844–860
Ben-Tal A, Ghaoui LE, Nemirovski A (2009) Robust Optimization, Princeton Series in Applied Mathematics
Bertsimas D, Pachamanova D, Sim M (2004) Robust linear optimization under general norms. Oper Res Lett 32(6):510–516
Bertsimas D, Brown D, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev 53(3):464–501
Burer S, Anstreicher KM (2013) Second-order-cone constraints for extended trust-region subproblems. SIAM J Optim 23(1):432–451
Burer S, Yang B (2015) The trust region subproblem with non-intersecting linear constraints. Math Program 149:253–264
Coleman TF, Liao A (1995) An efficient trust region method for unconstrained discrete-time optimal control problems. Comput Optim Appl 4:47–66
Conn AR, Gould NI, Toint PL (2000) Trust region methods. SIAM, Philadelphia
Fukushima M, Yamamoto Y (1986) A second-order algorithm for continuous-time nonlinear optimal control problems. IEEE Trans Automat Contr 31(7):673–676
Fortin C, Wolkowicz H (2004) The trust region subproblem and semidefinite programming. Optim Methods Softw 19(1):41–67
Gould NI, Lucidi S, Roma M, Toint PL (1999) Solving the trust-region subproblem using the Lanczos method. SIAM J Optim 9(2):504–525
Gould NI, Robinson DP, Thorne HS (2010) On solving trust-region and other regularised subproblems in optimization. Math Program Comput 2(1):21–57
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
Jeyakumar V, Li GY (2014) Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math Program 147:171–206
Martinez JM (1994) Local minimizers of quadratic functions on Euclidean balls and spheres. SIAM J Optim 4(1):159–176
Niesen U, Devavrat S, Gregory W (2009) Adaptive alternating minimization algorithms. IEEE Trans Inf Theory 55(3):1423–1429
Overton ML (1992) Large-scale optimization of eigenvalues. SIAM J Optim 2(1):88–120
Pardalos P, Romeijn H (2002) Handbook of Global Optimization, vol 2. Kluwer Academic Publishers, Dordrecht
Rendl F, Wolkowicz H (1997) A semidefinite framework for trust region subproblems with applications to large scale minimization. Math Program 77(1):273–299
Salahi M, Fallahi S (2016) Trust region subproblem with an additional linear inequality constraint. Optim Lett. 10:821–832
Sturm JF, Zhang S (2003) On cones of nonnegative quadratic functions. Math Oper Res 28(2):246–267
Ye Y, Zhang S (2003) New results on quadratic minimization. SIAM J Optim 14(1):245–267
Ye H (2011) Efficient Trust Region Subproblem Algorithms, Master thesis, Department of Combinatorics and Optimization, University of Waterloo
Acknowledgments
The authors would like to thank the reviewer for his/her useful suggestions and questions which improved the readability of the paper and Prof. H. Wolkowicz for his useful comments on the early version of this work. The first author also would like to thank University of Guilan for the financial support during his sabbatical leave 2015–2016 at the University of Waterloo.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by José Mario Martínez.
Appendix
Appendix
Proposition 1
Let \((t^{*},\lambda ^{*})\) be an optimal solution of problem (NewD-eTRS) with \(\lambda _{\text {min}}(D(t^{*},\lambda ^{*}))=\lambda _{\text {min}}(A)\). Moreover, let \(y(t^{*},\lambda ^{*})=[y_0(t^{*},\lambda ^{*}), z_0(t^{*},\lambda ^{*})^T]^T\) be a normalized eigenvector for \(\lambda _{\text {min}}(D(t^{*},\lambda ^{*}))\) with \(y_0(t^{*},\lambda ^{*})\ne 0\). Then \(||x^{*}||^2\le \Delta \) where \(x^{*}=\frac{z(t^{*},\lambda ^{*})}{y_0(t^{*},\lambda ^{*})}\).
Proof
First notice that, as discussed in proof of Item 1 of Theorem 4, we have
On the other hand, since \((t^{*},\lambda ^{*})\) is an optimal solution of problem (NewD-eTRS), we have
Moreover, we know, as shown in proof of Lemma 2, \(t^{*}=t_0\) where \(t_0\) is defined as before. The function \(k(t,\lambda ^{*})\) is not differentiable at \(t_0\) and the directional derivative from left, \(k'(t_0^{-})=(\Delta +1)y_0(t^{*},\lambda ^{*})^2-1\). The optimality of \(t_0\) implies that \(k'(t_0^{-})\ge 0\). This proves that \(||x^{*}||^2\le \Delta \).
Proposition 2
Suppose that \(\lambda _{\text {min}}(A)\) has multiplicity, \(i>2\) and let \(\lambda _1^{*}:=-\lambda _{\text {min}}(A)\ge 0\) and \(\lambda _2^{*}\ge 0\) be optimal Lagrange multipliers corresponding to the norm and the linear constraint of eTRS, respectively. Then \(\lambda _1^{*}\) and \(\lambda _2^{*}\) are also the optimal Lagrange multipliers corresponding to the norm and the linear constraint of eTRS with A replaced by \(A+\alpha vv^T\) where v is a normalized eigenvector for \(\lambda _{\text {min}}(A)\) such that \(v^Tb=0\) and \(\alpha >0\).
Proof
Let v be a normalized eigenvector for \(\lambda _{\text {min}}(A)\) such that \(v^Tb=0\). Moreover, let \(A=PDP^T\) be the eigenvalue decomposition of A in which P contains v. First, since \(\lambda _1^{*}=-\lambda _{\text {min}}(A)\) and \(\lambda _2^{*}\) are the optimal Lagrange multipliers for eTRS, we have \((a-\frac{\lambda _2^{*}}{2}b)\in \text {Range}(A+\lambda _1^{*} I).\) This implies that \(v^T(a-\frac{\lambda _2^{*}}{2}b)=0\) which results in \(v^Ta=0\). As strong duality holds for eTRS, we know that \(\lambda _1^{*}\) and \(\lambda _2^{*}\) are the optimal solution of the Lagrangian dual of eTRS. Hence, to prove the statement, it is enough to show that the Lagrangian dual of eTRS is equivalent to the one for eTRS with A replaced by \(A+\alpha vv^T\) where \(\alpha \) is a positive constant. The Lagrangian dual of eTRS is given by
Now let \(\lambda _1\) and \(\lambda _2\) be feasible for problem (15). Then it is easy to verify the following facts:
Equation (17) uses the fact that \(v^Ta=v^Tb=0\). It follows from (15),(16) and (17) that \(\lambda _1^{*}\) and \(\lambda _2^{*}\) are also the optimal Lagrange multipliers for eTRS with \(A+\alpha vv^T\). \(\square \)
Rights and permissions
About this article
Cite this article
Salahi, M., Taati, A. A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality . Comp. Appl. Math. 37, 329–347 (2018). https://doi.org/10.1007/s40314-016-0347-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40314-016-0347-3