Primal Barrier Methods for Linear Programming
STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB
Pagination or Media Count:
The linear program min c sub t sub x subject to Axb, x or 0, is solved by the projected Newton barrier method. The method consists of solving a sequence of subproblems of the form min c sub t sub x - micron sigma Ln x subject to Axb. Extentions for upper bounds, free and fixed variables are given. A linear modification is made to the logarithmic barrier function, which results in the solution being bounded in all cases. It also facilitates the provision of a good starting point. The solution of each subproblem involves repeatedly computing a search direction and taking a step along this direction. Ways to find an initial feasible solution, step sizes and convergence criteria are discussed. Like other interior-point method for linear programming, this method solves a system of the form AH 1AH A sub t sub q y, where H is diagonal. This system can be very ill-conditioned and special precautions must be taken for the Cholesky factorization. The matrix A is assumed to be large and sparse. Data structures and algorithms for the sparse factorization are explained. In particular, the consequences of relatively dense columns in A are investigated and a Schur-complement method is introduced to maintain the speed of the method in these cases. An implementation of the method was developed as part of the research. Results of extensive testing with medium to large problems are presented and the testing methodologies used are discussed.
- Operations Research