TY - JOUR
T1 - Conditioning of convex piecewise linear stochastic programs
AU - Shapiro, Alexander
AU - Homem-De-Mello, Tito
AU - Kim, Joocheol
PY - 2002/12
Y1 - 2002/12
N2 - 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.
AB - 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.
KW - Ill-conditioned problems
KW - Large deviations theory
KW - Monte Carlo simulation
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=3943087919&partnerID=8YFLogxK
U2 - 10.1007/s10107-002-0313-2
DO - 10.1007/s10107-002-0313-2
M3 - Article
AN - SCOPUS:3943087919
SN - 0025-5610
VL - 94
SP - 1
EP - 19
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1
ER -