## § 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 $p \in P$ where $P$ is a polytope, wecan use this to solve optimisation problems.
- Given the optimisation problem maximise $c^Tx$ subject to $Ax = b$, we canconstruct a new
*non-emptiness* problem. This allows us to convert optimisationinto *feasibility*. - The new problem is $Ax = b, A^Ty = c, c^Tx = b^T y$. Note that by duality,a point in this new polyhedra will
*be an optimal solution to the above linear program*.We are forcing $c^Tx = b^Ty$, 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 a*check if this polytope is empty* problem!