Distributionally robust optimization with polynomial densities

Theory, models and algorithms

Etienne de Klerk, Daniel Kuhn, K.S. Postek

Research output: Contribution to journalArticleScientificpeer-review

16 Downloads (Pure)

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.
Original languageEnglish
JournalMathematical Programming
DOIs
Publication statusE-pub ahead of print - Sep 2019

Fingerprint

Robust Optimization
Model Theory
Polynomials
Polynomial
Sum of squares
Insurance
Conditional Moments
Higher Order Moments
Portfolio Optimization
Probability distributions
Probability density function
Discrete Distributions
Conditional probability
Marginal Distribution
Polynomial function
Optimization Model
Agglomeration
Density Function
Aggregation
Polynomial time

Keywords

  • distributionally robust optimization
  • semidefinite programming
  • sum-of-squares polynomials
  • generalized eigenvalue problem

Cite this

@article{1ad603165a4e4d42aba214ec5e57ea27,
title = "Distributionally robust optimization with polynomial densities: Theory, models and algorithms",
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.",
keywords = "distributionally robust optimization, semidefinite programming, sum-of-squares polynomials, generalized eigenvalue problem",
author = "{de Klerk}, Etienne and Daniel Kuhn and K.S. Postek",
year = "2019",
month = "9",
doi = "10.1007/s10107-019-01429-5",
language = "English",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",

}

Distributionally robust optimization with polynomial densities : Theory, models and algorithms. / de Klerk, Etienne; Kuhn, Daniel; Postek, K.S.

In: Mathematical Programming , 09.2019.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Distributionally robust optimization with polynomial densities

T2 - Theory, models and algorithms

AU - de Klerk, Etienne

AU - Kuhn, Daniel

AU - Postek, K.S.

PY - 2019/9

Y1 - 2019/9

N2 - 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.

AB - 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.

KW - distributionally robust optimization

KW - semidefinite programming

KW - sum-of-squares polynomials

KW - generalized eigenvalue problem

U2 - 10.1007/s10107-019-01429-5

DO - 10.1007/s10107-019-01429-5

M3 - Article

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

ER -