Conic optimization methods for control, system identification, and signal processing

凸优化方法在控制、信号处理、机器学习以及许多其他工程和应用科学领域都很重要。在过去的二十五年里，凸优化算法的进步导致了可靠和用户友好的软件工具，广泛用于学术研究和工业。最流行的软件包是基于建模前端和半定优化（经典线性规划的矩阵扩展，以及二次线性优化的特殊情况）的通用求解器之间的分离。建模前端的任务是将优化问题转化为半定优化求解器所需的规范形式。在这个转换步骤中使用的技术是对如何以半确定优化格式表示非线性凸约束的广泛研究的结果。求解器中使用的算法是半确定优化的原始对偶内点法，该算法在21世纪初达到了很高的成熟度。这两层中的每一层都限制了可伸缩性。在建模步骤中简化为半定优化通常需要引入辅助变量和约束，这可以大大增加优化问题的规模。此外，在凸优化求解器中常用的半定优化算法是二阶方法，并且在每次迭代中需要求解大型的、通常是密集的线性方程组。这进一步限制了可以解决的问题的规模。这一建议的动机是日益增长的需求大规模凸优化算法在控制，信号处理，和系统识别。该项目专注于为两种类型的约束开发专门的方法，这两种约束是这些领域中一些最重要的凸优化应用的基础，最近在统计信号处理和机器学习中发现了新的应用。第一类问题是涉及非负波波夫函数的凸锥的凸优化问题。这包括非负矩阵多项式和三角多项式，在线性系统理论、控制和信号处理中具有重要的基础意义。第二类包括基于最小化结构化矩阵的核范数（迹范数）的系统辨识方法。关注这两个问题类有几个原因：首先，它们在系统理论和信号处理中的中心地位；二是使用通用半确定优化软件求解的众所周知的困难；第三，它们在最近发现的将稀疏信号恢复的1范数优化方法扩展到连续域上的稀疏信号恢复问题和矩阵秩最小化问题的技术中的重要性。对于这两类问题中的每一类，将考虑两种算法方法：非对称二次优化的内点方法，直接处理约束，而不会将它们嵌入到更大的半定优化问题中，以及基于算子分裂和分解技术的一阶近端算法。

Convex optimization methods are important in control, signal processing, machine learning, and many other fields of engineering and applied science. Advances in algorithms for convex optimization over the last twenty-five years have resulted in reliable and user-friendly software tools that are widely used in academic research and industry. The most popular software packages are based on a separation between a modeling front-end and a general-purpose solver for semidefinite optimization (a matrix extension of classical linear programming, and a special case of conic linear optimization). The task of the modeling front-end is to translate the optimization problem into the canonical form required by the semidefinite optimization solver. The techniques used in this translation step are the outcome of extensive research on how to represent nonlinear convex constraints in the semidefinite optimization format. The algorithms used in the solvers are primal-dual interior-point methods for semidefinite optimization, which reached a high level of maturity in the early 2000s. Each of these two layers brings a limit on scalability. The reduction to semidefinite optimization in the modeling step often requires the introduction of auxiliary variables and constraints, which can increase the size of the optimization problem considerably. In addition, the semidefinite optimization algorithms that are commonly used in convex optimization solvers are second-order methods and require in each iteration the solution of large, often dense, sets of linear equations. This further limits the size of the problems that can be solved. This proposal is motivated by the increasing demand for large-scale convex optimization algorithms in control, signal processing, and system identification. The project focuses on developing specialized methods for two types of constraints that underlie some of the most important convex optimization applications in these areas, and that have recently found new applications in statistical signal processing and machine learning. The first class of problems consists of convex optimization problems involving convex cones of nonnegative Popov functions. This includes nonnegative matrix polynomials and trigonometric polynomials, and is of fundamental importance in linear system theory, control, and signal processing. The second class includes system identification methods based on minimizing the nuclear norm (trace norm) of structured matrices. The focus on these two problem classes is motivated by several reasons: first, their central position in system theory and signal processing; second, well-known difficulties in solving them using general-purpose semidefinite optimization software; and, third, their importance in recently discovered techniques that extend 1-norm optimization methods for sparse signal recovery to sparse signal recovery problems over continuous domains and to matrix rank minimization problems. Two algorithmic approaches will be considered for each of the two problem classes: interior-point methods for non-symmetric conic optimization, that handle the constraints directly without embedding them in a much larger semidefinite optimization problem, and first-order proximal algorithms based on operator splitting and decomposition techniques.