Spline approximations for nonlinear hereditary control systems

A spline-based approximation scheme is discussed for optimal control problems governed by nonlinear nonautonomous delay differential equations. The approximating framework reduces the original control problem to a sequence of optimization problems governed by ordinary differential equations. Convergence proofs, which appeal directly to dissipative-type estimates for the underlying nonlinear operator, are given and numerical findings are summarized.This work was supported in part by the Air Force Office of Scientific Research under Contract No. AFOSR-76-3092D, in part by the National Science Foundation under Grants Nos. NSF-MCS-79-05774-05 and NSF-MCS-82-00883, and in part by the US Army Research Office under Contract No. ARO-DAAG29-79-C-0161. The results reported here are a portion of the author's doctoral dissertation written under the supervision of Professor H. T. Banks, Brown University. The author is indebted to Professor Banks for his many valuable comments and suggestions during the course of this work.Part of this research was completed while the author was a visitor at the Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, Hampton, Virginia.     

Fully discrete approximation methods for the estimation of parabolic systems and boundary parameters

A spatially and temporally discrete numerical approximation scheme is developed for the identification of a class of semilinear parabolic systems with unknown boundary parameters. The identification problem is formulated as a least squares fit to data subject to an equivalent representation for the dynamics in the form of an abstract evolution equation. Finite-dimensional difference equation state approximations are constructed using a cubic spline-based, Galerkin method and the Padé rational function approximations to the exponential. A sequence of approximating identification problems result, the solutions of which are shown to exist and, in a certain sense, approximate solutions to the original identification problem. Numerical results for two examples, one involving the modeling of biological mixing in deep sea sediment cores, and the other, the estimation of transport parameters for indoor mixing, are discussed. In both examples, the identification is based upon actual experimental data.Parts of the research were carried out while the authors were visitors at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, Virginia, which is operated under NASA Contracts No. NAS1-17070 and No. NAS1-17130.Research supported in part by NSF Grant MCS-8205355, AFOSR Contract 81-0198 and ARO Contract ARO-DAAG-29-K-0029.     

An augmented Lagrangian technique for variational inequalities

A general framework for the treatment of a class of elliptic variational inequalities by an augmented Lagrangian method, when inequalities with infinite-dimensional image space are augmented, is developed. Applications to the obstacle problem, the elastoplastic torsion problem, and the Signorini problem are given.The research of the first author was supported in part by the Air Force Office of Scientific Research under Grants AFOSR-84-0398 and AFOSR-85-0303, by the National Aeronautics and Space Administration under Grant NAG-1-1517, and by NSF under Grant No. UINT-8521208. The second author's research was supported in part by the Fonds zur Förderung der wissenschaftlichen Forschung under S3206 and P6005.     

Multi-sweep asynchronous parallel successive overrelaxation for the nonsymmetric linear complementarity problem

Convergence is established for themulti-sweep asynchronous parallel successive overrelaxation (SOR) algorithm for thenonsymmetric linear complementarity problem. The algorithm was originally introduced in [4] for the symmetric linear complementarity problem. Computational tests show the superiority of the multi-sweep asynchronous SOR algorithm over its single-sweep counterpart on both symmetric and nonsymmetric linear complementarity problems.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228, and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0124.     

Interior proximal point algorithm for linear programs

An interior proximal point algorithm for finding a solution of a linear program is presented. The distinguishing feature of this algorithm is the addition of a quadratic proximal term to the linear objective function. This perturbation has allowed us to obtain solutions with better feasibility. Implementation of this algorithm shows that the algorithms. We also establish global convergence and local linear convergence of the algorithm.This research was supported by National Science Foundation Grants DCR-85-21228 and CCR-87-23091 and by Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-89-0410. It was conducted while the author was a Graduate Student at the Computer Sciences Department, University of Wisconsin, Madison, Wisconsin.     

Finite perturbation of convex programs

This paper concerns a characterization of the finite-perturbation property of a convex program. When this property holds, finite perturbation of the objective function of a convex program leads to a solution of the original problem which minimizes the perturbation function over the set of solutions of the original problem. This generalizes a finite-termination property of the proximal point algorithm for linear programs and characterizes finite Tikhonov regularization of convex programs.This material is based on research supported by National Science Foundation Grants DCR-8521228 and CCR-8723091 and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-89-0410.     

On conforming finite element methods for the inhomogeneous stationary Navier-Stokes equations

Summary We consider the stationary Navier-Stokes equations, written in terms of the primitive variables, in the case where both the partial differential equations and boundary conditions are inhomogeneous. Under certain conditions on the data, the existence and uniqueness of the solution of a weak formulation of the equations can be guaranteed. A conforming finite element method is presented and optimal estimates for the error of the approximate solution are proved. In addition, the convergence properties of iterative methods for the solution of the discrete nonlinear algebraic systems resulting from the finite element algorithm are given. Numerical examples, using an efficient choice of finite element spaces, are also provided.Supported, in part, by the U.S. Air Force Office of Scientific Research under Grant No. AF-AFOSR-80-0083Supported, in part, by the same agency under Grant No. AF-AFOSR-80-0176-A. Both authors were also partially supported by NASA Contract No. NAS1-15810 while they were in residence at the Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, Hampton, VA 23665, USA     

Optimal quasi-static shape control for large aerospace antennae

In this paper, we propose an on-line control approach which will adjust the steady-state shape of a large antenna arbitrarily close to any achievable desired profile. The method makes use of distributed parameter system theory and allows refocusing using a limited number of control actuators and sensors.The controller gains are calculated by approximating the solution to an infinite-dimensional optimal quasi-static control problem. We prove a very general convergence result for such quasi-static controllers here and apply it to the antenna controller to show convergence using any Galerkin (finite-element) approximation method.This research was partially supported by the National Science Foundation, the National Aeronautics and Space Administration, and the Air Force Office of Scientific Research under Grants ECS-80-16173, NAG-1-171, and AFOSR-83-0124, respectively.     

Representations of quasi-Newton matrices and their use in limited memory methods

We derive compact representations of BFGS and symmetric rank-one matrices for optimization. These representations allow us to efficiently implement limited memory methods for large constrained optimization problems. In particular, we discuss how to compute projections of limited memory matrices onto subspaces. We also present a compact representation of the matrices generated by Broyden's update for solving systems of nonlinear equations.These authors were supported by the Air Force Office of Scientific Research under Grant AFOSR-90-0109, the Army Research Office under Grant DAAL03-91-0151 and the National Science Foundation under Grants CCR-8920519 and CCR-9101795.This author was supported by the U.S. Department of Energy, under Grant DE-FG02-87ER25047-A001, and by National Science Foundation Grants CCR-9101359 and ASC-9213149.     

Adaptive control of Markov processes with incomplete state information and unknown parameters

Recent results for parameter-adaptive Markov decision processes (MDP's) are extended to partially observed MDP's depending on unknown parameters. These results include approximations converging uniformly to the optimal reward function and asymptotically optimal adaptive policies.This research was supported in part by the Consejo del Sistema Nacional de Educación Tecnologica (COSNET) under Grant 178/84, in part by the Air Force Office of Scientific Research under Grant AFOSR-84-0089, in part by the National Science Foundation under Grant ECS-84-12100, and in part by the Joint Services Electronics Program under Contract F49602-82-C-0033.     

Finite termination of the proximal point algorithm

This paper concerns the notion of a sharp minimum on a set and its relationship to the proximal point algorithm. We give several equivalent definitions of the property and use the notion to prove finite termination of the proximal point algorithm.This material is based on research supported by National Science Foundation Grants DCR-8521228 and CCR-8723091, and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

Numerical investigation of a multiserver retrial model

We consider a queueing model in which customers arrive in a Poisson stream to be served by one ofc servers. Each arriving customer enters a pool of active customers and starts generating requests for service at exponentially distributed time intervals at rate until he finds a free server and begins service. An analytical solution of this model is difficult and does not lend itself to numerical implementation. In this paper, we make a simplifying approximation, based on understanding of the physical behavior of the system, which yields an infinitesimal generator with a modified matrix-geometric equilibrium probability vector. That vector can be very efficiently computed even for high congestion levels. Illustrative numerical examples demonstrate the effectiveness of the approximation as well as the effect of the retrial rate on the system behavior for various levels of congestion. This study shows how numerical results for analytically intractable systems can be obtained by combining intuition with efficient algorithmic methods.This author's research was supported in part by Grants Nos. ECS-88-03061 from the National Science Foundation and AFOSR-88-0076 from the Air Force Office of Scientific Research.     

A numerical method for reflected diffusions: Control of the reflection directions and applications

We are concerned with a numerical method for the optimal control of the reflection directions of a reflected diffusion process, and with either a discounted or an ergodic cost criterion. The Markov chain approximation method is adapted to this nonclassical problem and convergence of the method is proved. The problem originally arose in the important application of rerouting in large trunk-line communications systems. A reasonable heavy-traffic approximation leads to the described model. The numerical method has been applied with success, but no proofs of convergence were given previously. Nonboundary controls can be easily added.This work was partially supported by Grants (AFOSR) F49620-92-J-008-1DEF, AFOSR-91-0375, and DAAH04-93-6-0070.     

On critical orientations in the kedem-sharir motion planning algorithm

We discuss a technical problem arising in the motion planning algorithm of Kedem and Sharir [KS], and propose a way to overcome it without increasing the asymptotic complexity of the algorithm The first author was supported by the Eshkol Grant 04601-90 from the Israeli Ministry of Science and Technology. The second author was partly supported by the Fund for Basic Research administered by the Israeli Academy of Sciences, by National Science Foundation Grants CCR-91-22103 and CCR-93-11127, and by grants from the U.S.-Israeli Binational Science Foundation, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. The third author was partly supported by the Interdisciplinary Program at Tel-Aviv University. The third author’s current address is: Department of Computer Science, MIT, Boston, MA, USA.     

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.     

Parallel successive overrelaxation methods for symmetric linear complementarity problems and linear programs

A parallel successive overrelaxation (SOR) method is proposed for the solution of the fundamental symmetric linear complementarity problem. Convergence is established under a relaxation factor which approaches the classical value of 2 for a loosely coupled problem. The parallel SOR approach is then applied to solve the symmetric linear complementarity problem associated with the least norm solution of a linear program.This work was sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Science Foundation Grant DCR-84-20963 and Air Force Office of Scientific Research Grants AFOSR-ISSA-85-00080 and AFOSR-86-0172.on leave from CRAI, Rende, Cosenza, Italy.     

The augmented lagrangian method for equality and inequality constraints in hilbert spaces

In this paper we consider an augmented Lagrangian method for the minimization of a nonlinear functional in the presence of an equality constraint whose image space is in a Hilbert space, an inequality constraint whose image space is finite dimensional, and an affine inequality constraint whose image space is in an infinite dimensional Hilbert space. We obtain local convergence of this method without imposing strict complementarity conditions when the equality, as well as the inequality constraint with finite dimensional image space are augmented. To the author's knowledge this result even generalizes the convergence results which are known when all spaces are finite dimensional.This research was supported by the Air Force Office of Scientific Research under Grant AFOSR-84-0398 and AFOSR-85-0303, by the National Aeronautics and Space Administration under Grant NAG-1-517, and by NSF under Grant UINT-8521208.This research was supported in part by the Fonds zur Förderung der wissenschaftichen Forschung under S3206 and P6005 and by AFOSR-84-0398. Part of this work was performed while the author was visiting the Division of Applied Mathematics, Brown University, Providence, RI, USA.     

Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs

A gradient projection successive overrelaxation (GP-SOR) algorithm is proposed for the solution of symmetric linear complementary problems and linear programs. A key distinguishing feature of this algorithm is that when appropriately parallelized, the relaxation factor interval (0, 2) isnot reduced. In a previously proposed parallel SOR scheme, the substantially reduced relaxation interval mandated by the coupling terms of the problem often led to slow convergence. The proposed parallel algorithm solves a general linear program by finding its least 2-norm solution. Efficiency of the algorithm is in the 50 to 100 percent range as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0255.     

Estimation of system reliability in Brownian stress-strength models based on sample paths

Reliability of many stochastic systems depends on uncertain stress and strength patterns that are time dependent. In this paper, we consider the problem of estimating the reliability of a system when bothX(t) andY(t) are assumed to be independent Brownian motion processes, whereX(t) is the system stress, andY(t) is the system strength, at timet.This research was partially supported by the Air-Force Office of Scientific Research Grants AFOSR-89-0402 and AFOSR-90-0402.     

Asynchronous parallel successive overrelaxation for the symmetric linear complementarity problem

Convergence is established for asynchronous parallel successive overrelaxation (SOR) algorithms for the symmetric linear complementarity problem. For the case of a strictly diagonally dominant matrix convergence is achieved for a relaxation factor interval of (0, 2] with line search, and (0, 1] without line search. Computational tests on the Sequent Symmetry S81 multiprocessor give speedup efficiency in the 43%–91% range for the cases for which convergence is established. The tests also show superiority of the asynchronous SOR algorithms over their synchronous counterparts.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.