On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming.
We estimate the worst-case complexity of minimizing an unconstrained, nonconvex composite objective with a structured nonsmooth term by means of some first-order methods. We find that it is unaffected by the nonsmoothness of the objective in that a first-order trust-region or quadratic regularizatio...
| Hlavní autoři: | , , |
|---|---|
| Médium: | Journal article |
| Jazyk: | English |
| Vydáno: |
2011
|
| _version_ | 1826257867663998976 |
|---|---|
| author | Cartis, C Gould, N Toint, P |
| author_facet | Cartis, C Gould, N Toint, P |
| author_sort | Cartis, C |
| collection | OXFORD |
| description | We estimate the worst-case complexity of minimizing an unconstrained, nonconvex composite objective with a structured nonsmooth term by means of some first-order methods. We find that it is unaffected by the nonsmoothness of the objective in that a first-order trust-region or quadratic regularization method applied to it takes at most O(ε-2) function evaluations to reduce the size of a first-order criticality measure below ε. Specializing this result to the case when the composite objective is an exact penalty function allows us to consider the objective- and constraintevaluation worst-case complexity of nonconvex equality-constrained optimization when the solution is computed using a first-order exact penalty method. We obtain that in the reasonable case when the penalty parameters are bounded, the complexity of reaching within ε of a KKT point is at most O(ε-2) problem evaluations, which is the same in order as the function-evaluation complexity of steepest-descent methods applied to unconstrained, nonconvex smooth optimization. © 2011 Society for Industrial and Applied Mathematics. |
| first_indexed | 2024-03-06T18:24:58Z |
| format | Journal article |
| id | oxford-uuid:07a1a7e6-2d2c-4c20-b9f5-2ee372e27bee |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:24:58Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:07a1a7e6-2d2c-4c20-b9f5-2ee372e27bee2022-03-26T09:08:36ZOn the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:07a1a7e6-2d2c-4c20-b9f5-2ee372e27beeEnglishSymplectic Elements at Oxford2011Cartis, CGould, NToint, PWe estimate the worst-case complexity of minimizing an unconstrained, nonconvex composite objective with a structured nonsmooth term by means of some first-order methods. We find that it is unaffected by the nonsmoothness of the objective in that a first-order trust-region or quadratic regularization method applied to it takes at most O(ε-2) function evaluations to reduce the size of a first-order criticality measure below ε. Specializing this result to the case when the composite objective is an exact penalty function allows us to consider the objective- and constraintevaluation worst-case complexity of nonconvex equality-constrained optimization when the solution is computed using a first-order exact penalty method. We obtain that in the reasonable case when the penalty parameters are bounded, the complexity of reaching within ε of a KKT point is at most O(ε-2) problem evaluations, which is the same in order as the function-evaluation complexity of steepest-descent methods applied to unconstrained, nonconvex smooth optimization. © 2011 Society for Industrial and Applied Mathematics. |
| spellingShingle | Cartis, C Gould, N Toint, P On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming. |
| title | On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming. |
| title_full | On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming. |
| title_fullStr | On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming. |
| title_full_unstemmed | On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming. |
| title_short | On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming. |
| title_sort | on the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming |
| work_keys_str_mv | AT cartisc ontheevaluationcomplexityofcompositefunctionminimizationwithapplicationstononconvexnonlinearprogramming AT gouldn ontheevaluationcomplexityofcompositefunctionminimizationwithapplicationstononconvexnonlinearprogramming AT tointp ontheevaluationcomplexityofcompositefunctionminimizationwithapplicationstononconvexnonlinearprogramming |