Evaluation Complexity Bounds for Smooth Constrained Nonlinear Optimization Using Scaled KKT Conditions and High-Order Models

Coralia Cartis (), Nicholas I. M. Gould () and Philippe L. Toint ()
Additional contact information
Coralia Cartis: Oxford University
Nicholas I. M. Gould: Rutherford Appleton Laboratory
Philippe L. Toint: University of Namur

A chapter in Approximation and Optimization, 2019, pp 5-26 from Springer

Abstract: 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 O(𝜖 −(p+1)∕p) evaluations whenever derivatives of order p are available. It is also shown that the bound of O ( 𝜖 P − 1 ∕ 2 𝜖 D − 3 ∕ 2 ) $$O(\epsilon _{\mbox{ P}}^{-1/2}\epsilon _{\mbox{ D}}^{-3/2})$$ 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 O ( 𝜖 P − 1 ∕ p 𝜖 D − ( p + 1 ) ∕ p ) $$O(\epsilon _{\mbox{ P}}^{-1/p}\epsilon _{\mbox{ D}}^{-(p+1)/p})$$ evaluations under similarly weakened assumptions.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (2)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-030-12767-1_2

Ordering information: This item can be ordered from
http://www.springer.com/9783030127671

DOI: 10.1007/978-3-030-12767-1_2

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().