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.
In this paper, we adapt the Newton-CG method of @cite_9 for unconstrained optimization to the problem of minimizing the primal log-barrier function , for a small, fixed value of @math . We target the optimality conditions ), which avoid enforcing tighter conditions on Hessian and gradient components that correspond to components of @math that are far from zero at optimality. This change allows us to solve a preconditioned Newton system of linear equations at each iteration in which the norm of the matrix can be bounded by a constant independent of iteration number. The Capped CG method developed in @cite_9 is used to solve this system, returning a useful search direction in a reasonable number of iterations. Our algorithm finds a point satisfying ) in @math iterations and @math gradient evaluations Hessian vector products when @math , making our algorithm the first method for bound-constrained optimization with this overall computational complexity. Further, our algorithm has the appealing practical feature that it puts minimal restrictions on the step size, allowing the line search to take steps that are much closer to the boundary than the current iterate.
@cite_9
2963900797
We consider minimization of a smooth nonconvex objective function using an iterative algorithm based on Newton’s method and the linear conjugate gradient algorithm, with explicit detection and use of negative curvature directions for the Hessian of the objective function. The algorithm tracks Newton-conjugate gradient procedures developed in the 1980s closely, but includes enhancements that allow worst-case complexity results to be proved for convergence to points that satisfy approximate first-order and second-order optimality conditions. The complexity results match the best known results in the literature for second-order methods.