arXiv preprint ·
Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Chance-constrained stochastic programs (CCSPs) require solutions that satisfy uncertain constraints with high probability. Standard approaches either embed scenarios directly into optimization by considering sample average approximation (SAA)-based reformulations, growing prohibitively expensive and often failing to find feasible solutions; or employ conservative reformulations that guarantee feasibility but sacrifice objective quality by design. We propose ACCESS (Adaptive Chance-Constrained Exploration via Structured Sampling), a structured sampling framework that decouples optimization from feasibility evaluation. First, high-quality candidate solutions are generated by solving many inexpensive single-scenario subproblems, avoiding sampling directly in the constrained high-dimensional solution space. Second, feasibility is assessed separately via large-scale batched simulation over a massive number of scenarios, which is naturally amenable to GPU parallelism. That reduces the search from a high-dimensional solution space to a two-dimensional parameter space controlling conservatism and scenario diversity; while concentrating on candidates near the feasibility boundary, where high-quality feasible solutions lie. We also introduce a variant, ACCESS($δ$), which provides certified feasibility guarantees with probability $1-δ$. Experiments across three benchmark classes and five scenario distributions show that ACCESS matches or exceeds the best objective found by any method in nearly every setting, while ACCESS($δ$) is empirically feasible on every instance. The conservative reformulations remain several percent worse in objective, and SAA is frequently infeasible while taking an order of magnitude longer on the harder benchmarks.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Convex-Analytic View of Query Selection for Safety Verification of Markov Decision Processes
Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
Risk-Averse Inference-Time Diffusion Model Alignment with Finite-Sample Guarantees
On the Optimisation Landscape of Overparameterised Weighted MMD
On integrability of local utility maximizing strategies
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.