An Accelerated Successive Orthogonal Projections Method For Solving Large-scale Linear Feasibility Problems

We consider linear feasibility problems in the "standard" form Ax = b, 1 ≤ x ≤ u. The successive orthogonal projections method may be used for solving this problem using sparse orthogonal factorizations techniques for computing the projections on Ax = b. We introduce an acceleration technique in order to speed up the (generally slow) convergence of the method. We present some numerical experiments. © 1988.155367373Gill, Murray, Wright, (1981) Practical Optimization, , Academic Press, New YorkLuenberger, (1984) Linear and Nonlinear Programming, , Addison-Wesley, Reading, MABartels, Golub, The simplex method of linear programming using LU decomposition (1969) Communications of the ACM, 12, pp. 266-268Dantzig, (1963) Linear Programming and Extensions, , Princeton University Press, Princeton, NJBregman, The relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming (1967) U.S.S.R. comp. Math. math. Phys., 7, pp. 200-217Brocklehurst, Dennis, A comparison of six algorithms for dense linear programs (1974) NPL Report NAC 51Censor, Finite series expansion reconstruction methods (1983) Proc. IEEE, 71, pp. 409-419Censor, Herman, On some optimization techniques in image reconstruction from projections (1986) Medical Image Processing Group Technical Report No. MIPG107, , Department of Radiology, University of PennsylvaniaDe Pierro, Iusem, A simultaneous projection method for linear inequalities (1985) Linear Algebra Applic., 64, pp. 243-253Gordon, Bender, Herman, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography (1970) J. theor. Biol., 29, pp. 471-481Herman, (1980) Image Reconstruction from Projections: The Fundamentals of Computerized Tomography, , Academic Press, New YorkKaczmarz, Angenaerte Auflösung von Systemen linearer Gleichungen (1937) Bull. Acad. Polon. Sci. Lett., 35 A, pp. 355-357Spingarn, A primal-dual projections method for solving systems of linear inequalities (1985) Linear Algebra Applic., 65, pp. 45-62Censor, Row-action methods for huge and sparse systems and their applications (1981) SIAM Review, 23, pp. 444-466Garcia-Palomares, Q-relaxation method for solving a system of linear inequalities (1983) TM No. 19, , Mathematics and Computed Science Division, Argonne National Laboratory, ILMartínez, The projection method for solving nonlinear systems of equations under the most violated constraint condition control (1985) Computers & Mathematics with Applications, 11, pp. 987-993Martínez, Solution of nonlinear systems of equations by an optimal projection method (1986) Computing, 37, pp. 59-70Martínez, Solving systems of nonlinear equations by means of an accelerated successive orthonormal projections method (1986) J. Comput. appl. Math., 16, pp. 169-179Martínez, Sampaio, Parallel and sequential Kaczmarz methods for solving underdetermined nonlinear equations (1986) Journal of Computational and Applied Mathematics, 15, pp. 169-179Meyn, Solution of underdetermined nonlinear equations by stationary iteration methods (1983) Numer. Math., 42, pp. 161-172Wainwright, Four-dimensional x-projection method (with acceleration techniques) for solving systems of linear equations (1982) Comput. Math. Applic., 8, pp. 329-337Moretti, Aplicação do método de projeções ortogonais sucessivas a um problema de controle. Tese de Mestrado (1985) IMECC-UNICAMPColeman, (1984) Large Sparse Numerical Optimization. Lecture Notes in Computer Science, 165. , Springer, BerlinGeorge, Heath, Solution of sparse linear least squares using Givens rotations (1980) Linear Algebra Applic., 34, pp. 69-83George, Heath, Ng, A comparison of some methods for solving sparse least squares problems (1983) SIAM Journal on Scientific and Statistical Computing, 4, pp. 177-187Heath, Numerical methods for large sparse linear least squares problem (1984) SIAM Journal on Scientific and Statistical Computing, 5, pp. 497-513Karmarkar, A new polynomial-time algorithm for linear programming (1984) Combinatorica, 4, pp. 373-395Lustig, A practical approach to Karmarkar's algorithm (1985) TR SOL 85-5, , Department of Operations Research, Stanford University, CAGubin, Polyak, Raik, The method of projections for finding the common point of convex sets (1967) U.S.S.R. comp. Math. math. Phys., 7, pp. 1-24Gastinel, (1970) Linear Numerical Analysis, , Hermann, ParisFriedlander, Otimization com estrutura escada nas restrições. Tese de Doutorado (1986) FEE UNICAMPMurtagh, Saunders, Large scale linearly constrained optimization (1978) Mathematical Programming, 14, pp. 22-41Murtagh, Saunders, MINOS: a large-scale nonlinear programming system (for problems with linear constraints) (1977) TR SOL 77-9, , Department of Operations Research, Stanford University, C