A matrix-free line-search algorithm for nonconvex optimization. (2nd January 2019)

• Record Type: Journal Article
• Authors: Zhou, W.; Akrotirianakis, I.G.; Yektamaram, S.; Griffin, J.D.
• Is Part Of: Optimization methods and software. Volume 34:Number 1(2019)
• Page Start: 1
• Page End: 24
• Publication Date: 2019-01-02
• Subjects: nonlinear programming -- nonconvex large-scale problems -- trust-region methods -- conjugate gradient method -- Hessian-free methods -- machine learning; 90C06 -- 90C30 -- 90C26 -- 65K05 -- 68T01; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1332618
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In this paper, we have developed a new algorithm for solving nonconvex large-scale problems. The new algorithm performs explicit matrix modifications adaptively, mimicing the implicit modifications used by trust-region methods. Thus, it shares the equivalent theoretical strength of trust-region approaches, without needing to accommodate an explicit step-size constraint. We show that the algorithm is well suited for solving very large-scale nonconvex problems whenever Hessian-vector products are available. The numerical results on the CUTEr problems demonstrate the effectiveness of this approach in the context of a line-search method for large-scale unconstrained nonconvex optimization. Moreover, applications in deep-learning problems further illustrate the usefulness of this algorithm. It does not share any of the prohibitive traits of popular matrix-free algorithms such as truncated conjugate gradient (CG) due to the difficult nature of deep-learning problems. Thus the proposed algorithm serves to bridge the gap between the needs of data-mining community and existing state-of-the-art approaches embraced foremost by the optimization community. Moreover, the proposed approach can be realized with minimal modification to the CG algorithm itself with negligible storage and computational overhead.