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, Nick Gould, Philippe Toint

Résultats de recherche: Contribution à un journal/une revueArticle

28 Downloads (Pure)

Résumé

We propose a new termination criterion suitable for potentially singular, zero or nonzero residual, least-squares problems, with which cubic regularization variants take at most O(ε-3/2) residual- and Jacobian-evaluations to drive either the Euclidean norm of the residual or its gradient belowε this is the best known bound for potentially rank-deficient 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 ε-3/2 for nonconvexly constrained problems when higher accuracy is required for primal feasibility than for dual first-order criticality.

langue originaleAnglais
Pages (de - à)1553-1574
Nombre de pages22
journalSIAM Journal on Optimization
Volume23
Numéro de publication3
Les DOIs
étatPublié - 29 oct. 2013

Empreinte digitale

Nonlinear Least Squares Problem
Regularization Method
Constrained Optimization
Nonlinear Optimization
Regularization
Evaluation
Merit Function
Euclidean norm
Square Functions
Least Squares Problem
Criticality
Termination
Least Squares
Optimality
High Accuracy
Equality
Gradient
First-order
Target
Zero

Citer ceci

@article{c89a8d722a27432db33b34f3a20a3fbd,
title = "On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization",
abstract = "We propose a new termination criterion suitable for potentially singular, zero or nonzero residual, least-squares problems, with which cubic regularization variants take at most O(ε-3/2) residual- and Jacobian-evaluations to drive either the Euclidean norm of the residual or its gradient belowε this is the best known bound for potentially rank-deficient 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 ε-3/2 for nonconvexly constrained problems when higher accuracy is required for primal feasibility than for dual first-order criticality.",
keywords = "Constrained nonlinear optimization, Cubic regularization methods, Evaluation complexity, Least-squares problems, Worst-case analysis",
author = "Coralia Cartis and Nick Gould and Philippe Toint",
year = "2013",
month = "10",
day = "29",
doi = "10.1137/120869687",
language = "English",
volume = "23",
pages = "1553--1574",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics",
number = "3",

}

On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization. / Cartis, Coralia; Gould, Nick; Toint, Philippe.

Dans: SIAM Journal on Optimization, Vol 23, Numéro 3, 29.10.2013, p. 1553-1574.

Résultats de recherche: Contribution à un journal/une revueArticle

TY - JOUR

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

AU - Cartis, Coralia

AU - Gould, Nick

AU - Toint, Philippe

PY - 2013/10/29

Y1 - 2013/10/29

N2 - We propose a new termination criterion suitable for potentially singular, zero or nonzero residual, least-squares problems, with which cubic regularization variants take at most O(ε-3/2) residual- and Jacobian-evaluations to drive either the Euclidean norm of the residual or its gradient belowε this is the best known bound for potentially rank-deficient 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 ε-3/2 for nonconvexly constrained problems when higher accuracy is required for primal feasibility than for dual first-order criticality.

AB - We propose a new termination criterion suitable for potentially singular, zero or nonzero residual, least-squares problems, with which cubic regularization variants take at most O(ε-3/2) residual- and Jacobian-evaluations to drive either the Euclidean norm of the residual or its gradient belowε this is the best known bound for potentially rank-deficient 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 ε-3/2 for nonconvexly constrained problems when higher accuracy is required for primal feasibility than for dual first-order criticality.

KW - Constrained nonlinear optimization

KW - Cubic regularization methods

KW - Evaluation complexity

KW - Least-squares problems

KW - Worst-case analysis

U2 - 10.1137/120869687

DO - 10.1137/120869687

M3 - Article

VL - 23

SP - 1553

EP - 1574

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 3

ER -