New classes of adaptive cubic regularization algorithms for unconstrained optimization

The adaptive cubic regularization of Newton method gives rise to a local cubic overestimator of the objective function f which is employed for computing the step from one iterate to the next one. Under mild assumptions, ARC iterates converge to first-order critical points; by strengthening the conditions on the acceptance of the trial step, second-order variants of ARC show global and fast convergence to second-order critical points. A strategy that fits into ARC framework is introduced, thus retaining its worst-case complexity count. This can be done with any arbitrarily computed approximate minimizer for the model. To achieve this goal the approximate minimization of the model is combined, if necessary, with the exact optimization of the model in a suitable one-dimensional space. Further, is presented a new termination criterion (called early stopping) which monitors the value of f along the minimization of the model and can prevent an over-solving phenomenon when the objective function is not adequately represented by the cubic model. This thesis also investigates the use of nonmonotone techniques within the ARC framework. A nonmonotone variant of the ARC algorithm is introduced, its convergence properties are discussed and some numerical results on the comparison against the monotone version are presented.