{"ID":2822586,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2601.02134","arxiv_id":"2601.02134","title":"Complexity of quadratic penalty methods with adaptive accuracy under a PL condition for the constraints","abstract":"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(\\varepsilon_{0}^{-1}\\varepsilon_{1}^{-2})$ first-order oracle calls to find an $(\\varepsilon_{0},\\varepsilon_{1})$-approximate KKT point -- that is, a point that is $\\varepsilon_{0}$-approximately feasible and $\\varepsilon_{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(\\varepsilon_{0}^{-1/2}\\varepsilon_{1}^{-3/2}\\right)$ second-order oracle calls to find an $(\\varepsilon_{0},\\varepsilon_{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.","short_abstract":"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 co...","url_abs":"https://arxiv.org/abs/2601.02134","url_pdf":"https://arxiv.org/pdf/2601.02134v1","authors":"[\"Florentin Goyens\",\"Geovani N. Grapiglia\"]","published":"2026-01-05T14:06:53Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}