On the complexity of finding first-order critical points in constrained nonlinear optimization
The complexity of finding {Mathematical expression}-approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that {Mathematical expression} in terms of function and constraints evaluations. This result is obtained by analyzing the worst-...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
2012
|
| _version_ | 1797056937179742208 |
|---|---|
| author | Cartis, C Gould, N Toint, P |
| author_facet | Cartis, C Gould, N Toint, P |
| author_sort | Cartis, C |
| collection | OXFORD |
| description | The complexity of finding {Mathematical expression}-approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that {Mathematical expression} in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. |
| first_indexed | 2024-03-06T19:29:31Z |
| format | Journal article |
| id | oxford-uuid:1cfb18c8-297b-4747-921a-6608c0442d49 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:29:31Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:1cfb18c8-297b-4747-921a-6608c0442d492022-03-26T11:08:22ZOn the complexity of finding first-order critical points in constrained nonlinear optimizationJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:1cfb18c8-297b-4747-921a-6608c0442d49Symplectic Elements at Oxford2012Cartis, CGould, NToint, PThe complexity of finding {Mathematical expression}-approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that {Mathematical expression} in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. |
| spellingShingle | Cartis, C Gould, N Toint, P On the complexity of finding first-order critical points in constrained nonlinear optimization |
| title | On the complexity of finding first-order critical points in constrained nonlinear optimization |
| title_full | On the complexity of finding first-order critical points in constrained nonlinear optimization |
| title_fullStr | On the complexity of finding first-order critical points in constrained nonlinear optimization |
| title_full_unstemmed | On the complexity of finding first-order critical points in constrained nonlinear optimization |
| title_short | On the complexity of finding first-order critical points in constrained nonlinear optimization |
| title_sort | on the complexity of finding first order critical points in constrained nonlinear optimization |
| work_keys_str_mv | AT cartisc onthecomplexityoffindingfirstordercriticalpointsinconstrainednonlinearoptimization AT gouldn onthecomplexityoffindingfirstordercriticalpointsinconstrainednonlinearoptimization AT tointp onthecomplexityoffindingfirstordercriticalpointsinconstrainednonlinearoptimization |