Extreme points of well-posed polytopes

Abstract

Given a real matrix, we study the problem of finding a minimal set of columns spanning the convex polytope generated by the columns of the matrix. By considering the matrix as a data instance subject to perturbations, we introduce the notion of ill-posedness of a polytope, in the sense that small perturbations of the matrix might yield matrices with different combinatorial structures. We relate this notion of the ill-posedness to the better-known notion of the ill-posedness of conic homogeneous systems and propose a characterization of the ill-posed matrices. We introduce a new condition measure for a matrix and study the complexity of a solution algorithm in terms of this condition measure. The algorithm has a polynomial bound on the number of iterations to identify a set of columns corresponding to the extreme points of a polytope. The complexity bound depends on the condition measure and the size of the matrix.

Keywords:

• Convex polytopes
• Well-posedness
• Perturbation
• Continuous complexity
• Condition numbers
• Optimization

Keywords:

• AMS 2000 Mathematics Subject Classifications:
• 47A52
• 52B05
• 52B55
• 90C31
• 90C05