- 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.cartised.ac.uk) Nicholas I M Gould (nick.gouldstfc.ac.uk) Philippe L Toint (philippe.tointfundp.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/2012Entry Accepted: 03/11/2012Entry Last Modified: 03/22/2012Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.