Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Filters

1994 - 20002

Settings

Author: search.filters.author.Bartusek, John D.Subject: search.filters.subject.queueing networks

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Stochastic Approximation and Optimization for Markov Chains
    (2000) Bartusek, John D.; Makowski, Armand M.; ISR
    We study the convergence properties of the projected stochasticapproximation (SA) algorithm which may be used to find the root of an unknown steady state function of a parameterized family of Markov chains. The analysis is based on the ODE Method and we develop a set of application-oriented conditions which imply almost sure convergence and are verifiable in terms of typically available model data. Specific results are obtained for geometrically ergodic Markov chains satisfying a uniform Foster-Lyapunov drift inequality.

    Stochastic optimization is a direct application of the above root finding problem if the SA is driven by a gradient estimate of steady state performance. We study the convergence properties of an SA driven by agradient estimator which observes an increasing number of samples from the Markov chain at each step of the SA's recursion. To show almost sure convergence to the optimizer, a framework of verifiable conditions is introduced which builds on the general SA conditions proposed for the root finding problem.

    We also consider a difficulty sometimes encountered in applicationswhen selecting the set used in the projection operator of the SA algorithm.Suppose there exists a well-behaved positive recurrent region of the state process parameter space where the convergence conditions are satisfied; this being the ideal set to project on. Unfortunately, the boundaries of this projection set are not known a priori when implementing the SA. Therefore, we consider the convergence properties when the projection set is chosen to include regions outside the well-behaved region. Specifically, we consider an SA applied to an M/M/1 which adjusts the service rate parameter when the projection set includes parameters that cause the queue to be transient.

    Finally, we consider an alternative SA where the recursion is driven by a sample average of observations. We develop conditions implying convergence for this algorithm which are based on a uniform large deviation upper bound and we present specialized conditions implyingthis property for finite state Markov chains.

  • Thumbnail Image
    Item
    On Stochastic Approximations Driven by Sample Averages: Convergence Results via the ODE Method
    (1994) Bartusek, John D.; Makowski, Armand M.; ISR; CSHCN
    We consider a class of projected stochastic approximation algorithms drive by sample averages. These algorithms arise naturally in problems of on-line parametric optimization for discrete event dynamical systems., e.g., queueing systems and Petri net models. We develop a general framework for investigating the a.s. convergence of the iterate sequence, and show how such convergence results can be obtained by means of the ordinary differential equation (ODE) method under a condition of exponential convergence. We relate this condition of exponential convergence to certain Large Deviations upper bounds which are uniform in both the parameter q and the initial condition x. To demonstrate the applicability of the results, we specialize them to two specific classes of state processes, namely sequences of i.i.d. random variables and finite state time-homogeneous Markov chains. In both cases, we identify simple (and checkable) conditions that ensure the validity of a uniform Large Deviations upper bound.