research-article

Computational methods for optimization via simulation using gaussian markov random fields

Authors:

Mark Semelhago,

Barry L. Nelson,

Andreas Wächter,

Eunhye SongAuthors Info & Claims

WSC '17: Proceedings of the 2017 Winter Simulation Conference

Article No.: 164, Pages 1 - 12

Published: 03 December 2017 Publication History

Abstract

There has been recent interest, and significant success, in adapting and extending ideas from statistical learning via Gaussian process (GP) regression to optimization via simulation (OvS) problems. At the heart of all such methods is a GP representing knowledge about the objective function whose conditional distribution is updated as more of the feasible region is explored. Calculating the conditional distribution requires inverting a large, dense covariance matrix, and this is the primary bottleneck for applying GP learning to large-scale OvS problems. If the GP is a Gaussian Markov Random Field (GMRF), then the precision matrix (inverse of the covariance matrix) can be constructed to be sparse. In this paper we show how to exploit this sparse-matrix structure to extend the reach of OvS based on GMRF learning for discrete-decision-variable problems.

References

[1]

Frazier, P. 2012. "Tutorial: Optimization Via Simulation with Bayesian Statistics and Dynamic Programming". In Proceedings of the 2012 Winter Simulation Conference, edited by C. Laroque, J. Himmelspach, R. Pasupathy, O. Rose, and A. M. Uhrmacher, 1--16. Piscataway, NJ: Institute of Electrical and Electronics Engineers, Inc.

Digital Library

[2]

Frazier, P., W. Powell, and S. Dayanik. 2009. "The Knowledge-Gradient Policy for Correlated Normal Beliefs". INFORMS Journal on Computing 21 (4): 599--613.

[3]

Frazier, P. I., J. Xie, and S. E. Chick. 2011. "Value of Information Methods for Pairwise Sampling with Correlations". In Proceedings of the 2011 Winter Simulation Conference, edited by S. Jain, R. R. Creasey, J. Himmelspach, K. P. White, and M. Fu, 3979--3991. Piscataway, NJ: Institute of Electrical and Electronics Engineers, Inc.

Digital Library

[4]

Golub, G., and C. Van Loan. 2013. Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press.

[5]

Jalali, H., I. Van Nieuwenhuyse, and V. Picheny. 2015. "Comparison of Kriging-based Methods for Simulation Optimization with Heterogeneous Noise". Technical report, KU Leuven.

[6]

Johnson, C. R. 1982. "Inverse M-matrices". Linear Algebra and its Applications 47:195--216.

[7]

Jones, D. R., M. Schonlau, and W. J. Welch. 1998. "Efficient Global Optimization of Expensive Black-Box Functions". Journal of Global Optimization 13 (4): 455--492.

Digital Library

[8]

Kim, S. 2013. "Statistical Ranking and Selection". In Encyclopedia of Operations Research and Management Science, 1459--1469. New York: Springer.

[9]

Qu, H., I. O. Ryzhov, and M. C. Fu. 2012. "Ranking and Selection with Unknown Correlation Structures". In Proceedings of the 2012 Winter Simulation Conference, edited by C. Laroque, J. Himmelspach, R. Pasupathy, O. Rose, and A. M. Uhrmacher, 144--155. Piscataway, NJ: Institute of Electrical and Electronics Engineers, Inc.

Digital Library

[10]

Rue, H., and L. Held. 2005. Gaussian Markov Random Fields: Theory and Applications. New York: Chapman and Hall/CRC.

Digital Library

[11]

Salemi, P., B. L. Nelson, and J. Staum. 2014. "Discrete Optimization via Simulation Using Gaussian Markov Random Fields". In Proceedings of the 2014 Winter Simulation Conference, edited by A. Tolk, S. Y. Diallo, L. Y. I. O. Ryzhov, S. Buckley, and J. A. Miller, 3809--3820. Piscataway, NJ: Institute of Electrical and Electronics Engineers, Inc.

Digital Library

[12]

Salemi, P., E. Song, B. L. Nelson, and J. Staum. 2017. "Gaussian Markov Random Fields for Discrete Optimization via Simulation: Framework and Algorithms". Technical report, Northwestern University.

[13]

Santner, T. J., B. J. Williams, and W. Notz. 2003. The Design and Analysis of Computer Experiments. New York: Springer.

[14]

Schenk, O., and K. Gärtner. 2014, February. PARDISO User Guide Version 5.0.0.

[15]

Sun, L., L. J. Hong, and Z. Hu. 2011. "Optimization via Simulation Using Gaussian Process-based Search". In Proceedings of the 2011 Winter Simulation Conference, edited by S. Jain, R. R. Creasey, J. Himmelspach, K. P. White, and M. Fu, 4139--4150. Piscataway, NJ: Institute of Electrical and Electronics Engineers, Inc.

Digital Library

[16]

Takahashi, K., J. Fagan, and M.-S. Chin. 1973. "Formation of a Sparse Bus Impedance Matrix and Its Application to Short Ciruit Study". In 8th PICA Conference Proceedings, 16--29. IEEE Power Engineering Society.

[17]

Vanhatalo, J., and A. Vehtari. 2012. "Modelling Local and Global Phenomena with Sparse Gaussian Processes". arXiv preprint arXiv:1206.3290.

Digital Library

Cited By

Pei LNelson BHunter S(2020)Evaluation of bi-PASS for parallel simulation optimizationProceedings of the Winter Simulation Conference10.5555/3466184.3466525(2960-2971)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.5555/3466184.3466525
Li XSong E(2020)Smart linear algebraic operations for efficient Gaussian Markov improvement algorithmProceedings of the Winter Simulation Conference10.5555/3466184.3466517(2887-2898)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.5555/3466184.3466517
Eftekhari ABollhöfer MSchenk O(2018)Distributed memory sparse inverse covariance matrix estimation on high-performance computing architecturesProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.5555/3291656.3291683(1-12)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.5555/3291656.3291683
Show More Cited By

Recommendations

Deep Gaussian Markov random fields
ICML'20: Proceedings of the 37th International Conference on Machine Learning

Gaussian Markov random fields (GMRFs) are probabilistic graphical models widely used in spatial statistics and related fields to model dependencies over spatial structures. We establish a formal connection between GMRFs and convolutional neural networks (...
Gaussian Markov Random Fields and totally positive matrices
Abstract
The present paper focuses on the study of the conditions under which the covariance matrix of a multivariate Gaussian distribution is totally positive, paying particular attention to multivariate Gaussian distributions that are ...
Factorial Markov Random Fields
ECCV '02: Proceedings of the 7th European Conference on Computer Vision-Part III

In this paper we propose an extension to the standard Markov Random Field (MRF) model in order to handle layers. Our extension, which we call a Factorial MRF (FMRF), is analogous to the extension from Hidden Markov Models (HMM's) to Factorial HMM's. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '17: Proceedings of the 2017 Winter Simulation Conference

December 2017

4389 pages

ISBN:9781538634271

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

IEEE Press

Publication History

Published: 03 December 2017

Check for updates

Qualifiers

Research-article

Conference

WSC '17

Sponsor:

SIGSIM

WSC '17: Winter Simulation Conference

December 3 - 6, 2017

Nevada, Las Vegas

Acceptance Rates

Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
36
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pei LNelson BHunter S(2020)Evaluation of bi-PASS for parallel simulation optimizationProceedings of the Winter Simulation Conference10.5555/3466184.3466525(2960-2971)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.5555/3466184.3466525
Li XSong E(2020)Smart linear algebraic operations for efficient Gaussian Markov improvement algorithmProceedings of the Winter Simulation Conference10.5555/3466184.3466517(2887-2898)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.5555/3466184.3466517
Eftekhari ABollhöfer MSchenk O(2018)Distributed memory sparse inverse covariance matrix estimation on high-performance computing architecturesProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.5555/3291656.3291683(1-12)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.5555/3291656.3291683
Eftekhari ABollhöfer MSchenk O(2018)Distributed memory sparse inverse covariance matrix estimation on high-performance computing architecturesProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.1109/SC.2018.00023(1-12)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.1109/SC.2018.00023

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents