Recently, I'm studying an algorithm in Optimization, the Ellipsoid method or algorithm. With this method you can find(In polynomial time) a feasible solution of a linear program, or more precise can find a point in a polyhedron which we know the inequalities of the polyhedron.
But I want to know we can use this method to find an optimal solution or not?
I appreciate any help of you.
You can use it to determine if a certain value is attainable or not, and thus guess the optimal value. Suppose the problem is $\max(c^T x : Ax \leq b, x \geq 0)$. We can check if $(c^T x \geq \mbox{guess}, Ax \leq b, x \geq 0)$ is feasible and if so which point that is. You can then do binary search to converge onto an optimal solution