A METHOD FOR SOLVING LEAST-SQUARES PROBLEMS ARISING FROM ANGULAR LINEAR PROGRAMS

Main Article Content

EUGENE K. YANG
CHIA-HSIANG CHOU

Abstract




The most costly part of interior point methods for solving linear pro- gramming prbblems is in solving least squares subproblems. If the normal equation matrix of a least-squares problem is not nearly singular, it is well known that LDU decomposition is a stable method. However, for the nearly singular case, it can cause numerical difficulties. In this paper, we consider the linear proogram whose constraint matrix $B$ is large, sparse, and with angular structure. We assume that the normal equation matrices arising from such a linear program may be nearly singular. We present a numerically stable block method utilizing LDU decom- position wit5 diagonal pivoting for solving such normal equations. Although the method of the diagonal pivoting is old, this paper presents new results when the method is applied to the positive definite but nearly singular case.




Article Details

How to Cite
YANG, E. K., & CHOU, C.-H. (1994). A METHOD FOR SOLVING LEAST-SQUARES PROBLEMS ARISING FROM ANGULAR LINEAR PROGRAMS. Tamkang Journal of Mathematics, 25(1), 1–13. https://doi.org/10.5556/j.tkjm.25.1994.4419
Section
Papers

References

J. R. Bunch, "Analysis of the diagonal pivoting method", SIAM J. Numer. Anal. 8 (1971), 656-680.

J. R. Bunch and IL.Kaufman, "Some stable methods for calculating inertia and solving symmetric linear systems", Mathematics of Computation 31, No. 137 (1977), 163-179.

J. R. Bunch and B. N. Parlett, "Direct methods for solving symmetric indefinite systems of linear equations", SIAM J. Numer. Anal. 8, No. 4 (1971), 639-655.

T. F. Chan, "On the existence and computation of LU-factorizations with small pivots", Mathematics of Computation 42 (1984), 535-547.

P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin and M. H. Wright, "On projective Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method", Mathematical Programming, 36 (1986), 183-209.

G. H. Golub and G. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, MD (1983).

J. N. Hooker, "Karmarkar's linear programming algorithm", Interfaces 16 (1986), 75-90.

B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall Press (1980).

J. B. Rosen and Robert S. Maier, "Parallel solution of large-scale, block angular linear program", Annals of Operations Research 22 (1990}, 23-41.

J. A. Tomlin, "A note on comparing simplex and interior methods for linear programming", in Progress in Mathematical Programming (N. Megiddo ed.), Spbing-Verlag, New York (1989), 91-103. I

J. H. Wilkinson, Agebraic Eigenvalue Problem, Clarendon Press, Oxford (1965).