# Some Remarks On Projective Algorithm In Linear Optimization Graduate Seminar Report

## Mathematics Project Topics

### Get the Complete Project Materials Now! ยป

Although the ongm of the linear optimization as arnmathematical discipline is quite recent, it is now well establishedrnas an important and very active branch of applied mathematics.rnThe wide applicability of linear optimization models and the richrnmathematical theory underlying these models and the methodsrndeveloped to solve them have been the driving forces behind thernrapid and continuing evolution of the subject. The recognition ofrnthe importance of linear optimization models, especially in thernareas of economic analysis and planning, coincide with therndevelopment of both an effective method, the 'simplex method' of G.rnB. Dantzig, for solving linear optimization problems, and a means,rnthe digital computer, for doing so.rnAll forms of the simplex algorithm reach the optimum byrntransversing a series of basic solutions. Since each basic solutionrnrepresents an extreme point of the feasible region, the trackrnfollowed by the algorithm moves around the boundary of thernfeasible region. In the worst case, it may be necessary to examinernmost of, if not all, the extreme points. The worst case here justrnsimply means a worst possible data configuration that would takernthe simplex algorithm run many steps. This can be cripplinglyrninefficient given that the number of extreme points growsrnexponentially with n for fixed m.rnThe existence of such worst cases suggests that one shouldrnlook possibly for algorithms other than the simplex algorithms,rnwhich are good in such cases.rnThe first success was attributed to the Russianrnmathematician, Khachian (1979), who proposed the ellipsoidrnalgorithm or sometimes the Russian Method. Though theoreticallyrnefficient, code developers were never able to realize anrnimplementation that matched the performance of concurrentrnsimplex codes.rnJust about the time when the interest in the ellipsoid methodrnwas waning, a new technique to solve linear optimization problemsrnwas proposed by N. K. Karmarkar (1984) of AT & T BellrnLaboratories, namely, the projective algorithm or more generallyrninterior point algorithmrnContrary to the simplex algorithm, the projective algorithmrnmoves in the relative interior rather than on the outside of thernpolyhedron in the n - dimensional space.rnThe purpose of this paper is to describe the development of thisrnnew algorithm and the idea (coming from non-linear optimizationrnand projective geometry) on which it is based. Here we present thernoriginal algorithm, which is the approximation to the underlyingrnalgorithmic idea because of linearization of what is inherently arnnon-linear problem due to a projective transformation.rnI want to express my deepest gratitude to my adviser Prof. Dr.rnrer. nat. habil. R. Deumlich who cultivated me highly not onlyrnacademically but also socially. His constructive comments, advicernand material provision are extremely invaluable.rnI am especially thankful to my wife, Giloya Lemita, who madernmy life pleasurable and shouldered all the family responsibilitiesrnthroughout my study. My heartfelt thanks also goes to my brothersrnGuyo Jillo and Halege Jillo, and others I did not mention, who,rnregardless of situations, untiringly have given me a lot ofrnencouragement throughout my study.rnFinally, I am grateful to all my friends for their unreservedrnmoral and material support and made my study fruitful. Amongrnthe many, Mengistu Goa, Tesfa Yigrem and Workaferahu Seyoumrnare worth mentioning.