Projection algorithms for linear programming

Based on the nearest-point projection of geometric convexity the authors give a general projection approach for solving the feasibility problem of linear programming. Application of Shor’s method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact linear search the authors obtain a fast and practically well-behaving algorithm for linear programming.