This research project considers scaling limits of certain controlled stochastic processing networks in heavy traffic. Brownian control problems(BCP) have been proposed as formal diffusion approximations for a broad range of controlled networks.Currently there is a critical lack of general theory that establishes rigorous connections between a network control problem and its associated BCP. The first goal of this research is to establish that for a wide range of control forms, network structures and optimization criteria, the value functions of suitably scaled controlled network models converge to that of the corresponding diffusion control problem. The second goal is the study of qualitative properties of diffusion control problems arising from the above asymptotic analysis. These problems correspond to a family of singular control problems with state constraints in non-smooth domains. The Hamilton-Jacobi-Bellman (HJB) equations for such control problems are a challenging class of degenerate elliptic nonlinear partial differential equations with gradient constraints and somewhat non-standard boundary conditions. Existence, uniqueness and regularity theory for HJB equations for a range of such control problems and cost criteria will be developed. Wellposedness of such equations is a central ingredient in development of numerical schemes for obtaining near optimal controls. Additionally, regularity is key in reading off useful qualitative information on the form of an optimal control. An example of such information is the characterization of an optimally controlled process as a reflected diffusion over a domain determined in terms of a suitable free boundary problem. Such characterization results for singular control problems are some of the most elegant and useful results in the field and their study for problems with state constraints will be a focus of this research.

Dynamic control problems that motivate this work arise from a wide range of application areas, such as, telecommunications, manufacturing, service engineering, computing, etc. Control in such networks can take a variety of forms, examples include, scheduling, sequencing, routing and admissions of jobs, and input and processing rate controls. Networks of interest are in general quite complex and thus one seeks tractable approximate models. The overall theme of this research is the development of techniques for obtaining good scheduling policies for general families of such stochastic processing systems using the mathematical theory of diffusion approximations. The work will lead to improved design, stability and regulation of complex manufacturing, communication and computer systems. Research project will support the training of two graduate students and develop international collaborations and with faculty from non-Ph.D. granting institutions.

Project Report

Research partially supported by this grant culminated in the submission of twenty eight new research papers twenty three of which have now been accepted for publication. Six Ph.D. students were partially supported by the grant, four of which have now graduated. Some of the major outcomes of the research are as follows: 1. Development of optimal control policies in ergodic rate control problems for single class queueing networks. 2. Rigorous development of simple approximate models for stochastic networks using multiscale diffusion approximations. 3. Development of algorithms for adaptive control under incomplete information. 4. Results on exit time and invariant measure asymptotics for small noise constrained diffusions. 5. Scaling limit theorems for controlled stochastic networks in heavy traffic. 6. Results on stability properties of constrained Markov modulated diffusions. 7. Development of a numerical scheme for invariant distributions of constrained diffusions. 8. Analysis of admission control mechanisms for multidimensional workload with heavy tails. 9. Development of dynamic scheduling policies for Markov modulated single-server multiclass queueing systems in heavy traffic. 10.Using new central limit theorems, development of confidence intervals for solutions of certain stochastic variational problems. 11. Some new transition density estimates for constrained diffusions that are useful for the study of small noise asymptotics for such processes. 12. Some large deviations results for a family of multidimensional shot noise processes that arise in communication networks modeling. Some other outcomes that are not directly related to the main theme of the proposed research are as follows. 1. Large deviation results for weakly interacting stochastic processes. 2. Derivation of novel stochastic differential games associated with the infinity-Laplacian. 3. Large deviation results for systems driven by a Poisson noise. 4. Scaling limit theorems for dynamic random graphs on the critical regime. 5. Analysis of asymptotic behavior of random graphs described via bounded size rules. 6. Introduction of a mathematical object called `augmented multiplicative coalescent' which describes the limit behavior for a broad family of dynamic random graphs. 7. Analysis of near critical catalyst reactant branching processes with controlled immigration. 8. Representations for solutions of certain nonlinear stochastic PDE in terms of infinite dimensional backward-forward stochastic differential equations. 9. New Moderate deviation principles for stochastic differential equations with jumps. 10. Introduction of a mathematical object named, Multidimensional skew Brownian motion, that models diffusion in a disordered media. 11. Time asymptotic results for a family of weakly interacting particle systems in discrete time.

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Type
Standard Grant (Standard)
Application #
1004418
Program Officer
Tomek Bartoszynski
Project Start
Project End
Budget Start
2010-08-15
Budget End
2014-07-31
Support Year
Fiscal Year
2010
Total Cost
$311,261
Indirect Cost
Name
University of North Carolina Chapel Hill
Department
Type
DUNS #
City
Chapel Hill
State
NC
Country
United States
Zip Code
27599