Soft Separation for Adaptive Robust Optimization
Abstract
We propose an algorithmic framework for solving adaptive robust optimization with provable guarantees on both tractability and solution accuracy. The framework introduces soft separation, a probabilistic mechanism for identifying worst-case uncertainty realizations via a time-inhomogeneous Markov chain. Rather than solving an exact separation problem in each iteration, which is intractable in general, the chain carries adversarial information across iterations, co-evolves with the optimization iterates, and recovers exact separation at terminal iterates with high probability. For continuous first-stage (here-and-now) decisions, we design a first-order method that uses soft separation to produce adaptive gradient estimates. Notably, we prove polynomial-time convergence in expectation to the global optimum. For mixed-integer here-and-now decisions, we embed soft separation within a branch-and-cut framework to generate valid cuts for the robust objective and obtain a high-probability certificate of global optimality. Numerical experiments demonstrate that the proposed methods scale favorably with problem dimension and scenario size relative to state-of-the-art approaches. The instances and code are available online at https://github.com/xuqy2002/SoftSeparationARO.
Related
- Partially Adaptive Robust Optimization for Uncertain Fluid Processing Networks
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
- The Unified Separation Condition: A General Constraint Qualification for Smooth and Nonsmooth Optimization
- One Probability, Two Roles: The Separation of Coherence and Frequency in Adaptive Regimes
- Adjustable Robust Optimization with Discrete Uncertainty
BibTeX
@misc{xu2026soft,
title = {{Soft Separation for Adaptive Robust Optimization}},
author = {Qingyuan Xu and Ruiwei Jiang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36275},
eprint = {2609.36275},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36275},
}
RIS
TY - UNPB
TI - Soft Separation for Adaptive Robust Optimization
AU - Qingyuan Xu
AU - Ruiwei Jiang
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.36275
UR - https://arxiv.org/abs/2609.36275
AB - We propose an algorithmic framework for solving adaptive robust optimization with provable guarantees on both tractability and solution accuracy. The framework introduces soft separation, a probabilistic mechanism for identifying worst-case uncertainty realizations via a time-inhomogeneous Markov chain. Rather than solving an exact separation problem in each iteration, which is intractable in general, the chain carries adversarial information across iterations, co-evolves with the optimization iterates, and recovers exact separation at terminal iterates with high probability. For continuous first-stage (here-and-now) decisions, we design a first-order method that uses soft separation to produce adaptive gradient estimates. Notably, we prove polynomial-time convergence in expectation to the global optimum. For mixed-integer here-and-now decisions, we embed soft separation within a branch-and-cut framework to generate valid cuts for the robust objective and obtain a high-probability certificate of global optimality. Numerical experiments demonstrate that the proposed methods scale favorably with problem dimension and scenario size relative to state-of-the-art approaches. The instances and code are available online at https://github.com/xuqy2002/SoftSeparationARO.
ER -