Trust region subproblem (TRS), which is the problem of minimizing a quadratic function over a ball, plays a key role in solving unconstrained nonlinear optimization problems. Though TRS is not necessarily convex, there are efficient algorithms to solve it, particularly in large scale. Recently, extensions of TRS with extra linear constraints have received attention of several researchers. It has been shown that in the case where the linear constraints do not intersect within the ball, the optimal solution of the extended problem can be computed via solving a conic optimization problem. However, solving large-scale or even medium scale conic optimization problems are not practicable. In this paper, the extended trust region subproblem with two linear constraints without any assumptions on the constraints is considered. The latest algorithms for solving TRS and computing its local non-global minimizer, that solve the problem via a generalized eigenvalue problem, are used to solve the extended trust region subproblem. Finally, the efficiency of the proposed algorithm is evaluated on several randomly generated instances
Rights and permissions | |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |