Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization
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 conceptua...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Springer
2017
|
| _version_ | 1797063784454422528 |
|---|---|
| author | Cartis, C Gould, N Toint, P |
| author_facet | Cartis, C Gould, N Toint, P |
| author_sort | Cartis, C |
| collection | OXFORD |
| description | 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 deriva- tives 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. |
| first_indexed | 2024-03-06T21:04:52Z |
| format | Journal article |
| id | oxford-uuid:3c1ac5c6-dfe3-4b5c-8123-e95e8ecba423 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:04:52Z |
| publishDate | 2017 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:3c1ac5c6-dfe3-4b5c-8123-e95e8ecba4232022-03-26T14:11:36ZSecond-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimizationJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3c1ac5c6-dfe3-4b5c-8123-e95e8ecba423Symplectic Elements at OxfordSpringer2017Cartis, CGould, NToint, PHigh-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 deriva- tives 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. |
| spellingShingle | Cartis, C Gould, N Toint, P Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization |
| title | Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization |
| title_full | Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization |
| title_fullStr | Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization |
| title_full_unstemmed | Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization |
| title_short | Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization |
| title_sort | second order optimality and beyond characterization and evaluation complexity in convexly constrained nonlinear optimization |
| work_keys_str_mv | AT cartisc secondorderoptimalityandbeyondcharacterizationandevaluationcomplexityinconvexlyconstrainednonlinearoptimization AT gouldn secondorderoptimalityandbeyondcharacterizationandevaluationcomplexityinconvexlyconstrainednonlinearoptimization AT tointp secondorderoptimalityandbeyondcharacterizationandevaluationcomplexityinconvexlyconstrainednonlinearoptimization |