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

max𝑐𝑇π‘₯=𝑐⋅π‘₯𝐴π‘₯≀𝑏π‘₯β‰₯0

.

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 𝑦β‰₯0 (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 min𝑦⋅𝑏. This gives the dual

min𝑦⋅𝑏=𝑦𝑇𝑏𝑦𝑇𝐴β‰₯𝑐𝑦β‰₯0

.

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.