Nonparametric density estimation for stochastic optimization with an observable state variable
Pages 820 - 828
Abstract
In this paper we study convex stochastic optimization problems where a noisy objective function value is observed after a decision is made. There are many stochastic optimization problems whose behavior depends on an exogenous state variable which affects the shape of the objective function. Currently, there is no general purpose algorithm to solve this class of problems. We use nonparametric density estimation to take observations from the joint state-outcome distribution and use them to infer the optimal decision for a given query state s. We propose two solution methods that depend on the problem characteristics: function-based and gradient-based optimization. We examine two weighting schemes, kernel based weights and Dirichlet process based weights, for use with the solution methods. The weights and solution methods are tested on a synthetic multi-product newsvendor problem and the hour ahead wind commitment problem. Our results show that in some cases Dirichlet process weights offer substantial benefits over kernel based weights and more generally that nonparametric estimation methods provide good solutions to otherwise intractable problems.
References
[1]
Antoniak, C. E. [1974], 'Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems', The Annals of Statistics 2(6), 1152-1174.
[2]
Bennett, K. P. and Parrado-Hernández, E. [2006], 'The interplay of optimization and machine learning research', The Journal of Machine Learning Research 7, 1265-1281.
[3]
Blackwell, D. and MacQueen, J. B. [1973], 'Ferguson distributions via Polya urn schemes', The Annals Statistics 1(2), 353-355.
[4]
Cheung, R. K. and Powell, W. B. [2000], 'SHAPE-A stochastic hybrid approximation procedure for two-stage stochastic programs', Operations Research 48(1), 73-79.
[5]
Fan, J. and Gijbels, I. [1996], Local Polynomial Modelling and Its Applications, Chapman & Hall/CRC.
[6]
Ferguson, T. S. [1973], 'A Bayesian analysis of some nonparametric problems', The Annals of Statistics 1(2), 209-230.
[7]
Hayfield, T. and Racine, J. S. [2008], 'Nonparametric econometrics: The np package', Journal of Statistical Software 27(5), 1-32.
[8]
Ishwaran, H. and James, L. F. [2003], 'Generalized weighted Chinese restaurant processes for species sampling mixture models', Statistica Sinica 13(4), 1211-1236.
[9]
Kiefer, J. and Wolfowitz, J. [1952], 'Stochastic estimation of the maximum of a regression function', The Annals of Mathematical Statistics 23(3), 462-466.
[10]
Nadaraya, E. A. [1964], 'On estimating regression', Theory of Probability and its Applications 9(1), 141-142.
[11]
Neal, R. M. [2000], 'Markov chain sampling methods for Dirichlet process mixture models', Journal of Computational and Graphical Statistics 9(2), 249-265.
[12]
Parr, R., Painter-Wakefield, C., Li, L. and Littman, M. [2007], Analyzing feature generation for value-function approximation, in 'Proceedings of the 24th international conference on Machine learning', ACM, p. 744.
[13]
Pitman, J. [1996], 'Some developments of the Blackwell-MacQueen urn scheme', Lecture Notes-Monograph Series 30, 245-267.
[14]
Powell, W. B. [2007], Approximate Dynamic Programming: Solving the curses of dimensionality, Wiley-Blackwell.
[15]
Powell, W. B., Ruszczyński, A. and Topaloglu, H. [2004], 'Learning algorithms for separable approximations of discrete stochastic optimization problems', Mathematics of Operations Research 29(4), 814-836.
[16]
Puterman, M. L. [1994], Markov decision processes: Discrete stochastic dynamic programming, John Wiley & Sons, Inc. New York, NY, USA.
[17]
Robbins, H. and Monro, S. [1951], 'A stochastic approximation method', The Annals of Mathematical Statistics 22(3), 400-407.
[18]
Schwartz, E. S. [1997], 'The stochastic behavior of commodity prices: Implications for valuation and hedging', The Journal of Finance 52(3), 923-973.
[19]
Shapiro, A., Homem-de Mello, T. and Kim, J. [2002], 'Conditioning of convex piecewise linear stochastic programs', Mathematical Programming 94(1), 1-19.
[20]
Spall, J. C. [2003], Introduction to stochastic search and optimization: estimation, simulation, and control, John Wiley and Sons.
[21]
Sutton, R. S. and Barto, A. G. [1998], Introduction to reinforcement learning, MIT Press Cambridge, MA, USA.
[22]
Tsitsiklis, J. N. and Van Roy, B. [2001], 'Regression methods for pricing complex American-style options', IEEE Transactions on Neural Networks 12(4), 694-703.
[23]
Watson, G. S. [1964], 'Smooth regression analysis', Sankhyā: The Indian Journal of Statistics, Series A 26(4), 359-372.
- Nonparametric density estimation for stochastic optimization with an observable state variable
Recommendations
Planning and acting in partially observable stochastic domains
In this paper, we bring techniques from operations research to bear on the problem of choosing optimal actions in partially observable stochastic domains. We begin by introducing the theory of Markov decision processes (mdps) and partially observable ...
Limiting Discounted-Cost Control of Partially Observable Stochastic Systems
This paper presents two main results on partially observable (PO) stochastic systems. In the first one, we consider a general PO system $$ x_{t+1}= F (x_t, a_t, xi_t), , y_t= G(x_t, eta_t) (t=0,1,ldots) hspace{1in} (*) $$ on Borel spaces, with possibly ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2010
2630 pages
Publisher
Curran Associates Inc.
Red Hook, NY, United States
Publication History
Published: 06 December 2010
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 2Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Nov 2024