Lagrangian Dual Problem
I left off in my last post on the Lagrangian dual with the observation that we can turn the Lagrangian dual into the dual we are used to seeing as the dual LP, via a simple transformation. Now I will explain this simple transformation. Recall that we defined the Lagrangian dual as
for where means for all .
Standard Form Linear Program
Given a standard form linear program
we can furthermore write the Lagrangian dual for the standard form LP as
since any linear function is bounded below only when it is identically zero (see here for explanation), and is a linear function.
Lagrangian Dual Problem
We saw that the Lagrangian dual gives us a lower bound on the optimal value of the original optimization problem (given in the Lagrangian dual post). The Lagrangian dual is defined in terms of some parameters and . The natural question is, then, can we obtain the best possible lower bound by varying . This leads to a natural optimization problem where we try to optimize the value of the Lagrangian dual for various :
This optimization problem is called the Lagrangian dual problem. We see that solving this problem will provide the best possible lower bound for our original optimization problem. We can rename the original optimization problem to be the primal problem. The dual problem is feasible if and . We define the Lagrange multipliers to be dual optimal if they produce the optimal value to the dual problem.
Lagrangian Dual Problems of LPs
Then, using our above formulation of the Lagrangian dual of standard form LPs, we may write the following Lagrangian dual problem of standard form LPs:
subject to .
Because the above LP is bounded and feasible only when , we can make this an explicit constraint and create the following LP:
subject to .
And voilà, we have an LP representing the dual in a form that we recognize.
Other characteristics of the Lagrangian dual and Lagrangian dual problem
There are two other characteristics that I want to talk about before moving on to weak duality.
If we look back at our general Lagrangian dual problem
we see that is always concave because it is the pointwise infimum of a family of affine functions (see here for a detailed explanation).
Furthermore, because we know that is concave (regardless of whether or not the primal was convex), we then know that the Lagrangian dual problem is convex. The dual problem is convex because maximizing a concave function is equivalent to minimizing the convex function by definition. Therefore, the dual problem is actually a convex optimization problem. We see why this is important later on. (Spoiler alert: This is important because it is often easier to solve convex optimality problems than other types of optimality problems.)
Weak Duality and Certificate of Infeasibility
I wanted to first introduce weak duality. I’ve left out some details on Strong Duality, which is also a tremendously important concept. (Strong Duality specifies a tight lower bound on the optimal value of an optimization problem, i.e. the optimal value of the optimization problem equals the lower bound.) I will write about this concept in my next post.
I mentioned before in my previous blog post that the Lagrangian dual is a lower bound on the optimal solution of the primal
where is the optimal solution of the primal. Suppose that is the optimal solution to the dual problem
then, we also can easily see that
The statement given above is, in fact, weak duality. The advantage of finding an optimal solution for the dual problem is that the dual problem is often easier to solve than the primal problem because it is convex. In the case that strong duality applies, we can find the actual solution to the original optimization problem by solving the dual problem.
Using the dual, we can see that the primal is infeasible if the optimal solution for the dual is or, in other words, the dual is unbounded. This provides us with more information than just a lower bound, it is sufficient to show as a certificate of infeasibility of the primal problem.
References and Resources