Solving reduced KKT systems in barrier methods for linear programming.

*(English)*Zbl 0815.65080
Griffiths, D. F. (ed.) et al., Numerical analysis 1993. Proceedings of the 15th Dundee biennial conference on numerical analysis held at the University of Dundee (United Kingdom), June 29- July 2, 1993. Harlow: Longman Scientific & Technical. Pitman Res. Notes Math. Ser. 303, 89-104 (1994).

Authors’ summary: In barrier methods for constrained optimization, the main work lies in solving large linear systems \(Kp= r\), where \(K\) is symmetric and indefinite. For linear programs, the KKT systems are usually reduced to smaller positive definite systems \(AH^{-1} A^ T y= s\), where \(H\) is a large principal submatrix of \(K\). These systems can be solved more efficiently, but \(AH^{-1} A^ T\) is typically more ill- conditioned than \(K\).

In order to improve the numerical properties of barrier implementations, we discuss the use of “reduced KKT systems”, whose dimension and condition lie somewhere in between those of \(K\) and \(AH^{-1} A^ T\). We have implemented reduced KKT systems in a primal-dual algorithm for linear programming, based on the sparse indefinite solver MA27 from the Harwell subroutine library. Some features of the algorithm are presented, along with results from the netlib LP test set.

For the entire collection see [Zbl 0786.00024].

In order to improve the numerical properties of barrier implementations, we discuss the use of “reduced KKT systems”, whose dimension and condition lie somewhere in between those of \(K\) and \(AH^{-1} A^ T\). We have implemented reduced KKT systems in a primal-dual algorithm for linear programming, based on the sparse indefinite solver MA27 from the Harwell subroutine library. Some features of the algorithm are presented, along with results from the netlib LP test set.

For the entire collection see [Zbl 0786.00024].

Reviewer: H.Hollatz (Magdeburg)

##### Keywords:

Kurish-Kuhn-Tucker system; barrier methods; constrained optimization; reduced KKT systems; primal-dual algorithm; linear programming; Harwell subroutine library
PDF
BibTeX
XML
Cite

\textit{P. E. Gill} et al., in: Numerical analysis 1993. Proceedings of the 15th Dundee biennial conference on numerical analysis held at the University of Dundee (United Kingdom), June 29- July 2, 1993. Harlow: Longman Scientific \& Technical; New York: John Wiley \& Sons, Inc.. 89--104 (1994; Zbl 0815.65080)