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

Eugene Yang, Chia-hsiang ChouTamkang 1994 · DOI

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.

The bordered angular structure of the normal equation matrix S, typical in large-scale linear programs.

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.

Numerical results for Hilbert matrices (n=15, n=20). The diagonal elements $d_i$ closely track the eigenvalues $\lambda_i$, demonstrating the algorithm's rank-revealing capability.

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

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. 
 
 
BibTeX
@inproceedings{yang1994method,
  author = {Eugene Yang and CHIA-HSIANG CHOU},
  title = {{A METHOD FOR SOLVING LEAST-SQUARES PROBLEMS ARISING FROM ANGULAR LINEAR PROGRAMS}},
  booktitle = {Tamkang},
  year = {1994},
  doi = {10.5556/j.tkjm.25.1994.4419},
}
Figure