Interior-point algorithms for conic optimization with sparse matrix cone constraints

具有稀疏矩阵圆锥约束的圆锥优化的内点算法

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

Conic optimization is an extension of linear programming in which the componentwise vector inequalities are replaced by inequalities with respect to nonpolyhedral convex cones. The conic optimization model is widely used in the recent literature on convex optimization and providesan elegant framework for extending interior-point algorithms from linear programming to convex optimization. It is also the basis of popular modeling systems for convex optimization. The research on algorithms for conic optimization has mainly focused on three types of inequalities, associated with the nonnegative orthant, the second-order cone, and the positive semidefinite cone. This restriction is motivated by symmetry properties that can be exploited to formulate symmetric primal-dual interior-point algorithms.However, large gaps in linear algebra complexity exist between the three types of conic constraints, and this can lead to inefficiencies when convex optimization problems are converted to the standard conic format. This study considers approaches to improve the efficiency of conic optimization solvers by considering a larger class of conic constraints, defined by chordal sparse matrix cones, i.e., cones of positive semidefinite matrices with a given chordal sparsity pattern, and the associated dual cones of chordal sparse matrices that have a positive semidefinite completion. These cones include as special cases the three standard cones, but also several interesting non-self-dual cones. Moreover non-chordal sparsity patterns can often be efficiently embedded in chordal patterns and, as a consequence, sparse semidefinite programs can be solved as non-symmetric cone programs involving lower-dimensional cones than the positive semidefinite cone used in semidefinite programming methods. The choice for chordal matrix cones is further motivated by the existence of fast algorithms for evaluating the associated barrier functions and their derivatives.The investigator and his collaborators study nonsymmetric interior-point algorithms for sparse matrix cones, building on techniques developed for large-scale sparse matrix computations, in particular, multifrontal and supernodal factorization algorithms and parallel sparse matrix algorithms.A wide variety of practical problems in engineering and science can be formulated as nonlinear convex optimization problems, and solved using algorithms developed over the last few decades. The success of these techniques has created a demand for robust and efficient algorithms for very large convex optimization problems, especially for applications in machine learning, computer vision, electronic design automation, sensor networks, and combinatorial optimization. The problem sizes that arise in these fields often exceed the capabilities of general-purpose solvers. The work of the prinicipal investigator with his collaborators considers approaches to improve the scalability of interior-pointalgorithms, an important class of convex optimization algorithms.Freely available high-quality software implementations of the techniques developed in theproject are a product of the research.

二次优化是线性规划的一种扩展，它用关于非多面体凸锥的不等式来代替分量向量不等式。二次优化模型在最近的凸优化文献中得到了广泛的应用，它为将内点算法从线性规划扩展到凸优化提供了一个优雅的框架。它也是流行的凸优化建模系统的基础。圆锥优化算法的研究主要集中在非负正交、二阶锥和正半定锥三种不等式上。这种限制是由对称性质引起的，可以利用对称性来制定对称的原对偶内点算法。然而，三种类型的圆锥约束之间存在线性代数复杂度的巨大差距，这可能导致将凸优化问题转换为标准圆锥格式时效率低下。本研究通过考虑更大的一类由弦稀疏矩阵锥定义的圆锥约束，即具有给定弦稀疏模式的正半定矩阵锥，以及具有正半定补全的弦稀疏矩阵的相关对偶锥，来考虑提高二次优化求解器效率的方法。这些锥体包括作为特例的三个标准锥体，但也包括一些有趣的非自对偶锥体。此外，非弦性稀疏模式通常可以有效地嵌入到弦性模式中，因此，稀疏半确定规划可以求解为非对称锥规划，涉及比半确定规划方法中使用的正半确定锥更低维的锥。弦阵锥的选择进一步受到相关屏障函数及其导数快速计算算法的激励。研究者和他的合作者研究稀疏矩阵锥的非对称内点算法，建立在大规模稀疏矩阵计算技术的基础上，特别是多正面和超节点分解算法以及并行稀疏矩阵算法。工程和科学中的各种各样的实际问题都可以表述为非线性凸优化问题，并使用过去几十年发展起来的算法来解决。这些技术的成功创造了对大型凸优化问题的鲁棒和高效算法的需求，特别是在机器学习，计算机视觉，电子设计自动化，传感器网络和组合优化中的应用。这些领域中出现的问题规模往往超出了通用求解器的能力。首席研究员和他的合作者的工作考虑了提高内点算法（一类重要的凸优化算法）的可扩展性的方法。项目中开发的技术的免费高质量软件实现是研究的产物。