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

点击翻译按钮获取中文摘要

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.