PRIMAL-DUAL INTERIOR-POINT ALGORITHMS:

INTRODUCTION Spring 1995 We consider linear programming problems in the following primal (P ) and dual (D) forms: (P ) maximize c T x Ax = b; x 0; (D) minimize b T y A T y \Gamma s = c; s 0; where A 2 IR m\Thetan , b 2 IR m , and c 2 IR n (all vectors are column vectors). Note that we have explicitly included the slack variables s. We will assume rank(A) = m (if not, we can do Gaussian elimination). For now, we will also assume that there exist interior solutions for both problems, i.e. there exist ¯<