On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
Abstract
Distributionally Favorable Optimization (DFO) is a framework for decision-making under uncertainty, with applications spanning various fields, including reinforcement learning, online learning, robust statistics, chance-constrained programming, and two-stage stochastic optimization without complete recourse. In contrast to the traditional Distributionally Robust Optimization (DRO) paradigm, DFO presents a unique challenge– the application of the inner infimum operator often fails to retain the convexity. In light of this challenge, we study the tractability and complexity of DFO. We establish sufficient and necessary conditions for determining when DFO problems are tractable (i.e., solvable in polynomial time) or intractable (i.e., not solvable in polynomial time). Despite the typical nonconvex nature of DFO problems, our results show that they are mixed-integer convex programming representable (MICP-R), thereby enabling solutions via standard optimization solvers. Finally, we numerically validate the efficacy of our MICP-R formulations.
Related
- A Composite Bayesian Risk--Distributionally Robust Optimization Model for Stochastic Programming with Elliptical Distribution Ambiguity
- Data-driven joint optimization of maintenance and spare parts provisioning: A distributionally robust approach
- Conformal-DRO: Distributionally Robust Optimization with Conformalized Ambiguity Set
- Calibrating Ambiguity Set via Diagnostic Transport for Distributionally Robust Optimization
- Higher-Order Sensitivity Analysis of Wasserstein and Adapted Wasserstein Distributionally Robust Optimization Problems
BibTeX
@article{jiang2026tractability,
title = {{On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization}},
author = {Nan Jiang and Weijun Xie},
journal = {Mathematical Programming},
year = {2026},
month = oct,
doi = {10.1007/s10107-025-02299-w},
url = {https://hal.science/hal-05783682v1},
note = {CC BY},
}
RIS
TY - JOUR
TI - On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
AU - Nan Jiang
AU - Weijun Xie
PY - 2026
DA - 2026/10/07
JO - Mathematical Programming
DO - 10.1007/s10107-025-02299-w
UR - https://hal.science/hal-05783682v1
AB - Distributionally Favorable Optimization (DFO) is a framework for decision-making under uncertainty, with applications spanning various fields, including reinforcement learning, online learning, robust statistics, chance-constrained programming, and two-stage stochastic optimization without complete recourse. In contrast to the traditional Distributionally Robust Optimization (DRO) paradigm, DFO presents a unique challenge– the application of the inner infimum operator often fails to retain the convexity. In light of this challenge, we study the tractability and complexity of DFO. We establish sufficient and necessary conditions for determining when DFO problems are tractable (i.e., solvable in polynomial time) or intractable (i.e., not solvable in polynomial time). Despite the typical nonconvex nature of DFO problems, our results show that they are mixed-integer convex programming representable (MICP-R), thereby enabling solutions via standard optimization solvers. Finally, we numerically validate the efficacy of our MICP-R formulations.
SN - 0025-5610
SN - 1436-4646
ER -