A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees
arXiv:1904.03563
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.
References in corpus (6)
- Complexity and performance of an Augmented Lagrangian algorithm
- Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
- On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization
- "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
- Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
- Worst-case iteration bounds for log barrier methods on problems with nonconvex constraints