Augmented Lagrangian methods with telescopic subproblems for MPCCs and cardinality constraints with general constraints: constraint-preserving swaps and B-stationarity
Abstract
We consider optimization problems with general equality and inequality constraints and partitioned cardinality constraints, which include complementarity constraints. In the augmented Lagrangian method that we consider, the bounds and the cardinality constraints are kept in the subproblems, which are solved by the Telescopic Method. The limit points of this method are B-stationary, without constraint qualifications, if the penalty parameters remain bounded, but not in general. The reason is that the swaps of the Telescopic Method pass through points at which the constraints have different values, and the corresponding variation of the penalty term grows with the penalty parameter. With unbounded penalty parameters and a derivative test outside the current face, the feasible limit points at which a linear independence constraint qualification holds are M-stationary for MPCCs. We modify the swaps, by means of a scaled Newton restoration, so that they preserve the values of the constraints, and we prove that every feasible limit point at which this constraint qualification holds is then B-stationary (S-stationary for MPCCs), whatever the behavior of the penalty parameters. Counterexamples show that the modification is necessary, even with exact solutions of the subproblems, and that the constraint qualification cannot be weakened to one of Mangasarian-Fromovitz type. In the MacMPEC collection, the method found certified S- or B-stationary points in 185 of the 193 instances, more than Algencan and the regularization method of Scholtes. In experiments with cardinality-constrained portfolios and sparse principal component analysis, the constraint-preserving swaps improved the original swaps and the methods applied to complementarity reformulations.
Related
- A Telescopic Method with Guaranteed B-Stationarity for Partitioned Cardinality and Complementarity Constraints
- Randomized Branch Methods with Inexact Subproblems for Bouligand Stationarity in Linear and Quadratic Programs with Complementarity Constraints
- Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
- A Smoothed Augmented Lagrangian Method for Mathematical Programs with Vertical Complementarity Constraints
- Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
BibTeX
@misc{birgin2026augmented,
title = {{Augmented Lagrangian methods with telescopic subproblems for MPCCs and cardinality constraints with general constraints: constraint-preserving swaps and B-stationarity}},
author = {Ernesto G. Birgin and J. M. Martínez},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08404},
eprint = {2611.08404},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08404},
}
RIS
TY - UNPB
TI - Augmented Lagrangian methods with telescopic subproblems for MPCCs and cardinality constraints with general constraints: constraint-preserving swaps and B-stationarity
AU - Ernesto G. Birgin
AU - J. M. Martínez
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.08404
UR - https://arxiv.org/abs/2611.08404
AB - We consider optimization problems with general equality and inequality constraints and partitioned cardinality constraints, which include complementarity constraints. In the augmented Lagrangian method that we consider, the bounds and the cardinality constraints are kept in the subproblems, which are solved by the Telescopic Method. The limit points of this method are B-stationary, without constraint qualifications, if the penalty parameters remain bounded, but not in general. The reason is that the swaps of the Telescopic Method pass through points at which the constraints have different values, and the corresponding variation of the penalty term grows with the penalty parameter. With unbounded penalty parameters and a derivative test outside the current face, the feasible limit points at which a linear independence constraint qualification holds are M-stationary for MPCCs. We modify the swaps, by means of a scaled Newton restoration, so that they preserve the values of the constraints, and we prove that every feasible limit point at which this constraint qualification holds is then B-stationary (S-stationary for MPCCs), whatever the behavior of the penalty parameters. Counterexamples show that the modification is necessary, even with exact solutions of the subproblems, and that the constraint qualification cannot be weakened to one of Mangasarian-Fromovitz type. In the MacMPEC collection, the method found certified S- or B-stationary points in 185 of the 193 instances, more than Algencan and the regularization method of Scholtes. In experiments with cardinality-constrained portfolios and sparse principal component analysis, the constraint-preserving swaps improved the original swaps and the methods applied to complementarity reformulations.
ER -