Distributionally robust optimization with polynomial densities: theory, models and algorithms

Etienne de Klerk, Daniel Kuhn, Krzysztof PostekMath. Program 2020 · OpenReview

TL;DR

This paper introduces a new way to model uncertainty in optimization problems by using polynomial density functions for probability distributions. This approach allows for more realistic modeling of uncertainty compared to traditional methods that often rely on pathological discrete distributions, while still maintaining computational tractability through semidefinite programming.

What Problem Does This Paper Address?

In optimization problems with uncertain parameters, we often don't know the exact probability distribution of these parameters. Distributionally robust optimization (DRO) addresses this by considering an "ambiguity set" of possible distributions and optimizing for the worst-case scenario within that set. However, many existing DRO models use ambiguity sets that contain "pathological" discrete distributions, which can be overly pessimistic and unrealistic. This paper aims to bridge the gap between robust optimization (which ignores distributional information) and traditional stochastic programming (which requires precise distributional knowledge) by introducing a more flexible and realistic way to define ambiguity sets using polynomial density functions.

Methods

The core of the paper's methodology lies in leveraging the theory of polynomial optimization, specifically Lasserre's measure-based hierarchy. The authors propose using sum-of-squares (SOS) polynomial density functions to define the ambiguity sets. This means that instead of considering all possible distributions, they restrict the distributions to those that can be represented by a non-negative polynomial density of a certain degree.

Key methodological contributions include:

  • New Ambiguity Sets: Defining ambiguity sets based on SOS polynomial densities of a specified degree. These sets are shown to be highly expressive, capable of incorporating information about moments, conditional probabilities, and marginal distributions.
  • Semidefinite Programming (SDP) Reformulation: Exploiting Lasserre's hierarchy, the worst-case expectation constraints within these new ambiguity sets can be reformulated as tractable SDPs. This is a significant computational advantage.
  • Polynomial-Time Separation Oracle: For certain conditions, the feasible sets of these constraints admit a polynomial-time separation oracle, enabling efficient optimization using methods like the ellipsoid method.
  • Heuristic Algorithm: A practical, efficient heuristic algorithm is proposed to approximate solutions when the direct SDP formulation becomes computationally expensive due to high polynomial degrees.
  • Convergence Analysis: The paper analyzes the convergence of the worst-case expectations as the degree of the polynomial density increases, showing it converges to the classical worst-case expectations.

Datasets

The paper does not use traditional "datasets" for training. Instead, it employs stylized test functions and scenarios to demonstrate the effectiveness of the proposed methods. These include:

  • Matyas function and Motzkin polynomial: Used for testing the polynomial optimization framework.
  • Portfolio optimization problem: A stylized model with uncertain asset returns depending on risk factors.
  • Risk aggregation problem: A model for an insurance company dealing with multiple random losses.

The paper also discusses how to incorporate prior distributional information such as moment constraints, confidence information, conditional probabilities, and marginal distributions into the ambiguity sets.

Key Insights and Ideas

  • Polynomial Densities as a Realistic Ambiguity Set: The key insight is that restricting distributions to have SOS polynomial densities offers a more realistic and less "pathological" alternative to traditional discrete distributions in DRO. This allows for richer modeling of uncertainty while retaining tractability.
  • Expressiveness of Polynomial Densities: SOS polynomial densities are surprisingly flexible. They can naturally encode various distributional properties like higher-order moments, conditional probabilities, and marginal distributions through linear constraints on the polynomial coefficients.
  • Bridging Theory and Practice: The paper successfully connects advanced theoretical tools from polynomial optimization (Lasserre's hierarchy) with practical optimization problems in finance and insurance, demonstrating a clear path from theory to application.
  • Tuning Conservativeness with Degree: The degree of the polynomial density acts as a tuning parameter. Higher degrees allow for more flexible distributions (less conservative), while lower degrees lead to more restrictive and conservative models.
  • Approximate Solutions for Complex Problems: The proposed heuristic algorithm and the convergence analysis provide practical ways to handle situations where exact solutions might be computationally prohibitive.

Key Results

  • Tractable Optimization: Worst-case expectation constraints with SOS polynomial densities can be reformulated as tractable SDPs.
  • Modeling Power: The framework can effectively incorporate various forms of distributional information (moments, conditional probabilities, marginals) into the ambiguity sets.
  • Convergence Guarantees: As the degree of the polynomial density increases, the worst-case expectations converge to the classical worst-case expectations, providing a theoretical foundation for the approach.
  • Numerical Validation: The proposed methods were successfully applied to a portfolio optimization problem and a risk aggregation problem, demonstrating their practical utility. For instance, in the portfolio analysis, the method was able to evaluate worst-case probabilities under various distributional assumptions, showing how different modeling choices impact the outcome.

Limitations and Future Work

  • Applicability to Objective/Constraint Functions: The current approach is primarily applicable to problems where the objective and constraint functions have a polynomial dependence on the uncertain parameters. It is not directly applicable to problems with general piecewise polynomial or decision-dependent recourse functions (e.g., in linear two-stage stochastic programs).
  • Scalability of SDPs: While the problem is theoretically tractable, the resulting SDPs can become large and potentially ill-conditioned for high polynomial degrees or many variables. The paper proposes a heuristic algorithm to mitigate this, but further work on scalability is needed.
  • Generalization of Polynomial Dependence: Extending the framework to handle more general forms of polynomial dependence in objective/constraint functions would be valuable.
  • Further Exploration of Ambiguity Sets: Investigating richer classes of polynomial-based ambiguity sets and their properties could lead to even more powerful modeling capabilities.

Summary updated

Abstract

In distributionally robust optimization the probability distribution of the uncertain problem parameters is itself uncertain, and a fictitious adversary, e.g., nature, chooses the worst distribution from within a known ambiguity set. A common shortcoming of most existing distributionally robust optimization models is that their ambiguity sets contain pathological discrete distributions that give nature too much freedom to inflict damage. We thus introduce a new class of ambiguity sets that contain only distributions with sum-of-squares (SOS) polynomial density functions of known degrees. We show that these ambiguity sets are highly expressive as they conveniently accommodate distributional information about higher-order moments, conditional probabilities, conditional moments or marginal distributions. Exploiting the theoretical properties of a measure-based hierarchy for polynomial optimization due to Lasserre (SIAM J Optim 21(3):864–885, 2011), we prove that certain worst-case expectation constraints are polynomial-time solvable under these new ambiguity sets. We also show how SOS densities can be used to approximately solve the general problem of moments. We showcase the applicability of the proposed approach in the context of a stylized portfolio optimization problem and a risk aggregation problem of an insurance company.
BibTeX
@inproceedings{klerk2020distributionally,
  author = {Etienne de Klerk and Daniel Kuhn and Krzysztof Postek},
  title = {{Distributionally robust optimization with polynomial densities: theory, models and algorithms}},
  booktitle = {Math. Program},
  year = {2020},
  url = {https://openreview.net/forum?id=MnIDNUhEJo4},
}

Loading related content...

Figure