Remedying Normal-Equations Failures in Interior-Point Algorithms for LP

Karmarkar's 1984 paper [3] has kindled considerable interest in interior-point algorithms for linear programming (LP). Such algorithms produce sequences of iterates whose objective function values get 'close' to optimal after a few iterations. Often they get close enough that one can compute an optimal pair of primal and dual solutions with relatively little extra work, even when one uses the normal equations. Sometimes, though, the linear systems become sufficiently ill-conditioned that one cannot progress further with the normal equations. We consider two better-conditioned options in the context of dual affine or dual projective variants of Karmarkar's LP algorithm: use of LSQR and of the 'augmented system'.