Duality is an extraordinarily important concept in both linear and nonlinear programming. However, the equivalency of the primal and dual problems is not completely obvious, and difficult to give a geometric interpretation to. However, we can get a pretty good idea of how it works by examining the equivalency of the two problems. The following is mostly based on the notes from AA Ahmadi, but I have expanded them a little. Specifically, I show how you can also solve the dual problem from the primal. (I also recommend these notes for a really intuitive explanation of Farkas’ Lemma.)
Let us consider the following problem as the primal:
where if each component is .
We contend that this problem will have a solution if the dual problem does:
In both the above problems, we let , and an real matrix. When necessary, we shall refer to the primal problem as (P) and the dual as (D). Note that it does not really matter which one you pick as primal or dual, since the dual of the dual has to be the primal again. What we want to do is to show that the primal problem will have a solution as long as the dual one does.
We can start be rephrasing the problem (P) as follows:
The strategy here can be seen as maximising the lower bound for , instead of minimising directly. We can rephrase this as an ostensibly stronger problem. The above will have a solution as long as there exist , with such that
The stronger problem can now be reformulated as
Now, affine functions of will be equal everywhere if and only if their coefficients are equal, hence the problem can be written as
But this is the same as solving the problem
which is the dual problem. Thus, being able to solve the dual problem means we can solve the primal problem. Conversely, suppose that we can solve the primal problem. We phrase the dual problem as
The dual problem can be solved if there exists some such that:
This just means that, since is nonnegative, implies that is also nonnegative, meaning that we have a nonnegative , and we can minimise to be as close to as possible. Once again, we look at the coefficients in the above affine function of , and can set them to be equal. We therefore get the problem
which is of course just the primal problem again.
The usefulness of primality and duality is not limited to spaces such as . In fact, these basic concepts will hold for any vector lattice, which allows us to do things like semidefinite programming.