A numerical method for hybrid optimal control based on dynamic programming

This contribution extends a numerical method for solving optimal control problems by dynamic programming to a class of hybrid dynamic systems with autonomous as well as controlled switching. The value function of the hybrid control system is calculated based on a full discretization of the state and input spaces. A bound for the error due to discretization is obtained from modeling the error as perturbation of the continuous dynamics and the cost terms. It is shown that the bound approaches zero and that the value function of the discretized variant converges to the value function of the original problem if the discretization parameters go to zero. The performance of a numerical scheme exploiting the discretized system is illustrated for two different examples treated previously in literature.     

Risk-Sensitive Ergodic Control of Continuous Time Markov Processes With Denumerable State Space

In this article, we study risk-sensitive control problem with controlled continuous time Markov chain state dynamics. Using multiplicative dynamic programming principle along with the atomic structure of the state dynamics, we prove the existence and a characterization of optimal risk-sensitive control under geometric ergodicity of the state dynamics along with a smallness condition on the running cost.     

Risk-Sensitive Control of Pure Jump Process on Countable Space with Near Monotone Cost

In this article, we study risk-sensitive control problem with controlled continuous time pure jump process on a countable space as state dynamics. We prove multiplicative dynamic programming principle, elliptic and parabolic Harnack’s inequalities. Using the multiplicative dynamic programing principle and the Harnack’s inequalities, we prove the existence and a characterization of optimal risk-sensitive control under the near monotone condition.     

A decomposition approach for optimal control problems with integer innerpoint state constraints

A large class of optimal control problems for hybrid dynamic systems can be formulated as mixed‐integer optimal control problems (MIOCPs). A decomposition approach is suggested to solve a special subclass of MIOCPs with mixed integer inner point state constraints. It is the intrinsic combinatorial complexity of the discrete variables in addition to the high nonlinearity of the continuous optimal control problem that forms the challenges in the theoretical and numerical solution of MIOCPs. During the solution procedure the problem is decomposed at the inner time points into a multiphase problem with mixed integer boundary constraints and phase transitions at unknown switching points. Due to a discretization of the state space at the switching points the problem can be decoupled into a family of continuous optimal control problems (OCPs) and a problem similar to the asymmetric group traveling salesman problem (AGTSP). The OCPs are transcribed by direct collocation to large‐scale nonlinear programming problems, which are solved efficiently by an advanced SQP method. The results are used as weights for the edges of the graph of the corresponding TSP‐like problem, which is solved by a Branch‐and‐Cut‐and‐Price (BCP) algorithm. The proposed approach is applied to a hybrid optimal control benchmark problem for a motorized traveling salesman. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An optimal control problem with a random stopping time

This paper deals with a stochastic optimal control problem where the randomness is essentially concentrated in the stopping time terminating the process. If the stopping time is characterized by an intensity depending on the state and control variables, one can reformulate the problem equivalently as an infinite-horizon optimal control problem. Applying dynamic programming and minimum principle techniques to this associated deterministic control problem yields specific optimality conditions for the original stochastic control problem. It is also possible to characterize extremal steady states. The model is illustrated by an example related to the economics of technological innovation.This research has been supported by NSERC-Canada, Grants 36444 and A4952; by FCAR-Québec, Grant 88EQ3528, Actions Structurantes; and by MESS-Québec, Grant 6.1/7.4(28).     

Solving elliptic control problems with interior point and SQP methods: control and state constraints

We study optimal control problems for semilinear elliptic equations subject to control and state inequality constraints. Both boundary control and distributed control problems are considered with boundary conditions of Dirichlet or Neumann type. By introducing suitable discretization schemes, the control problem is transcribed into a nonlinear programming problem. Necessary conditions of optimality are discussed both for the continuous and the discretized control problem. It is shown that the recently developed interior point method LOQO of [35] is capable of solving these problems even for high discretizations. Four numerical examples with Dirichlet and Neumann boundary conditions are provided that illustrate the performance of the algorithm for different types of controls including bang–bang controls.     

Optimization Techniques for Solving Elliptic Control Problems with Control and State Constraints: Part 1. Boundary Control

We study optimal control problems for semilinear elliptic equations subject to control and state inequality constraints. In a first part we consider boundary control problems with either Dirichlet or Neumann conditions. By introducing suitable discretization schemes, the control problem is transcribed into a nonlinear programming problem. It is shown that a recently developed interior point method is able to solve these problems even for high discretizations. Several numerical examples with Dirichlet and Neumann boundary conditions are provided that illustrate the performance of the algorithm for different types of controls including bang-bang and singular controls. The necessary conditions of optimality are checked numerically in the presence of active control and state constraints.     

Optimal control of stochastic functional differential equations with a bounded memory

This paper treats a finite time horizon optimal control problem in which the controlled state dynamics are governed by a general system of stochastic functional differential equations with a bounded memory. An infinite dimensional Hamilton–Jacobi–Bellman (HJB) equation is derived using a Bellman-type dynamic programming principle. It is shown that the value function is the unique viscosity solution of the HJB equation.     

Algorithm for constructing an optimal control strategy in a nonlinear differential game with Lipschitz compactly supported payoff

For a zero-sum differential game, we consider an algorithm for constructing optimal control strategies with the use of backward minimax constructions. The dynamics of the game is not necessarily linear, the players’ controls satisfy geometric constraints, and the terminal payoff function satisfies the Lipschitz condition and is compactly supported. The game value function is computed by multilinear interpolation of grid functions. We show that the algorithm error can be arbitrarily small if the discretization step in time is sufficiently small and the discretization step in the state space has a higher smallness order than the time discretization step. We show that the algorithm can be used for differential games with a terminal set. We present the results of computations for a problem of conflict control of a nonlinear pendulum.     

Convergence Analysis of the Implicit Euler-discretization and Sufficient Conditions for Optimal Control Problems Subject to Index-one Differential-algebraic Equations

For optimal control problems subject to index-one differential-algebraic equations in semi-explicit form we discuss second order sufficient conditions in form of a coercivity condition taking into account the two-norm discrepancy. Furthermore we introduce a related Riccati-type and Legendre-Clebsch condition which are sufficient for the validity of the coercivity condition. Using the implicit Euler-discretization we approximate the optimal control problem and analyze the convergence of solutions of the local minimum principle for the discretized optimal control problem by applying the general convergence framework of Stetter, which requires the discretization method to be continuous, consistent, and stable.

     

Stochastic optimization of forward recursive functions

This note solves a finite-horizon stochastic optimization problem with forward recursive criterion through dynamic programming. The forward recursive criterion is wide; it includes additive (discounted), multiplicative (discounted risk-sensitive), minimum and terminal criteria. The basic idea is to apply invariant imbedding method for the stochastic optimization. The method incorporates recursive accumulation process into dynamics by expanding the original state space.     

Mesh-independent convergence of penalty methods applied to optimal control with partial differential equations

In this paper, optimal control problems with elliptic state equations and constraints on controls are considered. Also state constraints are briefly discussed. Barrier-penalty methods are applied to treat the occurring restrictions. In the case of finite-dimensional optimization problems, the considered methods have a linear rate of convergence in dependence of the penalty parameter. However, in the case of infinite-dimensional problems, as studied in this article, the direct application of finite-dimensional theory, as given in Grossmann and Zadlo [A general class of penalty/barrier path-following Newton methods for nonlinear programming, Optimization 54 (2005), pp. 161–190], would lead to mesh-dependent order one estimates that deteriorate if the discretization is refined. In this article a first rigorous proof is given for inequality constrained problems that in the case of quadratic penalties a mesh-independence principle holds, i.e. the first-order convergence estimate holds for the continuous problem as well as for discretized problems independently of the discretization step size. The penalty techniques rest upon the control approximate reduction as discussed, e.g. in Grossmann et al. [C. Grossmann, H. Kunz, and R. Meischner, Elliptic control by penalty techniques with control reduction, in System Modeling and Optimization, IFIP Advances in Information and Communication Technology, Vol. 312, Springer, Berlin, 2009, pp. 251–267; M. Hinze, A variational discretization concept in control constrained optimization: the linear-quadratic case, Comput. Optim. Appl. 30 (2005), pp. 45–61]. For the discretization conforming linear element discretization is applied. Some numerical examples illustrate and confirm the theoretical results.     

Convergent computational method for relaxed optimal control problems

A class of relaxed optimal control problems for ordinary differential equations with a state-space constraint is considered. The discretization by the control parametrization method, formerly proposed by Teo and Goh (Refs. 1, 2), is modified by admitting a tolerance in the state constraint, which enables one to prove a conditional convergence under certain additional qualification on the dynamics. Also, a counterexample is constructed, showing that the original, nonmodified discretization need not approximate the continuous problem.The author is grateful to Professor K. L. Teo for useful comments on this paper.     

Optimal control problems on manifolds: a dynamic programming approach

Dynamic programming identifies the value function of continuous time optimal control with a solution to the Hamilton-Jacobi equation, appropriately defined. This relationship in turn leads to sufficient conditions of global optimality, which have been widely used to confirm the optimality of putative minimisers. In continuous time optimal control, the dynamic programming methodology has been used for problems with state space a vector space. However there are many problems of interest in which it is necessary to regard the state space as a manifold. This paper extends dynamic programming to cover problems in which the state space is a general finite-dimensional C^∞ manifold. It shows that, also in a manifold setting, we can characterise the value function of a free time optimal control problem as a unique lower semicontinuous, lower bounded, generalised solution of the Hamilton-Jacobi equation. The application of these results is illustrated by the investigation of minimum time controllers for a rigid pendulum.     

On Applied Nonlinear and Bilevel Programming or Pursuit-Evasion Games

Motivated by the benefits of discretization in optimal control problems, we consider the possibility of discretizing pursuit-evasion games. Two approaches are introduced. In the first approach, the solution of the necessary conditions of the continuous-time game is decomposed into ordinary optimal control problems that can be solved using discretization and nonlinear programming techniques. In the second approach, the game is discretized and transformed into a bilevel programming problem, which is solved using a first-order feasible direction method. Although the starting points of the approaches are different, they lead in practice to the same solution algorithm. We demonstrate the usability of the discretization by solving some open-loop representations of feedback solutions for a complex pursuit-evasion game between a realistically modeled aircraft and a missile, with terminal time as the payoff. The solutions are compared with those obtained via an indirect method.     

Generalized solution in singular stochastic control: The nondegenerate problem

This paper is concerned with singular stochastic control for non-degenerate problems. It generalizes the previous work in that the model equation is nonlinear and the cost function need not be convex. The associated dynamic programming equation takes the form of variational inequalities. By combining the principle of dynamic programming and the method of penalization, we show that the value function is characterized as a unique generalized (Sobolev) solution which satisfies the dynamic programming variational inequality in the almost everywhere sense. The approximation for our singular control problem is given in terms of a family of penalized control problems. As a result of such a penalization, we obtain that the value function is also the minimum cost available when only the admissible pairs with uniformly Lipschitz controls are admitted in our cost criterion.     

Elliptic control problems with gradient constraints—variational discrete versus piecewise constant controls

We consider an elliptic optimal control problem with pointwise bounds on the gradient of the state. To guarantee the required regularity of the state we include the L ^r -norm of the control in our cost functional with r>d (d=2,3). We investigate variational discretization of the control problem (Hinze in Comput. Optim. Appl. 30:45–63, 2005) as well as piecewise constant approximations of the control. In both cases we use standard piecewise linear and continuous finite elements for the discretization of the state. Pointwise bounds on the gradient of the discrete state are enforced element-wise. Error bounds for control and state are obtained in two and three space dimensions depending on the value of r.