Simulation methods for queues: An overview

This paper gives an overview of those aspects of simulation methodology that are (to some extent) peculiar to the simulation of queueing systems. A generalized semi-Markov process framework for describing queueing systems is used through much of the paper. The main topics covered are: output analysis for simulation of transient and steady-state quantities, variance reduction methods that exploit queueing structure, and gradient estimation methods for performance parameters associated with queueing networks.The research of this author was supported by the U.S. Army Research Office under Contract DAAG29-84-K-0030.The research of this author was supported by the U.S. Army Research Office under Contract DAAG29-84-K-0030 and National Science Foundation Grant DCR-85-09668.     

An upper bound for the speedup of parallel best-bound branch-and-bound algorithms

This paper derives an upper bound for the speedup obtainable by any parallel branch-and-bound algorithm using the best-bound search strategy. We confirm that parallel branch-and-bound can achieve nearly linear, or even super-linear, speedup under the appropriate conditions.This work was supported by U.S. Army Research Office grant DAAG29-82-K-0107.     

Approximate solution of the trust region problem by minimization over two-dimensional subspaces

The trust region problem, minimization of a quadratic function subject to a spherical trust region constraint, occurs in many optimization algorithms. In a previous paper, the authors introduced an inexpensive approximate solution technique for this problem that involves the solution of a two-dimensional trust region problem. They showed that using this approximation in an unconstrained optimization algorithm leads to the same theoretical global and local convergence properties as are obtained using the exact solution to the trust region problem. This paper reports computational results showing that the two-dimensional minimization approach gives nearly optimal reductions in then-dimension quadratic model over a wide range of test cases. We also show that there is very little difference, in efficiency and reliability, between using the approximate or exact trust region step in solving standard test problems for unconstrained optimization. These results may encourage the application of similar approximate trust region techniques in other contexts.Research supported by ARO contract DAAG 29-84-K-0140, NSF grant DCR-8403483, and NSF cooperative agreement DCR-8420944.     

On monotone Abel-Volterra integral equations on the half line

Summary In this paper we reanalyze the trapezoidal method for the solution of nonlinear Abel-Volterra integral equations on the half line. We prove the convergence of the method in the uniform norm, provided the nonlinearity is Lipschitz-continuous and strictly monotone.Research supported in part by the United States Army under contracts DAAG29-83-K-0109 and DAAG 29-85-G-0009     

Linear complexity algorithms for semiseparable matrices

Linear complexity algorithms are derived for the solution of a linear system of equations with the coefficient matrix represented as a sum of diagonal and semiseparable matrices. LDU-factorization algorithms for such matrices and their inverses are also given. The case in which the solution can be efficiently update is treated separately.This work was supported in part by the U.S. Army Research Office, under Contract DAAG29-83-K-0028, and the Air Force Office of Scientific Research, Air Force Systems Command under Contract AF83-0228.     

Mean stochastic comparison of diffusions

Summary Stochastic bounds are derived for one dimensional diffusions (and somewhat more general random processes) by dominating one process pathwise by a convex combination of other processes. The method permits comparison of diffusions with different diffusion coefficients. One interpretation of the bounds is that an optimal control is identified for certain diffusions with controlled drift and diffusion coefficients, when the reward function is convex. An example is given to show how the bounds and the Liapunov function technique can be applied to yield bounds for multidimensional diffusions.This work was supported by the Office of Naval Research under Contract N00014-82-K-0359 and the U.S. Army Research Office under Contract DAAG29-82-K-0091 (administered through the University of California at Berkeley).     

Controlled diffusions with boundary-crossing costs

This paper considers control of nondegenerate diffusions in a bounded domain with a cost associated with the boundary-crossings of a subdomain. Existence of optimal Markov controls and a verification theorem are established.Research supported by ARO Contract No. DAAG29-84-K-0005 and AFOSR 85-0227.     

Properties of a representation of a basis for the null space

Given a rectangular matrixA(x) that depends on the independent variablesx, many constrained optimization methods involve computations withZ(x), a matrix whose columns form a basis for the null space ofA ^T(x). WhenA is evaluated at a given point, it is well known that a suitableZ (satisfyingA ^T Z = 0) can be obtained from standard matrix factorizations. However, Coleman and Sorensen have recently shown that standard orthogonal factorization methods may produce orthogonal bases that do not vary continuously withx; they also suggest several techniques for adapting these schemes so as to ensure continuity ofZ in the neighborhood of a given point.This paper is an extension of an earlier note that defines the procedure for computingZ. Here, we first describe howZ can be obtained byupdating an explicit QR factorization with Householder transformations. The properties of this representation ofZ with respect to perturbations inA are discussed, including explicit bounds on the change inZ. We then introduceregularized Householder transformations, and show that their use implies continuity of the full matrixQ. The convergence ofZ andQ under appropriate assumptions is then proved. Finally, we indicate why the chosen form ofZ is convenient in certain methods for nonlinearly constrained optimization.The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AM03-76SF00326, PA No. DE-AT03-76ER72018; the National Science Foundation Grants MCS-7926009 and ECS-8312142; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-84-K-0156.The research of G.W. Stewart was supported by the Air Force Office of Scientific Research Contract AFOSR-82-0078.     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

Parallel quasi-Newton methods for unconstrained optimization

We discuss methods for solving the unconstrained optimization problem on parallel computers, when the number of variables is sufficiently small that quasi-Newton methods can be used. We concentrate mainly, but not exclusively, on problems where function evaluation is expensive. First we discuss ways to parallelize both the function evaluation costs and the linear algebra calculations in the standard sequential secant method, the BFGS method. Then we discuss new methods that are appropriate when there are enough processors to evaluate the function, gradient, and part but not all of the Hessian at each iteration. We develop new algorithms that utilize this information and analyze their convergence properties. We present computational experiments showing that they are superior to parallelization either the BFGS methods or Newton's method under our assumptions on the number of processors and cost of function evaluation. Finally we discuss ways to effectively utilize the gradient values at unsuccessful trial points that are available in our parallel methods and also in some sequential software packages.Research supported by AFOSR grant AFOSR-85-0251, ARO contract DAAG 29-84-K-0140, NSF grants DCR-8403483 and CCR-8702403, and NSF cooperative agreement DCR-8420944.     

A note on a sufficient-decrease criterion for a non-derivative step-length procedure

A step-length algorithm is an essential part of many descent methods for unconstrained and constrained optimization. In this note we present a criterion that defines an acceptable step length when only function values are available at trial step lengths.This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110.     

Optimal impulse control problems for degenerate diffusions with jumps

Optimal stopping and impulse control problems for degenerate diffusion with jumps are studied in this paper. Lipschitzian coefficients for the diffusion process, data with polynomial growth, and evolution in the whole space are the main assumptions on the models. Several characterizations of the optimal cost functions are given. Existence of optimal policies is obtained.This research has been supported in part by Army Research Office Contract DAAG29-83-K-0014 and by National Science Foundation Grant DMS-8601998.     

Using parallel function evaluations to improve hessian approximation for unconstrained optimization

This paper presents a new class of methods for solving unconstrained optimization problems on parallel computers. The methods are intended to solve small to moderate dimensional problems where function and derivative evaluation is the dominant cost. They utilize multiple processors to evaluate the function, (finite difference) gradient, and a portion of the finite difference Hessian simultaneously at each iterate. We introduce three types of new methods, which all utilize the new finite difference Hessian information in forming the new Hessian approximation at each iteration; they differ in whether and how they utilize the standard secant information from the current step as well. We present theoretical analyses of the rate of convergence of several of these methods. We also present computational results which illustrate their performance on parallel computers when function evaluation is expensive.Research supported by AFOSR grant AFOSR-85-0251, ARO contract DAAG 29-84-K-0140, NSF grant DCR-8403483, and NFS cooperative agreement DCR -8420944.     

Concurrent stochastic methods for global optimization

The global optimization problem, finding the lowest minimizer of a nonlinear function of several variables that has multiple local minimizers, appears well suited to concurrent computation. This paper presents a new parallel algorithm for the global optimization problem. The algorithm is a stochastic method related to the multi-level single-linkage methods of Rinnooy Kan and Timmer for sequential computers. Concurrency is achieved by partitioning the work of each of the three main parts of the algorithm, sampling, local minimization start point selection, and multiple local minimizations, among the processors. This parallelism is of a coarse grain type and is especially well suited to a local memory multiprocessing environment. The paper presents test results of a distributed implementation of this algorithm on a local area network of computer workstations. It also summarizes the theoretical properties of the algorithm.Research supported by AFOSR grant AFOSR-85-0251, ARO contract DAAG 29-84-K-0140, NSF grant DCR-8403483, and NSF cooperative agreement DCR-8420944.     

A dual differentiable exact penalty function

A new penalty function is associated with an inequality constrained nonlinear programming problem via its dual. This penalty function is globally differentiable if the functions defining the original problem are twice globally differentiable. In addition, the penalty parameter remains finite. This approach reduces the original problem to a simple problem of maximizing a globally differentiable function on the product space of a Euclidean space and the nonnegative orthant of another Euclidean space. Many efficient algorithms exist for solving this problem. For the case of quadratic programming, the penalty function problem can be solved effectively by successive overrelaxation (SOR) methods which can handle huge problems while preserving sparsity features. Sponsored by the United States Army under Contract No. DAAG 29-80-C-0041. This material is based upon work supported by the National Science Foundation under Grants No. MCS-790166 and ENG-7903881.     

Sample-path analysis of processes with imbedded point processes

The purpose of this paper is to review, unify, and extend previous work on sample-path analysis of queues. Our main interest is in the asymptotic behavior of a discrete-state, continuous-time process with an imbedded point process. We present a sample-path analogue of the renewal-reward theorem, which we callY=X. We then applyY=X to derive several relations involving the transition rates and the asymptotic (long-run) state frequencies at an arbitrary point in time and at the points of the imbedded point process. Included are sample-path versions of the rate-conservation principle, the global-balance conditions, and the insensitivity of the asymptotic frequency distribution to the distribution of processing time in a LCFS-PR service facility. We also provide a natural sample-path characterization of the PASTA property.The research of this author was partially supported by the U.S. Army Research Office, Contract DAAG29-82-K-0151 at N.C. State University, and by the National Science Foundation, Grant No. ECS-8719825, at the University of North Carolina, Chapel Hill.The research of this author was partially supported by the U.S. Army Research Office, Contract DAAG29-82-K-0151 at N.C. State University.     

Stability and robustness of collocation methods for Abel-type integral equations

Summary We study stability aspects of collocation methods for Abel-type integral equations of the first kind using piecewise polynomials. These collocation methods may be formulated as projection methods. Stability is defined as the boundedness of the sequence of projectors in their natural setting. Robustness is essentially the optimal asymptotic insensitivity to perturbations in the data. We show that stability and robustness are equivalent for the above collocation methods. This allows us to obtain optimal error estimates for some methods that are well-known to be robust. We also present numerical results for some methods which appear to be robust.Research supported in part by the United States Army under Contract No. DAAG 29-83-K-0109     

On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method

Interest in linear programming has been intensified recently by Karmarkar’s publication in 1984 of an algorithm that is claimed to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming, the transformed problem can be solved by a “projected Newton barrier” method. This method is shown to be equivalent to Karmarkar’s projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications for future developments in linear programming are discussed. The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AA03-76SF00326, PA No. DE-AS03-76ER72018; National Science Foundation Grants DCR-8413211 and ECS-8312142; the Office of Naval Research Contract N00014-85-K-0343; and the U.S. Army Research Office Contract DAAG29-84-K-0156. The research of J.A. Tomlin was supported by Ketron, Inc. and the Office of Naval Research Contract N00014-85-C-0338.     

An Ergodic Control Problem for Reflected Diffusion with Jump

The control of the drift of a stochastic differential equationwith jump term is considered for the long-run average cost.The convergence of the discounted problem is studied, as wellas the corresponding dynamic programming condition. This research was supported in part by U.S. Army Research Officeunder contract DAAG29-83-K-0014 and completed during a visitto INRIA.     

Canonical representations of partial 2- and 3-trees

We give algorithms constructing canonical representations of partial 2-trees (series parallel graphs) and partial 3-trees. The algorithms can be implemented in log-linear space, or in linear time using quadratic space.Supported in part by a grant from the Swedish Natural Science Research Council.Research supported in part by the Office of Naval Research Contract N00014-86-K-0419.