2,631 karma · joined December 5, 2024
Any quality CS program will have you do that for a year or so, plus theory.
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.
Any proof which is correct can be formalized. That is what is means for a proof to be correct.
I’m not sure why you are restricting the scope of our discussion to what _Lean_ can(not) formalize. Even if we do choose to do that for some reason, Lean is not a formal system of fixed axioms; it supports optional additional axioms.
This is a common thing in complexity, and I think even the abstract says it is talking about “length n” and not “magnitude n”
It’s shocking really how wasteful the leaders of the United States can be.
That’s why it doesn’t make sense to present AI companies as dumping or burdening the scientific community into doing labor for them; the scientific community is self motivated to do so.