تقرير
Linear optimization over homogeneous matrix cones
| العنوان: | Linear optimization over homogeneous matrix cones |
|---|---|
| المؤلفون: | Tunçel, Levent, Vandenberghe, Lieven |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Optimization and Control, Mathematics - Numerical Analysis, 90C25 (Primary) 15B48, 65K05, 90C22 (Secondary) |
| الوصف: | 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. Comment: 59 pages, 10 figures, to appear in Acta Numerica |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2211.00761 |
| رقم الأكسشن: | edsarx.2211.00761 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |