Conditioning of convex piecewise linear stochastic programs |
| |
Authors: | Alexander Shapiro Tito Homem-de-Mello Joocheol Kim |
| |
Institution: | (1) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205, USA, e-mail: ashapiro@isye.gatech.edu, US;(2) Department of Industrial, Welding and Systems Engineering, The Ohio State University, 1971 Neil Ave., Columbus, Ohio 43210-1271, USA, e-mail: homem-de-mello.1@osu.edu, US;(3) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205, USA, US |
| |
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.
Received: May 2000 / Accepted: May 2002-07-16 Published online: September 5, 2002
RID="★"
The research of this author was supported, in part, by grant DMS-0073770 from the National Science Foundation
Key Words. stochastic programming – Monte Carlo simulation – large deviations theory – ill-conditioned problems |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|