Methods of conjugate directions versus quasi-Newton methods

It is shown that algorithms for minimizing an unconstrained functionF(x), x E ⁿ , which are solely methods of conjugate directions can be expected to exhibit only ann or (n–1) step superlinear rate of convergence to an isolated local minimizer. This is contrasted with quasi-Newton methods which can be expected to exhibit every step superlinear convergence. Similar statements about a quadratic rate of convergence hold when a Lipschitz condition is placed on the second derivatives ofF(x). Research was supported in part by Army Research Office, Contract Number DAHC 19-69-C-0017 and the Office of Naval Research, Contract Number N00014-71-C-0116 (NR 047-99).     

A note on a sufficient-decrease criterion for a non-derivative step-length procedure

A step-length algorithm is an essential part of many descent methods for unconstrained and constrained optimization. In this note we present a criterion that defines an acceptable step length when only function values are available at trial step lengths.This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110.     

Accelerated conjugate direction methods for unconstrained optimization

A family of accelerated conjugate direction methods, corresponding to the Broyden family of quasi-Newton methods, is described. It is shown thatall members of the family generate the same sequence of points approximating the optimum and the same sequence of search directions, provided only that each direction vector is normalized before the stepsize to be taken in that direction is determined.With minimal restrictions on how the stepsize is determined (sufficient only for convergence), the accelerated methods applied to the optimization of a function ofn variables are shown to have an (n+1)-step quadratic rate of convergence. Furthermore, the information needed to generate an accelerating step can be stored in a singlen-vector, rather than the usualn×n symmetric matrix, without changing the theoretical order of convergence.The relationships between this family of methods and existing conjugate direction methods are discussed, and numerical experience with two members of the family is presented.This research was sponsored by the United States Army under Contract No. DAAG29-75-C-0024.The author gratefully acknowledges the valuable assistance of Julia H. Gray, of the Mathematics Research Center, University of Wisconsin, Madison, who painstakingly programmed these methods and obtained the computational results.     

Glivenko-Cantelli properties of some generalized empirical DF's and strong convergence of generalized L-statistics

Summary We study a nonclassical form of empirical df H _nwhich is of U-statistic structure and extend to H _nthe classical exponential probability inequalities and Glivenko-Cantelli convergence properties known for the usual empirical df. An important class of statistics is given byT(H _n), where T(·) is a generalized form of L-functional. For such statisticswe prove almost sure convergence using an approach which separates the functional-analytic and stochastic components of the problem and handles the latter component by application of Glivenko-Cantelli type properties.Classical results for U-statistics and L-statistics are obtained as special cases without addition of unnecessary restrictions.Many important new types of statistics of current interest are covered as well by our result.Research supported by the U.S. Department of Navy under Office of Naval Research Contract No. N00014-79-C-0801 and by NATO under Research Grant No. 0034/87     

A weighted gram-schmidt method for convex quadratic programming

Range-space methods for convex quadratic programming improve in efficiency as the number of constraints active at the solution decreases. In this paper we describe a range-space method based upon updating a weighted Gram-Schmidt factorization of the constraints in the active set. The updating methods described are applicable to both primal and dual quadratic programming algorithms that use an active-set strategy. Many quadratic programming problems include simple bounds on all the variables as well as general linear constraints. A feature of the proposed method is that it is able to exploit the structure of simple bound constraints. This allows the method to retain efficiency when the number ofgeneral constraints active at the solution is small. Furthermore, the efficiency of the method improves as the number of active bound constraints increases. This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110. The work of Nicholas Gould was supported by the Science and Engineering Research Council of Great Britain.     

A Berry-Esseen bound for symmetric statistics

Summary The rate of convergence of the distribution function of a symmetric function of N independent and identically distributed random variables to its normal limit is investigated. Under appropriate moment conditions the rate is shown to be (N^–1/2). This theorem generalizes many known results for special cases and two examples are given. Possible further extensions are indicated.Research supported by the U.S. Office of Naval Research, Contract N 00014-80-C-0163     

The almost sure representation of intermediate order statistics

Summary Let {X _n} be independent and identically distributed and let X _kn ⁽ⁿ⁾ denote the k _n-th order statistic for X ₁ ..., X _n, where k _n but k _n/n0. A representation for X _kn ⁽ⁿ⁾ in terms of the empirical distribution function is developed. The conditions include those under which X _kn ⁽ⁿ⁾ is asymptotically normal.Research partially supported by the University of North Carolina at Chapel Hill under Office of Naval Research Contract No. N00014-75-C-0809 and by The Florida State University under Office of Naval Research Contract No. N00014-76-C-0608.     

Expansions for von Mises functionals

Summary Berry-Esseen results and expansions are derived for the distribution function of von Mises functionals of order r under moment conditions and conditions on the smoothness of the limit distribution.The results apply to goodness-of-fit statistics — as well as to the central limit theorem in L ^2p,p2, the rate of convergence being O(n ^–1) for centered balls, provided a fourth moment exists.Research sponsored in part under Office of Naval Research. Contract Number N00014-80-C-0163.     

Practical convergence conditions for the Davidon-Fletcher-Powell method

The convergence properties of the Davidon-Fletcher-Powell method when applied to the minimization of convex functions are considered for the case where the one-dimensional minimization required at each iteration is not solved exactly. Conditions on the error incurred at each iteration are given which are sufficient for the original method to have a linear or superlinear rate of convergence, and for the restarted version to have ann-step quadratic rate of convergence.Sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462.     

Low order polynomial bounds on the expected performance of local improvement algorithms

We present a general abstract model of local improvement, applicable to such diverse cases as principal pivoting methods for the linear complementarity problem and hill climbing in artificial intelligence. The model accurately predicts the behavior of the algorithms, and allows for a variety of probabilistic assumptions that permit degeneracy. Simulation indicates an approximately linear average number of iterations under a variety of probability assumptions. We derive theoretical bounds of 2en logn and en ² for different distributions, respectively, as well as polynomial bounds for a broad class of probability distributions. We conclude with a discussion of the applications of the model to LCP and linear programming.The author was supported by the New Faculty Research Development Program of the Georgia Institute of Technology. This work is based on the author's Ph.D. thesis, performed under George Dantzig at Stanford 1978–81, at the Systems Optimization Laboratory. While at Stanford, research was supported in part by Department of Energy Contract AM03-76SF00326, PA #DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS76-81259, MCS-7926009 and ECS-8012974; and Army Research Office Contract DAA29-79-C-0110. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Algorithmic equivalence in quadratic programming,I: A least-distance programming problem

It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.     

Solving geometric programs using GRG: Results and comparisons

This paper describes the performance of a general-purpose GRG code for nonlinear programming in solving geometric programs. The main conclusions drawn from the experiments reported are: (i) GRG competes well with special-purpose geometric programming codes in solving geometric programs; and (ii) standard time, as defined by Colville, is an inadequate means of compensating for different computing environments while comparing optimization algorithms.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865, the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18, and the National Science Foundation, Grant No. DCR75-04544 at Stanford University; and by the Office of Naval Research under Contract No. N00014-75-C-0240, and the National Science Foundation, Grant No. SOC74-23808, at Case Western Reserve University.     

A dynamic solution concept for abstract games

Several solution concepts have been defined for abstract games. Some of these are the core, due to Gillies and Shapley, the Von Neumann-Morgenstern stable sets, and the subsolutions due to Roth. These solution concepts are rather static in nature. In this paper, we propose a new solution concept for abstract games, called the dynamic solution, that reflects the dynamic aspects of negotiation among the players. Some properties of the dynamic solution are studied. Also, the dynamic solution of abstract games arising fromn-person cooperative games in characteristic function form is investigated.This research was supported by the Office of Naval Research under Contract No. N00014-75-C-0678, by the National Science Foundation under Grants Nos. MPS-75-02024 and MCS-77-03984 at Cornell University, by the United States Army under Contract No. DAAG-29-75-C-0024, and by the National Science Foundation under Grant No. MCS-75-17385-A01 at the University of Wisconsin. The author is grateful to Professor W. F. Lucas under whose guidance the research was conducted.     

A second-order method for the general nonlinear programming problem

This paper presents a multiplier-type method for nonlinear programming problems with both equality and inequality constraints. Slack variables are used for the inequalities. The penalty coefficient is adjusted automatically, and the method converges quadratically to points satisfying second-order conditions.The work of the first author was supported by NSF RANN and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by the National Science Foundation Grant No. ENG73-08214A01 and US Army Research Office Durham Contract No. DAHC04-73-C-0025.     

Optimal approximation of sparse hessians and its equivalence to a graph coloring problem

We consider the problem of approximating the Hessian matrix of a smooth non-linear function using a minimum number of gradient evaluations, particularly in the case that the Hessian has a known, fixed sparsity pattern. We study the class of Direct Methods for this problem, and propose two new ways of classifying Direct Methods. Examples are given that show the relationships among optimal methods from each class. The problem of finding a non-overlapping direct cover is shown to be equivalent to a generalized graph coloring problem—the distance-2 graph coloring problem. A theorem is proved showing that the general distance-k graph coloring problem is NP-Complete for all fixedk≥2, and hence that the optimal non-overlapping direct cover problem is also NP-Complete. Some worst-case bounds on the performance of a simple coloring heuristic are given. An appendix proves a well-known folklore result, which gives lower bounds on the number of gradient evaluations needed in any possible approximation method. This research was partially supported by the Department of Energy Contract AM03-76SF00326. PA#DE-AT03-76ER72018; Army Research Office Contract DAA29-79-C-0110; Office of Naval Research Contract N00014-74-C-0267; National Science Foundation Grants MCS76-81259, MCS-79260099 and ECS-8012974.     

Analysis of switched linear systems in the plane,part 1: Local behavior of trajectories and local cycle geometry

This paper investigates the problem of control of switched linear systems evolving inR ². The concept of an opposition point is introduced, and its properties related to the existence of closed trajectories in the phase plane are investigated. The geometry of cycles in a neighborhood of an opposition point is also studied.This research was supported by the Office of Naval Research, ONR Contract No. N0013-80-C-0199, and the United States Department of Energy, DOE Contract No. DE-AC01-79-ET-29363.     

Analysis of switched linear systems in the plane,part 2: Global behavior of trajectories,controllability and attainability

The controllability and attainability properties of switched linear systems in the plane are investigated. A main result is the state-space decomposition theorem which classifies various convex regions inR ² according to their controllability properties. A preliminary investigation into the problem of determining minimum switch trajectories between two points inR ² is also presented.This research was supported by the Office of Naval Research, ONR Contract No. N0014-80-C-0199, and the United States Department of Energy, DOE Contract No. DE-AC01-79-ET-29363.     

Distributed computing viewed as a team problem with constraints

The optimal distribution of the workload in a system of interconnected computer units is considered. Formulated as a team decision problem with a singular cost criterion and with equality and inequality constraints, it is shown that the problem admits always a unique piecewise linear strategy which is globally optimal. Some interesting particular cases are studied.The research reported in this paper was made possible through support from the Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-C-0648 and Contract No. N00014-77-C-0531 and by the National Science Foundation, Grant No. ENG-76-11824.     

A quasi-Newton method can be obtained from a method of conjugate directions

In a recent paper McCormick and Ritter consider two classes of algorithms, namely methods of conjugate directions and quasi-Newton methods, for the problem of minimizing a function ofn variablesF(x). They show that the former methods possess ann-step superlinear rate of convergence while the latter are every step superlinear and therefore inherently superior. In this paper a simple and computationally inexpensive modification of a method of conjugate directions is presented. It is shown that the modified method is a quasi-Newton method and is thus every step superlinearly convergent. It is also shown that under certain assumptions on the second derivatives ofF the rate of convergence of the modified method isn-step quadratic.This work was supported by the National Research Council of Canada under Research Grant A8189.     

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.