A bound on the Carathéodory number

The Carathéodory number k(K) of a pointed closed convex cone K is the minimum among all the k for which every element of K can be written as a nonnegative linear combination of at most k elements belonging to extreme rays. Carathéodory's Theorem gives the bound k(K) <= dim (K). In this work we observe that this bound can be sharpened to k(K) <= l-1, where l 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 family of examples 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.

No reviews yet.

No comments yet.