Extreme points of well-posed polytopes

Extreme points of well-posed polytopes

0.00 Avg rating0 Votes
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:
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.

Reviews

Required fields are marked *. Your email address will not be published.