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

用于控制、系统辨识和信号处理的圆锥优化方法

• 批准号: 1509789
• 负责人: Lieven Vandenberghe
• 金额: $ 32.96万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-15 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1509789&HistoricalAwards=false
• 关键词: Conic; optimization; methods; control; system

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.

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