Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
We provide sharp worst-case evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e., problems where the cost of evaluating/enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating...
| Հիմնական հեղինակներ: | , , |
|---|---|
| Ձևաչափ: | Journal article |
| Լեզու: | English |
| Հրապարակվել է: |
Society for Industrial and Applied Mathematics
2020
|
| _version_ | 1826291789075578880 |
|---|---|
| author | Cartis, C Gould, N Toint, P |
| author_facet | Cartis, C Gould, N Toint, P |
| author_sort | Cartis, C |
| collection | OXFORD |
| description | We provide sharp worst-case evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e., problems where the cost of evaluating/enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend, or improve all known upper and lower complexity bounds for nonconvex unconstrained and convexly constrained problems. It is shown that, given an accuracy level $\epsilon$, a degree of highest available Lipschitz continuous derivatives $p$, and a desired optimality order $q$ between one and $p$, a conceptual regularization algorithm requires no more than $O(\epsilon^{-\frac{p+1}{p-q+1}})$ evaluations of the objective function and its derivatives to compute a suitably approximate $q$th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the $p$th derivative is merely Hölder rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems; we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information.
|
| first_indexed | 2024-03-07T03:04:43Z |
| format | Journal article |
| id | oxford-uuid:b21c8a0c-0ab8-41fa-a91c-b7b29d7f371b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:04:43Z |
| publishDate | 2020 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:b21c8a0c-0ab8-41fa-a91c-b7b29d7f371b2022-03-27T04:09:23ZSharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraintsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b21c8a0c-0ab8-41fa-a91c-b7b29d7f371bEnglishSymplectic Elements at OxfordSociety for Industrial and Applied Mathematics2020Cartis, CGould, NToint, PWe provide sharp worst-case evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e., problems where the cost of evaluating/enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend, or improve all known upper and lower complexity bounds for nonconvex unconstrained and convexly constrained problems. It is shown that, given an accuracy level $\epsilon$, a degree of highest available Lipschitz continuous derivatives $p$, and a desired optimality order $q$ between one and $p$, a conceptual regularization algorithm requires no more than $O(\epsilon^{-\frac{p+1}{p-q+1}})$ evaluations of the objective function and its derivatives to compute a suitably approximate $q$th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the $p$th derivative is merely Hölder rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems; we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information. |
| spellingShingle | Cartis, C Gould, N Toint, P Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints |
| title | Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints |
| title_full | Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints |
| title_fullStr | Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints |
| title_full_unstemmed | Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints |
| title_short | Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints |
| title_sort | sharp worst case evaluation complexity bounds for arbitrary order nonconvex optimization with inexpensive constraints |
| work_keys_str_mv | AT cartisc sharpworstcaseevaluationcomplexityboundsforarbitraryordernonconvexoptimizationwithinexpensiveconstraints AT gouldn sharpworstcaseevaluationcomplexityboundsforarbitraryordernonconvexoptimizationwithinexpensiveconstraints AT tointp sharpworstcaseevaluationcomplexityboundsforarbitraryordernonconvexoptimizationwithinexpensiveconstraints |