Metraipolis › archive › dc_e8eb3a9888ea

When Is Two-Stage Sample Robust Optimization Asymptotically Optimal? A Simple Perspective — arXiv:2608.22999

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.22999
License (as archived)
CC0-1.0
Archived
2026-10-18T08:25:43.987Z
SHA-256 of the archived text
edb216471e3a0bfe5bd4f9261402d1a68532cd1dd0a6f1e14d00eb6658edc45c
Stable URL of this page
https://metraipolis.com/documento/dc_e8eb3a9888ea

How to cite

When Is Two-Stage Sample Robust Optimization Asymptotically Optimal? A Simple Perspective — arXiv:2608.22999 — arXiv (en), https://arxiv.org/abs/2608.22999 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e8eb3a9888ea (Metraipolis archive dc_e8eb3a9888ea, sha256 edb216471e3a0bfe5bd4f9261402d1a68532cd1dd0a6f1e14d00eb6658edc45c)
BibTeX
@misc{dce8eb3a9888ea,
  title = {When Is Two-Stage Sample Robust Optimization Asymptotically Optimal? A Simple Perspective — arXiv:2608.22999},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.22999},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e8eb3a9888ea; sha256 edb216471e3a0bfe5bd4f9261402d1a68532cd1dd0a6f1e14d00eb6658edc45c},
  year = {2026}
}

Archived text

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

Two-stage sample robust optimization with linear decision rules is a standard data-driven approach to two-stage stochastic linear programs with unknown distributions. \cite{bertsimas2022two} established that this approach is asymptotically optimal under several conditions. Most are mild, but one is technical, and whether it follows from the others was left as an open question. We resolve this open question through a single geometric feature of the support set: simpleness, the property that every vertex is incident to exactly as many edges as the ambient dimension. When the support set is simple, the technical condition is automatic, and asymptotic optimality holds under the remaining standard assumptions. When the support set is not simple, there exists a problem instance on which the technical condition fails, and asymptotic optimality breaks down. This settles the open question in the negative and yields a sharp dichotomy. The dichotomy has direct practical consequences, since widely used support sets may not be simple. For such supports, we provide a polynomial-time algorithm that certifies the technical condition at any given vertex using only its incident edge directions. Our case study illustrates the effectiveness of our algorithm.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-25 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.22999 — 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-18T08:18:05.705Z dalla pagina https://arxiv.org/catchup/math.OC/2026-08-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).