Duality
![](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmazJd56qTkL9413KPK6CWE2XKSxpa1bzjT7UjxgrrH34X/image.png)
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.
Congratulations @trilo! You have received a personal award!
Click on the badge to view your Board of Honor.
Do not miss the last post from @steemitboard:
Congratulations @trilo! You received a personal award!
You can view your badges on your Steem Board and compare to others on the Steem Ranking
Do not miss the last post from @steemitboard:
Vote for @Steemitboard as a witness to get one more award and increased upvotes!