A center of a polytope: An expository review and a parallel implementation

Abstract

The solution space of the rectangular linear system Ax=b, subject to x≥0, is called a polytope. An attempt is made to provide a deeper geometric insight, with numerical examples, into the condensed paper by Lord, et al. [1], that presents an algorithm to compute a center of a polytope. The algorithm is readily adopted for either sequential or parallel computer implementation. The computed center provides an initial feasible solution (interior point) of a linear programming problem.

Keywords

• center of a polytope
• consistency check
• Euclidean distance
• initial feasible solution
• linear programming
• Moore-Penrose inverse
• nonnegative solution
• parallel computation.