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

58 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.

  • Projects

    Complexity in nonlinear optimization

    TOINT, P., Gould, N. I. M. & Cartis, C.

    1/11/08 → …

    Project: Research

    Activities

    A path and some adventures in the jungle of high-order nonlinear optimization

    Philippe Toint (Speaker)

    24 Oct 2017

    Activity: Talk or presentation typesInvited talk

    How much patience do you have? Issues in complexity for nonlinear optimization

    Philippe Toint (Invited speaker)

    5 Feb 2016

    Activity: Talk or presentation typesOral presentation

    Polytechnic University of Hong Kong

    Philippe Toint (Visiting researcher)

    31 Jan 201614 Feb 2016

    Activity: Visiting an external institution typesResearch/Teaching in a external institution

    Prizes

    Honorary Professor

    TOINT, Philippe (Recipient), 10 Feb 2012

    Prize: Honorary degree

    Leverhulme Fellow

    TOINT, Philippe (Recipient), Sep 2015

    Prize: Fellowship awarded competitively

    Cite this