On Efficiently Combining Limited-Memory and Trust-Region Techniques

Burdakov, Oleg,1953-Linköpings universitet,Optimeringslära,Tekniska fakulteten (författare)

Limited-memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited-memory methods are usually combined with a line search. We show how to efficiently combine limited-memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited-memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead as compared with the cost of computing the quasi-Newton direction in line-search limited-memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.

Gong, LujinTencent, Beijing, China (författare)
Zikrin, SpartakLinköpings universitet,Optimeringslära,Tekniska fakulteten(Swepub:liu)spazi51 (författare)
Yuan, Ya-xiangState Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, AMSS, CAS, Beijing, China (författare)
Linköpings universitetOptimeringslära (creator_code:org_t)

Ingår i:Mathematical Programming Computation: Springer9:1, s. 101-1341867-29491867-2957

Av författaren/redakt...: Burdakov, Oleg, ...; Gong, Lujin; Zikrin, Spartak; Yuan, Ya-xiang

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.