MATH 340 Lecture Notes - Lecture 11: Object-Oriented Analysis And Design, Ellipsoid Method, Leonid Khachiyan
Document Summary
Proof: just follow the simplex method, using one of the ideas from last class if necessary to prevent cycling (and thus guaranteeing termination). It basically gives a owchart of what to do, ending in one of the three situations in statement (1). E ciency of the simplex method as an algorithm. So now we understand the simplex method pretty well, and if you"re handy with computer programming you could probably write a program to actually implement it for you. And in any case, if problems get beyond a fairly small size we"re going to turn to computers anyway because we don"t want to do it by hand. For the rst question, it"s a little harder to say. The answer to the second question is generally yes - for practical purposes the simplex method is the way to go, and improvements in speed come down to optimizing the implementation of the simplex method.
