Abstract
The most costly part of interior point methods for solving linear programming problems 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 program 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 decomposition with 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.
Introduction
Interior point methods are essential for solving large-scale linear programming (LP) problems. However, their performance is often bottlenecked by the need to solve least-squares subproblems, specifically systems of normal equations of the form $BY^2B^tx = BY^2c$. In practical applications such as stochastic programming or multi-period manufacturing, the constraint matrix $B$ often exhibits an angular structure.
This structure consists of several independent blocks tied together by global constraints. While this sparsity is beneficial for efficiency, real-world data is frequently "degenerate," leading to nearly singular matrices that cause standard numerical methods like Cholesky decomposition to fail.
Methodology: Algorithm DP and the Block Method
To address these challenges, the authors propose a two-pronged approach combining a specific factorization technique with a block-matrix strategy.
1. Algorithm DP (Diagonal Pivoting)
The core of the solution is a variant of $LDL^t$ factorization that employs diagonal pivoting. In each step, the algorithm selects the largest diagonal element as the pivot. For Symmetric Positive Semi-Definite (SPSD) matrices, the authors demonstrate that this simple diagonal search provides the same numerical stability as more expensive "complete pivoting" strategies, with an element growth factor of exactly one.
2. The Block Method
By applying Algorithm DP to the bordered angular structure, the method factorizes independent blocks first. This approach reveals the numerical rank of each block and defers "nearly zero" pivots to the end of the process, where they can be handled without compromising the stability of the entire system. Crucially, this method preserves the sparsity of the matrix by avoiding unnecessary "fill-in."
Numerical Performance and Rank Revelation
The algorithm's effectiveness was tested against notoriously ill-conditioned benchmarks, including Hilbert matrices. Unlike standard Cholesky methods, which often produce erroneous negative pivots on such matrices, Algorithm DP successfully identifies the numerical rank.
As shown in the results for Hilbert matrices, the diagonal elements $d_i$ produced by the factorization closely approximate the actual eigenvalues $\lambda_i$. This property allows the solver to accurately identify and manage the "nearly zero" components of nearly singular systems.
Conclusion
The proposed block method with diagonal pivoting offers a robust solution for the least-squares subproblems in angular linear programs. By balancing numerical stability with the preservation of sparse structures, it overcomes the limitations of traditional Cholesky decomposition in the presence of degeneracy. While a trade-off between sparsity and stability remains for general matrices, this specialized approach provides a reliable path forward for large-scale optimization.
Summary updated