Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Research output: Contribution in Book/Catalog/Report/Conference proceedingChapter

Abstract

Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

Original languageEnglish
Title of host publicationSpringer Optimization and Its Applications
Subtitle of host publicationAlgorithms, Complexity and Applications
EditorsIannis Demetriou, Panos Pardalos
PublisherSpringer Heidelberg
Chapter1
Pages5-26
Number of pages22
ISBN (Electronic)978-3-030-12766-4
DOIs
Publication statusPublished - Jun 2019

Publication series

NameSpringer Optimization and Its Applications
Volume145
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836

Fingerprint

KKT Conditions
Constrained Optimization
Nonlinear Optimization
Higher Order
Derivatives
Constrained optimization
Evaluation
Higher order derivative
Equality Constraints
Inequality Constraints
Model
Critical point
First-order
Derivative
Computing

Keywords

  • Complexity theory
  • Nonlinear optimization
  • scaled optimality conditions

Cite this

Cartis, C., Gould, N. I. M., & Toint, P. (2019). Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. In I. Demetriou, & P. Pardalos (Eds.), Springer Optimization and Its Applications: Algorithms, Complexity and Applications (pp. 5-26). (Springer Optimization and Its Applications; Vol. 145). Springer Heidelberg. https://doi.org/10.1007/978-3-030-12767-1_2
Cartis, Coralia ; Gould, Nicholas I M ; Toint, Philippe. / Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. Springer Optimization and Its Applications: Algorithms, Complexity and Applications. editor / Iannis Demetriou ; Panos Pardalos. Springer Heidelberg, 2019. pp. 5-26 (Springer Optimization and Its Applications).
@inbook{de94c500502543daa0d5f17b80c41c7d,
title = "Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models",
abstract = "Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.",
keywords = "Complexity theory, Nonlinear optimization, scaled optimality conditions",
author = "Coralia Cartis and Gould, {Nicholas I M} and Philippe Toint",
year = "2019",
month = "6",
doi = "10.1007/978-3-030-12767-1_2",
language = "English",
series = "Springer Optimization and Its Applications",
publisher = "Springer Heidelberg",
pages = "5--26",
editor = "Iannis Demetriou and Panos Pardalos",
booktitle = "Springer Optimization and Its Applications",
address = "Germany",

}

Cartis, C, Gould, NIM & Toint, P 2019, Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. in I Demetriou & P Pardalos (eds), Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Springer Optimization and Its Applications, vol. 145, Springer Heidelberg, pp. 5-26. https://doi.org/10.1007/978-3-030-12767-1_2

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.

Springer Optimization and Its Applications: Algorithms, Complexity and Applications. ed. / Iannis Demetriou; Panos Pardalos. Springer Heidelberg, 2019. p. 5-26 (Springer Optimization and Its Applications; Vol. 145).

Research output: Contribution in Book/Catalog/Report/Conference proceedingChapter

TY - CHAP

T1 - Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

AU - Cartis, Coralia

AU - Gould, Nicholas I M

AU - Toint, Philippe

PY - 2019/6

Y1 - 2019/6

N2 - Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

AB - Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

KW - Complexity theory

KW - Nonlinear optimization

KW - scaled optimality conditions

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

U2 - 10.1007/978-3-030-12767-1_2

DO - 10.1007/978-3-030-12767-1_2

M3 - Chapter

T3 - Springer Optimization and Its Applications

SP - 5

EP - 26

BT - Springer Optimization and Its Applications

A2 - Demetriou, Iannis

A2 - Pardalos, Panos

PB - Springer Heidelberg

ER -

Cartis C, Gould NIM, Toint P. Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. In Demetriou I, Pardalos P, editors, Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Springer Heidelberg. 2019. p. 5-26. (Springer Optimization and Its Applications). https://doi.org/10.1007/978-3-030-12767-1_2