Solving discrete resource allocation problems using the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm

ABSTRACT

We investigate optimization techniques for solving a class of discrete resource allocation problems, including several discrete forms of Simultaneous Perturbation Stochastic Optimization (SPSA). We explore the rate-of-convergence for discrete SPSA in a stochastic setting. Finally, we consider some of the difficulties that can arise when discrete resource allocation problems include a stochastic component.

REFERENCES

• 1: Y Ermoliev, "Facility Location Problem," in Numerical Techniques for Stochastic Optimization, Yuri Ermoliev and Roger J-B Wets, eds., Springer, New York, 1988, pp. 413--434.
• 2: C. G. Cassandras, L. Dai, and C. G. Panayiotou. "Ordinal Optimization for a Class of Deterministic and Stochastic Discrete Resource Allocation problems," IEEE Trans. Auto. Contr., vol. 43(7): pp. 881--900, 1998.
• 3: S. D. Hill, L. Gerencser and Z. Vago, "Stochastic Approximation on Discrete Sets Using Simultaneous Perturbation Difference Approximations," Proc. Of the 2003 Conf. On Information Science and Systems, The Johns Hopkins University, March 12--14, 2003.
• 4: S. D. Hill, L. Gerencser and Z. Vago, "Stochastic Approximation on Discrete Sets Using Simultaneous Difference Approximations," Proceedings of the 2004 American Control Conference, Boston, Massachusetts, June 30 -- July 2, pp. 2795--2798.
• 5: László Gerencsér , Stacy D. Hill , Zsuzsanna Vágó, Optimization over discrete sets via SPSA, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.466-470, December 05-08, 1999, Phoenix, Arizona, United States [doi>10.1145/324138.324294]
• 6: J. C. Spall, S. D. Hill and D. R. Stark, "Theoretical Framework for Comparing Several Stochastic Optimization Approaches," Probabilistic and Randomized Methods for Design under Uncertainty (F. Dabbene and G. Calafiore, eds.), Springer, 2005.
• 7: James C. Spall, Introduction to Stochastic Search and Optimization, John Wiley & Sons, Inc., New York, NY, 2003
• 8: V. Dupac and U. Herkenrath, "Stochastic Approximation on a Discrete Set and the Multi-Armed Bandit Problem," Communications in Statistic --- Sequential Analysis, vol. 1, pp. 1--25, 1982.
• 9: H. Neuburger, "User Benefit in the Evaluation of Transport and Land Use Plans," in the Journal of Transport Economics and Policy, January, 1971.
• 10: S. D. Hill, "Discrete Stochastic Approximation with Application to Resource Allocaton," in the Johns Hopkins APL Technical Digest, January --- March, 2005, Volume 26, Number 1, pp. 15--21.

INDEX TERMS

Keywords:
discrete stochastic optimization, resource allocation, simultaneous perturbation stochastic approximation