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

这个项目有两个组成部分。第一个是基于最大加法的无维灾算法的发展，用于求解非线性确定性最优控制问题；第二个是确定具有二次非线性的常微分方程组和偏微分方程组的基本解。在前者中，我们依赖于与控制问题相关的Hamilton-Jacobi-Bellman偏微分方程半群的极大加线性。在后者中，我们发展了这类方程的新的基本解和相关的指数快速数值方法，这些方程是通过幂等半环上的指数运算得到的。这个项目涉及非线性最优控制，例如航空和航天飞行器的自动驾驶，股票组合管理和制造控制。最优控制问题的数学模型通常涉及偏微分方程组，其解必须通过计算获得。困难在于，一个人必须在其上解方程的空间的维度是系统状态的维度。例如，物体运动的最简单模型依赖于一个六维状态向量，三个分量描述位置，三个分量描述速度。这样，就可以在六维空间中求解偏微分方程式。逼真的模型通常有十个或更多的维度。当人们开始在空间上放置网格时，每个维度所需的点数约为100个。因此，要在二维中求解偏微分方程，需要10,000个网格点，对于三维，需要1,000,000个网格点。对于一个六维问题，需要一万亿个网格点；这就是“维度诅咒”，半个多世纪以来，它一直是非线性控制的严重障碍。我们正在开发解决这些问题的方法，这些方法不受维度诅咒的影响。没有免费的午餐，还需要付出其他代价。尽管如此，我们已经在解决几十年来难以解决的问题，即使摩尔定律无限期地继续下去。此外，这只是个开始，接下来应该会有更多重大进展。

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.