Conditioning of convex piecewise linear stochastic programs

Alexander Shapiro, Tito Homem-De-Mello, Joocheol Kim

Research output: Contribution to journalArticlepeer-review

48 Scopus citations

Abstract

In this paper we consider stochastic programming problems where the objective function is given as an expected value of a convex piecewise linear random function. With an optimal solution of such a problem we associate a condition number which characterizes well or ill conditioning of the problem. Using theory of Large Deviations we show that the sample size needed to calculate the optimal solution of such problem with a given probability is approximately proportional to the condition number.

Original languageEnglish
Pages (from-to)1-19
Number of pages19
JournalMathematical Programming
Volume94
Issue number1
DOIs
StatePublished - Dec 2002
Externally publishedYes

Keywords

  • Ill-conditioned problems
  • Large deviations theory
  • Monte Carlo simulation
  • Stochastic programming

Fingerprint

Dive into the research topics of 'Conditioning of convex piecewise linear stochastic programs'. Together they form a unique fingerprint.

Cite this