Inexact Moreau Envelope Augmented Lagrangian Method for Nonconvex Robust Constrained Optimization

Many machine learning applications involve various constraints, motivating the study of nonconvex constrained optimization problems. The problem becomes even more challenging when the constraints must be robustly satisfied, leading to robust constrained optimization. In this paper, we propose an inexact Moreau Envelope Augmented Lagrangian (iMEAL) method and analyze its iteration complexity. The Moreau envelope is employed to smooth the robust constraints, enabling the use of first-order methods within the augmented Lagrangian framework. Our approach leverages a proximal gradient subroutine combined with a minimax optimization procedure to approximate the Moreau envelope efficiently. Under a regularity condition, we establish a complexity bound $\mathcal{O}(\epsilon_c^{-1}\epsilon_{\mathcal{L}}^{-2})$ for obtaining an $(\epsilon_c, \epsilon_{\mathcal{L}})$-KKT point of the original problem.