Practical Large-Scale Sum-of-Squares Optimization

多项式优化是一种基本的计算技术，在电力系统工程、信号处理、统计学、几何学和医学等广泛领域都有应用。有几种现有的多项式优化计算方法;然而，它们都有一些核心思想，限制了它们的效率和稳定性。随着现代应用程序中模型的大小和复杂性不断增加，这些现有的方法越来越受到限制。该研究项目旨在开发新的计算方法，同时比现有技术更可靠，更有效。为了保证研究的相关性，这些方法将被实现为易于使用的计算工具，这将被广泛传播到科学和工程界。全局多项式优化问题的解决方案的最常见的方法之一利用半定规划（SDP）层次。这些产生于结合代数理论的平方和多项式和观察平方和多项式是半定的表示。虽然理论上令人满意，但将平方和优化问题转化为SDP并不总是实用的。首先，平方和多项式的SDP表示粗略地平方了优化变量的数量，将求解算法的时间和内存复杂度增加了几个数量级。第二个问题是数字。在常见的SDP公式中，对偶变量是半定矩阵，其条件数随着所涉及的多项式的次数呈指数增长。这对于浮点实现是有害的。该项目建立在非对称圆锥优化和多元插值的最新结果的基础上，推导出规避使用标准的基于SDP的方法进行平方和优化所需的算法理论和实用计算工具。我们的目的是为这些问题提供算法，既有效，计算有效。主要研究者将研究新算法开发对各种应用的影响，包括最佳放射治疗的设计。

Polynomial optimization is a fundamental computational technique, with applications in a wide variety of fields that include power systems engineering, signal processing, statistics, geometry, and medicine. There are several existing computational approaches for polynomial optimization; however, they all share a few core ideas that limit both their efficiency and stability. As the size and complexity of the models arising from modern applications continues to increase, these existing approaches are increasingly limiting. This research project is aimed toward the development of novel computational methods that are simultaneously more reliable and more efficient than the existing techniques. To assure the relevance of the research, the approaches will be implemented as easily usable computational tools, which will be disseminated widely to the scientific and engineering community.One of the most common approaches to the solution of global polynomial optimization problems utilizes semi-definite programming (SDP) hierarchies. These arise from combining the algebraic theory of sum-of-squares polynomials and the observation that sum-of-squares polynomials are semi-definite representable. While theoretically satisfactory, the translation of sum-of-squares optimization problems to SDPs is not always practical. First, the SDP representation of sum-of-squares polynomials roughly squares the number of optimization variables, increasing the time and memory complexity of the solution algorithms by several orders of magnitude. The second problem is numerical. In the common SDP formulation, the dual variables are semi-definite matrices whose condition numbers grow exponentially with the degree of the polynomials involved. This is detrimental for a floating-point implementation. This project builds on recent results in non-symmetric conic optimization and multivariate interpolation to derive the algorithmic theory and practical computational tools needed to circumvent the need to use the standard SDP-based approach to sum-of-squares optimization. The aim is to provide algorithms for these problems that are both efficient and computationally effective. The principal investigator will investigate the impact of the novel algorithm developments for a diverse set of applications, including the design of optimal radiotherapy treatments.