Idempotent algebras include the max-plus and min-plus semifields and the min-max semiring. There is a deep relation between these algebras and the semigroups associated with Hamilton-Jacobi-Bellman (HJB) and Hamilton-Jacobi-Isaacs partial differential equations (PDEs). During the past decade, the max-plus curse-of-dimensionality-free methods for solution of classes of first-order HJB PDEs were discovered. Most importantly, for some classes of HJB PDEs, these methods can solve problems in significantly higher dimensions than would be feasible with classical, i.e., grid-based, methods, which are subject to the curse of dimensionality. More recently, it has been discovered that idempotent distributive properties allow such methods to address stochastic control and dynamic game problems, and this is opening up interesting new domains. The project has four components. The first is the further development of max-plus curse-of-dimensionality-free numerical methods, specifically extending the domain of applicability to diffusion processes. Second, application of these methods to the control of quantum-spin in the case of open quantum systems where one has stochastic inputs. On the third front, the investigators are developing idempotent algebra-based methods for solution of linear, infinite-dimensional control and estimation problems where the dynamics are described by systems of PDEs. The fourth component regards fundamental solutions of two-point boundary value problems (TPBVPs) for conservative systems, in which case one may apply the Stationary Action Principle. The fundamental solutions convert two-point boundary value problems into initial value problems via an idempotent convolution of the fundamental solution with a cost function related to the terminal data. Moreover, as these are fundamental solutions, once computed, one can easily convert any of a large class of TPBVPs for that system and time duration into an initial value problem. The investigators are also expanding this theory to cover the classic n-body problem. There, it can be found that an n-body TPBVP, posed in terms of the stationary-action principle, can be converted into a differential game, and the fundamental solution can be obtained as a set in Euclidean space.

Optimal control has not generally been feasible due to the half-century old problem of the curse of dimensionality, whereby with classical grid-based approaches, the computational complexity grows exponentially fast with the dimension of the system being controlled. Max-plus based curse-of-dimensionality-free methods are not necessarily subject to this exponential growth. Consequently, this research is opening up large application areas which were previously inaccessible. Specific applications of interest (among many possible application domains) include spacecraft and aircraft guidance and control, quantum spin control, signal amplification for long fiber-optic networks, UAV sensor tasking operations and portfolio optimization. The efforts on fundamental solutions for two-point boundary value problems will allow rapid solution of dynamical system problems where one seeks solutions of the dynamics for a variety of initial/terminal conditions. That is, the fundamental solution allows one to use the same object repeatedly for varying initial and terminal data. The applications of current interest include systems governed by linear, infinite-dimensional dynamics such as the standard heat and wave equations, as well as the n-body problem. In the latter case, applications could include rapid estimation of asteroid threats. Extensions to other classes of potential fields, beyond gravitational, will also be considered.

National Science Foundation (NSF)
Division of Mathematical Sciences (DMS)
Standard Grant (Standard)
Application #
Program Officer
Victor Roytburd
Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
University of California San Diego
La Jolla
United States
Zip Code