Idempotent Analysis and Curse-of-Dimensionality-Free Methods in Nonlinear Control

University Of California-San Diego, La Jolla CA

Investigators

Abstract

This project has two components. The first is the development of max-plus based curse-of-dimensionality-free algorithms for solution of nonlinear deterministic optimal control problems, and the second is determination of fundamental solutions for ordinary and partial differential equations with quadratic nonlinearities. In the former, we rely on the max-plus linearity of the semigroup associated to the Hamilton-Jacobi-Bellman partial differential equation associated with the control problem. In the latter, we develop new fundamental solutions and associated exponentially fast numerical methods for such equations, which are obtained through an exponentiation operation on an idempotent semiring. This project is concerned with nonlinear optimal control, of which auto-pilots for air and space vehicles, stock portfolio management, and manufacturing control are examples. Mathematical models of optimal control problems typically involve partial differential equations, whose solution must be obtained computationally. The difficulty is that the dimension of the space over which one must solve the equations is the dimension of the state of the system. For example, the absolutely simplest model of the motion of an object relies on a six-dimensional state vector, with three components describing position and three describing velocity. Thus one would solve the partial differential equation over six-dimensional space. Realistic models typically have say ten or more dimensions. When one begins putting a grid over space, the number of points needed per dimension is on the order of 100. Consequently, to solve a partial differential equation in two dimensions one would need 10,000 grid points, and for three dimensions, 1,000,000 grid points. For a six-dimensional problem one requires a trillion grid points; this is the "curse-of-dimensionality" and it has been a severe obstacle to nonlinear control for over a half-century. We are developing methods for solution of such problems, and these methods are not subject to the curse-of-dimensionality. There is no free lunch, and there are other prices to be paid. Nonetheless, we are already solving problems which would have been intractable for many decades, even if Moore's law were to continue indefinitely. Further, this is just the beginning, and more major advances should follow.