Recent Invited Presentations |
This paper concerns control of stochastic networks using state-dependent safety-stocks. Three examples are considered: a pair of tandem queues; a simple routing model; and the Dai-Wang re-entrant line. In each case, a single policy is proposed that is independent of network load. The policy is fluid-scale optimal, and approximately average-cost optimal: The steady-state cost η satisfies the bound
η_* < η < η_* + k_0 log( η_* ) ,
where η_* is the optimal steady-state cost. These results are based on the construction of an approximate solution to the average-cost dynamic programming equations via the one-dimensional relaxation and an associated fluid model.
References:
S.P. Meyn, Dynamic safety-stocks for asymptotic optimality in stochastic networks, Queueing Systems, 50, pp. 255-297 2005. (also available in pdf format)
Workshop on Large Deviations and Rare Events in Networks July 4-5, 2005
See also the three-part survey below
This talk concerns a robust asymptotic hypothesis testing framework in which candidate hypotheses are characterized by moment classes. As an elementary example, suppose you are told that a sequence of scalar observations is i.i.d. with zero mean. Its variance is either 10 or 50. What test would you use to decide which hypothesis is correct?
The following conclusions are obtained:
- There exists a test sequence that is asymptotically optimal in the min-max sense;
- An asymptotically optimal test sequence is constructed based on a log-linear combination of the constraint functions, and is interpreted as an extension of the usual log-likelihood ratio between worst-case distributions.
- Algorithms are described to compute the optimal test.
Extensions to the M-ary hypothesis testing problem are also included.
References:
I. Kontoyiannis, L.A. Lastras-Montaño, and S.P. Meyn, Relative Entropy and Exponential Deviation Bounds for General Markov Chains, ISIT 2005.
C. Pandit, and S.P. Meyn, Worst-Case Large-Deviations Asymptotics with Application to Queueing and Information Theory. To appear, SPA, 2006.
C. Pandit, J. Huang, S. Meyn, V. Veeravalli, Extremal Distributions in Information Theory and Hypothesis Testing. Proceedings of the IEEE Information Theory Workshop, San Antonio, Texas, October 24-29, 2004.
C. Pandit and S.P. Meyn, Robust Measurement-Based Admission Control Using Markov's Theory of Canonical Distributions. To appear, IEEE Trans. Info. Theory (preliminary versions presented at ISIT 2003, Yokohama, Japan, June 29 - July 4, 2003; 37th Annual Conference on Information Sciences and Systems, Baltimore, Maryland, March 12--14, 2003. )
IMA 2005 Summer Program: Wireless Communications, June 22 - July 1, 2005
This presentation concerns the structure of optimal codes for stochastic channel models. An investigation of an associated dual convex program reveals that the optimal distribution in channel coding is typically discrete. Based on this observation we obtain the following theoretical conclusions, as well as new algorithms for constructing efficient channel codes:
- Under general conditions, for low SNR the optimal random code is defined by a distribution whose magnitude is binary.
- Simple discrete approximations may be highly accurate even in cases where the optimal distribution is known to be absolutely continuous with respect to Lebesgue measure.
- A new class of algorithms is introduced, based on the cutting-plane method, to generate discrete distributions that are optimal within a prescribed class.
- Entropy, Inference, and Channel Coding. A review of concepts from information theory; in particular hypothesis testing and channel coding.
- Characterization and Computation of Optimal Distributions for Channel Coding A more detailed development of the structure of optimal input distributions in channel coding.
- Characterization and Computation ... and Worst-Case Models Numerical techniques for computing optimal input distributions, as well as optimal robust algorithms for hypothesis testing.
References:
J. Huang and S.P. Meyn, Characterization and Computation of Optimal Distributions for Channel Coding, IEEE Trans. Info. Theory 51(7) pp. 1--16. Published in abridged form in the proceedings of the 37th Annual Conference on Information Sciences and Systems, Baltimore, Maryland, March 12--14, 2003. (also available in pdf format)
J. Huang, M. Medard, and S.P. Meyn, Error Exponents and Signal Constellation Design. IEEE International Symposium on Information Theory, June 2004.
J. Huang, C. Pandit, S.P. Meyn, M. Medard, and V.\ Veeravalli Entropy, Inference, and Channel Coding. IEEE International Symposium on Information Theory, June 2004.
NBER/NSF Decentralization Conference, April 29 - May 1, 2005
See also October, 2005 SIAM News survey, SIAM Math model explains high prices in electricity markets
These two talks concern resource allocation, pricing, and performance evaluation in electric power markets. Our ultimate goal is the integration of new approaches to dynamic control of stochastic networks, with recent results concerning the competitive market equilibrium in network industries, to obtain comprehensive approaches to model reduction and control for network-level bulk power systems.
These talks describe some modest first steps:
- A dynamic flow model constructed for a single-consumer model in analogy with a standard stochastic queuing model.
- The approximation of the socially-optimal policy by an explicit threshold policy.
- The inability to sustain the socially-optimal policy as a decentralized market outcome.
Generalizations to complex models are also described.
These conclusions have implication to other industries that require high reliability and provide critical services which are undergoing rapid deregulation.
See also October, 2005 SIAM News survey, SIAM Math model explains high prices in electricity markets
The main point of this research is that deregulation often fails. The question is why? In the case of electric power, market designs and analyses are typically based on very simple static models that ignore some very important aspects of the problem. In particular, when capacity becomes low relative to demand, prices will be enormous! This leaves little incentive for generators to increase capacity. This was recognized in a January 23, 2001 New York Times article by R. A. Oppel Jr,
Under old-fashioned state regulation, utilities were given financial incentives - or otherwise were forced - to maintain surplus capacity, just in case it was needed. But deregulation has greatly reduced that tendency, leaving most power producers with smaller reserves, said Philip K. Verleger Jr., a California energy economist.
This is part of the trend to break up vertically integrated industries and operate with leaner inventories, Mr. Verleger said. Electric utilities used to be required to hold 15 percent reserve capacity, but this inventory has been wiped out,'' he said. ''No one has the responsibility to hold extra capacity. It is when peaks in demand sap scarce supply that prices soar in deregulated power markets.
References:
M. Chen, I.-K. Cho and S.P. Meyn, Reliability by design in a distributed power transmission network. Submitted to Automatica Special Issue on Optimal Control Applications to Management Sciences 2005.
I.-K. Cho and S.P. Meyn, Optimization and the Price of Anarchy in a Dynamic Newsboy Model. Submitted for publication.
IBM Watson Research Center, April 2004
Control-synthesis techniques are developed for demand-driven production systems. The resulting policies are time-optimal for a deterministic model, and approximately time-optimal for a stochastic model.
Moreover, they are easily adapted to take into account a range of issues that arise in a realistic, dynamic environment. In particular, control synthesis techniques are developed for models in which resources are temporarily unavailable. This may be due to failure, maintenance, or an unanticipated change in demand.
These conclusions are based upon the following development:
- Workload models are investigated for demand-driven systems, and an associated workload-relaxation is introduced as an approach to model-reduction.
- The impact of hard constraints on performance, and on optimal control solutions is addressed via Lagrange multiplier techniques. These include deadlines and buffer constraints.
- Rules for choosing appropriate safety-stocks as well as hedging-points are described to ensure robustness of control solutions with respect to persistent disturbances, such as variability in demand and yield.
References:
M. Chen, R. Dubrawski, and S.P. Meyn, Management of demand-driven production systems , IEEE Trans. Auto. Control, 49, pp. 686- 698, May 2004.
Value Functions, Performance Evaluation, and Optimization in Stochastic Networks
11:00am - 12:00 Monday March 1, 141 CSL
and the 2003 Applied Probability Workshop, Mathematisches Forschungsinstitut Oberwolfach
This talk surveys control and performance evaluation techniques for stochastic workload models. A controlled Brownian motion process is introduced to model workload in a particular example, and the following issues are considered:
- Scaling properties of the model and control solutions
- The dynamic programming equation for the workload model
- Performance approximation through simulation and control variates.
References:
M. Chen, C. Pandit, and S.P. Meyn, In Search of Sensitivity in Network Optimization. Queueing Systems, Volume 44, No. 4, pp. 313-363, 2003.
S.P. Meyn, Sequencing and Routing in Multiclass Queueing Networks. Part II: Workload Relaxations. SIAM J. Control and Optimization, Vol. 42, No. 1, pp. 178-217, 2003
S.P. Meyn, Workload Models for Stochastic Networks: Value Functions and Performance Evaluation. To appear, IEEE Transactions on Automatic Control, 2005
31st Conference on Stochastic Processes and their Applications, Paris, July 17 - 21, 2006
LMS Durham Symposium: Markov Chains, July 25 - August 4 2003, University of Durham, UK
These talks provide a survey of recent approaches to the spectral theory of Markov processes. The lectures will focus on diffusion models on finite-dimensional Euclidian space, with hypo-elliptic generator.
Part I describes a framework for spectral theory based on finite approximations in a weighted L-infinty norm. It is assumed that the process is exponentially ergodic, with Lyapunov function V, and the weighting function is equal to V. Under exponential ergodicity alone, the resolvent operator admits a spectral gap in this function space. If the diffusion satisfies a stronger condition, generalizing the drift condition used by Donsker and Varadahn in their classic papers, then the resolvent may be approximated by finite-rank operators. This leads to approximations for the eigenfunctions that arise in large deviation theory for the empirical measures. The expressions obtained are extensions of the standard representations of eigenfunctions and eigenmeasures via small functions used in the Perron-Frobenius theory of positive matrices.
Part II develops application of these results to eigen-function and eigen-measure expansions. Real eigenfunctions provide a decomposition of the state space into 'almost'-absorbing subsets. It is shown that the process mixes rapidly in each of these subsets prior to exiting, and that the conditional distributions of exit times are approximately exponential. These results may be viewed as an extension of the perturbation theory of Wentzell and Freidlin.
References:
I. Kontoyiannis and S.P. Meyn, Spectral Theory and Limit Theory for Geometrically Ergodic Markov Processes, Annals of Applied Prob., Volume 13, pp. 304-362, 2003.
J. Huang, I. Kontoyiannis, and S.P. Meyn, The O.D.E. Method and Spectral Theory of Markov Operators. Proceedings of the Second Kansas Workshop on Stochastic Theory - Adaptive Control, 2001.
W. Huisinga, S. P. Meyn, and C. Schuette. Phase Transitions & Metastability in Markovian and Molecular Systems. Annals of Applied Probability, Volume 14, No. 1, pp. 419-458, 2004
I. Kontoyiannis and S.P. Meyn, Large Deviations Asymptotics and the Spectral Theory of Multiplicatively Regular Markov Processes, Electronic Journal of Probability, vol. 10, no. 3, pp. 61-123, 2005. (electronic)
