How to obtain the dual of a Lagrangian?

Question

The Lagrangian function $L:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ is $$ L(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)$$ A lot of sources (including Wikipedia) say the dual "is defined as" $$g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}L(x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left(f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)\right).$$ My question: WHY? Is it really just a definition? Or is it the Fenchel-Conjugate of $L$ or something? How to obtain the Lagrangian dual?

Answer 1

I'm assuming you know why the Lagrangian is defined the way it is. Let's just consider inequality constraints (actually without loss of generality): with $f$ convex (and assume smooth for simplicity) define

$$L(x,\lambda) := f(x) + \langle g(x),\lambda\rangle$$

where $g(x)\le 0$ is the vector of constraints (assume they are smooth too) and $\lambda\in \mathbb R^m_+$ the corresponding vector of Lagrange multipliers. This is indeed just a definition.

Now $L$ is convex and smooth in $x$ for all $\lambda$ so that it is minimized in $x$ when $\nabla_x L(x,\lambda)=0$.

Let us define $x_\lambda$ such that $\left.\nabla_x L(x,\lambda)\right |_{x=x_\lambda} = 0$ then what we just said reads:

$$ \min_x L(x,\lambda) = L(x_{\lambda} ,\lambda) $$

That is a function in $\lambda$. Let us denote it $H(\lambda)$ (this is precisely your dual Lagrangian function).

Several observations:

$$ H(\lambda) \le L(x,\lambda) $$ for all $x$ with equality if $x=x_\lambda$.

by simple extension you get

$$\max_{\lambda \in \mathbb R^m_+} H(\lambda) \le \min_{x\in C} f(x)$$

since $\lambda$ is positive and for $x$ to be admissible ($x\in C$) you must have $g(x)\le 0$. This is weak duality (actually this also holds for non-convex problems).

Now the KKT conditions tell you that $x^\sharp$ is a minimizer if and only if there exists $\lambda^\circ$ such that $\left.\nabla_x L(x,\lambda^\circ)\right|_{x=x^\sharp}=0$ and $\langle g(x^\sharp),\lambda^\circ\rangle =0$.

Shortening notations a little, since $\nabla_x L(x^\sharp,\lambda^\circ)=0$, it can be directly plugged in our definition of $H$:

$$ H(\lambda^\circ) = L(x^\sharp,\lambda^\circ) = f(x^\sharp)$$

Gathering pieces:

$$\max_{\lambda \in \mathbb R^m_+} H(\lambda) = H(\lambda^\circ) = f(x^\sharp) = \min_{x\in C} f(x)$$

So what we've done is define a lower bound on the Lagrangian and show that the lower bound is tight (for a convex problem) if and only you are at the optimal point.

One interest in doing this is that you have a certificate. In most cases you will have to run some kind of numerical method on either the dual or the primal or both. And if you can measure $L(x,\lambda)-H(\lambda)$, the duality gap, then it tells you "how far" you are from the optimal solution. Another interest is that the dual may be simpler to solve than the primal.

If this does not answer your question, I would recommend reading Rockafellar's bible (Chapter 28) http://www.convexoptimization.com/TOOLS/ConvexAnalysis.pdf which has all the answers (including to the universe and everything).