Large-scale semidefinite programming algorithms and software for control, signal processing and system identification

用于控制、信号处理和系统辨识的大规模半定编程算法和软件

• 批准号: 0824003
• 负责人: Lieven Vandenberghe
• 金额: $ 32.48万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0824003&HistoricalAwards=false
• 关键词: Large; scale; semidefinite; programming; algorithms

ObjectivesSemidefinite programming is an extension of linear programming in which the inequality constraints are replaced by linear matrix inequalities. Semidefinite programs (SDPs) share most of the attractive properties of linear programs (convexity, polynomial-time complexity), but are also much more general. Numerous applications have been discovered during the last fifteen years, particularly in systems and control, and several general-purpose software packages have been developed. The proposal is motivated by the limited scalability of current general-purpose software. The objective is to develop specialized methods and software, with an efficiency far exceeding the capabilities of existing solvers, for two classes of SDPs that are of central importance in control and signal processing. The first class are SDPs derived from matrix sum-of-squares characterizations and the Kalman-Yakubovich-Popov lemma. This includes some of the most important applications of SDPs in control. The second class are nuclear norm minimization problems, which are important as convex heuristics for the NP-hard problem of minimizing the rank of a matrix subject to convex constraints. As an application of large-scale nuclear norm optimization, we intend to develop new system identification methods based on convex optimization.Intellectual meritSDP packages exploit sparsity, following the successful model of linear programming. This approach is less successful in semidefinite programming, for two reasons. First, techniques for exploiting sparsity in SDPs are much less effective than for linear programming. Second, converting a dense structured SDP into a sparse problem usually requires the auxiliary matrix variables and constraints, which greatly increases the problem dimensions. It is therefore of critical importance to develop new strategies for exploiting structure that are not only based on sparsity but incorporate domain-specific knowledge from system theory.Broader impactsSoftware based on the research results will be made freely available. This will contribute to a wider adoption of semidefinite programming, especially in the area of system identification. The research results will be integrated in the graduate optimization sequence in the Electrical Engineering Department at UCLA. We also plan to offer undergraduate research opportunities via individual study courses and summer internships, in partnership with the Center of Excellence in Engineering and Diversity at UCLA.

半定规划是线性规划的一种推广，其中不等式约束被线性矩阵不等式所取代。 半定规划（SDP）具有线性规划的大部分吸引人的特性（凸性，多项式时间复杂度），但也更一般。 在过去的十五年中，已经发现了许多应用，特别是在系统和控制方面，并且已经开发了几个通用软件包。 该提案的动机是目前通用软件的可扩展性有限。 我们的目标是开发专门的方法和软件，与效率远远超过现有的求解器的能力，两个类的SDP是在控制和信号处理的核心重要性。 第一类是从矩阵平方和特征和Kalman-Yakubovich-Popov引理导出的SDPs。 这包括SDP在控制中的一些最重要的应用。 第二类是核范数最小化问题，这是重要的凸算法的NP-难问题的最小化矩阵的秩受到凸约束。 作为大规模核范数优化的一个应用，我们打算开发新的系统识别方法的基础上凸优化。智能meritSDP包利用稀疏性，以下的线性规划的成功模型。 这种方法在半定规划中不太成功，有两个原因。 首先，在SDP中利用稀疏性的技术远不如线性规划有效。 其次，将密集结构的SDP转换为稀疏问题通常需要辅助矩阵变量和约束，这大大增加了问题的维数。 因此，开发不仅基于稀疏性，而且结合系统理论的特定领域知识的结构开发新战略至关重要。更广泛的影响基于研究结果的软件将免费提供。 这将有助于更广泛地采用半定规划，特别是在系统识别领域。 研究结果将被整合到加州大学洛杉矶分校电气工程系的研究生优化序列中。 我们还计划通过个人学习课程和暑期实习提供本科生研究机会，与加州大学洛杉矶分校的卓越工程和多样性中心合作。