G-2010-20
A Short Proof on the Cardinality of Maximal Positive Bases
BibTeX reference
A positive basis is a minimal set of vectors whose nonnegative linear combinations span the entire space Rn. Interest in positive bases was revived in the late nineties by the introduction and analysis of some classes of direct search optimization algorithms. It is easily shown that the cardinality of every positive basis is bounded below by n+1. There are proofs in the literature that 2n is a valid upper bound for the cardinality, but these proofs are quite technical and require several pages. The purpose of this note is to provide a simple demonstration that relies on a fundamental property of basic feasible solutions in linear programming theory.
Published March 2010 , 9 pages
Research Axis
Publication
Jan 2011
A short proof on the cardinality of maximal positive bases
Optimization Letters, 5(1), 191–194, 2011
BibTeX reference