Optimization Online


On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming

C Cartis (coralia.cartis***at***ed.ac.uk)
N I M Gould (nick.gould***at***stfc.ac.uk)
Ph L Toint (philippe.toint***at***fundp.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/2011
Entry Accepted: 02/08/2011
Entry Last Modified: 05/01/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society