Differential games of fixed duration with state constraints

We consider differential games of fixed duration with phase coordinate restrictions on the players. Results of Ref. 1 on games with phase restrictions on only one of the players are extended. Using Berkovitz's definition of a game (Ref. 2), we prove the existence and continuity (or Lipschitz continuity) of the value under appropriate assumptions. We also note that the value can be characterized as the viscosity solution of the associated Hamilton-Jacobi-Isaacs equation.This work comprises a part of the author's PhD Thesis completed at Purdue University under the direction of Professor L. D. Berkovitz. The author wishes to thank Professor Berkovitz for suggesting the problem and many valuable discussions. During the research for this work, the author was supported by a David Ross Grant from Purdue University as well as by NSF Grant No. DMS-87-00813.     

Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited

Recently, Zhang, Tapia, and Dennis (Ref. 1) produced a superlinear and quadratic convergence theory for the duality gap sequence in primal-dual interior-point methods for linear programming. In this theory, a basic assumption for superlinear convergence is the convergence of the iteration sequence; and a basic assumption for quadratic convergence is nondegeneracy. Several recent research projects have either used or built on this theory under one or both of the above-mentioned assumptions. In this paper, we remove both assumptions from the Zhang-Tapia-Dennis theory.Dedicated to the Memory of Magnus R. Hestenes, 1906–1991This research was supported in part by NSF Cooperative Agreement CCR-88-09615 and was initiated while the first author was at Rice University as a Visiting Member of the Center for Research in Parallel Computation.The authors thank Yinyu Ye for constructive comments and discussions concerning this material.This author was supported in part by NSF Grant DMS-91-02761 and DOE Grant DE-FG05-91-ER25100.This author was supported in part by AFOSR Grant 89-0363, DOE Grant DE-FG05-86-ER25017, and ARO Grant 9DAAL03-90-G-0093.     

Remarks on bang-bang control in Hilbert space

In this note, a natural definition of bang-bang control in Hilbert space is given, and some of the theory of the authors' paper (Ref. 1) is rebuilt upon it. An elliptic boundary-value problem illustrating the theory is given. In the last part of this note, the results of Ref. 1 are extended to nonlinear perturbations of linear operators and to homogeneous nonlinear operators.Communicated by L. CesariThis research was supported by NRC Grant No. A-4047 and NSF Grant No. GP-7445.     

Minimal trajectories of nonconvex differential inclusions

We consider an optimization problem with endpoint constraints associated with a nonconvex differential inclusion. We give a necessary condition of the maximum principle type for a solution of the problem. Following the approach from Ref. 1, the condition is stated in terms of single-valued selections of the convexified right-hand side of the inclusion.This work was supported in part by the National Science Foundation, Grant No. DMS-86-01774.     

Existence,uniqueness and continuity of solutions of integral equations. An addendum

Summary This note corrects au error in the continuous dependence theorem of an earlier paper on the subject stated in the title. Here it is shows that the topology of one of the spaces of functions can be modified in order to obtain the desired continuity results. This research was support in part by the National Aeronautics Space Administration under Grant No. NGL-40-002-015, and in part by the U. S. Air Force under Grant No. AF-AFOSR-67-0693A. This research was supported in part by the National Science Foundation under Grant No. GP-3904 and GP-7041 and in part by the U.S. Army under Grant No. D1-31-124-ARO-D-265. Entrata in Redazione il 10 aprile 1970.     

An iterative method for generalized nonlinear complementarity problems

An iterative method for solving generalized nonlinear complementarity problems (Ref. 1) involving stronglyK-copositive operators is introduced. Conditions are presented which guarantee the convergence of the method; in addition, the sequence of iterates is used to prove the existence of a solution to the problem under conditions not included in the previous study. Separate consideration is given to the generalized linear complementarity problem.This research was partially supported by National Science Foundation, Grant No. GP-16293. This paper constitutes part of the junior author's doctoral thesis written at Rensselaer Polytechnic Institute. Research support was provided by an NDEA Fellowship and an RPI Fellowship.     

On the stability theorem in failure-detection systems

A stability theorem for failure-detection systems, previously published in Ref. 1, is shown to be incomplete.This research was supported by the National Science Foundation of China under Grant No. 69304003.     

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.     

The synthesis of optimal controls for linear,time-optimal problems with retarded controls

Optimization problems involving linear systems with retardations in the controls are studied in a systematic way. Some physical motivation for the problems is discussed. The topics covered are: controllability, existence and uniqueness of the optimal control, sufficient conditions, techniques of synthesis, and dynamic programming. A number of solved examples are presented.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NGL-40-002-015, in part by the Air Force Office of Scientific Research under Grant No. AF-AFOSR-693-67B, and in part by the National Science Foundation under Grant No. GP-15132.     

On the updating scheme in a class of collinear scaling algorithms for sparse minimization

Sorensen (Ref. 1) has proposed a class of algorithms for sparse unconstrained minimization where the sparsity pattern of the Cholesky factors of the Hessian is known. His updates at each iteration depend on the choice of a vector, and in Ref. 1 the question of choosing this vector is essentially left open. In this note, we propose a variational problem whose solution may be used to choose this vector. The major part of the computation of a solution to this variational problem is similar to the computation of a trust-region step in unconstrained minimization. Therefore, well-developed techniques available for the latter problem can be used to compute this vector and to perform the updating.This research was supported by NSF Grant DMS-8414460 and by DOE Grant DE-FG06-85ER25007, awarded to Washington State University, and by the Applied Mathematical Sciences Subprogram of the US Department of Energy under Contract W-31-109-Eng-38 while the first author was visiting the Mathematics and Computer Science Division of Argonne National Laboratory.     

Computational results for extensions in quasilinearization techniques for optimal control

In a companion paper (Ref. 1), several extensions in quasilinearization were presented. These results are studied computationally in this paper for two problems: the brachistochrone problem and the reentry vehicle problem. For the brachistochrone free-time problem, it is shown that much more rapid convergence is obtained than that presented in previous literature (Ref. 2). It is also shown that, if the techniques of the companion paper are used, the normal region of convergence is extended significantly. Similar results are obtained for the reentry vehicle problem.The research presented in this paper was supported in part by the Air Force Office of Scientific Research, Grant No. AF-AFOSR-699-67.     

Multi-Armed bandit problem revisited

In this paper, we revisit aspects of the multi-armed bandit problem in the earlier work (Ref. 1). An alternative proof of the optimality of the Gittins index rule is derived under the discounted reward criterion. The proof does not involve an explicit use of the interchange argument. The ideas of the proof are extended to derive the asymptotic optimality of the index rule under the average reward criterion. Problems involving superprocesses and arm-acquiring bandits are also reexamined. The properties of an optimal policy for an arm-acquiring bandit are discussed.This research was supported by NSF Grant IRI-91-20074.     

Deletion-by-infeasibility rule for DC-constrained global optimization

In Ref. 1, a general class of branch-and-bound methods was proposed by Horst for solving global optimization problems. One of the main contributions of Ref. 1 was the opportunity of handling partition elements whose feasibility is not known. Deletion-by-infeasibility rules were presented for problems where the feasible set is convex, is defined by finitely many convex and reverse convex constraints, or is defined by Lipschitzian inequalities. In this note, we propose a new deletion-by-infeasibility rule for problems whose feasible set is defined by functions representable as differences of convex functions.This research was supported in part by the Hungarian National Research Foundation, Grant OTKA No. 2568.     

Second-variation methods in dynamic optimization

An entire class of rapid-convergence algorithms, called second-variation methods, is developed for the solution of dynamic optimization problems. Several well-known numerical optimization techniques included in this class are developed from a unified point of view. The generalized Riccati transformation can be applied in conjunction with any second-variation method. This fact is demonstrated for the Newton-Raphson or quasilinearization technique.This work was supported by the National Research Council of Canada under Grant No. 67-3134 and is based on investigations described in more detail in Ref. 1.     

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.     

Optimal control of diffusion processes with reflection

In this paper, we consider the problem of optimally controlling a diffusion process on a closed bounded region ofR ⁿ with reflection at the boundary. Employing methods similar to Fleming (Ref. 1), we present a constructive proof that there exists an optimal Markov control that is measurable or lower semicontinuous. We prove further that the expected cost function corresponding to the optimal control is the unique solution of the quasilinear parabolic differential equation of dynamic programming with Neumann boundary conditions and that there exists a diffusion process (in the sense of Stroock and Varadhan) corresponding to the optimal control.This work was partially supported by the National Science Foundation, Grant No. GK-18339, by the Office of Naval Research, Grant No. NR-042-264, and by the National Research Council of Canada, Grant No. A3609.The author would like to thank S. R. Pliska, J. Pisa, and N. Trudinger for helpful suggestions. He is especially grateful to Professor A. F. Veinott, Jr., for help and advice in the preparation of the doctoral dissertation, on which part of this paper is based. Finally, he wishes to thank one of the referees for the careful reading and constructive comments on an earlier version of this paper.     

Direct relaxation of optimal layout problems for plates

This paper suggests an application of a direct procedure initiated in Ref. 1 to problems of optimal layout for plates. Optimal microstructures are explicity indicated for a number of special cases, particularly for the case where the original and conjugate strain tensors are coaxial.This paper is dedicated to Professor Frithiof I. Niordson on the occasion of his 70th birthday. The research has been supported by AFOSR Grant No. 90-0268 and NSF Grant DMS-93-058040. The author acknowledges fruitful discussions with Andrei V. Cherkaev, Leonid V. Gibiansky, and Robert P. Lipton.     

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.     

A generalized hypergreedy algorithm for weighted perfect matching

We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log² n) time.This research was supported in part by the DIMACS Grant No. NSF-STC88-09648.This research was supported in part by the NSF under Grant No. CCR 88-07518.     

On minimizing sequences for an integral process with phase constraint

The purpose of this article is to find the conditions which a minimizing sequence for an integral process with a phase constraint obeys. We employ Ekeland's variational principle (Ref. 1) and follow Sumin (Ref. 2) to obtain the conditions satisfied by a minimizing sequence. The conditions derived actually hold, even for certain minimizing sequences that do not necessarily satisfy the imposed constraints. This statement is better understood from our theorem at the end of the paper. However, it is assumed that there are controls such that the imposed constraints are satisfied. We close the article with a discussion of an example.This research was supported by ONR Grant No. N0001-87-K-0276.