On optimal polling policies

In a single-server polling system, the server visits the queues according to a routing policy and while at a queue, serves some or all of the customers there according to a service policy. A polling (or scheduling) policy is a sequence of decisions on whether to serve a customer, idle the server, or switch the server to another queue. The goal of this paper is to find polling policies that stochastically minimize the unfinished work and the number of customers in the system at all times. This optimization problem is decomposed into three subproblems: determine the optimal action (i.e., serve, switch, idle) when the server is at a nonempty queue; determine the optimal action (i.e., switch, idle) when the server empties a queue; determine the optimal routing (i.e., choice of the queue) when the server decides to switch. Under fairly general assumptions, we show for the first subproblem that optimal policies are greedy and exhaustive, i.e., the server should neither idle nor switch when it is at a nonempty queue. For the second subproblem, we prove that in symmetric polling systems patient policies are optimal, i.e., the server should stay idling at the last visited queue whenever the system is empty. When the system is slotted, we further prove that non-idling and impatient policies are optimal. For the third subproblem, we establish that in symmetric polling systems optimal policies belong to the class of Stochastically Largest Queue (SLQ) policies. An SLQ policy is one that never routes the server to a queue known to have a queue length that is stochastically smaller than that of another queue. This result implies, in particular, that the policy that routes the server to the queue with the largest queue length is optimal when all queue lengths are known and that the cyclic routing policy is optimal in the case that the only information available is the previous decisions.This work was supported in part by NSF under Contract ASC-8802764.     

Disintegration of Gaussian measures and average-case optimal algorithms

It is shown that a Gaussian measure in a given infinite-dimensional Banach space always admits an essentially unique Gaussian disintegration with respect to a given continuous linear operator. This covers a similar statement made earlier in [Lee and Wasilkowski, Approximation of linear functionals on a Banach space with a Gaussian measure, J. Complexity 2(1) (1986) 12–43.] for the case of finite-rank operators.     

从最优规模到更大的最优规模--理性企业规模的线性优化

企业效益是以规模为基础的，不同企业最优规模及达到的方式不同。本讨论了企业为获得最优效益，在理性、线性的最优规模下处理过剩资源，单纯的规模扩张及价格与产量关系线性时的规模扩张。指出在初步最优规模，无过剩资源时，单纯的规模扩张以资源同增长的方式最优；在价格与产量关系线性时，企业有最优扩张系数，最大的最优规模。     

On the Quasiconcave Bilevel Programming Problem

Bilevel programming involves two optimization problems where the constraint region of the first-level problem is implicitly determined by another optimization problem. In this paper, we consider the case in which both objective functions are quasiconcave and the constraint region common to both levels is a polyhedron. First, it is proved that this problem is equivalent to minimizing a quasiconcave function over a feasible region comprised of connected faces of the polyhedron. Consequently, there is an extreme point of the polyhedron that solves the problem. Finally, it is shown that this model includes the most important case where the objective functions are ratios of concave and convex functions     

Inexact primal-dual interior point iteration for linear programs in function spaces

Motivated by a simple optimal control problem with state constraints, we consider an inexact implementation of the primal-dual interior point algorithm of Zhang, Tapia, and Dennis. We show how the control problem can be formulated as a linear program in an infinite dimensional space in two different ways and prove convergence results.The research of this author was supported by an Overseas Research Scholarship of the Ministry of Education, Science and Culture of Japan.The research of this author was supported by National Science Foundation grants #DMS-9024622 and #DMS-9321938, North Atlantic Treaty Organization grant #CRG 920067, and an allocation of computing resources from the North Carolina Supercomputing Program.The research of this author was supported by North Atlantic Treaty Organization grant #CRG 920067.     

Stability and performance analysis of rate-based feedback flow controlled ATM networks

Motivated by ABR class of service in ATM networks, we study a continuous time queueing system with a feedback control of the arrival rate of some of the sources. The feedback about the queue length or the total workload is provided at regular intervals (variations on it, especially the traffic management specification TM 4.0, are also considered). The propagation delays can be nonnegligible. For a general class of feedback algorithms, we obtain the stability of the system in the presence of one or more bottleneck nodes in the virtual circuit. Our system is general enough that it can be useful to study feedback control in other network protocols. We also obtain rates of convergence to the stationary distributions and finiteness of moments. For the single botterneck case, we provide algorithms to compute the stationary distributions and the moments of the sojourn times in different sets of states. We also show analytically (by showing continuity of stationary distributions and moments) that for small propagation delays, we can provide feedback algorithms which have higher mean throughput, lower probability of overflow and lower delay jitter than any open loop policy. Finally these results are supplemented by some computational results. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic analysis of stochastic programs

In this paper we discuss a general approach to studying asymptotic properties of statistical estimators in stochastic programming. The approach is based on an extended delta method and appears to be particularly suitable for deriving asymptotics of the optimal value of stochastic programs. Asymptotic analysis of the optimal value will be presented in detail. Asymptotic properties of the corresponding optimal solutions are briefly discussed.     

席位分配问题的数学模型

本文研究席位分配问题的求解方法及最优性评价标准 ,同时对现有方法的优缺点进行了分析 ,由此建立了充分体现所有成员平等的数学模型 ,并给出单位获得席位的检验数为 :bi=2 ni+ 1pi ,1 i m.     

Geometry of optimal value functions with applications to redundancy in linear programming

In 1967, Wets and Witzgall (Ref. 1) made, in passing, a connection between frames of polyhedral cones and redundancy in linear programming. The present work elaborates and formalizes the theoretical details needed to establish this relation. We study the properties of optimal value functions in order to derive the correspondence between problems in redundancy and the frame of a polyhedral cone. The insights obtained lead to schemes to improve the efficiency of procedures to detect redundancy in the areas of linear programming, stochastic programming, and computational geometry.The author is indebted to G. Dewan for his review and discussions.     

Design and optimal tuning of nonlinear PI compensators

In this paper, linear time-invariant single-input single-output (SISO) systems that are stabilizable by linear proportional and integral (PI) compensators are considered. For such systems, a five-parameter nonlinear PI compensator is proposed. The parameters of the proposed compensator are tuned by solving an optimization problem. The optimization problem always has a solution.Additionally, a general nonlinear PI compensator is proposed and is approximated by easy-to-compute compensators, for instance, a six-parameter nonlinear PI compensator. The parameters of the approximate compensators are tuned to satisfy an optimality condition. The superiority of the proposed nonlinear PI compensators over linear PI compensators is discussed and is demonstrated for two feedback systems.