Article ID: | iaor2004444 |
Country: | Netherlands |
Volume: | 31 |
Issue: | 1 |
Start Page Number: | 66 |
End Page Number: | 76 |
Publication Date: | Jan 2003 |
Journal: | Operations Research Letters |
Authors: | Powell Warren B., Topaloglu Huseyin |
Keywords: | piecewise linear, approximation |
An effective algorithm for solving stochastic resource allocation problems is to build piecewise linear, concave approximations of the recourse function based on sample gradient information. Algorithms based on this approach are proving useful in application areas such as the newsvendor problem, physical distribution and fleet management. These algorithms require the adaptive estimation of the approximations of the recourse function that maintain concavity at every iteration. In this paper, we prove convergence for a particular version of an algorithm that produces approximations from stochastic gradient information while maintaining concavity.