A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm (Q1089251): Difference between revisions

As described by \textit{D. Goldfarb} and \textit{S. Mehrotra} [''A relaxed version of Karmarkar's method'', Tech. Rep., Dept. of Industrial Engineering and Oper. Res., Columbia Univ., New York (1985)] the convergence analysis of Karamarkar's method for linear programming leads naturally to an acceptance criterion when approximate projections are used in the course of the algorithm. Unfortunately, the preliminary results of Golbfarb and Mehrotra indicate that their criterion is generally not strong enough to insure that the algorithm makes reasonable progress. In this note we present a stronger criterion and show that the difference between the two criteria is potentially large.