A second-order method for unconstrained optimization

This paper presents a quadratically converging algorithm for unconstrained minimization. All the accumulation points that it constructs satisfy second-order necessary conditions of optimality. Thus, it avoids second-order saddle andinflection points, an essential feature for a method to be used in minimizing the modified Lagrangians in multiplier methods.The work of the first author was supported by NSF RANN AEN 73-07732-A02 and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by NSF Grant No. GK-37672 and the ARO Contract No. DAHCO4-730C-0025.     

A note on duality in disjunctive programming

We state a duality theorem for disjunctive programming, which generalizes to this class of problems the corresponding result for linear programming.This work was supported by the National Science Foundation under Grant No. MPS73-08534 A02 and by the US Office of Naval Research under Contract No. N00014-75-C-0621-NR047-048.     

On the uniqueness of Nash strategies for a class of analytic differential games

The uniqueness of Nash equilibria is shown for the case where the data of the problem are analytic functions and the admissible strategy spaces are restricted to analytic functions of the current state and time.This work was supported in part by the Joint Services Electronics Program (US Army, US Navy, and US Air Force) under Contract No. DAAB-07-72-C-0259, in part by the National Science Foundation under Grant No. ENG-74-20091, and in part by the Department of Energy, Electric Energy Systems Division under Contract No. US ERDA EX-76-C-01-2088.     

Multimodel design of a Nash strategy

For interconnected systems with slow and fast modes, we analyze a multimodel design of a Nash equilibrium strategy. Decision makers use different models of the same system to obtain a composite strategy that approximates the exact Nash strategy. It is discussed in what sense this approximation holds.This work was supported by the Department of Energy, Electrical Energy Systems Division, under Contract No. EX-76-C-01-2088. The author wishes to thank Professor P. V. Kokotovic for his helpful suggestions in the course of this work.     

A decomposition of time scales for iterative computation of time-optimal controls

An iterative procedure, exploiting the multiple time scale properties of systems with slow and fast modes, is presented. This procedure solves the time-optimal problem for higher-order systems iteratively via the solutions of simple second-order problems. Computational complexity is so reduced that fourth-order problems can be solved using a microprocessor or programmable calculator.This work was supported in part by the Joint Services Electronics Program (US Army, US Navy, and US Air Force) under Contract No. DAAB-07-72-C-0259, in part by the US Air Force under Grant No. AFOSR-73-2570, and in part by the National Science Foundation under Grant No. ENG 74-20091.     

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.     

On the testing of marginal homogeneity with a one-sided alternative in the analysis of variance

We consider a two-factor experiment in which the factors have the same levels with a natural ordering among the levels. Likelihood ratio tests for testing equality of the main effects with a one-sided alternative and for testing the one-sided hypothesis as a null hypothesis are studied. Closed form expressions for the maximum likelihood estimates under the various hypotheses are obtained. The null hypothesis distributions for these test statistics are derived.The efforts of the first author were supported by the NSERC of Canada. The efforts of the second author were supported by the Office of Naval Research under Contract ONR N00014-80-C-0321. The efforts of the third author were supported by the Office of Naval Research under Contract ONR N00014-80-C-0322.     

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.     

Sufficient conditions for Stackelberg and Nash strategies with memory

Sufficiency conditions for Stackelberg strategies for a class of deterministic differential games are derived when the players have recall of the previous trajectory. Sufficient conditions for Nash strategies when the players have recall of the trajectory are also derived. The state equation is linear, and the cost functional is quadratic. The admissible strategies are restricted to be affine in the information available.This work was supported in part by the Joint Services Electronics Program under Contract No. N00014-79-C-0424, in part by the National Science Foundation under Grant No. ECS-79-19396, and in part by Department of Energy under Contract No. EX-76-C-01-2088.     

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.     

Projection method for unconstrained optimization

A method of conjugate directions, the projection method, for solving unconstrained minimization problems is presented. Under the assumption of uniform strict convexity, the method is shown to converge to the global minimizer of the unconstrained problem and to have an (n – 1)-step superlinear rate of convergence. With a Lipschitz condition on the second derivatives, the rate of convergence is shown to be a modifiedn-step quadratic one.This research was supported in part by the Army Research Office, Contract No. DAHC 19-69-C-0017, and the Office of Naval Research, Contract No. N00014-71-C-0116(NR-047-099).     

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.     

An exact penalty function algorithm for optimal control problems with control and terminal equality constraints,part 1

The presence of control constraints, because they are nondifferentiable in the space of control functions, makes it difficult to cope with terminal equality constraints in optimal control problems. Gradient-projection algorithms, for example, cannot be employed easily. These difficulties are overcome in this paper by employing an exact penalty function to handle the cost and terminal equality constraints and using the control constraints to define the space of permissible search directions in the search-direction subalgorithm. The search-direction subalgorithm is, therefore, more complex than the usual linear program employed in feasible-directions algorithms. The subalgorithm approximately solves a convex optimal control problem to determine the search direction; in the implementable version of the algorithm, the accuracy of the approximation is automatically increased to ensure convergence.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAAG-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.     

Analysis of decomposition algorithms via nonlinear splitting functions

This paper provides a structural analysis of decomposition algorithms using a generalization of linear splitting methods. This technique is used to identify explicitly the essential similarities and differences between several classical algorithms. Similar concepts can be used to analyze a large class of multilevel hierarchical structures.This research was supported in part by ONR Contract No. N00014-76-C-0346, in part by the US Department of Energy, Division of Electric Energy Systems, Contract No. ERDA-E(49-18)-2087 at the Massachusetts Institute of Technology, and in part by the Joint Services Electronics Program, Contract No. DAAG-29-78-C-0016.The authors would like to thank Dr. P. Varaiya, University of California at Berkeley, and Dr. D. Bertsekas for their comments and suggestions.     

A robust secant method for optimization problems with inequality constraints

This paper presents a secant method, based on R. B. Wilson's formula for the solution of optimization problems with inequality constraints. Global convergence properties are ensured by grafting the secant method onto a phase I - phase II feasible directions method, using a rate of convergence test for crossover control.This research was sponsored by the National Science Foundation, Grant No. ENG-73-08214 and Grant No. (RANN)-ENV-76-04264, and by the Joint Services Electronics Program. Contract No. F44620-76-C-0100.     

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.     

On the existence of Nash strategies and solutions to coupled riccati equations in linear-quadratic games

The existence of linear Nash strategies for the linear-quadratic game is considered. The solvability of the coupled Riccati matrix equations and the stability of the closed-loop matrix are investigated by using Brower's fixed-point theorem. The conditions derived state that the linear closed-loop Nash strategies exist, if the open loop matrixA has a sufficient degree of stability which is determined in terms of the norms of the weighting matrices. WhenA is not necessarily stable, sufficient conditions for existence are given in terms of the solutions of auxiliary problems using the same procedure.This work was supported in part by the Joint Services Electronics Program (US Army, US Navy, and US Air Force) under Contract No. DAAG-29-78-C-0016, in part by the National Science Foundation under Grant No. ENG-74-20091, and in part by the Department of Energy, Electric Energy Systems Division, under Contract No. US-ERDA-EX-76-C-01-2088.     

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.     

Solving the nonlinear least square problem: Application of a general method

An algorithm for solving the general nonlinear least-square problem is developed. An estimate for the Hessian matrix is constructed as the sum of two matrices. The first matrix is the usual first-order estimate used by the Gauss method, while the second matrix is generated recursively using a rank-one formula. Test results indicate that the method is superior to the standard Gauss method and compares favorably with other methods, especially for problems with nonzero residuals at the solution.This work was supported by the US Air Force under Contract No. F04701-73-C-0074.The author expresses his appreciation to Dr. H. E. Pickett and Dr. J. L. Searcy for their continuing support in the theoretical and practical development of the algorithm. The recursive method for generating the estimate of the Hessian matrix was developed jointly with Drs. Pickett and Searcy and is included here with their permission. The author would also like to acknowledge the contribution made by the stimulating environment of an optimal control seminar held at The Aerospace Corporation since 1970. Principle members of the seminar have been H. E. Pickett, J. L. Searcy, R. W. Reid, and the author.     

On sending one bit of information over an AGWN channel with noiseless feedback

We study the problem described by the title under the real-time constraint that no block coding is allowed. Three separate schemes, including the well known center-of-gravity scheme, and their performance are compared.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.The formulation of this problem took place when the first author was SRC Senior Fellow at Imperial College during the summer of 1977. He appreciates discussions with M. Davis and D. Mayne of Imperial College.