Linear optimization over homogeneous matrix cones

DOI10.1017/S0962492922000113MaRDI QIDQ6047504zbMATH OpenOpenAlexFDO

Authors Levent Tunçel, Lieven Vandenberghe

Publication date 12 September 2023

Published in Acta Numerica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2211.00761

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Interior-point methods (90C51) Semidefinite programming (90C22) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Positive matrices and their generalizations; cones of matrices (15B48) Numerical analysis (65-XX)

Abstract: A convex cone is homogeneous if its automorphism group acts transitively on the interior of the cone, i.e., for every pair of points in the interior of the cone, there exists a cone automorphism that maps one point to the other. Cones that are homogeneous and self-dual are called symmetric. The symmetric cones include the positive semidefinite matrix cone and the second order cone as important practical examples. In this paper, we consider the less well-studied conic optimization problems over cones that are homogeneous but not necessarily self-dual. We start with cones of positive semidefinite symmetric matrices with a given sparsity pattern. Homogeneous cones in this class are characterized by nested block-arrow sparsity patterns, a subset of the chordal sparsity patterns. We describe transitive subsets of the automorphism groups of the cones and their duals, and important properties of the composition of log-det barrier functions with the automorphisms in this set. Next, we consider extensions to linear slices of the positive semidefinite cone, i.e., intersection of the positive semidefinite cone with a linear subspace, and review conditions that make the cone homogeneous. In the third part of the paper we give a high-level overview of the classical algebraic theory of homogeneous cones due to Vinberg and Rothaus. A fundamental consequence of this theory is that every homogeneous cone admits a spectrahedral (linear matrix inequality) representation. We conclude by discussing the role of homogeneous cone structure in primal-dual symmetric interior-point methods.

Cites work

• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 108354 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1489808 (Why is no real title available?)
• scientific article; zbMATH DE number 1737519 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 802837 (Why is no real title available?)
• scientific article; zbMATH DE number 852536 (Why is no real title available?)
• scientific article; zbMATH DE number 3225176 (Why is no real title available?)
• scientific article; zbMATH DE number 3355265 (Why is no real title available?)
• A T-Algebraic Approach to Primal-Dual Interior-Point Algorithms
• A Note on "The Comparability Graph of a Tree"
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• A Polynomial Primal-Dual Dikin-Type Algorithm for Linear Programming
• A good submatrix is hard to find
• A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
• A mathematical view of interior-point methods in convex optimization
• A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization
• A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• Advances in convex optimization: conic programming
• Alfonso: Matlab Package for Nonsymmetric Conic Optimization
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Barrier Functions in Interior Point Methods
• CVXPY: a Python-embedded modeling language for convex optimization
• Characterization of the barrier parameter of homogeneous convex cones
• Collinear scaling and sequential estimation in sparse optimization algorithms
• Computing the Minimum Fill-In is NP-Complete
• Convex Analysis
• Correction to 'The construction of homogeneous convex cones'
• Decomposition of arrow type positive semidefinite matrices with application to topology optimization
• Direct methods for sparse matrices
• Estimation of a covariance matrix with zeros
• Existence and uniqueness of solutions for homogeneous cone complementarity problems
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Extension of the Olkin and Rubin characterization to the Wishart distribution on homogeneous cones
• Generalization of primal-dual interior-point methods to convex optimization problems in conic form
• Geometry of homogeneous convex cones, duality mapping, and optimal self-concordant barriers
• Graph-Theoretic Concepts in Computer Science
• Graphical methods for efficient likelihood inference in Gaussian covariance models
• Hyperbolic Polynomials and Interior Point Methods for Convex Programming
• Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones
• Incidence matrices and interval graphs
• Interior-point methods for optimization
• Invariance and efficiency of convex representations
• Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition
• Largest dual ellipsoids inscribed in dual cones
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Lifts of Convex Sets and Cone Factorizations
• Linear matrix inequality representation of sets
• Local Superlinear Convergence of Polynomial-Time Interior-Point Methods for Hyperbolicity Cone Optimization Problems
• Logarithmic barriers for sparse matrix cones
• Long-step path-following algorithm for quantum information theory: some numerical aspects and applications
• Matrix realization of a homogeneous cone
• On Finding Supernodes for Sparse Matrix Computations
• On Nesterov's approach to semi-infinite programming
• On self-concordant barriers for generalized power cones
• On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
• On the existence of convex decompositions of partially separable functions
• Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
• Parabolic target space and primal-dual interior-point methods
• Positive definite completions of partial Hermitian matrices
• Positive semidefinite matrices with a given sparsity pattern
• Primal-Dual Interior-Point Methods for Self-Scaled Cones
• Primal-dual interior-point methods for domain-driven formulations
• Primal-dual symmetry and scale invariance of interior-point algorithms for convex optimization
• Quasi-threshold graphs
• Realization of homogeneous cones through oriented graphs
• Relating Homogeneous Cones and Positive Definite Cones via T-Algebras
• Robust Solutions to Least-Squares Problems with Uncertain Data
• Robust optimization
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
• Semidefinite characterization of sum-of-squares cones in algebras
• Semidefinite representation of convex sets
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
• Sparse matrix decompositions and graph characterizations
• Spectrahedral shadows
• Symmetric primal-dual path-following algorithms for semidefinite programming
• The Comparability Graph of a Tree
• The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• The Role of Elimination Trees in Sparse Factorization
• The complexity of some edge deletion problems
• The construction of homogeneous convex cones
• The construction of homogeneous convex cones
• Towards non-symmetric conic optimization
• Trivially perfect graphs
• Wishart distributions for decomposable covariance graph models
• Wishart distributions for decomposable graphs
• Wishart distributions on homogeneous cones

Cited in

(2)

• Orthogonalizing linear operators in convex programming. I, II
• Minimal hyperbolic polynomials and ranks of homogeneous cones

This page was built for publication: Linear optimization over homogeneous matrix cones

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6047504)