Optimization Online


On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization

Coralia Cartis (coralia.cartis***at***ed.ac.uk)
Nicholas I M Gould (nick.gould***at***stfc.ac.uk)
Philippe L Toint (philippe.toint***at***fundp.ac.be)

Abstract: We propose a new termination criteria suitable for potentially singular, zero or non-zero residual, least-squares problems, with which cubic regularization variants take at most $\mathcal{O}(\epsilon^{-3/2})$ residual- and Jacobian-evaluations to drive either the Euclidean norm of the residual or its gradient below $\epsilon$; this is the best-known bound for potentially singular nonlinear least-squares problems. We then apply the new optimality measure and cubic regularization steps to a family of least-squares merit functions in the context of a target-following algorithm for nonlinear equality-constrained problems; this approach yields the first evaluation complexity bound of order $\epsilon^{-3/2}$ for nonconvexly constrained problems when higher accuracy is required for primal feasibility than for dual first-order criticality.

Keywords: evaluation complexity, worst-case analysis, least-squares, constrained nonlinear optimization, cubic regularization methods

Category 1: Nonlinear Optimization

Citation: ERGO Technical Report 12-001, School of Mathematics, University of Edinburgh, Scotland, UK, 2012.

Download: [PDF]

Entry Submitted: 03/11/2012
Entry Accepted: 03/11/2012
Entry Last Modified: 03/22/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society