Some Remarks on Projective Algorithm in Linear Optimization Graduate Seminar Report
No Thumbnail Available
Date
2003-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
Although the ongm of the linear optimization as a
mathematical discipline is quite recent, it is now well established
as an important and very active branch of applied mathematics.
The wide applicability of linear optimization models and the rich
mathematical theory underlying these models and the methods
developed to solve them have been the driving forces behind the
rapid and continuing evolution of the subject. The recognition of
the importance of linear optimization models, especially in the
areas of economic analysis and planning, coincide with the
development of both an effective method, the 'simplex method' of G.
B. Dantzig, for solving linear optimization problems, and a means,
the digital computer, for doing so.
All forms of the simplex algorithm reach the optimum by
transversing a series of basic solutions. Since each basic solution
represents an extreme point of the feasible region, the track
followed by the algorithm moves around the boundary of the
feasible region. In the worst case, it may be necessary to examine
most of, if not all, the extreme points. The worst case here just
simply means a worst possible data configuration that would take
the simplex algorithm run many steps. This can be cripplingly
inefficient given that the number of extreme points grows
exponentially with n for fixed m.
The existence of such worst cases suggests that one should
look possibly for algorithms other than the simplex algorithms,
which are good in such cases.
The first success was attributed to the Russian
mathematician, Khachian (1979), who proposed the ellipsoid
algorithm or sometimes the Russian Method. Though theoretically
efficient, code developers were never able to realize an
implementation that matched the performance of concurrent
simplex codes.
Just about the time when the interest in the ellipsoid method
was waning, a new technique to solve linear optimization problems
was proposed by N. K. Karmarkar (1984) of AT & T Bell
Laboratories, namely, the projective algorithm or more generally
interior point algorithm
Contrary to the simplex algorithm, the projective algorithm
moves in the relative interior rather than on the outside of the
polyhedron in the n - dimensional space.
The purpose of this paper is to describe the development of this
new algorithm and the idea (coming from non-linear optimization
and projective geometry) on which it is based. Here we present the
original algorithm, which is the approximation to the underlying
algorithmic idea because of linearization of what is inherently a
non-linear problem due to a projective transformation.
I want to express my deepest gratitude to my adviser Prof. Dr.
rer. nat. habil. R. Deumlich who cultivated me highly not only
academically but also socially. His constructive comments, advice
and material provision are extremely invaluable.
I am especially thankful to my wife, Giloya Lemita, who made
my life pleasurable and shouldered all the family responsibilities
throughout my study. My heartfelt thanks also goes to my brothers
Guyo Jillo and Halege Jillo, and others I did not mention, who,
regardless of situations, untiringly have given me a lot of
encouragement throughout my study.
Finally, I am grateful to all my friends for their unreserved
moral and material support and made my study fruitful. Among
the many, Mengistu Goa, Tesfa Yigrem and Workaferahu Seyoum
are worth mentioning.
Description
Keywords
Mathematics