- On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming C Cartis (coralia.cartised.ac.uk) N I M Gould (nick.gouldstfc.ac.uk) Ph L Toint (philippe.tointfundp.ac.be) 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 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 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. Keywords: steepest descent method, trust region method, global rate of convergence, nonlinear programming Category 1: Nonlinear Optimization Citation: ERGO Technical Report 11-002, School of Mathematics, University of Edinburgh, UK, 2011. Download: [PDF]Entry Submitted: 02/08/2011Entry Accepted: 02/08/2011Entry Last Modified: 05/01/2011Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.