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 journalArticlepeer-review

141 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

Keywords

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

Fingerprint Dive into the research topics of 'On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods'. Together they form a unique fingerprint.

Cite this