A bracketing technique to ensure desirable convergence in univariate minimization

This paper gives a general safeguarded bracketing technique for minimizing a function of a single variable. In certain cases the technique guarantees convergence to a stationary point and, when combined with sequential polynomial and/or polyhedral fitting algorithms, preserves rapid convergence. Each bracket has an interior point whose function value does not exceed those of the two bracket endpoints. The safeguarding technique consists of replacing the fitting algorithm's iterate candidate by a close point whose distance from the three bracket points exceeds a positive multiple of the square of the bracket length. It is shown that a given safeguarded quadratic fitting algorithm converges in a certain better than linear manner with respect to the bracket endpoints for a strongly convex twice continuously differentiable function.Research sponsored by the Institut National de Recherche en Informatique et en Automatique, Rocquencourt, France, and by the Air Force Office of Scientific Research, Air Force System Command, USAF, under Grant Number AFOSR-83-0210. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.Research sponsored, in part, by the Institut National de Recherche en Informatique et en Automatique, Rocquencourt, France.     

A quasi-second-order proximal bundle algorithm

This paper introduces an algorithm for convex minimization which includes quasi-Newton updates within a proximal point algorithm that depends on a preconditioned bundle subalgorithm. The method uses the Hessian of a certain outer function which depends on the Jacobian of a proximal point mapping which, in turn, depends on the preconditioner matrix and on a Lagrangian Hessian relative to a certain tangent space. Convergence is proved under boundedness assumptions on the preconditioner sequence. Research supported by NSF Grant No. DMS-9402018 and by Institut National de Recherche en Informatique et en Automatique, France.     

Probabilistic aspects of finite-fuel,reflected follower problems

The issue is that of following the path of a Brownian particle by a process of bounded total variation and subject to a reflecting barrier at the origin, in such a way as to minimize expected total cost over a finite horizon. We establish the existence of optimal processes and the dynamic programming equations for this question, and show (by purely probabilistic arguments) its relation to an appropriatefamily of optimal stopping problems with absorption at the origin.Work carried out during a visit by the second author at the University Pierre et Marie Curie (Paris VI), and at INRIA (Institut National de Recherche en Informatique et en Automatique). The hospitality of these institutions is gratefully acknowledged.Research supported in part by the U.S. Air Force Office of Scientific Research, under grant AFOSR-86-0203.     

Intégrales convexes et probabilités

The purpose of this paper is to establish some additional properties of the normal convex integrands as studied by R. T. Rockafellar and to define the conditional expectation of a normal convex integrand relative to a σ-algebra. By duality the inf-convolution of a normal convex integrand relative to this σ-algebra is then introduced. Some properties of the subdifferential of the new functionals are proved, and martingale type results are given on the conditional expectation and its dual.This paper is the first part of a thesis prepared under Professor J. L. Lions and Professor A. Bensoussan of the University of Paris at the Institut de Recherche d'Informatique et d'Automatique (78 Rocquencourt France). The results which are proved here will be applied in the next parts, especially to optimal stochastic control.     

Multicriterion Aerodynamic Shape Design Optimization and Inverse Problems Using Control Theory and Nash Games

Multicriterion design is gaining importance in aeronautics in order to cope with new needs of society. In the literature, contributions to single discipline and/or single-point design optimization abound. The goal of this paper is to introduce a new approach combining the adjoint method with a formulation derived from game theory for multipoint aerodynamic design problems. Transonic flows around lifting airfoils are analyzed via Euler computations. Airfoil shapes are optimized according to various aerodynamic criteria. The notion of player is introduced. In a competitive Nash game, each player attempts to optimize its own criterion through a symmetric exchange of information with others. A Nash equilibrium is reached when each player, constrained by the strategy of the others, cannot improve further its own criterion. Specific real and virtual symmetric Nash games are implemented to set up an optimization strategy for design under conflict. This work has benefited partially from the support of the National Science Foundation of China Grant NSFC-10372040 and Scientific Research Foundation (SRF) for Returned Overseas Chinese Scholars (ROCS) Grant 2003-091. The first author acknowledges the support of INRIA (Institut National de Recherche en Information et en Automatique), France.     

On superlinear convergence in univariate nonsmooth minimization

This note demonstrates a new result on superlinear convergence in nonsmooth univariate minimization. It also gives other concepts of rapid convergence for minimization of functions that may have discontinuous derivatives.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Numbers AFOSR-83-0210 and AFOSR-88-0180.     

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.     

On series in linear topological spaces

The main result is that in every complete locally-bounded linear topological space there exist series which are unconditionally yet not absolutely convergent. Relations between absolute, unconditional and metric convergence of series are studied. The research reported in this document has been sponsored in part by the Air Force Office of Scientific Research, OAR through the European Office, Aerospace Research, United States Air Force.     

Stationarity and superlinear convergence of an algorithm for univariate locally lipschitz constrained minimization

This paper introduces an algorithm for minimizing a single-variable locally Lipschitz function subject to a like function being nonpositive. The method combines polyhedral and quadratic approximation, a new type of penalty technique and a safeguard in such a way as to give convergence to a stationary point. The convergence is shown to be superlinear under somewhat stronger assumptions that allow both nonsmooth and nonconvex cases. The algorithm can be an effective subroutine for solving line search subproblems called for by multivariable optimization algorithms. Research sponsored, in part, by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-83-0210. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

Optimization with unary functions

Most nonlinear programming problems consist of functions which are sums of unary functions of linear functions. Advantage can be taken of this form to calculate second and higher order derivatives easily and at little cost. Using these, high order optimization techniques such as Halley's method can be utilized to accelerate the rate of convergence to the solution. These higher order derivatives can also be used to compute second order sensitivity information. These techniques are applied to the solution of the classical chemical equilibrium problem.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research and by the Office of Naval Research grant N00014-86-K0052.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research.     

A superlinearly convergent algorithm for minimization without evaluating derivatives

An algorithm for unconstrained minimization of a function of n variables that does not require the evaluation of partial derivatives is presented. It is a second order extension of the method of local variations and it does not require any exact one variable minimizations. This method retains the local variations property of accumulation points being stationary for a continuously differentiable function. Furthermore, because this extension makes the algorithm an approximate Newton method, its convergence is superlinear for a twice continuously differentiable strongly convex function.Research sponsored by National Science Foundation Grant GK-32710 and by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-74-2695.     

Laminar boundary layer oblique shock wave interaction on flat and curved plates

Résumé Ce mémoire décrit quelques recherches expérimentales et théoriques sur l'interaction des ondes de choc obliques avec les couches limites laminaires. Une série de mesures détaillées de pressions et du frottement a été faite dans la région d'interaction dans un écoulement le long d'une plaque plane. Un modèle du mécanisme en a été déduit, dont les prédictions s'accordent raisonnablement bien avec les résultats des expériences. Les mêmes idées ont été appliquées à l'interaction sur une surface courbe, et les résultats s'accordent encore avec les expériences. Une étude simplifiée de la région de stabilité de l'interaction sous l'action d'oscillations de faible amplitude a été faite.

---

---

This work was supported by the National Advisory Committee for Aeronautics Contracts Nos. Naw-6320, 6412, 6452, 6507 and Air Force Contract No. 33-(616-3064) sponsored by the Wright Air Development Center, Wright Patterson Air Force Base.     

Existence of a σ finite invariant measure for a Markov process on a locally compact space

A σ finite invariant measure is found, for a Markov process, on a locally compact space, which maps continuous functions to continuous functions. The research reported in this document has been sponsored by the Air Force Office of Scientific Research under Grant AF EOAR 66-18, through the European Office of Aerospace Research (OAR) United States Air Force.     

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-termination schemes for solving semi-infinite satisfycing problems

The problem of finding a parameter which satisfies a set of specifications in inequality form is sometimes referred to as the satisfycing problem. We present a family of methods for solving, in a finite number of iterations, satisfycing problems stated in the form of semi-infinite inequalities. These methods range from adaptive uniform discretization methods to outer approximation methods.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-8713334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, and the State of California MICRO Program Grant 532410-19900.     

Sequential quadratic programming for certain parameter identification problems

We analyze the method of sequential quadratic programming for equality constrained minimization problems in Hilbert spaces of functions, and for the discrete approximations of such problems in the context of an elliptic parameter identification problem. We show how the discretization can be constructed so as to preserve the convergence behavior of the iterates for the infinite dimensional problem in the finite dimensional approximations. We use the structure of the parameter identification problem to reduce the size of the linear system for the SQP step and verify nondegeneracy of the constraints.Supported by National Science Foundation grants #DMS-8601139 and #DMS-8900410, and Air Force Office of Scientific Research grants #AFOSR-ISSA-860074, #AFOSR-ISSA-890044 and #AFOSR-89-0124.Supported by National Science Foundation grants #DMS-8619903, #DMS-8900984 and #ASC-8714009, and Air Force Office of Scientific Research grants #AFOSR-ISSA-870092 and #AFOSR-89-0124.     

Competition between Most Rapid Approach Paths: Necessary and Sufficient Conditions

We revisit the optimality of the most rapid approach paths for problems of the calculus of variation in infinite horizon, which are scalar and linear w.r.t. the derivative. Our approach is based on the characterization of the value function in terms of the viscosity solutions of a Hamilton-Jacobi equation. We obtain a new necessary and sufficient condition when there is only one turnpike, but characterize also the optimality of several turnpikes in competition. In this last case, nonsmooth analysis is used. Finally, we illustrate the results on a fishery management problem, for which the growth function has a depensation and the price is variable.This work was done during the visit of the second author at the Laboratoire dAnalyse des Systèmes et de Biométrie, Montpellier, France. He is grateful to the Institut National de la Recherche Agronomique for the support.     

On the existence of noncontinuous irreducible representations of a locally compact group

It is shown that a non-discrete locally compact group has non-continuous irreducible representations.Research sponsored by the Air Force Office of Scientific Research under Grant AF-AFOSR-903-67 and by the National Aeronautics and Space Administration under Grant NGR 44-004-042 and Grant NSG-269-62.     

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.     

Continuity of Bessel potentials

It is shown that certain capacities associated with potentials of functions in Lebesgue classes are non-increasing under orthogonal projection of sets. This inequality is then used to discuss continuity of traces of potentials on subspaces of possibly low dimension. The case of principal interest is the Bessel potential. This research was partially sponsored by the Air Force Office of Scientific Research, Office of Aerospace Research, United States Air Force, under AFOSR Grant No. 883-67.