An Augmented Lagrangian Approach to Bi-Level Optimization via a Smooth Equilibrium Constrained Problem

Abstract Optimization problems involving smooth equilibrium constraints capture diverse optimization settings such as bi-level optimization, min-max problems and games, and the minimization over non-linear constraints. This paper introduces an Augmented Lagrangian approach with Hessian-vector product approximation to address an equilibrium constrained nonconvex nonsmooth optimization problem in which the equilibrium constraint is given by nonlinear equality constraints originating from the Fermat Condition of a continuously differentiable function. The underlying model in particular captures various settings of bi-level optimization problems, including those in which the inner problem may have a non-singleton set of optimal solutions. The proposed method attains approximated critical points and enjoys a standard rate of convergence after stabilization. It does not require double-loops, nested procedures, nor any Hessian computation, and subsequently bypasses any matrix storage requirements. We complement the theoretical results with numerical illustrations demonstrating the implementation of our method in a bi-level application and test problem.