Complexity of quadratic penalty methods with adaptive accuracy under a PL condition for the constraints
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915708498083840 |
|---|---|
| author | Goyens, Florentin Grapiglia, Geovani N. |
| author_facet | Goyens, Florentin Grapiglia, Geovani N. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_02134 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Complexity of quadratic penalty methods with adaptive accuracy under a PL condition for the constraints Goyens, Florentin Grapiglia, Geovani N. Optimization and Control 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. |
| title | Complexity of quadratic penalty methods with adaptive accuracy under a PL condition for the constraints |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2601.02134 |