A rapidly convergent five-point algorithm for univariate minimization

This paper presents an algorithm for minimizing a function of one variable which uses function, but not derivative, values at five-points to generate each iterate. It employs quadratic and polyhedral approximations together with a safeguard. The basic method without the safeguard exhibits a type of better than linear convergence for certain piecewise twice continuously differentiable functions. The safeguard guarantees convergence to a stationary point for very general functions and preserves the better than linear convergence of the basic method.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research sponsored by the Institut National de Recherche en Informatique et Automatique, Rocquencourt, France, and by the Air Force Office of Scientific Research, Air Force System Command, USAF, under Grant Number AFOSR-83-0210.Research sponsored, in part, by the Institut National de Recherche en Informatique et Automatique, Rocquencourt, France.     

QPCOMP: A quadratic programming based solver for mixed complementarity problems

QPCOMP is an extremely robust algorithm for solving mixed nonlinear complementarity problems that has fast local convergence behavior. Based in part on the NE/SQP method of Pang and Gabriel [14], this algorithm represents a significant advance in robustness at no cost in efficiency. In particular, the algorithm is shown to solve any solvable Lipschitz continuous, continuously differentiable, pseudo-monotone mixed nonlinear complementarity problem. QPCOMP also extends the NE/SQP method for the nonlinear complementarity problem to the more general mixed nonlinear complementarity problem. Computational results are provided, which demonstrate the effectiveness of the algorithm. This material is based on research supported by National Science Foundation Grant CCR-9157632, Department of Energy Grant DE-FG03-94ER61915, and the Air Force Office of Scientific Research Grant F49620-94-1-0036.     

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.     

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.     

Properties of the optimal trajectories for coplanar,aeroassisted orbital transfer

We show that the sequences of function values constructed by two versions of a minimax algorithm converge linearly to the minimum values. Both versions use the Pshenichnyi-Pironneau-Polak search direction subprocedure; the first uses an exact line search to determine the stepsize, while the second one uses an Armijo-type stepsize rule. The proofs depend on a second-order sufficiency condition, but not on strict complementary slackness. Minimax problems in which each function appearing in the max is a composition of a twice continuously differentiable function with a linear function typically do not satisfy second-order sufficiency conditions. Nevertheless, we show that, on such minimax problems, the two algorithms do converge linearly when the outer functions are convex and strict complementary slackness holds at the solutions.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-87-13334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, the State of California MICRO Program Grant 532410-19900, and a Howard Hughes Doctoral Fellowship (Hughes Aircraft Company). The authors would like to thank the referees for their helpful suggestions.     

On affine scaling and semi-infinite programming

We consider an extension of the affine scaling algorithm for linear programming problems with free variables to problems having infinitely many constraints, and explore the relationship between this algorithm and the finite affine scaling method applied to a discretization of the problem.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR 89-0410.     

Nonmonotone stabilization methods for nonlinear equations

We are concerned with defining new globalization criteria for solution methods of nonlinear equations. The current criteria used in these methods require a sufficient decrease of a particular merit function at each iteration of the algorithm. As was observed in the field of smooth unconstrained optimization, this descent requirement can considerably slow the rate of convergence of the sequence of points produced and, in some cases, can heavily deteriorate the performance of algorithms. The aim of this paper is to show that the global convergence of most methods proposed in the literature for solving systems of nonlinear equations can be obtained using less restrictive criteria that do not enforce a monotonic decrease of the chosen merit function. In particular, we show that a general stabilization scheme, recently proposed for the unconstrained minimization of continuously differentiable functions, can be extended to methods for the solution of nonlinear (nonsmooth) equations. This scheme includes different kinds of relaxation of the descent requirement and opens up the possibility of describing new classes of algorithms where the old monotone linesearch techniques are replace with more flexible nonmonotone stabilization procedures. As in the case of smooth unconstrained optimization, this should be the basis for defining more efficient algorithms with very good practical rates of convergence.This material is partially based on research supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410, National Science Foundation Grant CCR-91-57632, and Istituto di Analisi dei Sistemi ed Informatica del CNR.     

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.     

Relation between the memory gradient method and the Fletcher-Reeves method

The minimization of a function of unconstrained variables is considered using the memory gradient method. It is shown that, for the particular case of a quadratic function, the memory gradient algorithm and the Fletcher-Reeves algorithm are identical.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-828-67. In more expanded form, it can be found in Ref. 1.     

Locally adaptive hazard smoothing

Summary We consider nonparametric estimation of hazard functions and their derivatives under random censorship, based on kernel smoothing of the Nelson (1972) estimator. One critically important ingredient for smoothing methods is the choice of an appropriate bandwidth. Since local variance of these estimates depends on the point where the hazard function is estimated and the bandwidth determines the trade-off between local variance and local bias, data-based local bandwidth choice is proposed. A general principle for obtaining asymptotically efficient data-based local bandwiths, is obtained by means of weak convergence of a local bandwidth process to a Gaussian limit process. Several specific asymptotically efficient bandwidth estimators are discussed. We propose in particular an, asymptotically efficient method derived from direct pilot estimators of the hazard function and of the local mean squared error. This bandwidth choice method has practical advantages and is also of interest in the uncensored case as well as for density estimation.Research supported by UC Davis Faculty Research Grant and by Air Force grant AFOSR-89-0386Research supported by Air Force grant AFOSR-89-0386     

Marginal values and second-order necessary conditions for optimality

Second-order necessary conditions in nonlinear programming are derived by a new method that does not require the usual sort of constraint qualification. In terms of the multiplier vectors appearing in such second-order conditions, an estimate, is obtained for the generalized subgradients of the optimal, value function associated with a parameterized nonlinear programming problem. This yields estimates for ‘marginal values’ with respect to the parameters. The main theoretical tools are the augmented Lagrangian and, despite the assumption of second-order smoothness of objective constraints, the subdifferential calculus that has recently been developed for nonsmooth, nonconvex functions. Research sponsored in part by the Air Force Office of Scientific, Research, Air Force Systems Command United States Air Force, under grant No. F4960-82-k-0012.     

Algorithms for optimization problems with exclusion constraints

This paper proposes algorithms for minimizing a continuously differentiable functionf(x): ⁿ subject to the constraint thatx does not lie in specified bounded subsets of ⁿ . Such problems arise in a variety of applications, such as tolerance design of electronic circuits and obstacle avoidance in the selection of trajectories for robot arms. Such constraints have the form . The function is not continuously differentiable. Algorithms based on the use of generalized gradients have considerable disadvantages because of the local concavity of at points where the set {j|g ^j (x)=(x)} has more than one element. Algorithms which avoid these disadvantrages are presented, and their convergence is established.This research was sponsored in part by the National Science Foundation under Grant ECS-81-21149, the Air Force Office of Scientific Research (AFSC), United States Air Force under Contract F49620-79-C-0178, the Office of Naval Research under Grant N00014-83-K-0602, the Air Force Office of Scientific Research under Grant AFOSR-83-0361, and the Semiconductor Research Consortium under Grant SRC-82-11-008.     

Fenchel's duality theorem in generalized geometric programming

Fenchel's duality theorem is extended to generalized geometric programming with explicit constraints—an extension that also generalizes and strengthens Slater's version of the Kuhn-Tucker theorem.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-73-2516.     

Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems

We develop an iterative algorithm based on right-hand side decomposition for the solution of multicommodity network flow problems. At each step of the proposed iterative procedure the coupling constraints are eliminated by subdividing the shared capacity resource among the different commodities and a master problem is constructed which attempts to improve sharing of the resources at each iteration.As the objective function of the master problem is nonsmooth, we apply to it a new optimization technique which does not require the exact solutions of the single commodity flow subproblems. This technique is based on the notion of - subgradients instead of subgradients and is suitable for parallel implementation. Extensions to the nonlinear, convex separable case are also discussed.The work of this author has been supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410.     

Computing Karmarkar projections quickly

The paper presents a numerical method for computing the projections for Karmarkar's new algorithm for linear programming. The method is simple to implement, fully exploits sparsity, and appears in limited experimentation to have good stability properties. Preliminary numerical experience indicates that the method promises advantages over methods that refactor a matrix at every iteration.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF under Grant AFOSR-86-0170. The US Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.This work was initiated while the author was at the Graduate School of Administration, University of California, Davis, Davis, California.     

The treatment of nonhomogeneous Dirichlet boundary conditions by thep-version of the finite element method

Summary The paper addresses the problem of the implementation of nonhomogeneous essential Dirichlet type boundary conditions in thep-version of the finite element method.Partially supported by the Office of Naval Research under Grant N-00014-85-K-0169Research partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 85-0322     

Unified approach to quadratically convergent algorithms for function minimization

In this paper, a unified method to construct quadratically convergent algorithms for function minimization is described. With this unified method, a generalized algorithm is derived. It is shown that all the existing conjugate-gradient algorithms and variable-metric algorithms can be obtained as particular cases. In addition, several new practical algorithms can be generated. The application of these algorithms to quadratic functions as well as nonquadratic functions is discussed.This research, supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-828-67, is based on Ref. 1.     

Martingale representation and the Malliavin calculus

Using stochastic flows and the Itô differentiation rule, the integrand in the representation of a martingale as a stochastic integral is identified. By iterating this representation result a homogeneous chaos type expansion is obtained. Using the stochastic integral representation, an integration by parts formula is obtained without using any calculus of variations in function space. If the inverse of the Malliavin matrix belongs to all spacesL ^p() it follows that a random variable has a smooth density.The research of R. J. Elliott was partially supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-7964 and the Air Force Office of Scientific Research, United States Air Force, under Grant AFOSR-86-0332. The research of M. Kohlmann was partially supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-7964.     

An algorithm for minimizing a differentiable function subject to box constraints and errors

We consider the problem of minimizing a differentiable function ofn parameters, with upper and lower bounds on the parameters. The motivation for this work comes from the optimization of the design of transient electrical circuits. In such optimization, the parameters are circuit elements, the bound constraints keep these parameters physically meaningful, and both the function and gradient evaluations contain errors. We describe a quasi-Newton algorithm for such problems. This algorithm handles the box constraints directly and approximates the given function locally by nonsingular quadratic functions. Numerical tests indicate that the algorithm can tolerate the errors, if the errors in the function and gradient are of the same relative size.This paper was presented at the SIAM National Meeting, Chicago, Illinois, 1976.This research was sponsored in part by the Air Force Office of Scientific Research (AFSC), United States Air Force, under Contract No. F44620-76-C-0022.     

On the convergence of kernel estimators of probability density functions

Summary The properties of the characteristic function of the fixed-bandwidth kernel estimator of a probability density function are used to derive estimates of the rate of almost sure convergence of such estimators in a family of Hilbert spaces. The convergence of these estimators in a reproducing-kernel Hilbert space is used to prove the uniform convergence of variable-bandwidth estimators. An algorithm employing the fast Fourier transform and heuristic estimates of the optimal bandwidth is presented, and numerical experiments using four density functions are described. This research was supported by the United States Air Force, Air Force Office of Scientific Research, Under Grant Number AFOSR-76-2711.