Solving linear programming problem via a reduced dimension method

Motivated by the alternating direction method for variational inequalities, we consider a reduced dimension method in this paper for the solution of linear programming problems. Its main idea is to reformulate the complementary conditions in the primal-dual optimality conditions as a linear projection equation. By using this reformulation, we only need to make one projection and solve a linear system with reduced dimension at each iterate. Under weak conditions, the global convergence is established.