Cubic Regularization Method based on Mixed Factorizations for Unconstrained Minimization

Ernesto G. Birgin(egbirginime.usp.br)
J. M. Martínez(martinezime.unicamp.br)

Abstract: Newton's method for unconstrained optimization, subject to proper regularization or special trust-region procedures, finds first-order stationary points with precision $\varepsilon$ employing, at most, $O(\varepsilon^{-3/2})$ functional and derivative evaluations. However, the computer work per iteration of the best-known implementations may need several factorizations per iteration or may use rather expensive matrix decompositions. In this paper, we introduce a method that, preserving most features of the regularization approach, uses only one cheap factorization per iteration, as well as the same number of gradient and Hessian evaluations. We prove complexity and convergence results, even in the case in which the Hessians of the subproblems are far from being Hessians of the objective function. We also present fairly successful and fully reproducible numerical experiments and we make available the corresponding software.

Keywords: Smooth unconstrained minimization, Bunch-Parlett-Kaufman factorizations, regularization, Newton-type methods.

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation:

Download: [PDF]

Entry Submitted: 02/22/2018
Entry Accepted: 02/22/2018
Entry Last Modified: 02/22/2018

Modify/Update this entry