Total risk aversion,stochastic optimal control,and differential games

We present a connection between the theory of risk in the context of a stochastic optimal control problem and its relation to the theory of differential games. In particular, we define the notion of total risk aversion from the viewpoint of the upper value of a differential game. We prove that as the index of absolute risk aversion of a utility function in a stochastic control problem converges to infinity the (certainty equivalent) optimal payoff converges to the upper value of an associated deterministic differential game. The two main points of this paper are (1) a precise characterization oftotal risk aversion and (2) the construction of a stochastic optimal control problem intimately connected to a deterministic differential game.Partially supported by the Air Force Office of Scientific Research Grant No. AFOSR-86-0202.Partially supported by a grant from the National Science Foundation.     

Optimal scheduling of reservoir releases during flood: Deterministic optimization problem,part 1, procedure

In this paper, we are concerned with the optimal scheduling of water releases from retention reservoirs during flood, with the objective of minimizing flood damages at the important damage centers downstream of the reservoirs. Unlike in most other papers devoted to this subject, the flood routing equations are nonlinear. The performance index of the problem leads to a minimax optimal control problem. For this problem, the necessary optimality conditions are provided and a version of the feasible directions method is proposed.The research reported here has been supported by the Central Basic Research Program CPBP-03.09, Metody Analizy i Uytkowania Zasobow Wodnych, Polish Academy of Sciences, Warsaw, Poland. This support is kindly acknowledged.     

Controlled and optimally controlled multiplexing systems: A numerical exploration

Large controlled multiplexing systems are approximated by diffusion type processes yielding a very efficient way of approximation and good numerical methods. The limit equations are an efficient aggregation of the original system, and provide the basis of the actual numerical approximation to the control problem. The numerical approximations have the structure of the original problem, but are generally much simpler. The control can occur in a variety of places; e.g., leaky bucket controllers, control of marked cells at the transmitter buffer, or control of the transmitter speed. From the point of view of the limit equations, those are equivalent. Various forms of the optimal control problem are explored, where the main aim is to control or balance the losses at the control with those due to buffer overflow. It is shown that much can be saved via the use of optimal controls or reasonable approximations to them. We discuss systems with one to three classes of sources, various aggregation methods and control approximation schemes. There are qualitative comparisons of various systems with and without control and a discussion of the variations of control and performance as the systems data and control bounds vary. The approach is a very useful tool for providing both qualitative and quantitative information which would be hard to get otherwise. The results have applications to various forms of the ATM and broadband integrated data networks.The work was partially supported by AFOSR-91-0375 and (AFOSR) F49620-92-J-088-1DEF.The work was partially supported by grants (AFOSR) F49620-92-J-008-1DEF, AFOSR-91-03750.This work was partially supported by DAAH04-93-0070 (ARO) and AFOSR-91-0375.     

Weak and Strong Optimality Conditions for Constrained Control Problems with Discontinuous Control

In recent years, sufficient optimality criteria and solution stability in optimal control have been investigated widely and used in the analysis of discrete numerical methods. These results were concerned mainly with weak local optima, whereas strong optimality has been considered often as a purely theoretical aspect. In this paper, we show via an example problem how weak the weak local optimality can be and derive new strong optimality conditions. The criteria are suitable for practical verification and can be applied to the case of discontinuous controls with changes in the set of active constraints.     

Properties of Solutions to Second Order Evolution Control Systems. II

We continue the research of the first part of the article. We mainly study codensity for the set of admissible trajectory-control pairs of a system with nonconvex constraints in the set of admissible trajectory-control pairs of the system with convexified constraints. We state necessary and sufficient conditions for the set of admissible trajectory-control pairs of a system with nonconvex constraints to be closed in the corresponding function spaces. Using an example of a control hyperbolic system, we give an interpretation of the abstract results obtained. As application we consider the minimization problem for an integral functional on solutions of a control system.     

Min-max game theory and algebraic Riccati equations for boundary control problems with continuous input-solution map. Part II: The general case

We consider the abstract dynamical framework of [LT3, class (H.2)] which models a variety of mixed partial differential equation (PDE) problems in a smooth bounded domain ⁿ , arbitraryn, with boundaryL ₂-control functions. We then set and solve a min-max game theory problem in terms of an algebraic Riccati operator, to express the optimal quantities in pointwise feedback form. The theory obtained is sharp. It requires the usual Finite Cost Condition and Detectability Condition, the first for existence of the Riccati operator, the second for its uniqueness and for exponential decay of the optimal trajectory. It produces an intrinsically defined sharp value of the parameter, here called _c (critical), _c0, such that a complete theory is available for > _c, while the maximization problem does not have a finite solution if 0 < < _c. Mixed PDE problems, all on arbitrary dimensions, except where noted, where all the assumptions are satisfied, and to which, therefore, the theory is automatically applicable include: second-order hyperbolic equations with Dirichlet control, as well as with Neumann control, the latter in the one-dimensional case; Euler-Bernoulli and Kirchhoff equations under a variety of boundary controls involving boundary operators of order zero, one, and two; Schroedinger equations with Dirichlet control; first-order hyperbolic systems, etc., all on explicitly defined (optimal) spaces [LT3, Section 7]. Solution of the min-max problem implies solution of theH -robust stabilization problem with partial observation.The research of C. McMillan was partially supported by an IBM Graduate Student Fellowship and that of R. Triggiani was partially supported by the National Science Foundation under Grant NSF-DMS-8902811-01 and by the Air Force Office of Scientific Research under Grant AFOSR-87-0321.     

A way to the geometry of rings

This paper is concerned with the problem how to characterize geometrically the affine structure of free modules over rings (associative, with unit-element). The way to solve this problem leads to the concept of the so called affine line-geometry.     

Multi-stage stochastic optimization applied to energy planning

This paper presents a methodology for the solution of multistage stochastic optimization problems, based on the approximation of the expected-cost-to-go functions of stochastic dynamic programming by piecewise linear functions. No state discretization is necessary, and the combinatorial explosion with the number of states (the well known curse of dimensionality of dynamic programming) is avoided. The piecewise functions are obtained from the dual solutions of the optimization problem at each stage and correspond to Benders cuts in a stochastic, multistage decomposition framework. A case study of optimal stochastic scheduling for a 39-reservoir system is presented and discussed.     

Γ-convergence and optimal control problems

In this paper, we give some applications ofG-convergence and -convergence to the study of the asymptotic limits of optimal control problems. More precisely, given a sequence (P _h) of optimal control problems and a control problem (P), we determine some general conditions, involvingG-convergence and -convergence, under which the sequence of the optimal pairs of the problems (P _h) converges to the optimal pair of problem (P).The authors wish to thank Professor E. De Giorgi for many stimulating discussions.     

Optimal Control of Constrained Piecewise Affine Discrete-Time Systems

This paper makes two contributions; firstly, it provides a characterization of the solution of the optimal control problem for piecewise affine discrete-time systems with a quadratic cost function (the generally preferred option) and, secondly, provides a simple method (reverse transformation) for solving this and the previously solved &ell problem. The characterization is useful for on-line implementation.     

Remarks on certain growth conditions in problems of optimal control

In the Tonelli-Nagumo existence theorem for free problems of the calculus of variations, a uniform growth condition (T ₁) was employed to prove the equiabsolute continuity of the trajectories of a minimizing sequence. This same growth condition was shown to be equivalent to a pointwise growth condition (T ₂). Cesari utilized a generalization, condition (), in order to extend the Tonelli-Nagumo existence theorem to optimal control problems.In the present paper, we show that, for problems of optimal control, condition () is equivalent to a uniform growth condition () and that both conditions () and () are stronger than a pointwise growth condition (), a generalization of condition (T ₂). Two situations are given where conditions (), (), and () are equivalent, and the result of Tonelli and Turner concerning the equivalence of conditions (T ₁) and (T ₂) is obtained as a particular case of one of these situations.This research was partially supported by the National Science Foundation, Grant No. GK-234.     

On properties of the probabilistic constrained linear programming problem and its dual

In this paper, the two problems inf{inf{cx:x R ⁿ,A ₁ xy,A ₂ xb}:y suppF R ^m,F(y)p} and sup{inf{uy:y suppF R ^m,F(y)p}+vb:uA ₁+vA ₂=c, (u,v0} are investigated, whereA ₁,A ₂,b,c are given matrices and vectors of finite dimension,F is the joint probability distribution of the random variables ₁,..., _m, and 0<p<1. The first problem was introduced as the deterministic equivalent and the second problem was introduced as the dual of the probabilistic constrained linear programming problem inf{cx:P(A ₁ x)p,A ₂ xb}.b}. Properties of the sets and the functions involved in the two problems and regularity conditions of optimality are discussed.     

Optimal selection of the four best of a sequence

We consider the situation in which the decision-maker is allowed to have four choices with purpose to choose exactly the four absolute best candidates fromN applicants. The optimal stopping rule and the maximum probability of making the right choice are given for largeNN, the maximum asymptotic value of the best choice being lim _N P(win)0.12706.     

The Scalarization Approach to Multiobjective Markov Control Problems: Why Does It Work?

This paper concerns discrete-time multiobjective Markov control processes on Borel spaces and unbounded costs. Under mild assumptions, it is shown that the usual scalarization approach to obtain Pareto policies for the multiobjective control problem is in fact equivalent to solving the dual of a certain multiobjective infinite-dimensional linear program. The latter program is obtained from a multiobjective measure problem which is also used to prove the existence of strong Pareto policies, that is, Pareto policies whose cost vector is the closest to the control problems virtual minimum.     

A stochastic control approach to reciprocal diffusion processes

The problem of forcing a nondegenerate diffusion process to a given final configuration is considered. Using the logarithmic transformation approach developed by Fleming, it is shown that the perturbation of the drift suggested by Jamison solves an optimal stochastic control problem. Such perturbation happens to have minimum energy between all controls that bring the diffusion to the desired final distribution. A special property of the change of measure on the path-space that corresponds to the aforesaid perturbation of the drift is also shown.     

Chapter 13 Satisficing DEA models under chance constraints

DEA (Data Envelopment Analysis) models and concepts are formulated here in terms of the P-Models of Chance Constrained Programming, which are then modified to contact the satisficing concepts of H.A. Simon. Satisficing is thereby added as a third category to the efficiency/inefficiency dichotomies that have heretofore prevailed in DEA. Formulations include cases in which inputs and outputs are stochastic, as well as cases in which only the outputs are stochastic. Attention is also devoted to situations in which variations in inputs and outputs are related through a common random variable. Extensions include new developments in goal programming with deterministic equivalents for the corresponding satisficing models under chance constraints.     

Statistical verification of optimality conditions for stochastic programs with recourse

Statistically motivated algorithms for the solution of stochastic programming problems typically suffer from their inability to recognize optimality of a given solution algorithmically. Thus, the quality of solutions provided by such methods is difficult to ascertain. In this paper, we develop methods for verification of optimality conditions within the framework of Stochastic Decomposition (SD) algorithms for two stage linear programs with recourse. Consistent with the stochastic nature of an SD algorithm, we provide termination criteria that are based on statistical verification of traditional (deterministic) optimality conditions. We propose the use of bootstrap methods to confirm the satisfaction of generalized Kuhn-Tucker conditions and conditions based on Lagrange duality. These methods are illustrated in the context of a power generation planning model, and the results are encouraging.This work was supported in part by Grant No. AFOSR-88-0076 from the Air Force Office of Scientific Research and Grant No. DDM-89-10046 from the National Science Foundation.     

Sufficient conditions for bang-bang control in Hilbert space

Sufficient conditions for bang-bang and singular optimal control are established in the case of linear operator equations with cost functionals which are the sum of linear and quadratic terms, that is,Ax=u,J(u)=(r,x)+(x,x), >0. For example, ifA is a bounded operator with a bounded inverse from a Hilbert spaceH into itself and the control setU is the unit ball inH, then an optimal control is bang-bang (has norm l) if 0<1/2;A ^–1*r·A ^–1–2, but is singular (an interior point ofU) if >1/2A ^–1*r·A².This work was supported by NRC Grant No. A-4047 and NSF Grant No. GP-7445.     

A probabilistic analysis of the multiknapsack value function

The optimal solution value of the multiknapsack problem as a function of the knapsack capacities is studied under the assumption that the profit and weight coefficients are generated by an appropriate random mechanism. A strong asymptotic characterization is obtained, that yiclds a closed form expression for certain special cases.This research was partially supported by NSF Grant ECS-83-16224, and MPI Project Matematica computazionale.