This is very cool. I wish there was a little more information while running each algorithm. Saying the update rule and being able to tick “next iteration” or something would be interesting.
Thanks! Yeah this is something I've been thinking about, agreed it could be really cool. Just not quite sure on the UX yet, perhaps a separate site (i.e. lpviz.net/step, like the in-progress 3-variable mode https://0b2df09c-lpviz.michael-4e4.workers.dev/3d) that uses some LaTeX animations to show the actual calculations of each step..
A linear program is a fundamental type of constrained optimization problem. It is made of two things: linear inequalities and a linear objective function.
The linear inequalities are referred to as the constraints and the set of points which simultaneously obey all inequalities is called the feasible region. The goal of the game is to find a point in the feasible region which minimizes the linear objective function. That means when you plug the coordinates of that point into the linear objective, you get the smallest value of any point in the feasible region.
A fun fact which is not so difficult to prove in 2 dimensions is that if a linear program has an optimal point (guaranteed when the constraints define a convex polytope), then the minimum objective value will be achieved at one of the vertices of the polytope.
This website lets you change the shape of the feasible region and the direction of the objective function (it is a linear function, so it’s behavior for optimization purposes is fully defined by that direction vector). It then gives you multiple famous algorithms for solving the linear program:
Simplex, for example starts at an exterior point and moves toward optimality. Dual simplex will start at a point with optimal objective and move towards feasibility, etc.
> A fun fact which is not so difficult to prove in 2 dimensions is that if a linear program has an optimal point (guaranteed when the constraints define a convex polytope), then the minimum objective value will be achieved at one of the vertices of the polytope.
lpviz visualizes how different linear programming (LP) solver algorithms arrive at their solution, and how they react to adjustments in the problem definition. To start using lpviz you first draw a number of vertices to define the so-called feasible region. Then you point the objective arrow, defining the improvement direction. The answer/optimal point is the point furthest along the improvement direction, while still being inside the feasible region.
LP finds applications in tons of downstream fields, though the typical real-world problem has thousands to millions of variables (whereas lpviz is limited to 2) and constraints. Courses typically focus on how to model real-world problems as LP, instead of diving into how the solvers work. lpviz tries to fill that gap, so you can develop some intuition for how the different algorithms work.
Thanks for the suggestion, always looking to add more solvers. Here's a share link to a branch that adds criss-cross and a proximal primal-dual active set, animating criss-cross looks pretty cool on the Many Facets preset:
This is very cool. I wish there was a little more information while running each algorithm. Saying the update rule and being able to tick “next iteration” or something would be interesting.
Thanks! Yeah this is something I've been thinking about, agreed it could be really cool. Just not quite sure on the UX yet, perhaps a separate site (i.e. lpviz.net/step, like the in-progress 3-variable mode https://0b2df09c-lpviz.michael-4e4.workers.dev/3d) that uses some LaTeX animations to show the actual calculations of each step..
can someone explain what I am looking at?
A linear program is a fundamental type of constrained optimization problem. It is made of two things: linear inequalities and a linear objective function.
The linear inequalities are referred to as the constraints and the set of points which simultaneously obey all inequalities is called the feasible region. The goal of the game is to find a point in the feasible region which minimizes the linear objective function. That means when you plug the coordinates of that point into the linear objective, you get the smallest value of any point in the feasible region.
A fun fact which is not so difficult to prove in 2 dimensions is that if a linear program has an optimal point (guaranteed when the constraints define a convex polytope), then the minimum objective value will be achieved at one of the vertices of the polytope.
This website lets you change the shape of the feasible region and the direction of the objective function (it is a linear function, so it’s behavior for optimization purposes is fully defined by that direction vector). It then gives you multiple famous algorithms for solving the linear program:
Simplex, for example starts at an exterior point and moves toward optimality. Dual simplex will start at a point with optimal objective and move towards feasibility, etc.
> A fun fact which is not so difficult to prove in 2 dimensions is that if a linear program has an optimal point (guaranteed when the constraints define a convex polytope), then the minimum objective value will be achieved at one of the vertices of the polytope.
That is, if you assume there is no dual degeneracy :) https://lpviz.net/?s=AsEABN_FCIDiCQC_ixGg4BQAAMCLEYCS9AEAZAA
2 replies →
lpviz visualizes how different linear programming (LP) solver algorithms arrive at their solution, and how they react to adjustments in the problem definition. To start using lpviz you first draw a number of vertices to define the so-called feasible region. Then you point the objective arrow, defining the improvement direction. The answer/optimal point is the point furthest along the improvement direction, while still being inside the feasible region.
LP finds applications in tons of downstream fields, though the typical real-world problem has thousands to millions of variables (whereas lpviz is limited to 2) and constraints. Courses typically focus on how to model real-world problems as LP, instead of diving into how the solvers work. lpviz tries to fill that gap, so you can develop some intuition for how the different algorithms work.
There's tons of great videos/lectures introducing LP, this two-minute one is pretty good: https://www.youtube.com/watch?v=7ZjmPATPVzI
Great,
Congrats. Why not any active set methods?
Thanks for the suggestion, always looking to add more solvers. Here's a share link to a branch that adds criss-cross and a proximal primal-dual active set, animating criss-cross looks pretty cool on the Many Facets preset:
https://9b7c882e-lpviz.michael-4e4.workers.dev/?s=AtUAHIDTDg...
Cool.
I was going to ask about 3D but I saw you got that covered at least on your other reply.
I wish could upvote it again.
Simplex is there.