Metraipolis › archive › dc_c8ae01f9868c

Randomized Branch Methods with Inexact Subproblems for Bouligand Stationarity in Linear and Quadratic Programs with Complementarity Constraints — arXiv:2609.29888

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.29888
License (as archived)
CC0-1.0
Archived
2026-10-08T06:07:19.061Z
SHA-256 of the archived text
15af06ed9fba90a74cf8015caaac6ffd511a00db366d25a47c877f6c978df227
Stable URL of this page
https://metraipolis.com/documento/dc_c8ae01f9868c

How to cite

Randomized Branch Methods with Inexact Subproblems for Bouligand Stationarity in Linear and Quadratic Programs with Complementarity Constraints — arXiv:2609.29888 — arXiv (en), https://arxiv.org/abs/2609.29888 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c8ae01f9868c (Metraipolis archive dc_c8ae01f9868c, sha256 15af06ed9fba90a74cf8015caaac6ffd511a00db366d25a47c877f6c978df227)
BibTeX
@misc{dcc8ae01f9868c,
  title = {Randomized Branch Methods with Inexact Subproblems for Bouligand Stationarity in Linear and Quadratic Programs with Complementarity Constraints — arXiv:2609.29888},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.29888},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c8ae01f9868c; sha256 15af06ed9fba90a74cf8015caaac6ffd511a00db366d25a47c877f6c978df227},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29888. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.29888 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T05:31:31.167Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).