In 1948, at the meeting of the Econometric Society at the University of Wisconsin, Madison, George Dantzig first presented his formulation of Linear P

Convex Optimization in the Age of LLMs - by Ben Recht

submited by

Style Pass

2024-08-29 21:30:02

In 1948, at the meeting of the Econometric Society at the University of Wisconsin, Madison, George Dantzig first presented his formulation of Linear Programming. Dantzig proposed something radical at the time. Posing problems as goal maximization wasn’t particularly novel, nor were simple algorithms for finding extreme points. But no one had an algorithm for maximizing a goal subject to a complex model constraining potential solutions. Dantzig found he could model all sorts of important planning programs–whether it be the transportation of goods, assignment of people to tasks, or computing shortest paths–as maximizing linear functions subject to linear inequality constraints.

Dantzig’s breaktrhough was showing that any such optimization problem could be solved by the same algorithm. His Simplex Method worked by solving an appropriate sequence of linear equations, like the ones we torture our high school students with. As long as you could model a problem using linear equations and linear inequality constraints, Dantzig’s algorithm could find the solution.

After his talk, the first question from the audience was more of a belligerent comment. Mathematical statistician Harold Hotelling stood up and blustered, “We know the world is nonlinear." He’s not wrong, of course. Nonlinear just means “not linear,” and it’s pretty clear that many (most?) worldly phenomena are not well-modeled by linear functions. Any curvy function isn’t linear. But before Danztig could reply, John von Neumann interjected, ”The speaker titled his talk 'Linear Programming.’ Then he carefully stated his axioms. If you have an application that satisfies the axioms, use it. If it does not, then don’t.”