A log-barrier Newton-CG method for bound constrained optimization with complexity guarantees

DOI10.1093/IMANUM/DRZ074MaRDI QIDQ4964081zbMATH OpenOpenAlexFDO

Authors

Publication date 24 February 2021

Published in IMA Journal of Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.03563

zbMATH Keywords

bound constraintslog-barrier methodsNewton-CG methodnonconvex optimizationworst-case complexity

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Methods of quasi-Newton type (90C53)

Abstract: We describe an algorithm based on a logarithmic barrier function, Newton's method, and linear conjugate gradients that obtains an approximate minimizer of a smooth function over the nonnegative 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.

Recommendations

• A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
• A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees
• A logarithm barrier function method
• A Barrier Method for Large-Scale Constrained Optimization
• scientific article; zbMATH DE number 679870

Cited in

(13)

• Complexity of proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints
• A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
• MINRES: from negative curvature detection to monotonicity properties
• Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
• On optimality conditions for nonlinear conic programming
• Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems
• A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees
• A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees
• Complexity of a projected Newton-CG method for optimization with bounds
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
• Hessian barrier algorithms for non-convex conic optimization
• Strong global convergence properties of algorithms for nonlinear symmetric cone programming
• Constrained Dikin-Langevin diffusion for polyhedra

This page was built for publication: A log-barrier Newton-CG method for bound constrained optimization with complexity guarantees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4964081)