Value iteration in average cost Markov control processes on Borel spaces

This paper deals with discrete-time Markov control processes withBorel state and control spaces, with possiblyunbounded costs andnoncompact control constraint sets, and the average cost criterion. Conditions are given for the convergence of the value iteration algorithm to the optimal average cost, and for a sequence of finite-horizon optimal policies to have an accumulation point which is average cost optimal.This research was partially supported by the Consejo Nacional de Ciencia y Tecnología (CONACyT) under grant 1332-E9206.     

Efficient sample sizes in stochastic nonlinear programming

We consider a class of stochastic nonlinear programs for which an approximation to a locally optimal solution is specified in terms of a fractional reduction of the initial cost error. We show that such an approximate solution can be found by approximately solving a sequence of sample average approximations. The key issue in this approach is the determination of the required sequence of sample average approximations as well as the number of iterations to be carried out on each sample average approximation in this sequence. We show that one can express this requirement as an idealized optimization problem whose cost function is the computing work required to obtain the required error reduction. The specification of this idealized optimization problem requires the exact knowledge of a few problems and algorithm parameters. Since the exact values of these parameters are not known, we use estimates, which can be updated as the computation progresses. We illustrate our approach using two numerical examples from structural engineering design.     

Optimal convex correcting procedures in problems of high dimension

The properties of convex correcting procedures (CCPs) over sets of predictors are examined. It is shown that the minimization of the generalized error in a CCP is reduced to a quadratic programming problem. The conditions are studied under which a set of predictors cannot be reduced without degrading the accuracy of the corresponding optimal CCP. Experimental studies of the prognostic properties of CCPs for samples of one-dimensional linear regressions showed that CCP optimization can be an effective tool for regression variable selection.     

Adaptive control of constrained Markov chains: Criteria and policies

We consider the constrained optimization of a finite-state, finite action Markov chain. In the adaptive problem, the transition probabilities are assumed to be unknown, and no prior distribution on their values is given. We consider constrained optimization problems in terms of several cost criteria which are asymptotic in nature. For these criteria we show that it is possible to achieve the same optimal cost as in the non-adaptive case.We first formulate a constrained optimization problem under each of the cost criteria and establish the existence of optimal stationary policies.Since the adaptive problem is inherently non-stationary, we suggest a class ofAsymptotically Stationary (AS) policies, and show that, under each of the cost criteria, the costs of an AS policy depend only on its limiting behavior. This property implies that there exist optimal AS policies. A method for generating adaptive policies is then suggested, which leads to strongly consistent estimators for the unknown transition probabilities. A way to guarantee that these policies are also optimal is to couple them with the adaptive algorithm of [3]. This leads to optimal policies for each of the adaptive constrained optimization problems under discussion.This work was supported in part through United States-Israel Binational Science Foundation Grant BSF 85-00306.     

Blackwell Optimality in the Class of Markov Policies for Continuous-Time Controlled Markov Chains

This paper deals with Blackwell optimality for continuous-time controlled Markov chains with compact Borel action space, and possibly unbounded reward (or cost) rates and unbounded transition rates. We prove the existence of a deterministic stationary policy which is Blackwell optimal in the class of all admissible (nonstationary) Markov policies, thus extending previous results that analyzed Blackwell optimality in the class of stationary policies. We compare our assumptions to the corresponding ones for discrete-time Markov controlled processes.     

Infinite horizon asymptotic average optimality for large-scale parallel server networks

We study infinite-horizon asymptotic average optimality for parallel server networks with multiple classes of jobs and multiple server pools in the Halfin–Whitt regime. Three control formulations are considered: (1) minimizing the queueing and idleness cost, (2) minimizing the queueing cost under constraints on idleness at each server pool, and (3) fairly allocating the idle servers among different server pools. For the third problem, we consider a class of bounded-queue, bounded-state (BQBS) stable networks, in which any moment of the state is bounded by that of the queue only (for both the limiting diffusion and diffusion-scaled state processes). We show that the optimal values for the diffusion-scaled state processes converge to the corresponding values of the ergodic control problems for the limiting diffusion. We present a family of state-dependent Markov balanced saturation policies (BSPs) that stabilize the controlled diffusion-scaled state processes. It is shown that under these policies, the diffusion-scaled state process is exponentially ergodic, provided that at least one class of jobs has a positive abandonment rate. We also establish useful moment bounds, and study the ergodic properties of the diffusion-scaled state processes, which play a crucial role in proving the asymptotic optimality.     

Adaptive policies for time-varying stochastic systems under discounted criterion

We consider a class of time-varying stochastic control systems, with Borel state and action spaces, and possibly unbounded costs. The processes evolve according to a discrete-time equation x _{n + 1}=G _n (x _n , a _n , ξ_n), n=0, 1, … , where the ξ_n are i.i.d. ℜ^k-valued random vectors whose common density is unknown, and the G _n are given functions converging, in a restricted way, to some function G _∞ as n→∞. Assuming observability of ξ_n, we construct an adaptive policy which is asymptotically discounted cost optimal for the limiting control system x _n+1=G _∞ (x _n , a _n , ξ_n).     

Randomized pivot algorithms for P-matrix linear complementarity problems

We study orientations of the n-cube that come from simple principal pivot algorithms for the linear complementarity problem with a P-matrix. We show that these orientations properly generalize those that are obtained from linear objective functions on polytopes combinatorially equivalent to the cube. The orientations from LCP with a P-matrix may admit directed cycles. We give a sequence of problems on which the algorithm RANDOM-EDGE performs very badly. Received: February 12, 2001 / Accepted: September 9, 2001?Published online April 12, 2002     

Existence of Risk-Sensitive Optimal Stationary Policies for Controlled Markov Processes

In this paper we are concerned with the existence of optimal stationary policies for infinite-horizon risk-sensitive Markov control processes with denumerable state space, unbounded cost function, and long-run average cost. Introducing a discounted cost dynamic game, we prove that its value function satisfies an Isaacs equation, and its relationship with the risk-sensitive control problem is studied. Using the vanishing discount approach, we prove that the risk-sensitive dynamic programming inequality holds, and derive an optimal stationary policy. Accepted 1 October 1997     

Restricted 2-factor polytopes

The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph K _n , a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when ≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet inducing. Received March 4, 1997 / Revised version received September 7, 1998?Published online November 9, 1999     

Convergence of a queueing system in heavy traffic with general patience-time distributions

We analyze a sequence of single-server queueing systems with impatient customers in heavy traffic. Our state process is the offered waiting time, and the customer arrival process has a state dependent intensity. Service times and customer patient-times are independent; i.i.d. with general distributions subject to mild constraints. We establish the heavy traffic approximation for the scaled offered waiting time process and obtain a diffusion process as the heavy traffic limit. The drift coefficient of this limiting diffusion is influenced by the sequence of patience-time distributions in a non-linear fashion. We also establish an asymptotic relationship between the scaled version of offered waiting time and queue-length. As a consequence, we obtain the heavy traffic limit of the scaled queue-length. We introduce an infinite-horizon discounted cost functional whose running cost depends on the offered waiting time and server idle time processes. Under mild assumptions, we show that the expected value of this cost functional for the n-th system converges to that of the limiting diffusion process as n tends to infinity.     

Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow*

This paper presents two fast cycle canceling algorithms for the submodular ow problem. The rst uses an assignment problem whose optimal solution identies most negative node-disjoint cycles in an auxiliary network. Canceling these cycles lexicographically makes it possible to obtain an optimal submodular ow in O(n ⁴ h log(nC)) time, which almost matches the current fastest weakly polynomial time for submodular flow (where n is the number of nodes, h is the time for computing an exchange capacity, and C is the maximum absolute value of arc costs). The second algorithm generalizes Goldbergs cycle canceling algorithm for min cost flow to submodular flow to also get a running time of O(n ⁴ h log(nC)).. We show how to modify these algorithms to make them strongly polynomial, with running times of O(n ⁶ h log n), which matches the fastest strongly polynomial time bound for submodular flow. We also show how to extend both algorithms to solve submodular flow with separable convex objectives. * An extended abstract of a preliminary version of part of this paper appeared in [22]. Research supported in part by a Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan. Research supported by an NSERC Operating Grant. Part of this research was done during a sabbatical leave at Cornell SORIE.§ Research supported in part by a Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan.     

Stability and augmented Lagrangian duality in nonconvex semi-infinite programming

In this paper the pseudo-Lipschitz property of the constraint set mapping and the Lipschitz property of the optimal value function of parametric nonconvex semi-infinite optimization problems are obtained under suitable conditions on the limiting subdifferential and the limiting normal cone. Then we derive sufficient conditions for the strong duality of nonconvex semi-infinite optimality problems and a criterion for exact penalty representations via an augmented Lagrangian approach. Examples are given to illustrate the obtained results.     

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

A new polynomial-time algorithm for linear programming

We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n ^3.5 L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n ^2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C., April 1984.