We consider solving equality-constrained nonlinear, nonconvex optimization
problems. This class of problems appears widely in a variety of applications in
machine learning and engineering, ranging from constrained deep neural
networks, to optimal control, to PDE-constrained optimization. We develop an
adaptive inexact Newton method for this problem class. In each iteration, we
solve the Lagrangian Newton system inexactly via a randomized iterative
sketching solver, and select a suitable stepsize by performing line search on
an exact augmented Lagrangian merit function. The randomized solvers have
advantages over deterministic linear system solvers by significantly reducing
per-iteration flops complexity and storage cost, when equipped with suitable
sketching matrices. Our method adaptively controls the accuracy of the
randomized solver and the penalty parameters of the exact augmented Lagrangian,
to ensure that the inexact Newton direction is a descent direction of the exact
augmented Lagrangian. This allows us to establish a global almost sure
convergence. We also show that a unit stepsize is admissible locally, so that
our method exhibits a local linear convergence. Furthermore, we prove that the
linear convergence can be strengthened to superlinear convergence if we
gradually sharpen the adaptive accuracy condition on the randomized solver. We
demonstrate the superior performance of our method on benchmark nonlinear
problems in CUTEst test set, constrained logistic regression with data from
LIBSVM, and a PDE-constrained problem.

本篇研究开发了一种自适应的非精确牛顿法，通过使用随机迭代草图求解器不精确地求解拉格朗日牛顿系统，并在精确增广拉格朗日优势函数上执行线搜索以选择适当的步长，以控制随机求解器的精度和惩罚参数，以确保不精确的牛顿方向是精确增广拉格朗日的下降方向，从而全局近乎确定地收敛，并表明在本地可采用单位步长，因此该方法表现出局部线性收敛。