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.     

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.     

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).     

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.     

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.     

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.     

SomeL 1 existence and dependence results for semilinear elliptic equations under nonlinear boundary conditions

In this paper we study questions of existence, uniqueness, and continuous dependence for semilinear elliptic equations with nonlinear boundary conditions. In particular, we obtain results concerning the continuous dependence of the solutions on the nonlinearities in the problem, which in turn implies analogous results for a related parabolic problem. Such questions arise naturally in the study of potential theory, flow through porous media, and obstacle problems.Sponsored by the United States Army under Contract Nos. DAAG29-80-C-0041 and DAAL03-87-K-0043, and by the Air Force Office of Scientific Research under Contract No. AFOSR 84-0252 and by the National Science Foundation under Grant No. DMS-8505531. Research of the third author was carried out in part while visiting the Institute for Mathematics and Its Applications at the University of Minnesota.     

The optimal control of diffusions

Using a differentiation result of Blagovescenskii and Freidlin calculations of Bensoussan are simplified and the adjoint process identified in a stochastic control problem in which the control enters both the drift and diffusion coefficients. A martingale representation result of Elliott and Kohlmann is then used to obtain the integrand in a stochastic integral, and explicit forward and backward equations satisfied by the adjoint process are derived.This research was partially supported by NSERC under Grant A7964, the U.S. Air Force Office of Scientific Research under Contract AFOSR-86-0332, and the U.S. Army Research Office under Contract DAAL03-87-K-0102.     

Multi-sample cluster analysis using Akaike's Information Criterion

Summary Multi-sample cluster analysis, the problem of grouping samples, is studied from an information-theoretic viewpoint via Akaike's Information Criterion (AIC). This criterion combines the maximum value of the likelihood with the number of parameters used in achieving that value. The multi-sample cluster problem is defined, and AIC is developed for this problem. The form of AIC is derived in both the multivariate analysis of variance (MANOVA) model and in the multivariate model with varying mean vectors and variance-covariance matrices. Numerical examples are presented for AIC and another criterion calledw-square. The results demonstrate the utility of AIC in identifying the best clustering alternatives. This research was supported by Office of Naval Research Contract N00014-80-C-0408, Task NR042-443 and Army Research Office Contract DAAG 29-82-K-0155, at the University of Illinois at Chicago.     

A weighted gram-schmidt method for convex quadratic programming

Range-space methods for convex quadratic programming improve in efficiency as the number of constraints active at the solution decreases. In this paper we describe a range-space method based upon updating a weighted Gram-Schmidt factorization of the constraints in the active set. The updating methods described are applicable to both primal and dual quadratic programming algorithms that use an active-set strategy. Many quadratic programming problems include simple bounds on all the variables as well as general linear constraints. A feature of the proposed method is that it is able to exploit the structure of simple bound constraints. This allows the method to retain efficiency when the number ofgeneral constraints active at the solution is small. Furthermore, the efficiency of the method improves as the number of active bound constraints increases. 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. The work of Nicholas Gould was supported by the Science and Engineering Research Council of Great Britain.     

On solving boundary value problems for multi-scale systems using asymptotic approximations and multiple-shooting

This paper describes a method for obtaining the numerical solution of certain singularly perturbed boundary value problems for linear systems of ordinary differential equations whose solutions involve dynamics with multiple time scales. A technique to decouple different time scales using a Riccati transformation is presented. For the slow modes, which provide smooth solutions, regular perturbation expansion and multiple shooting strategies are combined. Fast modes, which are assumed to be significant only in endpoint layers, are computed after appropriate stretchings have been made in the system. Advantages of this approach include adaptability, flexible use of output points, and automatic determination of layer thicknesses.Dedicated to Professor Germund Dahlquist, with the hope that he will long continue to make significant and singular perturbations to the numerical analysis of differential equations.This research was supported in part by the National Science Foundation under Grant Number MCS-8301665 and by the U.S. Army Research Office under Grant Number DAAG29-82-K-0197.     

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.     

Fast algorithms for the integral equations of the inverse scattering problem

The Gelfand-Levitan and Marchenko equations of inverse scattering theory are integral equations with Toeplitz and Hankel kernels respectively. It is shown that these facts can be used to reduce the integral equations to differential equations which can be solved with an order of magnitude less computation than generally envisaged.This work was supported by the Army Research Office under Contract DAAG29-77-C-0042, by the Air Force Office of Scientific Research, Air Force Systems Command, under Contract AF44-620-74-C-0068 and the Australian Research Grants Committee.     

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.     

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     

Consistency of infinitesimal perturbation analysis estimators with rates

We study a class of infinitesimal perturbation analysis (IPA) algorithms for queueing systems with load-dependent service and/or arrival rates. Such IPA algorithms were originally motivated by applications to large queueing systems in conjunction with aggregation algorithms. We prove strong consistency of these estimators through a type of birth and death queue. This work was supported in part by the NSF under Grants Nos. ECS85-15449 and CDR-8803012, by ONR under Contracts Nos. N00014-89-J-0075 and N00014-90-K-1093, and by the US Army under Contract No. DAAL-03-83-K-0171. This paper was written while the author was with the Division of Applied Sciences at Harvard 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     

Relevance of the Bayesian paradigm for “applied probabilists”

This paper is based on an invited lecture given by the author at the ORSA/TIMS Special Interest Group on Applied Probability Conference onStatistical and Computational Problems in Probability Modeling, held at Williamsburg, Virginia, January 7–9, 1985.The theme of this paper is twofold. First, that members of the above group should be seriously concerned with issues of statistical inference — they should not stop short upon proposing a probability model. Second, that inference be undertaken via a strict adherence to the rules of probability — the Bayesian paradigm. To underscore a need for emphasizing the first theme, it may be pertinent to note that an overwhelming majority of the papers dealing with statistical and inferential issues that were presented at this conference were authored by members who did not claim to belong to the ORSA/TIMS Special Interest Group on Applied Probability.The lecture was followed by a panel discussion, with Drs. Lyle Broemeling and Edward Wegman of the Office of Naval Research as discussants. Dr. Robert Launer of the Army Research Office served as a moderator. Discussions from the floor included comments by Professors D. Harrington of Harvard University, E. Parzen of Texas A & M University, and R. Smith of Imperial College, London, England. This paper, and the comments of the panelists, are published in this volume of theAnnals of Operations Research, which is going to serve as a Proceedings of the Conference.Supported by Contract No. N00014-85-K-0202, Office of Naval Research, and Grant No. DAAG 29-84-K-0160, Army Research Office.     

Streams of a M/M/1 feedback queue in statistical equilibrium

Summary It is shown that, under statistical equilibrium, no stream in the M/M/1 feedback queue of Jackson [7], besides the exogenous input and the final output, is poissonian. The proof relies on martingale methods, especially the filtering formulas of [1].Work supported in part by Army Research Office Grant No. DAAG29-75-G-0189 and National Science Foundation Grant No. SOC76-80333, while the author was visiting the Dept. of Electrical Engineering and Computer Science at U.C. Berkeley