PATH-FOLLOWING METHODS FOR LINEAR PROGRAMMING

No Thumbnail Available
Date
1999-04
Authors
QUABILI, MUHAMMAD MASUDUR RAHMAN
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this thesis a unified treatment of various Path - following methods for linear programming is presented. A modification based on "Specifiic Most Violated Constraints" in Pivot and Probe Algorithm (PAPA) is introduced which ensures early termination of the algorithm. While comparing the Ellipsoid method with Karmarkar's algorirthm it has been shown that the hearts of these two algorithms depend on the solution of weighted least squares subproblems and these subproblems are closely related. Some results related to the volume reduction inequality for the ellipsoid method and convergence inequality for Karmarkar's algorithm have also been obtained. Various types of parameterization of central trajectory and proximity measures have been critically examined. As a result some inequalities which ensures faster convergence in Primal - Dual interior point path - following methods have been obtained.
Description
A thesis submitted to the post-graduate School, Ahmadu Bello University, Zaria, Nigeria, in partial fulfilment of the Requirements for the Degree of DOCTOR OF PHILOSOPHY (MATHEMATICS)
Keywords
PATH-FOLLOWING METHODS,, LINEAR PROGRAMMING,
Citation
Collections