Optimization Online


A bound on the Carathéodory number

Masaru Ito (ito.m***at***math.cst.nihon-u.ac.jp)
Bruno F. Lourenco (lourenco***at***st.seikei.ac.jp)

Abstract: 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.

Keywords: caratheodory number, longest chain of faces, symmetric cone, cp-rank

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 07/01/2016
Entry Accepted: 07/01/2016
Entry Last Modified: 07/06/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society