Complexity of quadratic penalty methods with adaptive accuracy under a PL condition for the constraints

We study the quadratic penalty method (QPM) for smooth nonconvex optimization problems with equality constraints. Assuming the constraint violation satisfies the PL condition near the feasible set, we derive sharper worst-case complexity bounds for obtaining approximate first-order KKT points. When the objective and constraints are twice continuously differentiable, we show that QPM equipped with a suitable first-order inner solver requires at most $O({\epsilon }_0^{-1}{\epsilon }_1^{-2})$ first-order oracle calls to find an $({\epsilon }_0,{\epsilon }_1)$-approximate KKT point – that is, a point that is ${\epsilon }_0$-approximately feasible and ${\epsilon }_1$-approximately stationary. Furthermore, when the objective and constraints are three times continuously differentiable, we show that QPM with a suitable second-order inner solver requires at most $O\left({\epsilon }_0^{-1\mathrm{/}2}{\epsilon }_1^{-3\mathrm{/}2}\right)$ second-order oracle calls to find an $({\epsilon }_0,{\epsilon }_1)$-approximate KKT point. We also introduce an adaptive, feasibility-aware stopping criterion for the subproblems, which relaxes the stationarity tolerance when far from feasibility. This rule preserves all theoretical guarantees while substantially reducing computational effort in practice.