A Telescopic Method with Guaranteed B-Stationarity for Partitioned Cardinality and Complementarity Constraints
Abstract
We consider the minimization of a smooth function subject to box constraints and partitioned cardinality constraints (PCC): the variables are divided into groups and, within each group, at most a prescribed number of variables may be non-zero. This class contains bound-constrained minimization, cardinality-constrained minimization and bound-constrained mathematical programs with complementarity constraints. We introduce the Telescopic Method, which alternates iterations of a bound-constrained method on the faces of the feasible set with inexpensive one-dimensional "escaping" tests that exchange a variable of the current face by a currently null one within the same group. We prove, without constraint qualifications and without requiring global solutions of subproblems, that every limit point of the generated sequence is B-stationary, i.e., it satisfies the first-order condition defined by the tangent cone of the feasible set. This guarantee is obtained with exchanges of a single variable, whatever the number of non-null entries of the limit point, because B-stationarity for this class of problems decomposes into conditions on single variables. On the 60 bound-constrained mathematical programs with complementarity constraints of the test set of Kirches, Larson, Leyffer and Manns, the method found approximately B-stationary points in all the problems. Applications to separable regression, sparse polynomial approximation and portfolio selection are described and tested numerically.
Related
- Augmented Lagrangian methods with telescopic subproblems for MPCCs and cardinality constraints with general constraints: constraint-preserving swaps and B-stationarity
- Randomized Branch Methods with Inexact Subproblems for Bouligand Stationarity in Linear and Quadratic Programs with Complementarity Constraints
- A Smoothed Augmented Lagrangian Method for Mathematical Programs with Vertical Complementarity Constraints
- Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
- Augmented Lagrangian Method for Mathematical Programs with Second-Order Cone Complementarity Constraints
BibTeX
@misc{birgin2026telescopic,
title = {{A Telescopic Method with Guaranteed B-Stationarity for Partitioned Cardinality and Complementarity Constraints}},
author = {Ernesto G. Birgin and J. M. Martínez},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00897},
eprint = {2611.00897},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00897},
}
RIS
TY - UNPB
TI - A Telescopic Method with Guaranteed B-Stationarity for Partitioned Cardinality and Complementarity Constraints
AU - Ernesto G. Birgin
AU - J. M. Martínez
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00897
UR - https://arxiv.org/abs/2611.00897
AB - We consider the minimization of a smooth function subject to box constraints and partitioned cardinality constraints (PCC): the variables are divided into groups and, within each group, at most a prescribed number of variables may be non-zero. This class contains bound-constrained minimization, cardinality-constrained minimization and bound-constrained mathematical programs with complementarity constraints. We introduce the Telescopic Method, which alternates iterations of a bound-constrained method on the faces of the feasible set with inexpensive one-dimensional "escaping" tests that exchange a variable of the current face by a currently null one within the same group. We prove, without constraint qualifications and without requiring global solutions of subproblems, that every limit point of the generated sequence is B-stationary, i.e., it satisfies the first-order condition defined by the tangent cone of the feasible set. This guarantee is obtained with exchanges of a single variable, whatever the number of non-null entries of the limit point, because B-stationarity for this class of problems decomposes into conditions on single variables. On the 60 bound-constrained mathematical programs with complementarity constraints of the test set of Kirches, Larson, Leyffer and Manns, the method found approximately B-stationary points in all the problems. Applications to separable regression, sparse polynomial approximation and portfolio selection are described and tested numerically.
ER -