Mathematical Sciences: Dynamical Systems, Complexity and Optimization

本课程将分析动力系统在最优化问题中的作用。我们将特别关注带有不等约束的最优化问题。要考虑的问题包括：半定规划，多面体上的非凸问题，一般的非线性凸数学规划问题，以及带有二次约束的线性-二次控制问题。研究相应动力系统的哈密顿结构及其与约束力学问题的关系。动力学系统的定性性质对势垒函数的选择的依赖性也将被考虑。比较了基于动力系统的算法构造的各种方法。将提出解决半定问题、测度空间中的最优化问题和无限维二次型问题的新方法。作为该项目的结果，预计在构建上述问题的内点算法方面将取得实质性进展。更重要的是，内点技术和序列二次规划方法的结合将导致求解具有状态空间和控制不等式约束的大类最优控制问题的有效算法。控制理论在从导弹制导到激光CD调谐等实际问题上有许多应用。控制策略的选择取决于可用的资源和性能指标，这是很自然的。这就是所谓最优控制理论的主要范式。直到最近，只有极少数的最优控制问题能被实时解决。所谓内点算法的快速发展完全改变了这种情况。现在很有可能解决最优控制和其他涉及不等式约束的无限维问题。机器人(包括运动规划、灵巧抓取力优化)和量子过程控制(对新材料的开发很重要)都是可以使用这些技术的问题的很好例子。内点算法最令人兴奋的方面是，它们的效率随着问题的大小而增长。在这项建议中，提出了一个开发内点算法的程序，该程序不能将这种方法应用于广泛的最优控制问题。概述了在保持其效率(通过复杂性估计来衡量)的同时推广内点算法的方法。动力系统理论为工程的实现提供了重要的理论工具。因此，人们期望开发出适合于最优控制应用的高效内点算法。将获得这些算法的复杂性估计。

The role of dynamical systems arising in connection with optimization problems will be analyzed. Special attention will be paid to optimization problems with inequality constraints. Among problems to be considered are: semidefinite programming, nonconvex problems on polytopes, general nonlinear convex mathematical programming problems, and linear-quadratic control problems with quadratic constraints. The Hamiltonian structure of corresponding dynamical systems and its relation to the problems of constraint mechanics will be studied. The dependence of qualitative properties of dynamical systems on the choice of barrier functions will also be considered. Various approaches to the construction of algorithms based on dynamical systems are compared. New approaches to semidefinite problems, optimization problems in spaces of measures, and infinite-dimensional quadratic problems will be suggested. As a result of the project, it is expected that substantial progress will be made toward construction of interior-point algorithms for the above mentioned classes of problems. More im portantly, the combination of interior-point techniques and sequential quadratic programming approaches will lead to efficient algorithms for solving broad classes of optimal control problems with both state space and control inequality constraints. Control theory has numerous applications to practical problems ranging from missile guidance to laser CD tuning. It is quite natural to expect that the choice of control strategy is determined by the available resources and the performance index. This is the main paradigm of so-called optimal control theory. Until very recently only few optimal control problems could be solved in real time. The very fast development of so-called interior-point algorithms completely changes the situation. It is now quite possible to address optimal control and other infinite-dimensional problems involving inequality constraints. Robotics (including motion planning, dexterous grasping force optimization) and control of quantum processes (important for the development of new materials) are good examples of problems where such techniques can be used. The exciting aspect of interior-point algorithms is that their efficiency grows with the size of the problem. In this proposal, a program of development interior-point algorithms is suggested which would unable one to apply this methodology to a broad class of optimal control problems. Ways are outlined to generalize interior-point algorithms while keeping their efficiency (measured by complexity estimates). Dynamical system theory provides an important theoretical tool for the realization of the project. As a result, it is expected that the efficient interior-point algorithms suitable for optimal control applications will be developed. Complexity estimates will be obtained fot these algorithms.