Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5773145 | Linear Algebra and its Applications | 2017 | 18 Pages |
Abstract
The Carathéodory number κ(K) of a pointed closed convex cone K is the minimum among all the κ for which every element of K can be written as a nonnegative linear combination of at most κ elements belonging to extreme rays. Carathéodory's Theorem gives the bound κ(K)â¤dimâ¡K. In this work we observe that this bound can be sharpened to κ(K)â¤âKâ1, where âK is the length of the longest chain of nonempty faces contained in K, thus tying the Carathéodory number with a key quantity that appears in the analysis of facial reduction algorithms. We show that this bound is tight for several families of cones, which include symmetric cones and the so-called smooth cones. We also give a simple example showing that this bound can also fail to be sharp. In addition, we furnish a new proof of a result by Güler and Tunçel which states that the Carathéodory number of a symmetric cone is equal to its rank. Finally, we connect our discussion to the notion of cp-rank for completely positive matrices.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Masaru Ito, Bruno F. Lourenço,