Robust optimization with ambiguous stochastic constraints under mean and dispersion information

Krzysztof Postek, A. Ben-Tal, Dick den Hertog, Bertrand Melenberg

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper we consider ambiguous stochastic constraints under partial information consisting of means and dispersion measures of the underlying random parameters. Whereas the past literature used the variance as the dispersion measure, here we use the mean absolute deviation from the mean (MAD). This makes it possible to use the 1972 result of Ben-Tal and Hochman (BH) in which tight upper and lower bounds on the expectation of a convex function of a random variable are given. First, we use these results to treat ambiguous expected feasibility constraints to obtain exact reformulations for both functions that are convex and concave in the components of the random variable. This approach requires, however, the independence of the random variables and, moreover, may lead to an exponential number of terms in the resulting robust counterparts. We then show how upper bounds can be constructed that alleviate the independence restriction, and require only a linear number of terms, by exploiting models in which random variables are linearly aggregated. Moreover, using the BH bounds we derive three new safe tractable approximations of chance constraints of increasing computational complexity and quality. In a numerical study, we demonstrate the efficiency of our methods in solving stochastic optimization problems under mean-MAD ambiguity.
Original languageEnglish
Pages (from-to)814-833
JournalOperations Research
Volume66
Issue number3
DOIs
Publication statusPublished - May 2018

Fingerprint

Random variables
Computational complexity
Robust optimization
Upper bound

Keywords

  • robust optimization
  • ambiguity
  • stochastic programming
  • chance constraints

Cite this

@article{7d7215c013eb4d98bc86ad1a03c1ff5c,
title = "Robust optimization with ambiguous stochastic constraints under mean and dispersion information",
abstract = "In this paper we consider ambiguous stochastic constraints under partial information consisting of means and dispersion measures of the underlying random parameters. Whereas the past literature used the variance as the dispersion measure, here we use the mean absolute deviation from the mean (MAD). This makes it possible to use the 1972 result of Ben-Tal and Hochman (BH) in which tight upper and lower bounds on the expectation of a convex function of a random variable are given. First, we use these results to treat ambiguous expected feasibility constraints to obtain exact reformulations for both functions that are convex and concave in the components of the random variable. This approach requires, however, the independence of the random variables and, moreover, may lead to an exponential number of terms in the resulting robust counterparts. We then show how upper bounds can be constructed that alleviate the independence restriction, and require only a linear number of terms, by exploiting models in which random variables are linearly aggregated. Moreover, using the BH bounds we derive three new safe tractable approximations of chance constraints of increasing computational complexity and quality. In a numerical study, we demonstrate the efficiency of our methods in solving stochastic optimization problems under mean-MAD ambiguity.",
keywords = "robust optimization, ambiguity, stochastic programming, chance constraints",
author = "Krzysztof Postek and A. Ben-Tal and {den Hertog}, Dick and Bertrand Melenberg",
year = "2018",
month = "5",
doi = "10.1287/opre.2017.1688",
language = "English",
volume = "66",
pages = "814--833",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "3",

}

Robust optimization with ambiguous stochastic constraints under mean and dispersion information. / Postek, Krzysztof; Ben-Tal, A.; den Hertog, Dick; Melenberg, Bertrand.

In: Operations Research, Vol. 66, No. 3, 05.2018, p. 814-833.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Robust optimization with ambiguous stochastic constraints under mean and dispersion information

AU - Postek, Krzysztof

AU - Ben-Tal, A.

AU - den Hertog, Dick

AU - Melenberg, Bertrand

PY - 2018/5

Y1 - 2018/5

N2 - In this paper we consider ambiguous stochastic constraints under partial information consisting of means and dispersion measures of the underlying random parameters. Whereas the past literature used the variance as the dispersion measure, here we use the mean absolute deviation from the mean (MAD). This makes it possible to use the 1972 result of Ben-Tal and Hochman (BH) in which tight upper and lower bounds on the expectation of a convex function of a random variable are given. First, we use these results to treat ambiguous expected feasibility constraints to obtain exact reformulations for both functions that are convex and concave in the components of the random variable. This approach requires, however, the independence of the random variables and, moreover, may lead to an exponential number of terms in the resulting robust counterparts. We then show how upper bounds can be constructed that alleviate the independence restriction, and require only a linear number of terms, by exploiting models in which random variables are linearly aggregated. Moreover, using the BH bounds we derive three new safe tractable approximations of chance constraints of increasing computational complexity and quality. In a numerical study, we demonstrate the efficiency of our methods in solving stochastic optimization problems under mean-MAD ambiguity.

AB - In this paper we consider ambiguous stochastic constraints under partial information consisting of means and dispersion measures of the underlying random parameters. Whereas the past literature used the variance as the dispersion measure, here we use the mean absolute deviation from the mean (MAD). This makes it possible to use the 1972 result of Ben-Tal and Hochman (BH) in which tight upper and lower bounds on the expectation of a convex function of a random variable are given. First, we use these results to treat ambiguous expected feasibility constraints to obtain exact reformulations for both functions that are convex and concave in the components of the random variable. This approach requires, however, the independence of the random variables and, moreover, may lead to an exponential number of terms in the resulting robust counterparts. We then show how upper bounds can be constructed that alleviate the independence restriction, and require only a linear number of terms, by exploiting models in which random variables are linearly aggregated. Moreover, using the BH bounds we derive three new safe tractable approximations of chance constraints of increasing computational complexity and quality. In a numerical study, we demonstrate the efficiency of our methods in solving stochastic optimization problems under mean-MAD ambiguity.

KW - robust optimization

KW - ambiguity

KW - stochastic programming

KW - chance constraints

U2 - 10.1287/opre.2017.1688

DO - 10.1287/opre.2017.1688

M3 - Article

VL - 66

SP - 814

EP - 833

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 3

ER -