A finite algorithm for ϵ-optimal solutions of adaptive queueing control

In this paper, by introducing a weighted supremum norm, then using non-adaptive approach and backward induction, we suggest an ε-optimal algorithm for the problem of adaptive queueing control. In case of Bernoulli queues, we obtain an ε-optimal cost and a 2ε-optimal policy. Furthermore, a simple inequality is given as an upper bound of the error, which can be used for determining the number of backward induction steps.     

The critical groups of a family of graphs and elliptic curves over finite fields

Let q be a power of a prime, and E be an elliptic curve defined over  . Such curves have a classical group structure, and one can form an infinite tower of groups by considering E over field extensions for all k≥1. The critical group of a graph may be defined as the cokernel of L(G), the Laplacian matrix of G. In this paper, we compare elliptic curve groups with the critical groups of a certain family of graphs. This collection of critical groups also decomposes into towers of subgroups, and we highlight additional comparisons by using the Frobenius map of E over  . This work was partially supported by the NSF, grant DMS-0500557 during the author’s graduate school at the University of California, San Diego, and partially supported by an NSF Postdoctoral Fellowship.     

Functional continuity and large deviations for the behavior of single-class queueing networks

We consider a single-class queueing network in which the functional network primitives describe the cumulative exogenous arrivals, service times and routing decisions of the queues. The behavior of the network consisting of the cumulative total arrival, cumulative idle time, and queue length developments for each node is specified by conditions which relate the network primitives to the network behavior. For a broad class of network primitives, including discrete customer and fluid models, a network behavior exists, but need not be unique. Nevertheless, the mapping from network primitives to the set of associated network behavior is upper semicontinuous at network primitives with continuous routing. As an application we consider a sequence of random network primitives satisfying a sample path large deviation principle. We take advantage of the partial functional set-valued upper semicontinuity in order to derive a large deviation principle for the sequence of associated random queue length processes and to identify the rate function. This extends the results of Puhalskii (Markov Process. Relat. Fields 13(1), 99–136, 2007) about large deviations for the tail probabilities of generalized Jackson networks. Since the analysis is carried out on the doubly-infinite time axis ?, we can directly treat stationary situations.     

Risk averse asymptotics in a Black–Scholes market on a finite time horizon

We consider the optimal investment and consumption problem in a Black–Scholes market, if the target functional is given by expected discounted utility of consumption plus expected discounted utility of terminal wealth. We investigate the behaviour of the optimal strategies, if the relative risk aversion tends to infinity. It turns out that the limiting strategies are: do not invest at all in the stock market and keep the rate of consumption constant!     

A priori error estimates for space–time finite element discretization of semilinear parabolic optimal control problems

In this paper, a priori error estimates for space–time finite element discretizations of optimal control problems governed by semilinear parabolic PDEs and subject to pointwise control constraints are derived. We extend the approach from Meidner and Vexler (SIAM Control Optim 47(3):1150–1177, 2008; SIAM Control Optim 47(3):1301–1329, 2008) where linear-quadratic problems have been considered, discretizing the state equation by usual conforming finite elements in space and a discontinuous Galerkin method in time. Error estimates for controls discretized by piecewise constant functions in time and cellwise constant functions in space are derived in detail and we explain how error estimate for further discretization approaches, e.g., cellwise linear discretization in space, the postprocessing approach from Meyer and R?sch (SIAM J Control Optim 43:970–985, 2004), and the variationally discrete approach from Hinze (J Comput Optim Appl 30:45–63, 2005) can be obtained. In addition, we derive an estimate for a setting with finitely many time-dependent controls.     

A combined splitting—cross entropy method for rare-event probability estimation of queueing networks

We present a fast algorithm for the efficient estimation of rare-event (buffer overflow) probabilities in queueing networks. Our algorithm presents a combined version of two well known methods: the splitting and the cross-entropy (CE) method. We call the new method SPLITCE. In this method, the optimal change of measure (importance sampling) is determined adaptively by using the CE method. Simulation results for a single queue and queueing networks of the ATM-type are presented. Our numerical results demonstrate higher efficiency of the proposed method as compared to the original splitting and CE methods. In particular, for a single server queue example we demonstrate numerically that both the splitting and the SPLITCE methods can handle our buffer overflow example problems with both light and heavy tails efficiently. Further research must show the full potential of the proposed method.     

Discrete time queueing networks with product form steady state. Availability and performance analysis in an integrated model

For a discrete time network of generalized Bernoulli servers with unreliable nodes we derive the steady state probabilities for the joint queue length vector for all nodes and the availability status of the network. This allows us to assess the performance behavior and the reliability, resp. availability, of the network in an integrated model. Because our result exhibits a product form for the steady state distribution it opens the path to fast algorithmic evaluation of the desired performance and reliability indices.     

Asymptotically optimal importance sampling for Jackson networks with a tree topology

This note describes an importance sampling (IS) algorithm to estimate buffer overflows of stable Jackson networks with a tree topology. Three new measures of service capacity and traffic in Jackson networks are introduced and the algorithm is defined in their terms. These measures are effective service rate, effective utilization and effective service-to-arrival ratio of a node. They depend on the nonempty/empty states of the queues of the network. For a node with a nonempty queue, the effective service rate equals the node’s nominal service rate. For a node i with an empty queue, it is either a weighted sum of the effective service rates of the nodes receiving traffic directly from node i, or the nominal service rate, whichever smaller. The effective utilization is the ratio of arrival rate to the effective service rate and the effective service-to-arrival ratio is its reciprocal. The rare overflow event of interest is the following: given that initially the network is empty, the system experiences a buffer overflow before returning to the empty state. Two types of buffer structures are considered: (1) a single system-wide buffer shared by all nodes, and (2) each node has its own fixed size buffer. The constructed IS algorithm is asymptotically optimal, i.e., the variance of the associated estimator decays exponentially in the buffer size at the maximum possible rate. This is proved using methods from (Dupuis et al. in Ann. Appl. Probab. 17(4):1306–1346, 2007), which are based on a limit Hamilton–Jacobi–Bellman equation and its boundary conditions and their smooth subsolutions. Numerical examples involving networks with as many as eight nodes are provided.     

The superiority of “optimal control” over simulation in policy analysis

The simulation approach to policy analysis usually concentrates on policy multipliers as a measure of the thrust of economic policy. However, this measure is inadequate for one branch of economic policy, namely, fiscal policy. The reason is that the effectiveness of fiscal policy depends, via the government budget constraint, on the method of finance. It is argued in this paper that for this very reason the conventional way of calculating simulation-based dynamic multipliers introduces a bias towards the no-crowding-out thesis. This bias arises even in models of monetarist persuasion. Furthermore, it is shown that this bias can be removed by utilizing multipliers based on optimal control. We illustrate this proposition by providing numerical results using a large-scale U.K. econometric model of international monetarist persuasion (the London Business School model, LBS). Section 1 builds up a framework through which policy optimization can be compared and evaluated to policy simulations. In Section 2 we derive and compare policy multipliers obtained through policy simulations and optimal control. Section 3 provides a numerical example with the findings being summarized in Section 4.     

The finite–horizon version for a partially–observed stochastic control problem of benesš & rishel

A Bayesian adaptive control problem with several interesting features, due to Bene? and Rishel, was treated as a stochastic control problem with partial observations – and on an infinite horizon with discounting – in thepapers [2] and [10]. We discuss here in full detail the finite–horizon version of that problem, by solving fairly explicitly the associated, fully nonlinear and degenerate, Hamilton-Jacobi-Bellman equation of parabolic type     

Optimal birth control of free horizon problems for predator-prey system with age-structure

We study optimal birth policies for three age-dependent populations in a predator-prey system, which is controlled by fertility. New results on problems with free final time and integral phase constraints are presented, the approximate controllability of system is discussed.     

Approximate solutions to infinite dimensional LQ problems over infinite time horizon

This paper is addressed to develop an approximate method to solve a class of infinite dimensional LQ optimal regulator problems over infinite time horizon. Our algorithm is based on a construction of approximate solutions which solve some finite dimensional LQ optimal regulator problems over finite time horizon, and it is shown that these approximate solutions converge strongly to the desired solution in the double limit sense.     

Dynamic control of a single-server system with abandonments

In this paper, we discuss the dynamic server control in a two-class service system with abandonments. Two models are considered. In the first case, rewards are received upon service completion, and there are no abandonment costs (other than the lost opportunity to gain rewards). In the second, holding costs per customer per unit time are accrued, and each abandonment involves a fixed cost. Both cases are considered under the discounted or average reward/cost criterion. These are extensions of the classic scheduling question (without abandonments) where it is well known that simple priority rules hold.     

Tractability of Multivariate Approximation over a Weighted Unanchored Sobolev Space

We study d-variate L ₂-approximation for a weighted unanchored Sobolev space having smoothness m≥1. This space is equipped with an unusual norm which is, however, equivalent to the norm of the d-fold tensor product of the standard Sobolev space. One might hope that the problem should become easier as its smoothness increases. This is true for our problem if we are only concerned with asymptotic analysis: the nth minimal error is of order n ^?(m?δ) for any δ>0. However, it is unclear how long we need to wait before this asymptotic behavior kicks in. How does this waiting period depend on d and m? It is easy to prove that no matter how the weights are chosen, the waiting period is at least m ^d , even if the error demand ε is arbitrarily close to 1. Hence, for m≥2, this waiting period is exponential in d, so that the problem suffers from the curse of dimensionality and is intractable. In other words, the fact that the asymptotic behavior improves with m is irrelevant when d is large. So we will be unable to vanquish the curse of dimensionality unless m=1, i.e., unless the smoothness is minimal. In this paper, we prove the more difficult fact that our problem can be tractable if m=1. That is, we can find an ε-approximation using polynomially-many (in d and ε ^?1) information operations, even if only function values are permitted. When m=1, it is even possible for the problem to be strongly tractable, i.e., we can find an ε-approximation using polynomially-many (in ε ^?1) information operations, independently of d. These positive results hold when the weights of the Sobolev space decay sufficiently quickly or are bounded finite-order weights, i.e., the d-variate functions we wish to approximate can be decomposed as sums of functions depending on at most ω variables, where ω is independent of d.     

Verification theorems for stochastic optimal control problems via a time dependent Fukushima–Dirichlet decomposition

This paper is devoted to presenting a method of proving verification theorems for stochastic optimal control of finite dimensional diffusion processes without control in the diffusion term. The value function is assumed to be continuous in time and once differentiable in the space variable (C^0,1$C^{0,1}$) instead of once differentiable in time and twice in space (C^1,2$C^{1,2}$), like in the classical results. The results are obtained using a time dependent Fukushima–Dirichlet decomposition proved in a companion paper by the same authors using stochastic calculus via regularization. Applications, examples and a comparison with other similar results are also given.     

On the dynamics of a finite buffer queue conditioned on the amount of loss

This paper is concerned with computing large-deviation asymptotics for the loss process in a stylized queueing model that is fed by a Brownian input process. In addition, the dynamics of the queue, conditional on such a large deviation in the loss, is calculated. Finally, the paper computes the quasi-stationary distribution of the system and the corresponding dynamics, conditional on no loss occurring.     

On the stationary distribution of queue lengths in a multi-class priority queueing system with customer transfers

This paper deals with a multi-class priority queueing system with customer transfers that occur only from lower priority queues to higher priority queues. Conditions for the queueing system to be stable/unstable are obtained. An auxiliary queueing system is introduced, for which an explicit product-form solution is found for the stationary distribution of queue lengths. Sample path relationships between the queue lengths in the original queueing system and the auxiliary queueing system are obtained, which lead to bounds on the stationary distribution of the queue lengths in the original queueing system. Using matrix-analytic methods, it is shown that the tail asymptotics of the stationary distribution is exact geometric, if the queue with the highest priority is overloaded.      

On the asymptotic optimality of the cμ-rule in queueing networks

Although the cμ-rule is proven to be exactly or asymptotically optimal in various parallel queueing networks, its performance in non-parallel queueing networks is relatively unexplored. We study the performance of the cμ-rule (that is, the performance of implementing the cμ-rule at all servers) in non-parallel queueing networks. We numerically show that the cμ-rule can perform poorly even in a simple tandem queue with two job types. We derive conditions under which the cμ-rule is asymptotically optimal in diffusion scale.