IMPROVING THE GLOBAL CONVERGENCE OF INEXACT RESTORATION METHODS FOR CONSTRAINED OPTIMIZATION PROBLEMS

Inexact restoration (IR) methods are an important family of numerical methods for solving constrained optimization problems with applications to electronic structures and bilevel programming, among others areas. In these methods, the minimization is divided in two phases: decreasing infeasibility (feasibility phase) and improving optimality (optimality phase). The feasibility phase does not require the generated points to be feasible, so it has a practical appeal. In turn, the optimization phase involves minimizing a simplified model of the problem over a linearization of the feasible set. In this paper, we introduce a new optimization phase through a novel linearization that carries more information about complementarity than that employed in previous IR strategies. We then prove that the resulting algorithmic scheme is able to converge globally to the so-called complementary approximate KKT (CAKKT) points. This global convergence result improves upon all previous results for this class of methods. In particular, convergence to KKT points is established with the very weak CAKKT-regularity condition. Furthermore, to the best of our knowledge, this is the first time that a method for general nonlinear programming has reached CAKKT points without exogenous assumptions. From the practical point of view, the new optimization phase does not require significant additional computational effort compared to the usual one. Our theory also provides new insights, even for the classical IR method, for cases where it is reasonable to compute exact feasible points in the feasibility phase. We present numerical experiments on CUTEst problems to support our findings.