Confidence level solutions for stochastic programming
(2000)
Files
dp2000-13.pdf
Open Access - Adobe PDF
- 146.03 KB
Details
- Authors
- Abstract
- We propose an alternative approach to stochastic programming based on Monte-Carlo sampling and stochastic gradient optimization. The procedure is by essence probabilistic and the computed solution is a random variable. The associated objective value is doubly random, since it depends on two outcomes: the event in the stochastic program and the randomized algorithm. We propose a solution concept in which the probability that the randomized algorithm produces a solution with an expected objective value departing from the optimal one by more than is small enough. We derive complexity bounds for this process. We show that by repeating the basic process on independent sample, one can significantly sharpen the complexity bounds.
- Affiliations
Citations
Nesterov, Y., & Vial, J.-P. (2000). Confidence level solutions for stochastic programming (CORE Discussion Papers 2000/13).