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.
All Science Journal Classification (ASJC) codes
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics
- Almost sure convergence
- Concave functions
- Stochastic gradient methods