Article ID: | iaor2007398 |
Country: | United Kingdom |
Volume: | 55 |
Issue: | 3 |
Start Page Number: | 269 |
End Page Number: | 288 |
Publication Date: | Jun 2006 |
Journal: | Optimization |
Authors: | Nunez Manuel A. |
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.