Efficient idempotent methods for optimal control

Dynamic programming (DP) is a very powerful and robust tool for nonlinear optimization. Nevertheless, the applications have been limited to discrete / low dimensional systems due to the ubiquitous curse-of- dimensionality (CoD), which increases computation cost exponentially with the dimensionality of the problem. Application of DP to continuous-time and continuous-space systems gives rise to Hamilton-Jacobi-Bellman (HJB) PDEs, which are nonlinear and can have non-smooth solutions. Recently, a CoD-free method was developed to solve certain nonlinear semiconvex HJB PDEs. It is based on the linearity of the underlying semigroup on a suitable idempotent algebra. The CoD is avoided as it is grid-less and the solution is expressed as the maximum of quadratic functions. Moreover, the Hamiltonian is approximated by the maximum of M linear-quadratic Hamiltonians, where M is called the complexity. In process, the original problem is approximated by the optimal switching problem between M linear systems. Unfortunately, although the above method avoids the CoD, it suffers from a curse-of-complexity (CoC) as the number of quadratic bases used to approximate the value function, grow exponentially with the complexity. In this thesis, through the use of semidefinite programming based pruning techniques, this CoC has been partially abated. High dimensional, low complexity problems have been solved, pushing the envelope of the applicability of DP. This thesis also carries out the analysis of the error in the solution due to the PDE approximation and suboptimality of feedback control computed using it. This thesis also extends the original method for semiconcave Hamiltonians arising in cost minimization problems without nominal stability. As a generalization of a sub-problem within the CoD-free method, this thesis also develops the fundamental solution for the time-varying differential Riccati Equation (DRE). This is the counterpart of the state transition matrix in time- varying ODEs, and allows analytic computation of a general solution from a particular solution. It is also shown that the semiconvex duality transforms one DRE into another, and compatibility conditions are derived. In time- invariant special case, efficient doubling algorithms and analytic solutions are proposed. These show dramatic improvement over the time marching methods for long time horizon evolution of stiff DRE