Prior reduced fill-in in solving equations in interior point algorithms

Prior reduced fill-in in solving equations in interior point algorithms

0.00 Avg rating0 Votes
Article ID: iaor1993738
Country: Netherlands
Volume: 11
Issue: 4
Start Page Number: 195
End Page Number: 198
Publication Date: May 1992
Journal: Operations Research Letters
Authors: , ,
Keywords: interior point methods
Abstract:

The efficiency of interior-point algorithms for linear programming is related to the effort required to factorize the matrix used to solve for the search direction at each iteration. When the linear program is in symmetric form (i.e., the constraints are Ax•b, x≥0), then there are two mathematically equivalent forms of the search direction, involving different matrices. One form necessitates factoring a matrix whose sparsity pattern has the same form as that of (AAT). The other form necessitates factoring a matrix whose sparsity pattern has the same form as that of (ATA). Depending on the structure of the matrix A, one of these two forms may produce significantly less fill-in than the other. Furthermore, by analyzing the fill-in of both forms prior to starting the iterative phase of the algorithm, the form with the least fill-in can be computed and used throughout the algorithm. Finally, this methodology can be applied to linear programs that are not in symmetric form, that contain both equality and inequality constraints.

Reviews

Required fields are marked *. Your email address will not be published.