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.     

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 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.     

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.     

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.     

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.     

Nonlinear programming: Global use of the Lagrangian

In some constrained nonlinear programming problems possessing several local optima, a local optimum can be recognized as the global optimum by looking closely at the Lagrangian, the augmented function. Similarly, classes of constrained optimization problems, such as geometric programming problems, can be recognized as possessing at most a single local optimum.This research was supported in part by the Atomic Energy Commission under Research Contract No. A(11-1)-1493 and by the Department of Defense under Themis Grant No. F44620-69-C-0116.     

A comparison of computational strategies for geometric programs

Numerous algorithms for the solution of geometric programs have been reported in the literature. Nearly all are based on the use of conventional programming techniques specialized to exploit the characteristic structure of either the primal or the dual or a transformed primal problem. This paper attempts to elucidate, via computational comparisons, whether a primal, a dual, or a transformed primal solution approach is to be preferred.The authors wish to thank Captain P. A. Beck and Dr. R. S. Dembo for making available their codes. This research was supported in part under ONR Contract No. N00014-76-C-0551 with Purdue University.     

Cut sharing for multistage stochastic linear programs with interstage dependency

Multistage stochastic programs with interstage independent random parameters have recourse functions that do not depend on the state of the system. Decomposition-based algorithms can exploit this structure by sharing cuts (outer-linearizations of the recourse function) among different scenario subproblems at the same stage. The ability to share cuts is necessary in practical implementations of algorithms that incorporate Monte Carlo sampling within the decomposition scheme. In this paper, we provide methodology for sharing cuts in decomposition algorithms for stochastic programs that satisfy certain interstage dependency models. These techniques enable sampling-based algorithms to handle a richer class of multistage problems, and may also be used to accelerate the convergence of exact decomposition algorithms. Research leading to this work was partially supported by the Department of Energy Contract DE-FG03-92ER25116-A002; the Office of Naval Research Contract N00014-89-J-1659; the National Science Foundation Grants ECS-8906260, DMS-8913089; and the Electric Power Research Institute Contract RP 8010-09, CSA-4O05335. This author's work was supported in part by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Algorithms for a class of nondifferentiable problems

A nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities are due to terms of the form min(f ₁(x),...,f _n(x)), which may enter nonlinearly in the cost and the constraints. Necessary and sufficient conditions are developed. Two algorithms for solving this problem are described, and their convergence is studied. A duality framework for interpretation of the algorithms is also developed.This work was supported in part by the National Science Foundation under Grant No. ENG-74-19332 and Grant No. ECS-79-19396, in part by the U.S. Air Force under Grant AFOSR-78-3633, and in part by the Joint Services Electronics Program (U.S. Army, U.S. Navy, and U.S. Air Force) under Contract N00014-79-C-0424.     

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.     

An algorithm for a piecewise linear model of trade and production with negative prices and bankruptcy

The general equilibrium model is approximated as a piecewise linear convex model and solved from the point of view of welfare economics using linear programming and fixed point methods.This research was supported in part by Army Research Office-Durham Contract DAAG-29-74-C-0032, NSF Grant MPS-72-04832-A03, and Energy Research and Development Administration Contract E(04-3)-326 PA#18.     

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.     

Numerical experiments with the LANCELOT package (release A) for large-scale nonlinear optimization

In this paper, we describe the algorithmic options of Release A of LANCELOT, a Fortran package for large-scale nonlinear optimization. We then present the results of intensitive numberical tests and discuss the relative merits of the options. The experiments described involve both academic and applied problems. Finally, we propose conclusion, both specific to LANCELOT and of more general scope. 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     

Optimal design of pitched laminated wood beams

The optimal design of a pitched laminated wood beam is considered. An engineering formulation is given in which the volume of the beam is minimized. The problem is then reformulated and solved as a generalized geometric (signomial) program. Sample designs are presented.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865; by the US Energy Research and Development Administration Contract No. E(04-3)-326 PA-18; and by the National Science Foundation, Grant No. DCR75-04544 at Stanford University. This work was carried out during the first author's stay at the Management Science Division of the University of British Columbia and the Systems Optimization Laboratory of Stanford University. The authors are indebted to Mr. S. Liu and Mrs. M. Ratner for their assistance in performing the computations.     

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.     

Critical point theorems for indefinite functionals

A variational principle of a minimax nature is developed and used to prove the existence of critical points for certain variational problems which are indefinite. The proofs are carried out directly in an infinite dimensional Hilbert space. Special cases of these problems previously had been tractable only by an elaborate finite dimensional approximation procedure. The main applications given here are to Hamiltonian systems of ordinary differential equations where the existence of time periodic solutions is established for several classes of Hamiltonians.Supported in part by the U.S. Army under Contract No. DAAG-29-75-C-0024 and by the Conseglio Nazionale delle Ricerche-Gruppo Nazionale Analisi Funzionale e ApplicazioneSupported in part by the J.S. Guggenheim Memorial Foundation, and by the Office of Naval Research under Contract No. N00014-76-C-0300. Reproduction in whole or in part is permitted for any purpose of the U.S. Government     

Constant potential primal—dual algorithms: A framework

We start with a study of the primal—dual affine-scaling algorithms for linear programs. Using ideas from Kojima et al., Mizuno and Nagasawa, and new potential functions we establish a framework for primal—dual algorithms that keep a potential function value fixed. We show that if the potential function used in the algorithm is compatible with a corresponding neighborhood of the central path then the convergence proofs simplify greatly. Our algorithms have the property that all the iterates can be kept in a neighborhood of the central path without using any centering in the search directions.Research performed while the author was Ph.D. student at Cornell University and was supported in part by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027, and also by NSF, AFOSR and ONR through NSF Grant DMS-8920550.     

On the solution of some (parametric) linear complementarity problems with applications to portfolio selection,structural engineering and actuarial graduation

In this paper we discuss three applications of a class of (parametric) linear complementarity problems arising independently from such diverse areas as portfolio selection, structural engineering and actuarial graduation. After explaining how the complementarity problems emerge in these applications, we perform some analytical comparisons (based on operation counts and storage requirements) of several existing algorithms for solving this class of complementarity problems. We shall also present computational results to support the analytical comparisons. Finally, we deduce some conclusions about the general performance of these algorithms.This research is supported in part by the United States Army under Contract No. DAAG29-75-C-0024, the National Science Foundation under Grant No. MCS75-17385 and Grant ENG77-11136.     

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.