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 separated into two phases: decreasing infeasibility (feasibility phase) and improving solution (optimality phase). The feasibility phase does not require the generated points to be exactly feasible, so it has a practical appeal. In turn, the optimization phase consists of minimizing a simplified model of the problem over a linearization of the feasible set. In this paper, we introduce a novel optimization phase through a new 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 points (CAKKT). This global convergence result improves all previous ones for this class of methods. In particular, convergence to KKT is established with the very weak CAKKT-regularity condition. Furthermore, and to the best of our knowledge, this is the first time that a method for general nonlinear programming reaches CAKKT points without exogenous assumptions. From the practical point of view, the new optimization phase does not aggregate additional computational effort compared to the usual one. Our theory also gives us a new insight, even for the classical IR method, for cases where it is reasonable to compute exact feasible points in the feasibility phase. Numerical experiments on CUTEst problems are provided.

Article

Download

View Improving the global convergence of Inexact Restoration methods for constrained optimization problems