Active set identification and rapid convergence for degenerate primal-dual problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917266804703232 |
|---|---|
| author | Díaz, Mateo Lehmann, Pedro Izquierdo Lu, Haihao Yang, Jinwen |
| author_facet | Díaz, Mateo Lehmann, Pedro Izquierdo Lu, Haihao Yang, Jinwen |
| contents | Primal-dual methods for solving convex optimization problems with functional constraints often exhibit a distinct two-stage behavior. Initially, they converge towards a solution at a sublinear rate. Then, after a certain point, the method identifies the set of active constraints and the convergence enters a faster local linear regime. Theory characterizing this phenomenon spans over three decades. However, most existing work only guarantees eventual identification of the active set and relies heavily on nondegeneracy conditions, such as strict complementarity, which often fail to hold in practice. We characterize mild conditions on the problem geometry and the algorithm under which this phenomenon provably occurs. Our guarantees are entirely nonasymptotic and, importantly, do not rely on strict complementarity. Our framework encompasses several widely-used algorithms, including the proximal point method, the primal-dual hybrid gradient method, the alternating direction method of multipliers, and the extragradient method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10436 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Active set identification and rapid convergence for degenerate primal-dual problems Díaz, Mateo Lehmann, Pedro Izquierdo Lu, Haihao Yang, Jinwen Optimization and Control 90C25, 90C06, 90C47, 65K05, 65K10 G.1.6 Primal-dual methods for solving convex optimization problems with functional constraints often exhibit a distinct two-stage behavior. Initially, they converge towards a solution at a sublinear rate. Then, after a certain point, the method identifies the set of active constraints and the convergence enters a faster local linear regime. Theory characterizing this phenomenon spans over three decades. However, most existing work only guarantees eventual identification of the active set and relies heavily on nondegeneracy conditions, such as strict complementarity, which often fail to hold in practice. We characterize mild conditions on the problem geometry and the algorithm under which this phenomenon provably occurs. Our guarantees are entirely nonasymptotic and, importantly, do not rely on strict complementarity. Our framework encompasses several widely-used algorithms, including the proximal point method, the primal-dual hybrid gradient method, the alternating direction method of multipliers, and the extragradient method. |
| title | Active set identification and rapid convergence for degenerate primal-dual problems |
| topic | Optimization and Control 90C25, 90C06, 90C47, 65K05, 65K10 G.1.6 |
| url | https://arxiv.org/abs/2602.10436 |