Nonsmooth exact penalty methods for equality-constrained optimization: complexity and implementation

Penalty methods are a well-known class of algorithms for constrained optimization. They transform a constrained problem into a sequence of unconstrained penalized problems in the hope that approximate solutions of the latter converge to a solution of the former. If Lagrange multipliers exist, exact penalty methods ensure that the penalty parameter only need increase a finite number of times, but they are typically scorned in smooth optimization because the penalized problems are not smooth. This led researchers to consider the implementation of exact penalty methods inconvenient. Recent advances in proximal methods have led to increasingly efficient solvers for nonsmooth optimization. We study a general exact penalty algorithm and use it to show that the exact l₂₋ penalty method for equality-constrained optimization can, in fact, be implemented efficientlyby solving the penalized problem using a proximal-type algorithm. We study the convergence of ouralgorithm and establish a worst-case complexity bound of O (∈⁻²) to bring a stationarity measure below ∈ > 0 under the Mangasarian--Fromovitz constraint qualification and Lipschitz continuity ofthe objective gradient and constraint Jacobian. While the Lipschitz continuity of the objectivegradient is not required for convergence in view of recent works, it is used in our analysis to derivethe complexity bound. In a degenerate scenario where the penalty parameter grows unbounded,the complexity becomes O (∈⁻⁸), which is worse than another bound found in the literature. Wejustify the difference by arguing that our feasibility measure is properly scaled. Finally, we reportnumerical experience on small-scale problems from a standard collection and compare our solverwith an augmented-Lagrangian and an SQP method. Our preliminary implementation is superiorto the augmented Lagrangian in terms of robustness and efficiency and is competitive with the SQPmethod in terms of robustness, though the latter retains a slight edge in terms of number of problemfunction evaluations.