Simple unified convergence proofs for Trust Region and a new ARC variant, and implementation issues

We provide a simple convergence analysis unified for TR and a new ARC algorithms, which we name ARCq and which is very close in spirit to trust region methods, closer than the original ARC is. We prove global convergence to second order points. We also obtain as a corollary the convergence of the original ARC method. Since one of our aims is to achieve a simple presentation, we sacrifice some generality which we discuss at the end of our developments. In this simplified setting, we prove the optimal complexity property for the ARCq and identify the key elements which allow it. We then propose efficient implementations using a Cholesky like factorization as well as a scalable version based on conjugate gradients.