Duality

Moritz: Hey Max, I have a problem.

Max: Yeah whats up?

Moritz: I hate spending money on fruit, but I want to get my daily recommended amount of vitamins...

Max (suddenly excited): Oh I can help you with that, thats just an optimization problem with constraints!

Moritz (relieved): Great, I already know the prices of apples and bananas per kilo at the supermarket.

Max: We'll call that 2D vector p for prices.

Moritz: I also have a table that has two columns for apple and banana and three rows for vitamin A, B and C. It shows how much units of a particular vitamin is in a kilo of a certain fruit.

Max: We'll call that 3x2 matrix M.

Moritz: I also have a list of the recommended amount of each vitamin.

Max: We'll call that 3D vector c for 'constraint'.

Moritz: Great! So now I need to find out how many kilos of apples and how many kilos of bananas to buy.

Max: We'll call the 2D vector that represents how much kilo of which fruit to buy x. In summary you are trying to minimize p_transpose * x while satisfying the constraint M * x >= c.

Moritz: Ah that makes sense, so now all I need to do is solve these equations and...

Max (interupting): I have another idea. I recently started a business selling vitamin supplements. I could sell some to you now. That way you don't have to go the supermarket.

Moritz (surprised): Thats great! So how much are you selling vitamins A, B and C for per unit? I want to see if you can compete with the supermarket.

Max (self aware and greedy): Look, I am no communist. I will determine the vitamin price vector y you mentioned by maximizing the amount of money I will make if I sell you the recommended amount of each vitamin. In other words I am trying to maximize c_transpose * y.

Moritz (slightly offended): So you're just going to sell at the highest price possible? How do I know you're not ripping me off? Can you guarantee me that I will not pay you more than what I would have otherwise at the supermarket?

Max (impatient): Let me finish! I guarantee that the price of all the vitamins in a fruit will never cost more than the fruit itself does at the supermarket.

Moritz (taking a moment to understand what Max is saying): So, for example, if I buy all the vitamins that are in a kilo of apples from you as supplements...

Max: ...then I guarantee that you won't be spending more for the supplements than you would for the apples. So all in all, I guarantee that A_transpose * y <= p.

Moritz (biting his lip): While this gave me a newfound understanding of what taking the transpose of a matrix means and I trust you that you won't break your guarantees, I am still left wondering whether it is really guaranteed that I wont get a worse deal than at the store.

A theorem descends from heaven

Duality Theorem: You have summoned me!

Max and Moritz in unison: To what do we owe the pleasure?!!

Duality Theorem: From my heavenly vantage point I can see that Max's maximization problem of finding y is the dual problem of Moritz's minimization problem of finding x. In such cases, I embody the proof that Max's price will always be equal or better than the best supermarket price Moritz can find! In your case it is exactly equal for there is a unique solution for x and a unique solution for y!

Moritz: Thats pretty cool, my dog.

Max: I might have to rethink my business model...

Everyone in the story disappears in a cloud of glitter as the author of this post becomes aware that they are procrastinating instead of studying for their exams.