Optimization Online


An adaptive cubic regularisation algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity

Coralia Cartis(coralia.cartis***at***ed.ac.uk)
Nick Gould(nick.gould***at***stfc.ac.uk)
Philippe Toint(philippe.toint***at***fundp.ac.be)

Abstract: The adaptive cubic overestimation algorithm described in Cartis, Gould and Toint (2007) is adapted to the problem of minimizing a nonlinear, possibly nonconvex, smooth objective function over a convex domain. Convergence to first-order critical points is shown under standard assumptions, but without any Lipschitz continuity requirement on the objective's Hessian. A worst-case complexity analysis in terms of evaluations of the problem's function and derivatives is also presented for the Lipschitz continuous case and for a variant of the resulting algorithm. This analysis extends the best known bound for general unconstrained problems to nonlinear problems with convex constraints.

Keywords: Nonlinear optimization, convex constraints, cubic regularisation, numerical algorithms, global convergence, worst-case complexity.

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Nonlinear Optimization (Bound-constrained Optimization )

Citation: Technical Report 08/05R, Department of Mathematics, FUNDP-Unviversity of Namur, Namur, Belgium

Download: [PDF]

Entry Submitted: 02/20/2009
Entry Accepted: 02/20/2009
Entry Last Modified: 02/20/2009

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 Programming Society