The Ambrosini Critique

In 1972, Klee and Minty gave an example of a linear programming problem in which the polytope P is a distortion of an n-dimensional cube. They showed that the simplex method as formulated by Danzig visits all 2ⁿ vertices before arriving at the optimal vertex.

This is a quote from wikipedia. Maybe I should dig up that paper…

I’m trying to get my head around duality. Essentially, every linear program has a dual program. If in the original problem, you’re maximizing, in the second you’re minimizing. Also, you swap the ‘costs’ and the constraints. The costs become constraints and the original constraints go into the objective function.

Economically, duality means that the problem of maximizing profit is the same as the the problem of minimizing costs.

Of course, a system of constraints usually has many feasible solutions. One result of duality is that if one of the problems has a solution than its dual will have a solution, too. A more interesting result about duality is that if the maximizing problem has a solution then the value of its objective function will be less than or equal to the value of the objective function for some solution to the minimizing problem.

This last result, called the weak duality theorem, can be used to show that the optimal solution for the maximizing problem results in a value of its objective function equal to the value of the objective fuction for the minimizing problem at its optimal solution. In this way, you can know if you have an optimal solution by checking if the dual problem gives an equal value of the objective function.

I’m still wrapping my head around all this and I certainly don’t understand the math…. There’s a great presentation I grabbed off a google search.

Confirmation of the rumor reported at kottke.org.

I just recieved this email from a friend:

My sister was on Jeopardy! so we went down to L.A. Wednesday to see the taping. Her episodes will air the first week of December or thereabouts.

And yes, Ken got beat the day before we saw the tapings. My sister said that she and the other contestants were all standing around in the morning nervously wondering “where’s Ken? anyone seen Ken? does he not have to come in with the rest of the contestants anymore?” until a security guard took pity on them and said “Ken got beaten yesterday” and then they all cheered.

I think I did pretty well. I really screwed the pooch on the number of ‘petrol’ stations in the UK. I was guessing 1 per 1000 folks, having estimated that there is 100M Britons (hence my guess of 100k). It turns out that using the gas station density in a small, rural US town overestimates the density in the UK by about 10X. Who knew… Well, probably most people.

BTW, Chris Lightfoot comments on the results from the quiz.

App deadline: 12/15

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

App deadline: 2/1

Materials:

- 2 letters of rec

- transcripts

- gre

App deadline: 1/5

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

App deadline: 1/14

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

?

App deadline: 12/28

Materials:

- 3 letters of rec

- transcripts

- gre

- sop