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

目的半定规划是线性规划的一种推广，它用线性矩阵不等式代替了不等式约束。半定规划(SDP)具有线性规划的大部分吸引人的性质(凸性、多项式时间复杂性)，但也更具一般性。在过去的15年中，发现了许多应用，特别是在系统和控制方面，并开发了几个通用软件包。这项提议的动机是当前通用软件的可扩展性有限。其目标是为在控制和信号处理中至关重要的两类SDP开发专门的方法和软件，其效率远远超过现有解算器的能力。第一类是由矩阵平方和刻画和Kalman-Yakubovich-Popov引理得到的SDP。这包括SDP在控制中的一些最重要的应用。第二类是核范数最小化问题，这类问题对于凸约束矩阵的最小秩NP-Hard问题来说是很重要的凸启发式问题。作为大规模核范数优化的一种应用，我们打算开发基于凸优化的新的系统辨识方法。智能优点SDP包遵循线性规划的成功模型，利用稀疏性。这种方法在半定编程中不太成功，原因有两个。首先，利用SDP中的稀疏性的技术远不如线性规划有效。其次，将稠密结构的SDP问题转化为稀疏问题通常需要辅助矩阵变量和约束，这大大增加了问题的维度。因此，开发新的开发结构的策略是至关重要的，这些策略不仅基于稀疏性，而且纳入了来自系统理论的特定领域的知识。Broader Impact基于研究成果的软件将免费提供。这将有助于更广泛地采用半定程序设计，特别是在系统识别领域。研究结果将被整合到加州大学洛杉矶分校电机系的毕业生优化序列中。我们还计划与加州大学洛杉矶分校工程与多样性卓越中心合作，通过个人学习课程和暑期实习提供本科生研究机会。

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.