Randomized Branch Methods with Inexact Subproblems for Bouligand Stationarity in Linear and Quadratic Programs with Complementarity Constraints
Abstract
We develop randomized branch methods for finding Bouligand-stationary (B-stationary) points of linear and quadratic programs with complementarity constraints (LPCCs and QPCCs) using only linear programming subproblems. The methods exploit the finite-union geometry of the feasible set and search for first-order descent on randomly selected compatible branches. For LPCCs, an exact method optimizes over sampled branches, while an inexact simplex method can accept an improving branch-feasible vertex before solving the sampled penalty problem to optimality. For QPCCs, including problems with indefinite quadratic objectives, branch quadratic programs are replaced by linearized trust-region subproblems; a ratio test ensures actual decrease, and thresholded sampling detects branches that emerge only at accumulation points. Under the stated assumptions, the LPCC methods stabilize after finitely many changes at B-stationary points almost surely. For the QPCC method, finite termination yields a B-stationary point, and every accumulation point of an infinite run is B-stationary almost surely. Experiments on bilevel-induced instances, instances arising from inverse quadratic programming, and sparse affine generalized Nash equilibrium instances, together with 129 MacMPEC embedding tests, show that the methods return points with competitive objective quality and runtimes on large-scale complementarity systems.
Related
- Augmented Lagrangian methods with telescopic subproblems for MPCCs and cardinality constraints with general constraints: constraint-preserving swaps and B-stationarity
- A Telescopic Method with Guaranteed B-Stationarity for Partitioned Cardinality and Complementarity Constraints
- A sequential quadratic programming method for optimization with expectation objective functions, deterministic inequality constraints and robust subproblems
- A Smoothed Augmented Lagrangian Method for Mathematical Programs with Vertical Complementarity Constraints
- Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
BibTeX
@misc{hu2026randomized,
title = {{Randomized Branch Methods with Inexact Subproblems for Bouligand Stationarity in Linear and Quadratic Programs with Complementarity Constraints}},
author = {Ziyin Hu and Xin Liu and Shangzhi Zeng and Jin Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29888},
eprint = {2609.29888},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29888},
}
RIS
TY - UNPB
TI - Randomized Branch Methods with Inexact Subproblems for Bouligand Stationarity in Linear and Quadratic Programs with Complementarity Constraints
AU - Ziyin Hu
AU - Xin Liu
AU - Shangzhi Zeng
AU - Jin Zhang
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.29888
UR - https://arxiv.org/abs/2609.29888
AB - We develop randomized branch methods for finding Bouligand-stationary (B-stationary) points of linear and quadratic programs with complementarity constraints (LPCCs and QPCCs) using only linear programming subproblems. The methods exploit the finite-union geometry of the feasible set and search for first-order descent on randomly selected compatible branches. For LPCCs, an exact method optimizes over sampled branches, while an inexact simplex method can accept an improving branch-feasible vertex before solving the sampled penalty problem to optimality. For QPCCs, including problems with indefinite quadratic objectives, branch quadratic programs are replaced by linearized trust-region subproblems; a ratio test ensures actual decrease, and thresholded sampling detects branches that emerge only at accumulation points. Under the stated assumptions, the LPCC methods stabilize after finitely many changes at B-stationary points almost surely. For the QPCC method, finite termination yields a B-stationary point, and every accumulation point of an infinite run is B-stationary almost surely. Experiments on bilevel-induced instances, instances arising from inverse quadratic programming, and sparse affine generalized Nash equilibrium instances, together with 129 MacMPEC embedding tests, show that the methods return points with competitive objective quality and runtimes on large-scale complementarity systems.
ER -