2
$\begingroup$

I found a Linear Programming textbook somewhere, and I skimmed through the first few pages. While I am not nearly enough ready to go through it, the things it dealt with seemed very much like calculus optimization problems, just a lot more complicated. Can the former be turned into Linear Programming problems?

For example, what we're doing right now in calculus is expressing some variable as a function of another, whereas originally they are expressed as a function of two or more (area, volume, etc...). That way we can use derivatives and their extrema and what not. The Linear Programming textbook seems to be fine with leaving the original function as one of multiple variables. So could I technically do those questions with linear optimization methods?

Sorry if all this is wrong, like I said I'm not at all ready for linear programming.

$\endgroup$
2
$\begingroup$

Apart from handling optimization problems, they are quite different.

When you use calculus to solve an optimization problem, you're depending on the theorem that (under appropriate conditions) the minimum is found either at a point with zero derivative, or on the boundary of the domain. You use calculus to find the points with zero derivative, and then it is usually a simple matter to compare those with the function value at the boundary. The domains in the calculus-ready problems are simple -- typically just an interval of the real line, so finding their boundaries hardly requires thought.

In linear programming problems, the complicated thing is to grasp what the boundary looks like. By definition linear programming is about problems where the actual function to minimize is linear -- so all calculus can tell us (and it does so very quickly) is that there are no extrema in the interior of the domain. But the domain is usually a space of very high dimension, so one cannot just imagine its shape; instead one has a large number of inequalities that define a complicated polyhedron in, say, $\mathbb R^{100}$. It's easy to see that the minimum must be on one of the corners of the polyhedron -- the difficulty is to find the corners, and figure out the one with the minimal function value, preferably without finding and trying all the corners, because there can be a huge number of those too.

The two styles of problem combine in general convex programming where you both have a target function that is not linear (so there may be interior extrema) and a complicated domain that you can't get any intuitive handle on.

$\endgroup$
0
$\begingroup$

Linear programming really is a combinatorial phenomenon. Calculus optimizes by an entirely different process. The two don't seem very interrelated to me.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.