A primal null-space affine-scaling method

ABSTRACT

This article develops an affine-scaling method for linear programming in standard primal form. Its descent search directions are formulated in terms of the null-space of the linear programming matrix, which, in turn, is defined by a suitable basis matrix. We describe some basic properties of the method and an experimental implementation that employs a periodic basis change strategy in conjunction with inexact computation of the search direction by an iterative method, specifically, the conjugate-gradient method with diagonal preconditioning. The result of a numerical study on a number of nontrivial problems representative of problems that arise in practice are reported and discussed.A key advantage of the primal null-space affine-scaling method is its compatibility with the primal simplex method. This is considered in the concluding section, along with implications for the development of a more practical implementation.

REFERENCES

• 1: ADLER, I., KARMARKAR, N., RESENDE, M. G. C., AND VEIGA, G. 1986. An implementation of Karmarkar's algorithm for linear programming. Math. Program. 44, 297-336.
• 2: Earl R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Mathematical Programming: Series A and B, v.36 n.2, p.174-182, Nov. 1986 [doi>10.1007/BF02592024]
• 3: DANTZIG, G. B. 1963. Linear Programming and Extensions. Princeton University Press, Princeton, N.J.
• 4: DANTZIG, G. B., AND YE, Y. 1990. A build-up interior method for linear programming: Affine scaling form. Tech. Rep. SOL 90-4, Systems Optimization Lab., Stanford Univ., Stanford, Calif.
• 5: DEMBO, R., AND SAHI, S. 1984. A convergent framework for constrained nonlinear optimization. School of Organization and Management Working Paper, Series B #69, Yale Univ., New Haven, Conn.
• 6: DIKIN, I. I. 1967. Iterative solution of problems of linear and quadratic programming. Soy. Math. Doklady 8, 674-675.
• 7: GAY, D. M. 1986. Electronic mail distribution of linear programming test problems. Numerical Analysis Manuscript 86-0, AT & T Bell Laboratories, Murray Hill, N.J.
• 8: Philip E. Gill , Walter Murray , Dulce B. Ponceleón , Michael A. Saunders, Preconditioners for indefinite systems arising in optimization, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.292-311, Jan. 1992 [doi>10.1137/0613022]
• 9: GILL, P. E., MURRAY, W., SAUNDERS, M. A., AND WRIGHT, M. H. 1987. Maintaining LU factors of a general sparse matrix. Lin. Alg. Appl. 88/89, 239-270.
• 10: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 11: Koonchan Kim , John L. Nazareth, The effective integration of simplex and interior point techniques. part i. decomposition. part ii. null-space affine scaling, 1991
• 12: KIM, K., AND NAZARETH, J. L. 1992. Implementation of a primal null-space affine scaling method and its extensions. Tech. Rep. 92-1, Washington State Univ., Pullman, Wash.
• 13: LUSTIG, I. J., MARSTEN, R. E., AND SHANNO, D. F. 1992. Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming. Tech. Rep. SOR 92-10, Dept. of Civil Engineering and Operations Research, Princeton Univ., Princeton, N.J.
• 14: N. Megiddo, Pathways to the optimal set in linear programming, on Progress in Mathematical Programming: Interior-Point and Related Methods, p.131-158, September 1989, Pacific Grove, California, United States
• 15: MEHROTRA, S. 1989. Implementations of affine scaling methods: Approximate solutions of systems of linear equations using preconditioned conjugate-gradient methods. Tech. Rep. 89-04, Dept. of IEMS, Northwestern Umv., Evanston, Ill.
• 16: MURTAGH, B. A., AND SAUNDERS, M. A. 1983. MINOS user's guide. Tech. Rep. SOL 83-20, Stanford Optimization Lab., Stanford, Calif.
• 17: NAZARETH, J. L. 1993. Quadratic and conic approximating models in linear programming. MPS-COAL Bull. 23 (Dec.).
• 18: J. L. Nazareth, Computer solution of linear programs, Oxford University Press, Inc., New York, NY, 1987
• 19: J. L. Nazareth, Pricing criteria in linear programming, Progress in Mathematical Programming Interior-point and related methods, Springer-Verlag New York, Inc., New York, NY, 1988
• 20: J. L. Nazareth, Implementation aids for optimization algorithms that solve sequences of linear programs, ACM Transactions on Mathematical Software (TOMS), v.12 n.4, p.307-323, Dec. 1986 [doi>10.1145/22721.22959]
• 21: NAZARETH, J. L. 1985. Hierarchical implementation of optimization methods. In Numerical Optimizatio,. SIAM, Philadelphia, Penn., 199 210.
• 22: RErD, J. K. 1976. Fortran subroutines for handling sparse linear programming bases. A.E.R.E.- R.8269, Computer Science and Systems Div., AERE Harwell, Oxfordshlre, U.K.
• 23: D. F. Shanno , R. E. Marsten, A reduced-gradient variant of Karmarkar's algorithm and null-space projections, Journal of Optimization Theory and Applications, v.57 n.3, p.383-397, June 1988 [doi>10.1007/BF02346159]
• 24: STEWART, G. W. 1988. On scaled projections and pseudo-inverses. Computer Science Tech. Rep. Series, TR-2026, Univ. of Maryland, College Park, Md.
• 25: TSENG, P. 1992. Partial affine-sca|ing for linearly constrained minimization. Dept. of Mathematics, Univ of Washington, Seattle (preprint).
• 26: VANDERBEI, R. J., MEKETON, M. S., AND FREEDMAN, B~ A. 1986. A modification of Karmarkar's algorithm. Algorlthmlca 1,395 409.
• 27: Y. Ye, A "build-down" scheme for linear programming, Mathematical Programming: Series A and B, v.46 n.1, p.61-72, Jan. 1990 [doi>10.1007/BF01585727]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms

Keywords:
conjugate gradients, diagonal preconditioning, interior-point algorithm, null-space affine scaling, primal method