PATH-FOLLOWING METHODS FOR LINEAR PROGRAMMING
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,