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 nonsmooth 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 DREs.
|Commitee:||Bitmead, Robert, Gill, Philip, Helton, William, Krstic, Miroslav|
|School:||University of California, San Diego|
|Department:||Engineering Sciences (Mechanical Engineering)|
|School Location:||United States -- California|
|Source:||DAI-B 71/01, Dissertation Abstracts International|
|Subjects:||Applied Mathematics, Mechanical engineering, Systems science|
|Keywords:||Dynamic programming, Hamilton-Jacobi-Bellman PDEs, Max-plus algebra, Numerical method, Optimal control, Riccati differential equations|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be