Lagrangian Duality

In the following section we will derive the so-called dual problem of a (primal) optimization problem, following the derivation demonstrated in a series of short lectures which accompany the book [Bierlaire2018]. Possibly the most important property of the dual problem (from a practical point of view) is that it is convex even if the primal optimization problem is not [Boyd2004].

Let us consider a constrained optimization problem in the form $$\begin{array}{rl}\underset{x}{\min }& f(x)\\ \text{s.t.}& g(x)\le 0\\ & h(x)=0,\end{array}$$ to which we will refer to as the primal problem. With regard to this problem, let us define the Lagrangian $$L(x,\lambda ,\mu )=f(x)+{\lambda }^{\top }h(x)+{\mu }^{\top }g(x),$$ where $\lambda$ and $\mu$ are Lagrange multipliers, and the dual function $$q(\lambda ,\mu )=\underset{x}{\min }L(x,\lambda ,\mu ).$$

Theorem

Let $x^{\ast }$ be the solution to the primal problem. If $\mu \ge 0$, then $$q(\lambda ,\mu )\le f(x^{\ast }).$$

Proof

$$q(\lambda ,\mu )=\underset{x}{\min }L(x,\lambda ,\mu )\le L(x^{\ast },\lambda ,\mu )$$

(For any $\lambda$ and $\mu \ge 0$, I can find an $x$ that minimizes the Lagrangian as well as or better than $x^{\ast }$ by violating the constraints.)

and

$$L(x^{\ast },\lambda ,\mu )=f(x^{\ast })+{\lambda }^{\top }\underset{=0}{\underbrace{h(x^{\ast })}}+\underset{\ge 0}{\underbrace{{\mu }^{\top }}}\underset{\le 0}{\underbrace{g(x^{\ast })}}\le f(x^{\ast })$$ (Because if ${\mu }_i>0$ and $g_i(x^{\ast })<0$ then ${\mu }_i{g}_i(x^{\ast })<0$)

$\square$

Corollary

Let $x^{\ast }$ be the solution to the primal problem and $x$ feasible w.r.t its constraints. If $\lambda \in {\mathbb{R}}^n$ and $\mu \in {\mathbb{R}}^p$, $\mu \ge 0$, then $$q(\lambda ,\mu )\le f(x^{\ast })\le f(x).$$

Dual problem

As was proven ${\min }_{x}L(x,\lambda ,\mu )$ provides a lower bound on the solution of the primal problem when $\mu \ge 0$. The dual problem can then be regarded as maximing this lower bound by penalizing violations of the primal problem's constraints using the Lagrange multipliers: $$\begin{array}{rl}\underset{\lambda ,\mu }{\max }& \underset{q(\lambda ,\mu )}{\underbrace{\underset{x}{\min }L(x,\lambda ,\mu )}}\\ \text{s.t.}& \mu \ge 0\\ & (\lambda ,\mu )\in \{\lambda ,\mu \mid q(\lambda ,\mu )>-\infty \}.\end{array}$$

The second condition states that we consider on $\lambda$ and $\mu$ such that the dual function is bounded. This is necessary for the problem to be well posed.

(Weak duality) theorem

If $x^{\ast }$ is the solution to the primal problem and $({\lambda }^{\ast },{\mu }^{\ast })$ is the solution to the dual problem, then $$q({\lambda }^{\ast },{\mu }^{\ast })\le f(x^{\ast }).$$

Corollary

If one problem is unbounded the other is infeasible.

Corollary

If $\exists x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }$ such that $$q({\lambda }^{\ast },{\mu }^{\ast })=f(x^{\ast }),$$ they are optimal.