Affine scaling algorithm fails for semidefinite programming

In this paper, we introduce an affine scaling algorithm for semidefinite programming (SDP), and give an example of a semidefinite program such that the affine scaling algorithm converges to a non-optimal point. Both our program and its dual have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and they are non-degenerate everywhere.     

Single-server queues with spatially distributed arrivals

Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.     

An extended continuous Newton method

This paper describes a numerical realization of an extended continuous Newton method defined by Diener. It traces a connected set of locally one-dimensional trajectories which contains all critical points of a smooth functionf: ⁿ . The results show that the method is effectively applicable.The authors would like to thank L. C. W. Dixon for pointing out some errors in the original version of this paper and for several suggestions of improvements.     

Relationships between characteristics in periodic Poisson queues

We study single server periodic queues in the day equilibrium conditions. The following characteristics of interest are considered at time of dayt: V^p(t)-the work load, L^p(t)-the number of customers and u^p(t)-the departure rate. We give relationships between E[V^p(t)], E[L^p(t)] and u^p(t). We also prove that E[V^p(t)] < and E[L^p(t)] < provided the second moment of the service time is finite.     

On consistency of bounding operations in deterministic global optimization

This technical comment refers to the discussion of strong consistency of several bounding procedures in Lemma 2.1 and Proposition 2.1 of Ref. 1. A necessary clarification is given of the notion of convergence _q in Lemma 2.1, and a derivation of Proposition 2.1 is presented that includes a new and simple consistency proof of the classical bounding by convex envelopes used in many branch-and-bound procedures.     

Random tunneling by means of acceptance-rejection sampling for global optimization

Any global minimization algorithm is made by several local searches performed sequentially. In the classical multistart algorithm, the starting point for each new local search is selected at random uniformly in the region of interest. In the tunneling algorithm, such a starting point is required to have the same function value obtained by the last local minimization. We introduce the class of acceptance-rejection based algorithms in order to investigate intermediate procedures. A particular instance is to choose at random the new point approximately according to a Boltzmann distribution, whose temperatureT is updated during the algorithm. AsT 0, such distribution peaks around the global minima of the cost function, producing a kind of random tunneling effect. The motivation for such an approach comes from recent works on the simulated annealing approach in global optimization. The resulting algorithm has been tested on several examples proposed in the literature.     

Some Properties of Solutions to the Novikov Equation with Weak Dissipation Terms

In this paper, we investigate the Novikov equation with weak dissipation terms. First, we give the local well-posedness and the blow-up scenario. Then, we discuss the global existence of the solutions under certain conditions. After that, on condition that the compactly supported initial data keeps its sign, we prove the infinite propagation speed of our solutions, and establish the large time behavior. Finally, we also elaborate the persistence property of our solutions in weighted Sobolev space.     

Large deviation analysis of the single server queue

We establish the large deviation principle (LDP) for the virtual waiting time and queue length processes in the GI/GI/1 queue. The rate functions are found explicitly. As an application, we obtain the logarithmic asymptotics of the probabilities that the virtual waiting time and queue length exceed high levels at large times. Additional new results deal with the LDP for renewal processes and with the derivation of unconditional LDPs for conditional ones. Our approach applies in large deviations ideas and methods of weak convergence theory.This work was supported in part by AT&T Bell Labs.     

Computing global minima to polynomial optimization problems using Gröbner bases

The local optimality conditions to polynomial optimization problems are a set of polynomial equations (plus some inequality conditions). With the recent techniques of Gröbner bases one can find all solutions to such systems, and hence also find global optima. We give a short survey of these methods. We also apply them to a set of problems termed with exact solutions unknown in the problem sets of Hock and Schittkowski. To these problems we give exact solutions.     

Rate conservation laws: A survey

We survey the rate conservation law, RCL for short, arising in queues and related stochastic models. RCL was recognized as one of the fundamental principles to get relationships between time and embedded averages such as the extended Little's formulaH=G, but we show that it has other applications. For example, RCL is one of the important techniques for deriving equilibrium equations for stochastic processes. It is shown that the various techniques, including Mecke's formula for a stationary random measure, can be formulated as RCL. For this purpose, we start with a new definition of the rate with respect to a random measure, and generalize RCL by using it. We further introduce the notion of quasi-expectation, which is a certain extension of the ordinary expectation, and derive RCL applicable to the sample average results. It means that the sample average formulas such asH=G can be obtained as the stationary RCL in the quasi-expectation framework. We also survey several extensions of RCL and discuss examples. Throughout the paper, we would like to emphasize how results can be easily obtained by using a simple principle, RCL.