Turnpike properties for a class of piecewise deterministic systems arising in manufacturing flow control

This paper deals with a general class of piecewise deterministic control systems that encompasses FMS flow control models. One uses the Markov renewal decision process formalism to characterize optimal policies via a discrete event dynamic programming approach. A family of control problems with a random stopping time is associated with these optimality conditions. These problems can be reformulated as infinite horizon deterministic control problems. It is then shown how the so-calledturnpike property should hold for these deterministic control problems under classical convexity assumptions. These turnpikes have the same generic properties as the attractors obtained via a problem specific approach in FMS flow control models and production planning and are calledhedging points in this literature.This research has been supported by NSERC-Canada, Grants No. A4952 by FCAR-Québec, Grant No. 88EQ3528, Actions Structurantes, MESS-Québec, Grant No. 6.1/7.4(28), and FNRS-Switzerland.     

A discrete method of optimal control based upon the cell state space concept

A discrete method of optimal control is proposed in this paper. The continuum state space of a system is discretized into a cell state space, and the cost function is discretized in a similar manner. Assuming intervalwise constant controls and using a finite set of admissible control levels (u) and a finite set of admissible time intervals (), the motion of the system under all possible interval controls (u, ) can then be expressed in terms of a family of cell-to-cell mappings. The proposed method extracts the optimal control results from these mappings by a systematic search, culminating in the construction of a discrete optimal control table.The possibility of expressing the optimal control results in the form of a control table seems to give this method a means to make systems real-time controllable.Dedicated to G. LeitmannThe material is based upon work supported by the National Science Foundation under Grant No. MEA-82-17471. The author is also indebted to Professor G. Leitmann for his many helpful comments.     

Maximum principle of optimal control for functional differential systems

We show that the maximum principle holds for optimal periodic control problems governed by functional differential equations under a Lipschitz condition on the value functional. Generalizations to other boundary conditions are also considered.This research was partially supported by NSF Grant No. DMS-84-01719.The first author was partially supported by the Science Fund of the Chinese Academy of Sciences, Beijing, China.     

Efficient dynamic programming implementations of Newton's method for unconstrained optimal control problems

Naive implementations of Newton's method for unconstrainedN-stage discrete-time optimal control problems with Bolza objective functions tend to increase in cost likeN ³ asN increases. However, if the inherent recursive structure of the Bolza problem is properly exploited, the cost of computing a Newton step will increase only linearly withN. The efficient Newton implementation scheme proposed here is similar to Mayne's DDP (differential dynamic programming) method but produces the Newton step exactly, even when the dynamical equations are nonlinear. The proposed scheme is also related to a Riccati treatment of the linear, two-point boundary-value problems that characterize optimal solutions. For discrete-time problems, the dynamic programming approach and the Riccati substitution differ in an interesting way; however, these differences essentially vanish in the continuous-time limit.This work was supported by the National Science Foundation, Grant No. DMS-85-03746.     

Pointwise quasi-Newton method for unconstrained optimal control problems,II

In this paper, the necessary optimality conditions for an unconstrained optimal control problem are used to derive a quasi-Newton method where the update involves only second-order derivative terms. A pointwise update which was presented in a previous paper by the authors is changed to allow for more general second-order sufficiency conditions in the control problem. In particular, pointwise versions of the Broyden, PSB, and SR1 update are considered. A convergence rate theorem is given for the Broyden and PSB versions.This research was supported by NSF Grant No. DMS-89-00410, by NSF Grant No. INT-88-00560, by AFOSR Grant No. AFOSR-89-0044, and by the Deutsche Forschungsgemeinschaft.     

A note on the use of direct sufficient conditions in optimal control problems

It is always possible to transform a nonautonomous optimal control problem into an autonomous one. However, the direct sufficient conditions may yield no information when applied to this autonomous problem, even though they do allow one to conclude sufficiency when applied to the original nonautonomous problem.This research was supported by the Air Force Office of Scientific Research, under Grant No. AFOSR-76-2923.     

A projected Newton method in a Cartesian product of balls

We formulate a locally superlinearly convergent projected Newton method for constrained minimization in a Cartesian product of balls. For discrete-time,N-stage, input-constrained optimal control problems with Bolza objective functions, we then show how the required scaled tangential component of the objective function gradient can be approximated efficiently with a differential dynamic programming scheme; the computational cost and the storage requirements for the resulting modified projected Newton algorithm increase linearly with the number of stages. In calculations performed for a specific control problem with 10 stages, the modified projected Newton algorithm is shown to be one to two orders of magnitude more efficient than a standard unscaled projected gradient method.This work was supported by the National Science Foundation, Grant No. DMS-85-03746.     

Numerical solution of minimax problems of optimal control,part 1

This paper contains general transformation techniques useful to convert minimax problems of optimal control into the Mayer-Bolza problem of the calculus of variations [Problem (P)]. We consider two types of minimax problems: minimax problems of Type (Q), in which the minimax function depends on the state and does not depend on the control; and minimax problems of Type (R), in which the minimax function depends on both the state and the control. Both Problem (Q) and Problem (R) can be reduced to Problem (P).For Problem (Q), we exploit the analogy with a bounded-state problem in combination with a transformation of the Jacobson type. This requires the proper augmentation of the state vectorx(t), the control vectoru(t), and the parameter vector , as well as the proper augmentation of the constraining relations. As a result of the transformation, the unknown minimax value of the performance index becomes a component of the parameter vector being optimized.For Problem (R), we exploit the analogy with a bounded-control problem in combination with a transformation of the Valentine type. This requires the proper augmentation of the control vectoru(t) and the parameter vector , as well as the proper augmentation of the constraining relations. As a result of the transformation, the unknown minimax value of the performance index becomes a component of the parameter vector being optimized.In a subsequent paper (Part 2), the transformation techniques presented here are employed in conjunction with the sequential gradient-restoration algorithm for solving optimal control problems on a digital computer; both the single-subarc approach and the multiple-subarc approach are discussed.This research was supported by the National Science Foundation, Grant No. ENG-79-18667, and by Wright-Patterson Air Force Base, Contract No. F33615-80-C3000. This paper is a condensation of the investigations reported in Refs. 1–7. The authors are indebted to E. M. Coker and E. M. Sims for analytical and computational assistance.     

Optimal intensity control of a multi-class queue

We study a mixed problem of optimal scheduling and input and output control of a single server queue with multi-classes of customers. The model extends the classical optimal scheduling problem by allowing the general point processes as the arrival and departure processes and the control of the arrival and departure intensities. The objective of our scheduling and control problem is to minimize the expected discounted inventory cost over an infinite horizon, and the problem is formulated as an intensity control. We find the well-knownc is the optimal solution to our problem.Supported in part by NSF under grant ECS-8658157, by ONR under contract N00014-84-K-0465, and by a grant from AT&T Bell Laboratories.The work was done while the author was a postdoctoral fellow in the Division of Applied Sciences, Harvard University, Cambridge, Massachusetts 02138.     

Generalized exterior boundary-value problems and optimization for the Helmholtz equation

A class of radiation problems is considered for the Helmholtz equation in exterior domains bounded by a smooth surface on which Dirichlet, Neumann, or Robin boundary conditions are imposed. The problem of finding the boundary data which maximizes far field power in a restricted subset of far field directions is formulated as a constrained maximization problem. Existence of an optimal solution in a variety of control domains is established. The particular case when the boundary is circular and the control domain is the unit ball inL ² is treated in detail. An algorithm for constructing the optimal solution is derived and used to obtain explicit numerical results.This work was supported by the US Air Force under Grant No. AFOSR 81-0156. The work was completed while the first author was on leave to the Institut für Numerische und Angewandte Mathematik, Universität Göttingen, Göttingen, BRD.     

A generalization of a minimax theorem of Fan via a theorem of the alternative

A minimization problem for a functional on a convex subsetC of a normed linear space is considered. Under certain hypotheses, optimality in a certain subset ofC implies the validity of first-order necessary optimality conditions for the problem inC. The result is applied to a problem in optimal periodic control of neutral functional differential equations.This work was partially supported by a grant from Deutsche Forschungsgemeinschaft and by AFOSR under Grant No. AFOSR-84-0398.     

Stabilization and control of distributed systems with time-dependent spatial domains

This paper considers the problem of the stabilization and control of distributed systems with time-dependent spatial domains. The evolution of the spatial domains with time is described by a finite-dimensional system of ordinary differential equations, while the distributed systems are described by first-order or second-order linear evolution equations defined on appropriate Hilbert spaces. First, results pertaining to the existence and uniqueness of solutions of the system equations are presented. Then, various optimal control and stabilization problems are considered. The paper concludes with some examples which illustrate the application of the main results.This work was supported by the Air Force Office of Scientific Research, Grant No. AFOSR 86-0132, by the National Science Foundation, Grant No. 87-18473, and by the Jet Propulsion Laboratory, Pasadena, California.     

Optimal impulsive control of compartment models,II: Algorithm

The optimal impulsive control of systems arising from linear compartment models for drug distribution in the human body is considered. A system of linear, time-invariant, homogeneous differential equations is given along with a set of continuous constraints on state and control. The object is to develop a constructive algorithm for the computation of the optimal control relative to a convex cost functional. Under suitable hypotheses, satisfying the continuous constraints is equivalent to satisfying the constraints at a finite set of abstractly definedcritical points. Once these critical points have been determined, the solution of the optimal control problem is found as the solution of an ordinary finite-dimensional convex programming problem. An iterative algorithm is given for the situation in which the critical points cannot all be determineda priori.This work was supported in part by the National Science Foundation under Grant No. MPS-74-13332.     

Optimal control of a nonlinear singular system with state constraints

A control system described by a nonlinear equation of parabolic type is considered in the situation where there may be no global solution. A particular optimal control problem subject to state constraints is studied. A proof of the existence of an optimal control is presented. The penalty method is used to obtain necessary conditions for optimal control. A proof of the convergence of this method is given. The successive approximation method is used to obtain an approximate solution for the conditions derived. Translated fromMatematicheskie Zametki, Vol. 60, No. 4, pp. 511–518, October, 1996.     

Small-time local controllability and continuity of the optimal time function for linear systems

For a finite-dimensional linear system, in which the control is restricted to belong to a completely arbitrary setJ, we give a simple necessary and sufficient condition for small-time local controllability from a pointp. The condition is equivalent to a characterization of the property that the Bellman function for the corresponding minimum-time optimal control problem is continuous atp.This work was partially supported by the National Science Foundation, Grant No. MCS-78-02442.     

Approximations of linear control problems with bang-bang solutions

We analyse the Euler discretization to a class of linear optimal control problems. First we show convergence of order h for the discrete approximation of the adjoint solution and the switching function, where h is the mesh size. Under the additional assumption that the optimal control has bang-bang structure we show that the discrete and the exact controls coincide except on a set of measure O(h). As a consequence, the discrete optimal control approximates the optimal control with order 1 w.r.t. the L ¹-norm and with order 1/2 w.r.t. the L ²-norm. An essential assumption is that the slopes of the switching function at its zeros are bounded away from zero which is in fact an inverse stability condition for these zeros. We also discuss higher order approximation methods based on the approximation of the adjoint solution and the switching function. Several numerical examples underline the results.     

A survey of Markov decision models for control of networks of queues

We review models for the optimal control of networks of queues. Our main emphasis is on models based on Markov decision theory and the characterization of the structure of optimal control policies.This research was partially supported by the National Science Foundation under Grant No. DDM-8719825. The Government has certain rights in this material. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The research was also partially supported by the C.I.E.S. (France), while the author was on leave at INRIA, Sophia-Antipolis, 1991–92.     

Optimal control of systems governed by a class of nonlinear evolution equations in a reflexive Banach space

The paper presents a closure theorem for the attainable trajectories of a class of control systems governed by a large class of nonlinear evolution equations in reflexive Banach spaces. Several existence theorems for optimal controls are proven that include a terminal control problem, a time-optimal control problem, and a special Bolza problem. Some results of independent interest are also presented.This work was supported in part by the National Research Council of Canada under Grant No. 7109.The authors would like to thank Professor L. Cesari for pointing out that joint continuity off is required for the setsG andR to satisfy the upper semicontinuity property (Theorems 5.1 and 5.2).     

Robust inverse optimal control for flexible structures

An inverse optimal control problem is formulated to develop robust control laws for purely oscillatory systems. The optimal control solution requires output feedback with specified constraints, leading to robustness with respect to unmodeled modes and a large class of parameter variations. The robustness properties are proved directly from known properties of control laws resulting from quadratic performance indices. The control laws are useful for poorly damped flexible structures.This research was supported by the Office of Naval Research, Contract No. N00014-77-C-0247.     

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

In Part 1 of this paper, implementable and conceptual versions of an algorithm for optimal control problems with control constraints and terminal equality constraints were presented. It was shown that anyL accumulation points of control sequences generated by the algorithms satisfy necessary conditions of optimality. Since such accumulation points need not exist, it is shown in this paper that control sequences generated by the algorithms always have accumulation points in the sense of control measure, and these accumulation points satisfy optimality conditions for the corresponding relaxed control problem.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAA-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.