Optimization Online


Epi-convergence of Sample Averages of a Random Lower Semi-continuous Functional Generated by a Markov Chain and Application to Stochastic Optimization

Arnab Sur(arnabsur2002***at***gmail.com)
John Birge(john.birge***at***chicagobooth.edu)

Abstract: The purpose of this article is to establish epigraphical convergence of the sample averages of a random lower semi-continuous functional associated with a Harris recurrent Markov chain with stationary distribution $\pi$. Sample averages associated with an ergodic Markov chain with stationary probability distribution will epigraphically converge from $\pi$-almost all starting points. The property of Harris recurrence allows us to replace ``almost all" by ``all", which is potentially important when running Markov chain Monte Carlo algorithms. That result on epi-convergence is then applied to establish the consistency of the optimal solutions and optimal value of a stochastic optimization problem involving expectation functional of the form $ E_{\pi}[f(x,\xi)].$ Moreover, we develop asymptotic normality of the statistical estimator of the optimal value using a Markov chain central limit theorem.

Keywords: Sample average approximation method, Epigraphical convergence, Random lower semi-continuous function, Measure-preserving ergodic transformation, Harris recurrent Markov chain, Consistency, Asymptotic normality.

Category 1: Stochastic Programming

Citation: MOR-2020-092, The University of Chicago, March/2020

Download: [PDF]

Entry Submitted: 04/21/2020
Entry Accepted: 04/21/2020
Entry Last Modified: 04/21/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society