Coordinate Transformations and Derivation of Open-Loop Nash Equilibria

Leitmann (Ref. 1) introduced coordinate transformations to derive global optima of a class of dynamic optimization problems. We present applications of this method to derive open-loop Nash equilibria for finite-time horizon differential games. The method of coordinate transformations is especially useful in cases where the original game does not satisfy the global curvature conditions normally imposed in sufficient optimality conditions.     

Generalized Newton algorithm to minimize a function with many variables using computer-evaluated exact higher-order derivatives

This paper describes an optimization algorithm which uses up torth-order derivatives to find the optimum of anr-times continuously differentiable function of many variables. The algorithm, developed by Kalaba and Tishler (Ref. 1), obtains the exact values of the derivatives required for the optimization from the table algorithm presented in Kalabaet al. (Ref. 2) and Kalaba and Tishler (Ref. 3). The optimization algorithm described here reduces to the well-known Newton-Raphson algorithm when only first-order and second-order derivatives are used.on leave from the Faculty of Management, Tel Aviv University, Tel Aviv, Israel.     

Book Notices

Finding Pareto-minimum vectors among r given vectors, each of dimension m, is a fundamental problem in multiobjective optimization problems or multiple-criteria decision-making problems. Corley and Moon (Ref. 1) have given an algorithm for finding all the Pareto-minimum paths of a multiobjective network optimization problem from the initial node to any other node. It uses another algorithm by Corley and Moon, which actually computes the Pareto-minimum vectors. We observed that the latter algorithm is incorrect. In this note, we correct the algorithm for computing Pareto-minimum vectors and present a modified algorithm.     

Nonrandomized strategy equilibria in noncooperative stochastic games with additive transition and reward structure

In this paper, we study a discounted noncooperative stochastic game with an abstract measurable state space, compact metric action spaces of players, and additive transition and reward structure in the sense of Himmelberget al. (Ref. 1) and Parthasarathy (Ref. 2). We also assume that the transition law of the game is absolutely continuous with respect to some probability distributionp of the initial state and together with the reward functions of players satisfies certain continuity conditions. We prove that such a game has an equilibrium stationary point, which extends a result of Parthasarathy from Ref. 2, where the action spaces of players are assumed to be finite sets. Moreover, we show that our game has a nonrandomized (- )-equilibrium stationary point for each >0, provided that the probability distributionp is nonatomic. The latter result is a new existence theorem.     

Guaranteed avoidance strategies

We consider a dynamical system under the control of two agents, one of whom desires to keep the system's state out of a given set regardless of the other agent's actions. The guaranteed avoidance conditions of Ref. 1 are generalized to admit piecewiseC ¹ test functions; this generalization permits application to a wider class of problems. The results are illustrated by application to a version of the homicidal chauffeur game.Dedicated to R. BellmanThis paper is based on research supported by NSF under Grant No. ENG-78-13931.     

Sequential Systems of Linear Equations Algorithm for Nonlinear Optimization Problems with General Constraints

In Ref. 1, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints was proposed. At each iteration, this new algorithm only needs to solve four systems of linear equations having the same coefficient matrix, which is much less than the amount of computation required for existing SQP algorithms. Moreover, unlike the quadratic programming subproblems of the SQP algorithms (which may not have a solution), the subproblems of the SSLE algorithm are always solvable. In Ref. 2, it is shown that the new algorithm can also be used to deal with nonlinear optimization problems having both equality and inequality constraints, by solving an auxiliary problem. But the algorithm of Ref. 2 has to perform a pivoting operation to adjust the penalty parameter per iteration. In this paper, we improve the work of Ref. 2 and present a new algorithm of sequential systems of linear equations for general nonlinear optimization problems. This new algorithm preserves the advantages of the SSLE algorithms, while at the same time overcoming the aforementioned shortcomings. Some numerical results are also reported.     

Equilibrium Problems with Applications to Eigenvalue Problems

In this paper, we consider equilibrium problems and introduce the concept of (S)₊ condition for bifunctions. Existence results for equilibrium problems with the (S)₊ condition are derived. As special cases, we obtain several existence results for the generalized nonlinear variational inequality studied by Ding and Tarafdar (Ref. 1) and the generalized variational inequality studied by Cubiotti and Yao (Ref. 2). Finally, applications to a class of eigenvalue problems are given.     

Derived Sets for Weak Multiobjective Optimization Problems with State and Control Variables

The concept of a K-gradient, introduced in Ref. 1 in order to generalize the concept of a derived convex cone defined by Hestenes, is extended to weak multiobjective optimization problems including not only a state variable, but also a control variable. The new concept is employed to state multiplier rules for the local solutions of such dynamic multiobjective optimization problems. An application of these multiplier rules to the local solutions of an abstract multiobjective optimal control problem yields general necessary optimality conditions that can be used to derive concrete maximum principles for multiobjective optimal control problems, e.g., problems described by integral equations with additional functional constraints.     

Switching surfaces inN-person differential games

Switching surfaces inN-person differential games are essentially similar to those encountered in optimal control and two-person, zero-sum differential games. The differences between the Nash noncooperative solution and the saddle-point solution are reflected in the dispersal surfaces. These are discussed through classification and construction procedures for switching surfaces. A simple example of a two-person, nonzero-sum game is considered. A complete solution of this game will be presented in a companion paper (Ref. 1).     

Local Saddle Points and Convexification for Nonconvex Optimization Problems

Recently, Li (Ref. 1) obtained a saddle-point result for a general class of nonconvex optimization problems with inequality constraints, by using a transformation equivalent to taking the pth power of the objective function and the constraints, under several conditions. In this paper, we show that, by an equivalent transformation, using the pth power of the constraints or using the pth power of the objective function and the constraints, the same result can be obtained under much weaker and reasonable conditions. Also, our results can be extended to the problem in which equality and inequality constraints are involved.     

Planar quasi-Newton algorithms for unconstrained saddlepoint problems

A new class of quasi-Newton methods is introduced that can locate a unique stationary point of ann-dimensional quadratic function in at mostn steps. When applied to positive-definite or negative-definite quadratic functions, the new class is identical to Huang's symmetric family of quasi-Newton methods (Ref. 1). Unlike the latter, however, the new family can handle indefinite quadratic forms and therefore is capable of solving saddlepoint problems that arise, for instance, in constrained optimization. The novel feature of the new class is a planar iteration that is activated whenever the algorithm encounters a near-singular direction of search, along which the objective function approaches zero curvature. In such iterations, the next point is selected as the stationary point of the objective function over a plane containing the problematic search direction, and the inverse Hessian approximation is updated with respect to that plane via a new four-parameter family of rank-three updates. It is shown that the new class possesses properties which are similar to or which generalize the properties of Huang's family. Furthermore, the new method is equivalent to Fletcher's (Ref. 2) modified version of Luenberger's (Ref. 3) hyperbolic pairs method, with respect to the metric defined by the initial inverse Hessian approximation. Several issues related to implementing the proposed method in nonquadratic cases are discussed.An earlier version of this paper was presented at the 10th Mathematical Programing Symposium, Montreal, Canada, 1979.     

Further generalization of the Dubovicki-Milutin theorem

Combining the results of Walczak (Ref. 1) and Lasiecka (Refs. 2 and 3), we extend the well-known Dubovicki-Milutin theorem in two directions: (i) We allow for treatment of several equality constraints in optimization problems; and (ii) We assume less regularity of optimization problems by requiring the existence of external cones instead of tangent cones. An example of an optimization problem is also considered.     

Comment on a note on duality gaps in linear programming over convex sets

In Ref. 1, Soyster has given a rather complicated proof of the absence of a duality gap, under a certain interiority condition, for a variant of a pair of optimization problems introduced by Ben-Israel, Charnes, and Kortanek (Ref. 2). A proof can be given directly (and under weaker conditions) by a simple application of a Lagrange multiplier theorem on convex programming in abstract spaces (Ref. 3).     

Generalized proximal point algorithm for convex optimization

Ha (Ref. 1) recently introduced a generalized proximal point algorithm for solving a generalized equation. In this note, we present a generalized proximal point algorithm for convex optimization problems based on Ha's work. The idea behind this algorithm is that, instead of adding a quadratic term to all the variables, we add a quadratic term to a subset of the variables. We extend the criteria for approximate solutions given by Rockafellar (Ref. 2) and Auslender (Ref. 3) and present convergence results. Finally, we show how this algorithm can be applied to solve block-angular linear and quadratic programming problems.     

Second-order game problem: Decision dynamics in gaming phenomena

The paradigm of decision dynamics (Ref. 1) is used to describe the decision dynamics involving more than one decision-maker. The framework supplied in this paper is different from traditional game theory or differential games. Traditional simplicity assumptions are replaced by a more complicated, but more realistic, setting. Although many mathematically beautiful results in traditional game theory or differential games have disappeared in second-order games, the more realistic setting of the latter does make it easier for the decision-makers to find agood decision. Concepts of time optimality and time stability, and their necessary and/or sufficient conditions are described. Unconventional concepts of strategies and uncertainty involved in gaming phenomena are discussed. A highlight of the paper is a systematic discussion on reframing tactics of gaming situations, which do not exist in the context of traditional game theory or differential games. Various research topics are discussed at the end of the paper.     

On solving discontinuous extremal problems

An approach to solving discontinuous problems of optimization and control is described. The approach is based on the concept of approximate gradient introduced in Ref. 1. Generalizations of the theorems of Kuhn-Tucker and Dubovitsky-Milyutin and the maximum principle of Pontryagin are proved. The mathematical constructions described allow one to solve a wide variety of applied problems of optimization and control within the class of nonsmooth (including discontinuous) functions. The paper continues the investigations of Refs. 1–2.     

Generalized Surrogate Problem Methodology for Online Stochastic Discrete Optimization

We consider stochastic discrete optimization problems where the decision variables are nonnegative integers and propose a generalized surrogate problem methodology that modifies and extends previous work in Ref. 1. Our approach is based on an online control scheme which transforms the problem into a surrogate continuous optimization problem and proceeds to solve the latter using standard gradient-based approaches while simultaneously updating both the actual and surrogate system states. In contrast to Ref. 1, the proposed methodology applies to arbitrary constraint sets. It is shown that, under certain conditions, the solution of the original problem is recovered from the optimal surrogate state. Applications of this approach include solutions to multicommodity resource allocation problems; in these problems, exploiting the convergence speed of the method, one can overcome the obstacle posed by the presence of local optima.     

On the Stability of Globally Projected Dynamical Systems

Two types of projected dynamical systems, whose equilibrium states solve the corresponding variational inequality problems, were proposed recently by Dupuis and Nagurney (Ref. 1) and by Friesz et al. (Ref. 2). The stability of the dynamical system developed by Dupuis and Nagurney has been studied completely (Ref. 3). This paper analyzes and proves the global asymptotic stability of the dynamical system proposed by Friesz et al. under monotone and symmetric mapping conditions. Furthermore, the dynamical system is shown to be globally exponentially stable under stronger conditions. Finally, we show that the dynamical system proposed by Friesz et al. can be applied easily to neural networks for solving a class of optimization problems.     

Precision,complexity, and computational schemes of the cubic algorithm

The cubic algorithm (Ref. 1) is a nongradient method for the solution of multi-extremal, nonconvex Lipschitzian optimization problems. The precision and complexity of this algorithm are studied, and improved computational schemes are proposed.     

An extension of Jørgensen's differential game

This note extends Jørgensen's exponential differential game (Ref. 1) to a more general type of game structure. In particular, the Hamiltonians of the players are not required to be linear in the state variables and the control variables may not be in exponential form.The helpful comments of Professor C. Plourde and an anonymous referee are gratefully acknowledged.