A log-barrier Newton-CG method for bound constrained optimization with complexity guarantees. (18th April 2020)

• Record Type: Journal Article
• Authors: O'Neill, Michael; Wright, Stephen J
• Is Part Of: IMA journal of numerical analysis. Volume 41:Number 1(2021)
• Page Start: 84
• Page End: 121
• Publication Date: 2020-04-18
• Subjects: nonconvex optimization -- log-barrier methods -- worst-case complexity -- bound constraints; Numerical analysis -- Periodicals; 519.405
• DOI: 10.1093/imanum/drz074
• Languages: English
• ISSNs: 0272-4979

Abstract

Abstract: We describe an algorithm based on a logarithmic barrier function, Newton's method and linear conjugate gradients that seeks an approximate minimizer of a smooth function over the non-negative orthant. We develop a bound on the complexity of the approach, stated in terms of the required accuracy and the cost of a single gradient evaluation of the objective function and/or a matrix-vector multiplication involving the Hessian of the objective. The approach can be implemented without explicit calculation or storage of the Hessian.