Second-order optimality and beyond: characterization and evaluation complexity in nonconvex convexly-constrained optimization

ePubs

The open archive for STFC research publications

Persistent URL	http://purl.org/net/epubs/work/29688263
Record Status	Checked
Record Id	29688263
Title	Second-order optimality and beyond: characterization and evaluation complexity in nonconvex convexly-constrained optimization
Contributors	C Cartis (Oxford Univ.), NIM Gould (STFC Rutherford Appleton Lab.), PL Toint (Namur Univ.)
Abstract	High-order optimality conditions for convexly-constrained nonlinear optimization problems are analyzed. 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 q-th 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.
Organisation	STFC , SCI-COMP , SCI-COMP-CM
Keywords
Funding Information	EPSRC (RP/1028854/1); EPSRC (EP/M025179/1)
Related Research Object(s):	39627571
Licence Information:
Language	English (EN)

Type	Details	URI(s)	Local file(s)	Year
Preprint	RAL Preprints RAL-P-2016-008, Foundations of Computational Mathematics 2016.		RAL-P-2016-008.pdf	2016