Tightly Robust Optimization via Empirical Domain Reduction
This work addresses the challenge of robust decision-making under uncertainty for optimization practitioners, offering a method that is less affected by high-dimensional parameters, though it appears incremental as it builds on existing robust optimization frameworks.
The paper tackles the problem of determining the robustness scale in data-driven optimization to ensure solutions satisfy true constraints with high probability, proposing an algorithm that achieves an asymptotic scale of O(1/√n), outperforming the standard O(√d/n) approach by reducing sensitivity to parameter dimensionality.
Data-driven decision-making is performed by solving a parameterized optimization problem, and the optimal decision is given by an optimal solution for unknown true parameters. We often need a solution that satisfies true constraints even though these are unknown. Robust optimization is employed to obtain such a solution, where the uncertainty of the parameter is represented by an ellipsoid, and the scale of robustness is controlled by a coefficient. In this study, we propose an algorithm to determine the scale such that the solution has a good objective value and satisfies the true constraints with a given confidence probability. Under some regularity conditions, the scale obtained by our algorithm is asymptotically $O(1/\sqrt{n})$, whereas the scale obtained by a standard approach is $O(\sqrt{d/n})$. This means that our algorithm is less affected by the dimensionality of the parameters.