Geodesic
On First Experiences with the Implementation of a Newton Based Linear Programming Approach
Séminaire lotharingien de combinatoire, Tome 21 (1989)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

This paper presents the implementation of an exterior point linear programming approach introduced by Betke. In every iteration of this algorithm Newton's method is used in order to determine nearest points of two convex sets. The method is simple to implement, fully exploits sparsity and at the presence of rounding errors it achieves high precision and stability.

Beside the nice geometric proceeding a particular interest in this method is derived from the following observation: In Karmarkar's as well as in this algorithm one has to solve a linear equation system of the form A D2ATy = b. The solution of this system is the most time consuming part in linear programs. While in Karmarkar's method the entries of the diagonal Matrix D are the coordinates of the iteration point, the diagonal entries are either 0 or 1 in our method. Hence throughout this paper D is a purely combinatorial matrix which yields to reasonable numbers of rank one updates of the corresponding Cholesky factor of A D2AT. Moreover, the Cholesky factors become sparser than in Karmarkar's approach.

Math. Inst. der Universit�t zu K�ln 
@article{SLC_1989_21_a6,
     author = {A. Wanka},
     title = {On {First} {Experiences} with the {Implementation} of a {Newton} {Based} {Linear} {Programming} {Approach}},
     journal = {S\'eminaire lotharingien de combinatoire},
     publisher = {mathdoc},
     volume = {21},
     year = {1989},
     url = {http://geodesic.mathdoc.fr/item/SLC_1989_21_a6/}
}
TY  - JOUR
AU  - A. Wanka
TI  - On First Experiences with the Implementation of a Newton Based Linear Programming Approach
JO  - Séminaire lotharingien de combinatoire
PY  - 1989
VL  - 21
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_1989_21_a6/
ID  - SLC_1989_21_a6
ER  - 
%0 Journal Article
%A A. Wanka
%T On First Experiences with the Implementation of a Newton Based Linear Programming Approach
%J Séminaire lotharingien de combinatoire
%D 1989
%V 21
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_1989_21_a6/
%F SLC_1989_21_a6
A. Wanka. On First Experiences with the Implementation of a Newton Based Linear Programming Approach. Séminaire lotharingien de combinatoire, Tome 21 (1989). http://geodesic.mathdoc.fr/item/SLC_1989_21_a6/