Technical Report ERGO 09-004

An adaptive cubic regularisation algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity
Coralia Cartis, Nicholas I. M. Gould and Philippe L. Toint


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.


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




Written: 20 February 2009


Published in IMA Journal of Numerical Analysis.