It's so great to see someone taking out time and doing efforts to make us understand optimization better in visualisation....kudos to you.... Please make more videos on optimization including topic like duality, Non-Linear optimization and constraint Non linear optimization and on Neural network as well...
Great work! It's been a few years since I've done LP, but it would have been nice to have a visual as sharp as this when I first learned it. I actually wasn't familiar with "strongly" polynomial time (as opposed to just polynomial time). I'm sure these videos are made with brevity in mind, but consider putting a quick, informal definition off to the side? Unless I just missed it
Thanks for watching! You make a good point. I have added more details about the distinction between polynomial and strongly polynomial time algorithms. The definition is somewhat technical, but the basic idea is that a polynomial time algorithm is allowed to take more time as the magnitude of the coefficients grows (while keeping the number of variables/constraint constant), but a strongly polynomial time algorithm is not. The interior point method is a polynomial time algorithm, but not a strongly polynomial time one.
That is indeed not the case. There can be no solution (feasible set is empty), uncountable infinite solutions (feasible set is not completely bounded), infinite solutions (all the solutions on a edge between two points) multiple solutions (one solution per vertex). For your question: Lets say we have a feasible set where the optimal solution is on one of the faces of the polyhedron. Which means there is a vector from (0,0,0) to the optimal point (x,y,z) of optimal length n. Now every point on the plane has to be closer to the origin than our point (x,y,z), which is striclty impossible, unless the plane is curved, which by definition is never true. Furthermore any point inside the feasible set is clearly not optimal, because the vector could stretch through that point until it hits the boundary. With those 2 ideas in mind you can see that every optimal solution is on a vertex or on the edge between two vertices.
Thanks for the suggestion! In my experience, the automatically generated captions are pretty good. Let me know if you still have problems with that and I will consider adding custom captions.
While the two questions sound similar, there is a priori no direct relationship between the two. For all we know, someone could prove that a variant of the simplex method runs in strongly polynomial time, and we would still have no clue about P=NP.
