Gondzio, Jacek

Hall, Julian

Schork, Lukas Marius

2019-07-02T12:28:19Z

2019-07-02T12:28:19Z

2019-07-01

Solving normal equations AAᵀx = b, where A is an m x n matrix, is a common task in numerical optimization. For the efficient use of iterative methods, this thesis studies the class of preconditioners of the form BBᵀ , where B is a nonsingular "basis" matrix composed of m columns of A. It is known that for any matrix A of full row rank B can be chosen so that the entries in [B⁻¹A] are bounded by 1. Such a basis is said to have "maximum volume" and its preconditioner bounds the spectrum of the transformed normal matrix in the interval [1, 1+mn]. The theory is extended to (numerically) rank deficient matrices, yielding a rank revealing variant of Gaussian elimination and a method for computing the minimum norm solution for x from a reduced normal system and a low-rank update. Algorithms for finding a maximum volume basis are discussed. In the linear programming interior point method a sequence of normal equations needs to be solved, in which A changes by a column scaling from one system to the next. A heuristical algorithm is proposed for maintaining a basis of approximate maximum volume by update operations as those in the revised simplex method. Empirical results demonstrate that the approximation means no loss in the effectiveness of the preconditioner, but makes basis selection much more efficient. The implementation of an interior point solver based on the new linear algebra is described. Features of the code include the elimination of free variables during preconditioning and the removal of degenerate variables from the optimization process once sufficiently close to a bound. A crossover method recovers a vertex solution to the linear program, starting from the basis at the end of the interior point solve. A computational study shows that the implementation is robust and of general applicability, and that its average performance is comparable to that of state-of-the-art solvers.

http://hdl.handle.net/1842/35682

en

The University of Edinburgh

L. Schork and J. Gondzio. An inexact potential reduction method for linear programming. Technical Report ERGO-16-005, University of Edinburgh, 2016.

L. Schork and J. Gondzio. Maintaining a basis matrix in the linear programming interior point method. Technical Report ERGO-17-009, University of Edinburgh, 2017.

L. Schork and J. Gondzio. Permuting spiked matrices to triangular form and its application to the Forrest-Tomlin update. Technical Report ERGO-17-002, University of Edinburgh, 2017.

L. Schork and J. Gondzio. Implementation of an interior point method with basis preconditioning. Technical Report ERGO-18-014, University of Edinburgh, 2018.

L. Schork and J. Gondzio. Rank revealing Gaussian elimination by the maximum volume concept. Technical Report ERGO-18-002, School of Mathematics, University of Edinburgh, 2018.

preconditioners

nonsingular basis matrix

rank deficient matrices

linear programming interior point

interior point solver

Basis preconditioning in interior point methods

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy