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

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

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.