×

An acceleration scheme for solving convex feasibility problems using incomplete projection algorithms. (English) Zbl 1056.65027

An accelerated iterative projection method is presented for solving systems of linear inequalities. This method is an extension of the projection methods for solving systems of linear equations given by H. Scolnik, N. Echebest, M. T. Guardarucci, and M. C. Vacchino [Stud. Comput. Math. 8, 457–471 (2001; Zbl 1003.65027); Ann. Oper. Res. 117, 95–115 (2002; Zbl 1023.65026)]. The general scheme is similar to the incomplete projection algorithm, and therefore it is very convenient for parallel processing. The idea is that at the current iterate the set of violated constraints is splitted into subsets or blocks, in such a way that the required incomplete projection is obtained by combining exact projection onto simple convex sets. The new iterate is defined by the projection of the current iterate onto a separating hyperplane. The advantages of this approach are illustrated both theoretically and numerically.

MSC:

65F10 Iterative numerical methods for linear systems
15A39 Linear inequalities of matrices
65K05 Numerical mathematical programming methods
90C05 Linear programming

Software:

SPARSKIT
Full Text: DOI