Journal Article

On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming

Toint, Philippe L., Cartis, Coralia, Gould, Nicholas I. M.

2011

Overview

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 $\\mathcal{O}(\\epsilon^{-2})$ function evaluations to reduce the size of a first-order criticality measure below $\\epsilon$. Specializing this result to the case when the composite objective is an exact penalty function allows us to consider the objective- and constraint-evaluation 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 $\\epsilon$ of a KKT point is at most $\\mathcal{O}(\\epsilon^{-2})$ problem evaluations, which is the same in order as the function-evaluation complexity of steepest-descent methods applied to unconstrained, nonconvex smooth optimization. [PUBLICATION ABSTRACT]

• Publisher: Society for Industrial and Applied Mathematics
• Subject: Algorithms / Applied mathematics / Lagrange multiplier / Optimization / Regularization methods