Computable bounds on parametric solutions of convex problems

We present a new method for computing bounds on parametric solutions of convex problems. The approach is based on a uniform quadratic underestimation of the objective function and a simple technique for the calculation of bounds on the optimal value function.Research supported by Grant ECS-8619859, National Science Foundation and Contract N00017-86-K-0052, Office of Naval Research.     

Weak convergence of Markov chain sampling methods and annealing algorithms to diffusions

Simulated annealing algorithms have traditionally been developed and analyzed along two distinct lines: Metropolis-type Markov chain algorithms and Langevin-type Markov diffusion algorithms. Here, we analyze the dynamics of continuous state Markov chains which arise from a particular implementation of the Metropolis and heat-bath Markov chain sampling methods. It is shown that certain continuous-time interpolations of the Metropolis and heat-bath chains converge weakly to Langevin diffusions running at different time scales. This exposes a close and potentially useful relationship between the Markov chain and diffusion versions of simulated annealing.The research reported here has been supported by the Whirlpool Foundation, by the Air Force Office of Scientific Research under Contract 89-0276, and by the Army Research Office under Contract DAAL-03-86-K-0171 (Center for Intelligent Control Systems).     

Control of partially observed diffusions

The optimal control of a partially observed diffusion is discussed when the control parameter is present in both the drift and diffusion coefficients. Using a differentiation result of Blagovescenskii and Freidlin, and adapting techniques of Bensoussan, we obtain a stochastic minimum principle.This research was partially supported by NSERC Grant A7964, by the US Air Force Office of Scientific Research Contract AFOSR-86-0332, and by the US Army Research Office Contract DAAL03-87-K-0102.     

Minimizing pseudoconvex functions on convex compact sets

An algorithm is presented which minimizes continuously differentiable pseudoconvex functions on convex compact sets which are characterized by their support functions. If the function can be minimized exactly on affine sets in a finite number of operations and the constraint set is a polytope, the algorithm has finite convergence. Numerical results are reported which illustrate the performance of the algorithm when applied to a specific search direction problem. The algorithm differs from existing algorithms in that it has proven convergence when applied to any convex compact set, and not just polytopal sets.This research was supported by the National Science Foundation Grant ECS-85-17362, the Air Force Office Scientific Research Grant 86-0116, the Office of Naval Research Contract N00014-86-K-0295, the California State MICRO program, and the Semiconductor Research Corporation Contract SRC-82-11-008.     

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.     

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.     

Sublinear upper bounds for stochastic programs with recourse

Separable sublinear functions are used to provide upper bounds on the recourse function of a stochastic program. The resulting problem's objective involves the inf-convolution of convex functions. A dual of this problem is formulated to obtain an implementable procedure to calculate the bound. Function evaluations for the resulting convex program only require a small number of single integrations in contrast with previous upper bounds that require a number of function evaluations that grows exponentially in the number of random variables. The sublinear bound can often be used when other suggested upper bounds are intractable. Computational results indicate that the sublinear approximation provides good, efficient bounds on the stochastic program objective value.This research has been partially supported by the National Science Foundation. The first author's work was also supported in part by Office of Naval Research Grant N00014-86-K-0628 and by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Superlinearly convergent algorithm for min-max problems

Algorithms for solving the problem of minimizing the maximum of a finite number of functions are proposed and analyzed. Quadratic approximations to the functions are employed in the determination of a search direction. Global convergence is proven and it is shown that a quadratic rate of convergence is obtained.This research was sponsored in part by National Science Foundation Grant ECS-81-21149, Air Force Office of Scientific Research Grant 83-0361, Office of Naval Research Contract N00014-83-K-0602, Semiconductor Research Corporation Contract SRC-82-11-008, State of California MICRO Program, and General Electric Company.     

Packet routing and job-shop scheduling inO(congestion+dilation) steps

In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, inO(c+d) steps, wherec is the congestion of the paths in the network, andd is the length of the longest path. The result has applications to packet routing in parallel machines, network emulations, and job-shop scheduling.This research was conducted while the authors were at MIT. Support was provided by the Defense Advanced Research Projects Agency under Contract N00014-87-K-825, the Office of Naval Research under Contract N00014-86-K-0593, the Air Force under Contract OSR-86-0076, and the Army under Contract DAAL-03-86-K-0171. Tom Leighton is supported by an NSF Presidential Young Investigator Award with matching funds provided by IBM.     

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.     

Linear/nonlinear forms and the normal law: Characterization by high order correlations

Summary The problem of characterizing the normal law associated with linear forms and processes, as well as with quadratic forms, is considered. The classical condition of constancy of regression is replaced by a distinct condition of high-order uncorrelatedness. The work of E. Masry was supported by the Office of Naval Research under Contract N00014-84-K-0042.     

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.     

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.     

Informational uniqueness of closed-loop Nash equilibria for a class of nonstandard dynamic games

This paper discusses an extension of the currently available theory of noncooperative dynamic games to game models whose state equations are of order higher than one. In a discrete-time framework, it first elucidates the reasons why the theory developed for first-order systems is not applicable to higher-order systems, and then presents a general procedure to obtain an informationally unique Nash equilibrium solution in the presence of random disturbances. A numerical example solved in the paper illustrates the general approach.Dedicated to G. LeitmannResearch that led to this paper was supported in part by the Office of Naval Research under Contract No N00014-82-K-0469 and in part by the U.S. Air Force under Grant No. AFOSR-84-0054.     

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.     

On stable laws for estimating functions and derived estimators

Summary Stable laws forM-estimators, maximum likelihood and other estimators and obtained through parallel results for the estimating functions and relative compactness of some related estimating functional processes. Work supported by the Office of Naval Research, Contract No. N00014-83-K-0387.     

Simplified Voronoi diagrams

We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in anr-dimensional space may be simplified to a search on an (r–1)-dimensional Voronoi diagram. We define a Voronoi diagramV based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion-planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the half-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the Euclidean metric.This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's Artificial Intelligence research is provided in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494 and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-85-K-0124 and N00014-82-K-0334. John Canny was supported by an IBM fellowship. Bruce Donald was funded in part by a NASA fellowship administered by the Jet Propulsion Laboratory.     

Scenario analysis via bundle decomposition

Scenario analysis, originally proposed by Rockafellar and Wets, is a widely applicable method for introducing uncertainty into practical decision problems. As it often leads to very large optimization problems, one needs special techniques for the resulting numerical computation. One such technique, the Progressive Hedging Algorithm, is simple and universally applicable, but it can be slow. In this paper we show how the bundle decomposition method can be applied to linear or convex scenario analysis problems that are loosely coupled. We illustrate its effectiveness by presenting computational results for military force planning problems and for multi-scenario network models of production planning.The research reported here was sponsored by the National Science Foundation under Grant CCR-9109345, by the Air Force Systems Command, USAF, under Grants AFOSR-91-0089 and F49620-93-1-0068, by the US Army Research Office under Contract DAAL03-89-K-0149 and Grant No. DAAL03-92-G-0408, and by the US Army Space and Strategic Defense Command under Contract No. DASG60-91-C-0144. The US Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

Stopping rules,permutation invariance and sufficiency principle

In the context of sequential (point as well as interval) estimation, a general formulation of permutation-invariant stopping rules is considered. These stopping rules lead to savings in the ASN at the cost of some elevation of the associated risk—a phenomenon which may be attributed to the violation of the sufficiency principle. For the (point and interval) sequential estimation of the mean of a normal distribution, it is shown that such permutation-invariant stopping rules may lead to a substantial saving in the ASN with only a small increase in the associated risk.Work partially supported by (i) Office of Naval Research, Contract Number N00014-85-K-0548, and (ii) Office of Naval Research, Contract Number N00014-83-K-0387.     

On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2}

In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions.The research underlying this report was supported by Grant ECS-8601660 of the National Science Foundation, Contract N00014-85-K-0198 with the Office of Naval Research, and Grant AFOSR-870292 of the Air Force Office of Scientific Research.