A linear-time algorithm for the trust region subproblem based on hidden convexity |
| |
| Authors: | Jiulin Wang Yong Xia |
| |
| Institution: | 1.State Key Laboratory of Software Development Environment, LMIB of the Ministry of Education School of Mathematics and System Sciences,Beihang University,Beijing,People’s Republic of China |
| |
| Abstract: | We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov’s accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
