Linear optimization over homogeneous matrix cones

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.


arXiv:2211.00761 November 2022



View Linear optimization over homogeneous matrix cones