§ Linear optimisation is the same as linear feasibility checking
Core building block of effectively using the ellipsoid algorithm.
- If we posess a way to check if a point where is a polytope, wecan use this to solve optimisation problems.
- Given the optimisation problem maximise subject to , we canconstruct a new non-emptiness problem. This allows us to convert optimisationinto feasibility.
- The new problem is . Note that by duality,a point in this new polyhedra will be an optimal solution to the above linear program.We are forcing , which will be the optimal solution, since thesolution where the primal and dual agree is the optimal solution by strongduality.
- This way, we have converted a linear programming problem into acheck if this polytope is empty problem!