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

这个项目有两个组成部分。首先是基于max-plus的求解非线性确定性最优控制问题的无量纲算法的发展，其次是二次非线性常微分方程和偏微分方程的基本解的确定。在前者中，我们依赖于与控制问题相关的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.