On theory and practice of row relaxation methods
by
Achiya Dax
Hydrological Service, P.O.Box 6381, Jerusalem 91063, ISRAEL

Row relaxation methods have proven to be a useful tool for handling various types of large sparse problems. This paper presents, analyzes, and tests a row relaxation method for solving the regularized linear programming problem

minimize   1 2 ||x||22+acTx subject to   Ax ³ b,

where a is a given positive constant. The proposed method is based on the observation that the dual of this problem has the form

maximize  bTy- 1 2 ||ATy-ac||22 subject to   y ³ 0,

and if   y_a   solves the dual then the point  \ x_a=A^Ty_a-ac   provides the unique solution of the primal. Maximizing the dual objective function by changing one variable at a time results in an effective row-relaxation method which is suitable for solving large sparse problems. One aim of this paper is to clarify the convergence properties of the proposed scheme. Let   y_k   denote the estimated dual solution at the end of the k-the iteration, and let \ x_k=A^Ty_k-ac   denote the corresponding primal estimate. It is proved that the sequence {x_k} converges to x_a, while the sequence {y_k} converges to a point y_a that solves the dual. The only assumption which is needed in order to establish these claims is that the feasible region is not empty. The rate of convergence at the final stage is determined by the active constraints matrix at x_a.

Yet perhaps the more fascinating features of the algorithm are related to a situation in which it attempts to solve an inconsistent system. It is shown that under certain conditions the sequence {y_k} obeys the rule

yk=uk+kv,

where {u_k} is a converging sequence and v is a fixed vector that satisfies A^Tv =0 and b^Tv > 0. So the sequence {x_k} converges in spite of the inconsistency. The paper ends with numerical experiments that illustrate the effects of this phenomenon and the close links with Kaczmarz's method.

Date received: February 5, 2001