Nonlinear distributionally robust optimization

Mohammed Rayyan Sheriff, Peyman Mohajerin EsfahaniMath. Program 2023

Abstract

Traditional Distributionally Robust Optimization (DRO) typically optimizes an expected loss, which is linear with respect to the underlying probability distribution. However, many real-world applications require nonlinear risk measures such as variance or entropic risk. This paper introduces a novel framework for Nonlinear DRO (NDRO) that leverages a norm-independent notion of Gateaux smoothness and a specialized Frank-Wolfe algorithm. By mapping infinite-dimensional probability spaces to finite-dimensional sufficient statistics, the proposed method achieves $O(1/k)$ convergence to saddle-point solutions, providing a computationally tractable path for complex risk-averse optimization.

Introduction

In stochastic programming, decision-makers often optimize against a single estimated probability distribution. Distributionally Robust Optimization (DRO) enhances this by considering the worst-case distribution within an "ambiguity set." While standard DRO focuses on linear expectations, practical scenarios—such as portfolio management—often necessitate nonlinear risk measures to penalize volatility or model exponential risk aversion.

Optimizing nonlinear functions over infinite-dimensional probability spaces is traditionally difficult due to the requirement of Frechet derivatives, which necessitate a specific norm. This paper addresses these challenges by proposing a "norm-free" framework for NDRO.

Methodology

Regular Risk (RR) Measures

The framework centers on Regular Risk measures, which depend on the distribution only through a finite-dimensional "sufficient statistic" (e.g., mean or covariance). This property allows the reduction of an infinite-dimensional problem into a manageable finite-dimensional optimization task.

Gateaux (G)-Derivatives and G-Smoothness

To avoid the theoretical and computational complexities of Frechet derivatives in infinite dimensions, the authors utilize the Gateaux directional derivative. They introduce a definition of G-smoothness that is independent of any underlying norm, making the theory applicable across diverse ambiguity sets like Wasserstein or moment-based sets.

Geometric interpretation of the Gateaux derivative $dR(\mathbb{P}; \mathbb{Q})$ on the space of distributions $\mathcal{P}$.

As illustrated in the figure above, the Gateaux derivative $dR(\mathbb{P}; \mathbb{Q})$ characterizes the change in the risk functional $R$ along the direction from distribution $\mathbb{P}$ to $\mathbb{Q}$. This geometric approach allows for a robust analysis of the objective surface without relying on specific distance metrics.

Frank-Wolfe for NDRO

The authors adapt the Frank-Wolfe (FW) algorithm to find $\epsilon$-saddle points. FW is a first-order method that solves linear sub-problems (oracles) at each iteration, bypassing the need for expensive projections onto complex ambiguity sets. For many nonlinear risks, the algorithm only needs to track the evolution of sufficient statistics. To ensure efficiency, the authors show that adding a small quadratic regularizer can stabilize convergence to a predictable $O(1/k)$ rate.

Results and Numerical Validation

The theoretical framework is supported by proofs of $O(1/k)$ convergence rates. The authors derive explicit, tractable FW-oracles for variance and entropic risk. For instance, variance risk with ellipsoidal support is shown to be equivalent to a Semidefinite Program (SDP).

Numerical simulations on portfolio selection problems confirm these findings. Using synthetic samples of assets (e.g., $n=250$ for entropic risk), the authors demonstrate that the duality gap shrinks consistently as iterations progress, even as the size of the ambiguity set increases.

Conclusion

This work provides a mathematically elegant and computationally efficient framework for handling nonlinearities in DRO. By moving to a norm-free definition of smoothness and utilizing the Frank-Wolfe algorithm, the authors bridge the gap between theoretical robustness and practical risk-averse optimization. While the framework currently relies on "Regular Risk" measures, future work may explore extensions to non-convex decision sets and non-flat probability manifolds.

Summary updated

BibTeX
@inproceedings{sheriff2023nonlinear,
  author = {Mohammed Rayyan Sheriff and Peyman Mohajerin Esfahani},
  title = {{Nonlinear distributionally robust optimization}},
  booktitle = {Math. Program},
  year = {2023},
}
Figure