Error bounds for strongly convex programs and (super)linearly convergent iterative schemes for the least 2-norm solution of linear programs

Given an arbitrary point (x, u) in Rn× R+m, we give bounds on the Euclidean distance between x and the unique solution {Mathematical expression} to a strongly convex program in terms of the violations of the Karush-Kuhn-Tucker conditions by the arbitrary point (x, u). These bounds are then used to derive linearly and superlinearly convergent iterative schemes for obtaining the unique least 2-norm solution of a linear program. These schemes can be used effectively in conjunction with the successive overrelaxation (SOR) methods for solving very large sparse linear programs. © 1988 Springer-Verlag New York Inc