Linear programming approach to discrete time optimal control problems with time discounting

The linear programming (LP) approach to control systems is based on the fact that the occupational measures generated by admissible controls and the corresponding solutions of a nonlinear system satisfy certain linear equations representing the system’s dynamics in an integral form. The idea of such linearization was explored extensively in relation to various deterministic and stochastic problems of optimal control of systems that evolve in continuous time. However, no results based on this idea for deterministic discrete time control systems is available in the literature. The thesis aims at the development of LP based techniques for analysis and solution of a deterministic discrete time optimal control problem with time discounting criteria. To this end, we reformulate the optimal control problem as that of optimization problem on the set of discounted occupational measures and we show that the optimal value of the latter is equal to the optimal value of a certain infinite dimensional (ID) LP problem. We then show that this IDLP problem can be approximated by semi-infinite linear programming problems and subsequently by finite-dimensional (“standard”) LP problems. We also indicate a way how a near optimal control of the underlying nonlinear optimal control problem can be constructed on the basis of the solution of an approximating finite-dimensional LP problem.