Second-order optimality and beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Research output: Contribution to journalArticle

Abstract

High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥ 1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ - ( q + 1 )) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.

Original languageEnglish
Pages (from-to)1073-1107
Number of pages35
JournalFoundations of Computational Mathematics
Volume18
Issue number5
DOIs
Publication statusPublished - 1 Oct 2018

Fingerprint

Constrained Optimization
Nonlinear Optimization
Optimality
Derivatives
Critical point
Evaluation
Higher Order
Trust Region Algorithm
Derivative
Order Conditions
Arbitrary
Criticality
Optimality Conditions
Lipschitz
Nonlinear Problem
Objective function
Optimization Problem

Keywords

  • Complexity theory
  • optimality conditions
  • nonlinear optimization

Cite this

@article{bd6f0a4f1ea04f118480bfabe0e76c6a,
title = "Second-order optimality and beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization",
abstract = "High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥ 1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ - ( q + 1 )) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.",
keywords = "Complexity theory, optimality conditions, nonlinear optimization",
author = "Coralia Cartis and Gould, {Nicholas I M} and Philippe Toint",
year = "2018",
month = "10",
day = "1",
doi = "10.1007/s10208-017-9363-y",
language = "English",
volume = "18",
pages = "1073--1107",
journal = "Foundations of Computational Mathematics",
issn = "1615-3375",
publisher = "Springer New York",
number = "5",

}

Second-order optimality and beyond : Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.

In: Foundations of Computational Mathematics, Vol. 18, No. 5, 01.10.2018, p. 1073-1107.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Second-order optimality and beyond

T2 - Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

AU - Cartis, Coralia

AU - Gould, Nicholas I M

AU - Toint, Philippe

PY - 2018/10/1

Y1 - 2018/10/1

N2 - High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥ 1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ - ( q + 1 )) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.

AB - High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥ 1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ - ( q + 1 )) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.

KW - Complexity theory

KW - optimality conditions

KW - nonlinear optimization

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

U2 - 10.1007/s10208-017-9363-y

DO - 10.1007/s10208-017-9363-y

M3 - Article

VL - 18

SP - 1073

EP - 1107

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

SN - 1615-3375

IS - 5

ER -