Linear Programming and Duality
Recall that moves from the original vector space (which we will call the primal space) to an image vector space (which we will call the dual space).
Also recall that the dot product can be interpreted geometrically as how far along does lie? 11 Try taking dot products with the unit vectors, for example.
In linear programming, we are given a primal
.
This gives a nice geometric interpretation of the primal. Given a positive vector in the primal space, it is feasible iff after performing the linear transformation to transform it into the dual space, it is within the box . We want to choose the vector which lies furthest along the direction of .
This is great, but doesnβt tell us very much about .
To start, letβs make some observations about the dual space. In order to describe the relationship, we can look at a vector , and measure how far along the transformed vector lies, i.e. .
Clearly, since the vector cannot be outside of the box , cannot extend in any direction further than . In other words, , as long as (which might reverse the inequality).
Because of associativity, we can also look at as taking a vector in the dual space, transforming it into the primal space, and then measuring it along , and that we want the largest such vector. For simplicity, we rewrite this as .
Since we are maximizing , we want to find the largest vector we can take in a feasible solution based on this intuition. To do this, letβs look at the relationship between the two vectors in the primal space, and .
Since we are maximizing , we only need to try to upper-bound . In the dual space, we know that the vector which when transformed into the primal space, is as far as possible along , and that this is at least as far as along . Thus, we want .
Now we get that .
Since we want this upper bound to be tight, we want to find . This gives the dual
.
This relationship gives some intuition for duality, but it is still unclear what to do for any vector or . This is described by Farkasβs Lemma.