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.