A Numerically Stable Reduced-gradient Type Algorithm For Solving Large-scale Linearly Constrained Minimization Problems

In this paper we present a reduced-gradient type algorithm for solving large-scale linearly constrained minimization problems. During each iteration of the algorithm linear systems are solved using a preconditioned conjugate-gradient scheme. The preconditioning scheme uses orthogonal transformations, thus providing numerical stability. The total storage used by the algorithm may be predicted before beginning the calculations. We present some numerical experiments which confirm the reliability of the algorithm. © 1991.1811731Murtagh, Saunders, Large-scale linearly constrained optimization (1978) Mathl Program, 14, pp. 41-72Murtagh, Saunders, (1977) MINOS user's guide. Technical Report, , 2nd edn., Dept of Operations Research, Stanford Univ, CalifBartels, A stabilization of the simplex method (1971) Num. Math., 16, pp. 414-434Bartels, Golub, The simplex method using LU decomposition (1969) Communications of the ACM, 12, pp. 266-268Bartels, Golub, Saunders, Numerical techniques in mathematical programming (1970) Nonlinear Programming, pp. 123-176. , J.B. Rosen, O.L. Mangasarian, K. Ritter, Academic Press, New YorkReid, A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming basis (1975) Report CSS 20, , 2nd edn., AERE, HarwellM. Saunders, A fast stable implementation of the simplex method using Bartels-Golub updating. In Sparse Matrix Computations (Edited by J. Bunch and D. Rose), pp. 213–226. Academic Press, New YorkFourer, Staircase matrices and systems (1984) SIAM Rev., 26, pp. 1-70Friedlander, Lyra, Tavares, Medina, Optimization with staircase structure: an application to generation scheduling (1990) Computers Ops Res., 17, pp. 143-152Amaral, Lopes, Martinez, Taube, A numerically stable multiblending system for microcomputers (1987) Contributed paper at SIAM Conf. on Optimization, , Houston, TexGill, Murray, Wright, (1981) Practical Optimization, , Academic Press, New YorkGentleman, Least squares computations by Givens transformations without square roots (1973) J. Inst. Math. Applic., 12, pp. 329-336George, Heath, Solution of sparse linear least squares using Givens rotations (1980) Linear Algebra Applic., 34, pp. 69-83Axelsson, Lindskog, On the rate of convergence of the preconditioned conjugate gradient method (1986) Num. Math., 48, pp. 479-498Martinez, An algorithm for solving sparse nonlinear least squares problems (1987) Computing, 39, pp. 307-325Bertsekas, Projected newton methods for optimization problems with simple constraints (1982) SIAM Journal on Control and Optimization, 20, pp. 221-246Fletcher, (1987) Practical Methods in Optimization, , 2nd edn., Wiley, New YorkLuenberger, (1984) Linear and Nonlinear Programming, , 2nd edn., Addison-Wesley, Reading, MassO'Leary, A generalized conjugate gradient algorithm for solving a class of quadratic programming problems (1980) Linear Algebra Applic., 34, pp. 371-399Jacobson, Oksman, An algorithm that minimizes homogeneous functions of N variables in N + 2 iterations and rapidly minimizes general functions (1972) J. Math. Analysis Applic., 38, pp. 535-552Kowalik, Ramakrishman, A numerically stable optimization method based on an homogeneous functions (1976) Mathl Program, 11, pp. 50-66Schnabel, Ta-Tung, Tensor methods for unconstrained optimization (1987) Contributed paper at SIAM Conf. on Optimization, , Houston, TexGill, Murray, Saunders, Tomlin, Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method (1985) Report SOL 85-11, , 3rd edn., Systems Optimization Lab., Dept of Operations Research, Stanford Univ, CalifGonzaga, (1989) Algoritmos de Pantos Interiores Para Programação Linear, , CNPq, BrazilBertocchi, Spedicato, Computational experiments with conjugate gradient algorithms (1979) Calcolo, 15, pp. 255-269Bjorck, Methods for sparse linear least squares problems (1976) Sparse Matrix Computations, pp. 177-199. , J.R. Bunch, D.J. Rose, Academic Press, New YorkHestenes, (1980) Conjugate Direction Methods in Optimization, , Springer, New YorkHestenes, Stiefel, Methods of conjugate gradients for solving linear systems (1952) Journal of Research of the National Bureau of Standards, 49, pp. 409-436Paige, Saunders, LSQR an algorithm for sparse linear equations and sparse least squares (1982) ACM Transactions on Mathematical Software, 8, pp. 43-72Fletcher, Reeves, Function minimization by conjugate gradients (1964) The Computer Journal, 2, pp. 149-15