Nonlinear Control, HJB Equations, and the Max-Plus Algebra

该项目的重点是使用极大代数作为解决非线性控制和估计问题的工具。所讨论的主要问题是与之相关的动态规划方程采用非线性Hamilton-Jacobi-Bellman偏微分方程(HJB PDE)的形式的问题。与这类问题相关的半群是时间指标算子，它们是极大加线性的。最大-加线性可以被用来发展HJB偏微分方程组的数值方法，这可以被描述为(最大-加)谱方法。这些形成了一类全新的HJB偏微分方程组的数值方法。该项目还将考虑一种方法，在这种方法中，人们可以在半凸对偶空间中从算子构造复杂算子来解决更简单的问题，如线性-二次问题。这使得人们可以避免在基于最大值+的方法中计算最密集的部分的计算中的维度诅咒，对于其算子可以通过对偶空间中的这样的结构来逼近的问题。控制理论对于任何希望估计系统的真实状态和/或控制其未来行为的系统是有用的。控制理论的方法适用于各种各样的真实世界系统，如飞机动力学、航天器动力学、投资组合优化、期权定价和机器人车辆集合。虽然对行为接近线性的系统的控制已经相当成功，但仍存在许多问题，其中系统的行为可能是高度非线性的，并且此类问题的数量正在增加。非线性控制问题的求解是相当困难的，对于状态仅由两个或三个以上标量变量描述的系统，在计算上也不容易处理。这类问题的解通常是通过解相关的偏微分方程解得到的。最常见的方法是采用有限元方法(通常用于解决流体流动等问题)来求解此类偏微分方程组，从而解决控制问题。然而，计算需求随着标量状态变量的数量呈指数级快速增长，这通常被称为维灾。由于计算成本的指数增长，我们不能指望速度更快的计算机将在可预见的未来导致相当大的问题的解决。因此，我们必须探索解决这些问题的替代办法。在本项目中，我们将一类新的方法应用于此类非线性控制问题。这些方法利用了这样一个事实，即这些非线性问题在一组不同的代数运算上是线性的，这组运算被称为极大加代数。通过使用这种极大加线性，人们可以获得新的数值方法，这些方法似乎提供了计算上的节省。尽管人们不能指望完全消除维度诅咒，但这些方法应该会减弱其影响。

The project focuses on the use of the max-plus algebra as a tool for the solution of nonlinear control and estimation problems. The main classes of problems addressed are those for which the associated dynamic programming equation takes the form of a nonlinear Hamilton-Jacobi-Bellman partial differential equation (HJB PDE). The semigroups associated with such problems are time-indexed operators which are max-plus linear. The max-plus linearity may be exploited to develop numerical methods for HJB PDEs, which might be described as (max-plus) spectral methods. These form a completely new class of numerical methods for HJB PDEs. The project will also consider approaches where one can construct complex operators in the semiconvex dual space from operators for simpler problems such as linear-quadratic problems. This allows one to avoid the curse-of-dimensionality in the most computationally intensive portion of the computations in max-plus based methods for problems whose operators may be approximated by such constructions in the dual-space.Control Theory is useful for any system where one desires to estimate the true state of the system and/or to control its future behavior. The methods of control theory apply to a tremendous variety of real-world systems such as aircraft dynamics, spacecraft dynamics, portfolio optimization, option pricing, and collections of robotic vehicles. Although the control of systems whose behavior is close to linear has been quite successful, there are many problems where the system behavior may be highly nonlinear, and the number of such problems is on the rise. The solution of nonlinear control problems is quite difficult, and not computationally tractable for systems whose states are described by more than just two or three scalar variables. The solution of such problems is most often obtained by the solution of an associated partial differential equation. The most common approach has been to adopt finite element methods (often used to solve problems such as fluid flow) in order to solve such partial differential equations, and consequently, the control problems. However, the computational requirements grow exponentially fast as a function of the number of scalar state variables.This is commonly referred to as the curse-of-dimensionality. Due to this exponential growth in computational cost, we cannot hope that faster computers will lead to solution of reasonably large problems in the foreseeable future. Therefore, we must explore alternative approaches to the solution of such problems. In this project, we apply a new class of methods to such nonlinear control problems. These methods exploit the fact that these nonlinear problems are linear over a different set of algebraic operations known as the max-plus algebra. By employing this max-plus linearity, one can obtain new numerical methods that appear to provide computational savings. Although one cannot hope to completely remove the curse-of-dimensionality, these methods should attenuate its effects.