Abstract: We tackle robust optimization problems under objective uncertainty in the oracle model, i.e., when the deterministic problem is solved by an oracle. The oracle-based setup is favorable in many situations, e.g., when a compact formulation of the feasible region is unknown or does not exist. We propose an iterative method based on a Frank-Wolfe type algorithm applied to a smoothed version of the piecewise linear objective function. Our approach bridges several previous efforts from the literature, attains the best known oracle complexity for the problem and performs better than state-of-the-art on high-dimensional problem instances, in particular for larger uncertainty sets.
Introduction
In the field of optimization, Robust Optimization (RO) is a critical framework for making decisions that remain effective under parameter uncertainty (such as fluctuating costs or demands). Traditionally, solving RO problems requires a clear, polynomial-sized mathematical description of the feasible region—the set of all valid solutions.
However, many complex real-world problems, such as the Traveling Salesperson Problem (TSP) or intricate network designs, lack a simple list of linear equations to describe their feasible sets. In these cases, we often rely on an oracle: a specialized "black box" algorithm capable of solving the deterministic version of the problem efficiently. The challenge lies in the fact that existing oracle-based methods, like "Constraint Generation," often scale poorly. These methods solve auxiliary linear programs that grow in size and complexity with every iteration, eventually stalling as the problem dimensions increase. This paper introduces a more scalable, iterative approach to leverage these oracles without the computational overhead of traditional methods.
The Smoothing Frank-Wolfe Approach
The authors propose a method centered on the Frank-Wolfe (FW) algorithm, a classic optimization technique valued for its "projection-free" nature. Their framework integrates three primary components to adapt FW for robust optimization:
- Objective Smoothing: Robust objective functions are typically piecewise linear and non-differentiable because they account for the worst-case scenario. To navigate this "jagged" landscape, the authors employ Nesterov’s smoothing technique, transforming the objective into a smooth, differentiable function.
- Adaptive Smoothing: The algorithm utilizes a dynamic smoothness parameter that evolves over time. This allows for large, exploratory steps in the early stages and increasingly precise refinements as the algorithm converges toward the optimum.
- The Oracle Link: Unlike methods requiring a full map of the feasible region, this algorithm only requires the oracle to provide a single linear optimization solution per step. By utilizing a modern variant known as the Blended Pairwise Conditional Gradient (BPCG) with "lazification," the method minimizes the frequency of expensive oracle calls by reusing previously discovered solutions.
Theoretical Context and Complexity
Smoothing serves as a mathematical bridge, allowing Frank-Wolfe—traditionally a tool for smooth machine learning problems—to tackle the sharp, non-differentiable world of robust combinatorial optimization. By avoiding the "constraint explosion" seen in traditional methods, the FW approach keeps subproblems simple, typically requiring only a single projection onto the uncertainty set.
As shown in the comparison above, the proposed Smoothing Frank-Wolfe method matches the best-known theoretical oracle complexity, reaching an $\epsilon$-accurate solution in $O(1/\epsilon^2)$ iterations. This places it on par with established methods like projected subgradient descent while offering superior empirical performance in high-dimensional settings.
Empirical Evaluation and Results
The researchers evaluated their algorithm on two fundamental combinatorial optimization benchmarks: the Robust Minimum-Weight Spanning Tree (MST) and the Robust Traveling Salesperson Problem (TSP). For the TSP, a Mixed-Integer Programming (MIP) solver acted as the oracle. These benchmarks were tested across varying dimensions and "uncertainty budgets" ($\Gamma$), which limit how many parameters can deviate from their mean values simultaneously.
Key findings from these experiments include:
- Empirical Superiority: On high-dimensional instances, the proposed algorithm significantly outperformed standard constraint generation methods, particularly when using a convex hull of previous solutions.
- Stability under Uncertainty: The method proved exceptionally effective in "high-uncertainty" regimes. While traditional methods often struggle as the uncertainty set grows, the Frank-Wolfe approach remained stable and computationally efficient.
- Efficiency via Laziness: The "lazified" implementation allowed the algorithm to make significant progress using cached solutions, drastically reducing the total number of expensive oracle calls required in practice.
Conclusion and Future Work
While the Smoothing Frank-Wolfe algorithm offers a powerful new tool for robust optimization, it is an iterative method that provides an $\epsilon$-approximate solution rather than a provably exact mathematical optimum. While sufficient for most engineering applications, this may be a limitation for specific theoretical use cases.
Future research directions include extending this oracle-based framework to two-stage robust optimization, where some decisions are made after uncertainty is revealed. Additionally, while this work focuses on uncertainty in the objective function (e.g., costs), addressing uncertainty within the constraints themselves remains a significant open challenge for oracle-based models.
Summary updated