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.     

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.     

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.     

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.     

Iterative techniques for Riccati game equations

We present a monotone iterative technique for the computation of a solution of a Riccati-type equation relevant to the theory of differential games. For this purpose, we show that the Kleinman algorithm for Riccati equation computations converges under extremely general conditions.The research reported in this paper was made possible in part through the Division of Engineering and Applied Physics, Harvard University, by the US Office of Naval Research, Joint Electronics Program, Contract No. N00014-75-C-0648, and by the National Science Foundation, Grant No. GK-31511.     

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.     

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.     

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.     

Transcendental geometric programs

This paper treats a class of posynomial-like functions whose variables may appear also as exponents or in logarithms. It is shown that the resulting programs, called transcendental geometric programs, retain many useful properties of ordinary geometric programs, although the new class of problems need not have unique minima and cannot, in general, be transformed into convex programs. A duality theory, analogous to geometric programming duality, is formulated under somewhat more restrictive conditions. The dual constraints are not all linear, but the notion ofdegrees of difficulty is maintained in its geometric programming sense. One formulation of the dual program is shown to be a generalization of the chemical equilibrium problem where correction factors are added to account for nonideality. Some of the computational difficulties in solving transcendental programs are discussed briefly.This research was partially supported by the National Institute of Health Grant No. GM-14789; Office of Naval Research under Contract No. N00014-75-C-0276; National Science Foundation Grant No. MPS-71-03341 A03; and the US Atomic Energy Commission Contract No. AT(04-3)-326 PA #18.     

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.     

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.     

Communication games with partially soft power constraints

We consider a class of communication games which involves the transmission of a Gaussian random variable through a conditionally Gaussian memoryless channel in the presence of an intelligent jammer. The jammer is allowed to tap the channel and feed a correlated signal back into it. The transmitter-receiver pair is assumed to cooperate in minimizing some quadratic fidelity criterion while the jammer maximizes this same criterion. Security strategies which protect against irrational jammer behavior and which yield an upper bound on the cost are shown to exist for the transmitter-receiver pair over a class of fidelity criteria. Closed-form expressions for these strategies are provided in the paper, which are, in all cases but one, linear in the available information.This work was supported in part by the US Air Force under Grant No. AFOSR-84-0056 and in part by the Joint Services Electronics Program under Contract No. N00014-84-C-0149. An earlier version of this paper was presented at the 1986 IEEE Symposium on Information Theory, Ann Arbor, Michigan, 1986.     

Approximation procedures based on the method of multipliers

In this paper, we consider a method for solving certain optimization problems with constraints, nondifferentiabilities, and other ill-conditioning terms in the cost functional by approximating them by well-behaved optimization problems. The approach is based on methods of multipliers. The convergence properties of the methods proposed can be inferred from corresponding properties of multiplier methods with partial elimination of constraints. A related analysis is provided in this paper.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, and by the National Science Foundation under Grant No. ENG-74-19332.     

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.     

Nonlinear programming: A quadratic analysis of ridge paralysis

The numerical solution of nonlinear programming problems by first-order techniques, such as gradient projection techniques, is difficult when ridges are encountered. Ridges are described and analyzed. Second-order information about the augmented objective function, properly used, can yield a search direction that moves along a ridge, even in the constrained case. The analysis applies to situations in which the objective function (maximization) is not necessarily concave and the constraint functions (G _j 0) are not necessarily convex.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.     

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.     

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.     

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     

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.