On globally solving nonconvex trust region subproblem via projected gradient method
From MaRDI portal
Publication:6404734
arXiv2207.05597MaRDI QIDQ6404734FDOQ6404734
Authors: Mengmeng Song, Yong Xia, Jin-Yang Zheng 
Publication date: 12 July 2022
Abstract: The trust region subproblem (TRS) is to minimize a possibly nonconvex quadratic function over a Euclidean ball. There are typically two cases for (TRS), the so-called ``easy case and ``hard case. Even in the ``easy case, the sequence generated by the classical projected gradient method (PG) may converge to a saddle point at a sublinear local rate, when the initial point is arbitrarily selected from a nonzero measure feasible set. To our surprise, when applying (PG) to solve a cheap and possibly nonconvex reformulation of (TRS), the generated sequence initialized with {it any} feasible point almost always converges to its global minimizer. The local convergence rate is at least linear for the ``easy case, without assuming that we have possessed the information that the ``easy case holds. We also consider how to use (PG) to globally solve equality-constrained (TRS).
Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Methods of reduced gradient type (90C52)
This page was built for publication: On globally solving nonconvex trust region subproblem via projected gradient method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404734)
