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

非线性控制中的幂等分析和无维数灾难方法

• 批准号: 0808131
• 负责人: William McEneaney
• 金额: $ 19万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0808131&HistoricalAwards=false
• 关键词: Idempotent; Analysis; Curse; Dimensionality; Free

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.

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