Newton's method for a class of nonsmooth functions

This paper presents and justifies a Newton iterative process for finding zeros of functions admitting a certain type of approximation. This class includes smooth functions as well as nonsmooth reformulations of variational inequalities. We prove for this method an analogue of the fundamental local convergence theorem of Kantorovich including optimal error bounds.The research reported here was sponsored by the National Science Foundation under Grants CCR-8801489 and CCR-9109345, by the Air Force Systems Command, USAF, under Grants AFOSR-88-0090 and F49620-93-1-0068, by the U. S. Army Research Office under Grant No. DAAL03-92-G-0408, and by the U. S. Army Space and Strategic Defense Command under Contract No. DASG60-91-C-0144. The U. S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

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.     

Implementation of a continuation method for normal maps

This paper presents an implementation of a nonsmooth continuation method of which the idea was originally put forward by Alexander et al. We show how the method can be computationally implemented and present numerical results for variational inequality problems in up to 96 variables. The research reported here was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAH04-95-1-0149, and by the National Science Foundation under grant number CCR-9109345. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the sponsoring agencies or the U.S. Government.     

Nonsingularity and symmetry for linear normal maps

Normal maps are single-valued, generally nonsmooth functions expressing conditions for the solution of variational problems such as those of optimization or equilibrium. Normal maps arising from linear transformations are particularly important, both in their own right and as predictors of the behavior of related nonlinear normal maps. They are called (locally or globally)nonsingular if the functions appearing in them are (local or global) homeomorphisms satisfying a Lipschitz condition. We show here that when the linear transformation giving rise to such a normal map has a certain symmetry property, the necessary and sufficient condition for nonsingularity takes a particularly simple and convenient form, being simply a positive definiteness condition on a certain subspace.This paper in dedicated to Phil Wolfe on the occasion of his 65th birthday.The research reported here was sponsored by the National Science Foundation under Grant CCR-9109345, by the Air Force Systems Command, USAF, under Grant AFOSR-91-0089, by the U.S. Army Research Office under Contract No. DAAL03-89-K-0149, and by the U.S. Army Strategic Defense Command under Contract 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.     

A reduction method for variational inequalities

This paper explains a method by which the number of variables in a variational inequality having a certain form can be substantially reduced by changing the set over which the variational inequality is posed. The method applies in particular to certain economic equilibrium problems occurring in applications. We explain and justify the method, and give examples of its application, including a numerical example in which the solution time for the reduced problem was approximately 2% of that for the problem in its original form. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.The research reported here was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number F49620-95-1-0222, and by the U.S. Army Research Office under grant number DAAH04-95-1-0149. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the sponsoring agencies or the U.S. Government.     

Wachspress type rational complex planar splines of degree (3,1)

We study the existence, uniqueness and approximation properties of rational complex planar spline interpolants of order (3, 1). We also find sufficient conditions for such interpolants to be quasiregular and quasiconformal. Examples are given. This work was carried out with the aid of MACSYMA, a large symbolic manipulation program developed at the MIT Laboratory for Computer Science and supported from 1975 to 1983 by the National Aeronautics and Space Administration under grant NSG 1323, by the Office of Naval Research under grant N00014-77C-0641, by the U.S. Department of Energy under grant ET-78-C-024687, and by the U.S. Air Force under grant F49620-79-C-020, and since 1982 by Symbolics, Inc. of Burlington, MA.     

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.     

On the pricing of American options

The problem of valuation for contingent claims that can be exercised at any time before or at maturity, such as American options, is discussed in the manner of Bensoussan [1]. We offer an approach which both simplifies and extends the results of existing theory on this topic.Research supported in part by the National Science Foundation under Grant No. NSF-DMS-84-16736 and by the Air Force Office of Scientific Research under Grant No. F49620-85-C-0144.     

Numerical experiments with the LANCELOT package (release A) for large-scale nonlinear optimization

In this paper, we describe the algorithmic options of Release A of LANCELOT, a Fortran package for large-scale nonlinear optimization. We then present the results of intensitive numberical tests and discuss the relative merits of the options. The experiments described involve both academic and applied problems. Finally, we propose conclusion, both specific to LANCELOT and of more general scope. This research was supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079     

Optimal interception with time constraint

This paper considers the problem of minimum-fuel interception with time constraint. The maneuver consists of using impulsive thrust to bring the interceptor from its initial orbit into a collision course with a target which is moving on a well-defined trajectory. The intercept time is either prescribed or is restricted to be less than an upper limit.The necessary conditions and the transversality conditions for optimality are discussed. The method of solution amounts to first solving a set of equations to obtain the primer vector for an initial one-impulse solution. Then, based on the information provided by the primer vector, rules are established to search for the optimal solution if the initial one-impulse trajectory is not optimal. The method is general, in the sense that it allows for solving the problem of three-dimensional interception with arbitrary motion for the target.Several numerical examples are presented, including orbital interceptions and interception at hyperbolic speeds of a ballistic missile.This research was supported by US Army Strategic Defense Command, Contract No. DASG60-88-C-0037.     

High-order adaptive finite element-singly implicit Runge-Kutta methods for parabolic differential equations

We describe an adaptive mesh refinement finite element method-of-lines procedure for solving one-dimensional parabolic partial differential equations. Solutions are calculated using Galerkin's method with a piecewise hierarchical polynomial basis in space and singly implicit Runge-Kutta (SIRK) methods in time. A modified SIRK formulation eliminates a linear systems solution that is required by the traditional SIRK formulation and leads to a new reduced-order interpolation formula. Stability and temporal error estimation techniques allow acceptance of approximate solutions at intermediate stages, yielding increased efficiency when solving partial differential equations. A priori energy estimates of the local discretization error are obtained for a nonlinear scalar problem. A posteriori estimates of local spatial discretization errors, obtained by order variation, are used with the a priori error estimates to control the adaptive mesh refinement strategy. Computational results suggest convergence of the a posteriori error estimate to the exact discretization error and verify the utility of the adaptive technique.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-90-0194; the U.S. Army Research Office under Contract Number DAAL 03-91-G-0215; by the National Science Foundation under Grant Number CDA-8805910; and by a grant from the Committee on Research, Tulane University.     

A note on exploiting structure when using slack variables

We show how to exploit the structure inherent in the linear algebra for constrained nonlinear optimization problems when inequality constraints have been converted to equations by adding slack variables and the problem is solved using an augmented Lagrangian method.This research was supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079. The United States Goverment is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.Corresponding author.     

The Skorohod integral and the derivative operator of functional of a cylindrical Brownian motion

The paper presents a definition of the Skorohod integral of operator-valued processes and the derivative operator for functional of a cylindrical Brownian motionW on a Hilbert space. The method is based on the chaos expansions in terms of multiple Wiener integrals ofW.This research was partially supported by the U.S. Air Force Office of Scientific Research Contract No. F49620 85C 0144. The research of V. Pérez-Abreu was also supported by CONACYT Grant D111-904237.     

On inverses of Vandermonde and confluent Vandermonde matrices III

Summary We derive lower bounds for the norm of the inverse Vandermonde matrix and the norm of certain inverse confluent Vandermonde matrices. They supplement upper bounds which were obtained in previous papers.Sponsored in part by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under grant MCS 76-00842A01     

On the behavior of ECN/RED gateways under a large number of TCP flows: Limit theorems

We consider a discrete-time stochastic model of an ECN/RED gateway where competing TCP sources share the link capacity. As the number of competing flows becomes large, the asymptotic queue behavior (normalized by the number of flows) at the gateway can be described by a simple recursion and the throughput behavior of individual TCP flows becomes asymptotically independent. A Central Limit Theorem complement is also presented, yielding a more accurate characterization of the asymptotic queue size. These results suggest a scalable yet accurate model of this complex large-scale stochastic feedback system, and crisply reveal the sources of queue fluctuations. This work was prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. This work was also supported by the Space and Naval Warfare Systems Center—San Diego under Contract No: N66001-00-C-8063. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government.     

A posteriori error estimation with finite element methods of lines for one-dimensional parabolic systems

Summary Consider the solution of one-dimensional linear initial-boundary value problems by a finite element method of lines using a piecewiseP ^th -degree polynomial basis. A posteriori estimates of the discretization error are obtained as the solutions of either local parabolic or local elliptic finite element problems using piecewise polynomial corrections of degreep+1 that vanish at element ends. Error estimates computed in this manner are shown to converge in energy under mesh refinement to the exact finite element discretization error. Computational results indicate that the error estimates are robust over a wide range of mesh spacings and polynomial degrees and are, furthermore, applicable in situations that are not supported by the analysis.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 90-0194; by the U.S. Army Research Office under Contract Number DAAL03-91-G-0215; and by the National Science Foundation under Institutional Infrastructure Grant Number CDA-8805910     

Algorithms for a class of nondifferentiable problems

A nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities are due to terms of the form min(f ₁(x),...,f _n(x)), which may enter nonlinearly in the cost and the constraints. Necessary and sufficient conditions are developed. Two algorithms for solving this problem are described, and their convergence is studied. A duality framework for interpretation of the algorithms is also developed.This work was supported in part by the National Science Foundation under Grant No. ENG-74-19332 and Grant No. ECS-79-19396, in part by the U.S. Air Force under Grant AFOSR-78-3633, and in part by the Joint Services Electronics Program (U.S. Army, U.S. Navy, and U.S. Air Force) under Contract N00014-79-C-0424.     

Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph

An upper bound is given on the number of acyclic orientations of a graph, in terms of the spectrum of its Laplacian. It is shown that this improves upon the previously known bound, which depended on the degree sequence of the graph. Estimates on the new bound are provided.A lower bound on the number of acyclic orientations of a graph is given, with the help of the probabilistic method. This argument can take advantage of structural properties of the graph: it is shown how to obtain stronger bounds for small-degree graphs of girth at least five, than are possible for arbitrary graphs. A simpler proof of the known lower bound for arbitrary graphs is also obtained.Both the upper and lower bounds are shown to extend to the general problem of bounding the chromatic polynomial from above and below along the negative real axis.Partially supported by the NSF under grant CCR-9404113. Most of this research was done while the author was at the Massachusetts Institute of Technology, and was supported by the Defense Advanced Research Projects Agency under Contracts N00014-92-J-1799 and N00014-91-J-1698, the Air Force under Contract F49620-92-J-0125, and the Army under Contract DAAL-03-86-K-0171.Supported by an ONR graduate fellowship, grants NSF 8912586 CCR and AFOSR 89-0271, and an NSF postdoctoral fellowship.     

A quadratic programming algorithm

By using conjugate directions a method for solving convex quadratic programming problems is developed. The algorithm generates a sequence of feasible solutions and terminates after a finite number of iterations. Extensions of the algorithm for nonconvex and large structured quadratic programming problems are discussed.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 and in part by the Natural Sciences and Engineering Research Council of Canada under Grant Nos. A 8189 and E 5582.     

Large deviations for diffusion processes in duals of nuclear spaces

Motivated by applications to neurophysiological problems, various authors have studied diffusion processes in duals of countably Hilbertian nuclear spaces governed by stochastic differential equations. In these models the diffusion coefficients describe the random stimuli received by spatially extended neurons. In this paper we present a large deviation principle for such processes when the diffusion terms tend to zero in terms of a small parameter. The lower bounds are established by making use of the Girsanov formula in abstract Wiener space. The upper bounds are obtained by Gaussian approximation of the diffusion processes and by taking advantage of the nuclear structure of the state space to pass from compact sets to closed sets.This research was partially supported by the National Science Foundation and the Air Force Office of Scientific Research Grant No. F49620-92-J-0154 and the Army Research Office Grant No. DAAL03-92-G-0008.