According to the internet, if you ate only ramen, you’d save thousands of dollars each year in food.

That sounds great, except there’s a problem: ramen lacks a wide range of essential nutrients and vitamins. You’d lose your teeth to scurvy, a lack of vitamin D would cause your bones to become brittle and easily broken, you’d suffer nightblindness from a lack of vitamin A, and you’d be tired all the time from a lack of iron and the B vitamins. In short, all the money you saved on food, and much, much, more, would be spent on increased medical care.

The problem is that eating healthy is costly. And this leads to a national security crisis.

If you want the short version, I’ve summarized the key points in a ten-minute video:

A little more mathematics:

Food buyers face what mathematicians call a *constrained optimization problem*: they have to meet certain caloric and nutritional goals (the constraints), which defines a feasible region. Generally speaking, any point in the feasible region defines a solution to the problem; what you want to do is to find the optimal solution.

The optimal solution is generally determined by the *objective function. *For example, if you lived off packages of ramen and eggs, the important objective function might be the total cost of your meals. At 15 cents a pack of ramen and 20 cents an egg, the objective function has the form , and we might want to minimize the value of the objective function.

In the following, I’ll assume you want to minimize the value of the objective function; the arguments are similar if you’re trying to maximize the value (for example, if you’re designing a set of roads, you might want to maximize the traffic flow through a town center).

There’s a theorem in mathematics that says the optimal solution will be found on the boundary of the feasible region. The intuition behind this theorem is the following: Imagine any point *inside* the feasible region. If you change any *one *of the coordinates while leaving the others the same, the value of the objective function will generally change. The general idea is to move in the direction that decreases the objective function, and continue moving in that direction until you hit the boundary of the feasible region.

At this point, you can’t move any further in that direction. But you can try one of the other directions. Repeating this process allows us to find the optimal solution.

We can go further. Suppose our objective function is linear (like the cost function). Then the same analysis tells us the optimal solution will be found at a *vertex* of the feasible region. This suggests an elegant way to solve linear optimization problems:

- Graph the feasible region and locate all the vertices. Generally speaking, the constraints are themselves linear functions, so (in our ramen and egg example) the feasible region will be a polygon.
- Evaluate the objective function at each vertex,
- Choose the vertex that minimizes the value of the objective function.

Easy, huh? Except…

- If you have commodities, you have to work in .
- This means the feasible region will be some sort of higher solid.
- This also means that finding the vertices of the feasible region will require solving systems of equations in unknowns.

In 1945 ,George Stigler did such an analysis to find a minimal cost diet that met caloric and nutritional requirements. To make the problem tractable, he focused on a diet consisting of just seven food items: wheat flour; evaporated milk; cabbage; spinach; dried navy beans; pancake flour; and pork liver.

“Thereafter the procedure is experimental because there does not appear to be any direct method of finding the minimum of a linear function subject to linear conditions.” The problem is that with seven items, you’re working with hyperplanes in , and the constraints will give you hundreds of vertices to check.

Note the date: 1945. What Stigler didn’t know is that there *was* a method for finding the minimum value easily. But that’s a story for another post…