Linear Programming Duality The definition of the dual LP Consider the following LP in vector-matrix from: We can associate another LP with it, which is called the dual of the above, while the first is called the primal LP: Let us take the above for the definition of duality. We will soon see its importance, but let us look first into how can we find the dual if the LP is given in some other form, so that it remains consistent with the above definition.The Duality Theorem Throughout this section we consider the primal in standard form, so we have (3) and (4) What does this mean? It means that the objective function value of the primal is always greater than or equal to the objective function value of the dual. In other words any feasible solution of the primal minimization problem is an upper bound on the dual maximization optimum. Similarly, any feasible solution of the dual maximization task is a lower bound on the primal minimization optimum. Fig 1. Relation of primal and dual feasible valuesThe Weak Duality Lemma is surprisingly easy to prove: What is the significance of all this? We can see that either task (primal and dual) yields a bound on the optimal value of the other. Therefore, we obtain the following consequence: This is very useful in the following situation. Assume we found a feasible solution to the primal problem and we claim it is optimal. The fact that it is feasible can be easily checked by substituting it into the constraints, and seeing that all constraints are satisfied. But how do we prove that it is optimal? How can we make sure that there was no error in the program that found it? An opportunity is offered by the above Corollary. If we can exhibit a dual feasible solution, such that holds, then this proves the optimality of the primal solution, since the left-hand side is the primal objective function value, which is always bounded from below by the dual objective function value that is on the right-hand side. That is, we always haveNow, if they are actually equal, then both must be optimal, as then the gap in Fig 1 disappears. In other words, if the primal objective function value is equal to the dual one, then this primal value must be the smallest possible, since the dual is always a lower bound. Thus, the dual solution can serve as a certificate of the optimality of the primal solution. Note that in order to check this certificate, we only need to check that both the claimed primal and the dual solutions are feasible, we do not have to check their optimality! But the whole thing only works if one can indeed guarantee that there is no gap between the set of primal and dual feasible solutions. In case there is a gap, then the above optimality certificate does not exist. Therefore, it is an important question whether is it generally true that there is no such gap between the primal minimum and dual maximum, given that they are both finite? The answer is that it is indeed generally true, and it is guaranteed by the Duality Theorem of Linear Programming: The proof of this is significantly harder than that of the Weak Duality Lemma, so we do not study the proof details in this course. LP duality is a fundamental result. The above “optimality certificate” application is only a very simple one. It is applied in much more sophisticated ways, for example in constructing LP algorithms.Exercise Find the dual
View Full Document
Unlocking...