On the evaluation complexity of composite
function minimization with applications
to nonconvex nonlinear programming
C. Cartis, N. I. M. Gould and Ph. L. Toint
Report NAXYS-06-2011 7 February 2011
Abstract.
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.