Groupe d’études et de recherche en analyse des décisions

G-2010-20

A Short Proof on the Cardinality of Maximal Positive Bases

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.

, 9 pages