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

               C. Cartis, N. I. M. Gould and Ph. L. Toint
                    Report TR08/05R, February 2009

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.