PHIL: Phil Wolfe
IRV: Irvin Lustig
IRV
What brought about the simplex solution to the quadratic problem?
PHIL
Bob Dorfman, an economist at UC Berkeley, had been interested in mathematical methods for economics for a long time. He worked with Ed Barankin, especially on quadratic programming, a problem with the quadratic objective function to minimize under linear constraints.
Dorfman used the then very new Kuhn-Tucker theory for nonlinear programming to show that if you wrote the Kuhn-Tucker conditions down together with the original constraints of the problem, you had a big set of linear equations that looked like a simplex method tableau. Really quite exquisite.
As a matter of fact, you could show that the solution of the quadratic problem was an extreme point of this tableau problem. It was exciting, but the trouble is nobody knew how to find one of those extreme points.
Unlike linear programming, we didn't have any clear way of getting there. At Princeton in 1955, working on Tucker's logistics project, Marguerite Frank and I started to look at nonlinear programming problems. We devised a somewhat clumsy method of doing it, now known as the Frank-Wolfe algorithm. While it's a precursor to quadratic programming, it turned out to have a lot of applications in other areas where you have messy
objective functions and linear constraints.
We submitted this for publication to the Naval Research Logistics Quarterly. Alan Hoffman was an editor. At the same time, he received a manuscript from Harry Markowitz on portfolio selection by parametric quadratic minimization. Because these were similar subjects, he sent the Markowitz manuscript to me to referee and he sent our manuscript to Markowitz to referee.
Talking to Harry much later, I found that we did the same sort of thing: looked at the other's paper, couldn't understand it very well, but it sounded like competent mathematics. So we turned in our reports saying "publish this."
I had some twinges of conscience; I knew I hadn't really understood his work. A year later I went back and tried to figure out what was going on. I came close, but I was unfortunately struck by a creative idea: it sounded like the simplex method!
I wanted to see if I could model the steps he was taking in the simplex method. I never made a perfect model, but I made a version of the simplex method to solve a quadratic program. That was a breakthrough in early 1957. Sent a copy to Dantzig at Rand.
He sent a letter back saying, "This is a terrific result, if it's true." That was one reason I was welcome at Rand and I wanted to join there. So, I worked on that algorithm and polished it some. The connection with Dantzig was terrific for me.
|