On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods

Coralia Cartis, Nicholas I M Gould, Philippe L. Toint

Research output: Contribution to journalArticle

35 Downloads (Pure)

Abstract

When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∈ can be obtained by a second-order method using cubic regularization in at most O(∈<sup>-3/2</sup> ) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear least-squares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∈<sup>-2</sup> )) evaluation-complexity bound for solving general nonconvexly constrained optimization problems.

Original languageEnglish
Pages (from-to)836-851
Number of pages16
JournalSIAM Journal on Numerical Analysis
Volume53
Issue number2
DOIs
Publication statusPublished - 2015

Fingerprint

Constrained Least Squares
Nonlinear Least Squares
Constrained Optimization
Nonlinear Optimization
Nonconvex Optimization
Inequality Constraints
Critical point
Constrained optimization
Evaluation
First-order
Nonconvex Problems
Equality Constraints
Constrained Optimization Problem
Regularization
Equality
Optimization Problem

Keywords

  • Complexity theory
  • Nonlinear optimization
  • Constrained problems
  • Least-squares problems

Cite this

@article{05aa52f379a548b7a56ae9679e01c573,
title = "On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods",
abstract = "When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∈ can be obtained by a second-order method using cubic regularization in at most O(∈-3/2 ) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear least-squares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∈-2 )) evaluation-complexity bound for solving general nonconvexly constrained optimization problems.",
keywords = "Complexity theory, Nonlinear optimization, Constrained problems, Least-squares problems",
author = "Coralia Cartis and Gould, {Nicholas I M} and Toint, {Philippe L.}",
year = "2015",
doi = "10.1137/130915546",
language = "English",
volume = "53",
pages = "836--851",
journal = "SIAM Journal on Numerical Analysis",
issn = "0036-1429",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe L.

In: SIAM Journal on Numerical Analysis, Vol. 53, No. 2, 2015, p. 836-851.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods

AU - Cartis, Coralia

AU - Gould, Nicholas I M

AU - Toint, Philippe L.

PY - 2015

Y1 - 2015

N2 - When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∈ can be obtained by a second-order method using cubic regularization in at most O(∈-3/2 ) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear least-squares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∈-2 )) evaluation-complexity bound for solving general nonconvexly constrained optimization problems.

AB - When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∈ can be obtained by a second-order method using cubic regularization in at most O(∈-3/2 ) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear least-squares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∈-2 )) evaluation-complexity bound for solving general nonconvexly constrained optimization problems.

KW - Complexity theory

KW - Nonlinear optimization

KW - Constrained problems

KW - Least-squares problems

UR - http://www.scopus.com/inward/record.url?scp=84929414148&partnerID=8YFLogxK

U2 - 10.1137/130915546

DO - 10.1137/130915546

M3 - Article

VL - 53

SP - 836

EP - 851

JO - SIAM Journal on Numerical Analysis

JF - SIAM Journal on Numerical Analysis

SN - 0036-1429

IS - 2

ER -