Lagrangian Dual Problem and Weak Duality

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

g(\lambda, \nu) = \inf_{x \in \mathrm{D}} L(x, \lambda, \nu) = \inf_{x \in \mathrm{D}} f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x)

for \lambda \succeq 0 where \succeq means \lambda_i \geq 0 for all i.

Standard Form Linear Program

Given a standard form linear program

minimize c^Tx

subject to Ax=b

x \succeq 0,

we can furthermore write the Lagrangian dual for the standard form LP as

g(\lambda, \nu) = \inf_{x} (c^Tx - \lambda^Tx + \nu^T(Ax - b))

= -\nu^T b + \inf_{x} (c + A^T \nu -\lambda)^T x

or

g(\lambda, \nu)=\begin{cases} -b^T\nu,  & c + A^T \nu -\lambda = 0\\ -\infty, &otherwise. \end{cases}

since any linear function is bounded below only when it is identically zero (see here for explanation), and f(x) = (c + A^T \nu -\lambda)^T x 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 \lambda and \nu. The natural question is, then, can we obtain the best possible lower bound by varying \lambda, \nu. This leads to a natural optimization problem where we try to optimize the value of the Lagrangian dual for various \lambda, \nu:

maximize g(\lambda, \nu)

\lambda \succeq 0.

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 g(\lambda, \nu) > -\infty and \lambda \succeq 0. We define the Lagrange multipliers (\lambda^*, \nu^*) 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:

maximize g(\lambda, \nu)=\begin{cases} -b^T\nu,  & c + A^T \nu -\lambda = 0\\ -\infty, &otherwise. \end{cases}

subject to \lambda \succeq 0.

Because the above LP is bounded and feasible only when c + A^T \nu -\lambda = 0, we can make this an explicit constraint and create the following LP:

maximize -b^T\nu

subject to c + A^T \nu \succeq 0.

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

maximize g(\lambda, \nu)

\lambda \succeq 0,

we see that g(\lambda, \nu) 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 g(\lambda, \nu) 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 f is equivalent to minimizing the convex function -f 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.

Weak Duality

I mentioned before in my previous blog post that the Lagrangian dual is a lower bound on the optimal solution of the primal

g(\lambda, \nu) \leq p^*

where p^* is the optimal solution of the primal. Suppose that d^* is the optimal solution to the dual problem

maximize g(\lambda, \nu)

\lambda \succeq 0

then, we also can easily see that

d^* \leq p^*.

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 \infty or, in other words, the dual is unbounded. This provides us with more information than just a lower bound, it is sufficient to show d^* = \infty as a certificate of infeasibility of the primal problem.

References and Resources

  1. http://stanford.edu/~boyd/cvxbook/
  2. http://www.mit.edu/~parrilo/cdc03_workshop/02_convexity_and_duality_2003_12_07_03_screen.pdf
Advertisements
This entry was posted in Algorithms, Math and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s