The Lagrange dual function is always concave

Consider an optimization problem in standard form:

$\begin{aligned} \text{minimize} \quad& f_0(x) \\ \text{subject to} \quad& f_i(x) \leq 0, \quad i = 1, \dots, m, \\ & h_i(x) = 0, \quad i = 1, \dots, p, \end{aligned}$

with the variable $x \in \mathbb{R}^n$ . Let $\mathcal{D}$ be the domain for $x$ , i.e. the intersection of the domains of the $f_i$ ‘s and the $h_i$ ‘s.

The Lagrangian associated with this problem is the function $L: \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \mapsto \mathbb{R}$ defined as

$\begin{aligned} 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), \end{aligned}$

with domain $\mathcal{L} = \mathcal{D} \times \mathbb{R}^m \times \mathbb{R}^p$ . The Lagrange dual function is the function $g: \mathbb{R}^m \times \mathbb{R}^p \mapsto \mathbb{R}$ defined as the minimum value of the Lagrangian over $x$ :

$\begin{aligned} g(\lambda, \nu) = \inf_{x \in \mathcal{D}} L(x, \lambda, \nu). \end{aligned}$

The dual function is a very important function in optimization theory. One interesting fact about the dual function is that it is always concave, even if the original optimization problem is not convex. The proof can be stated in one-line: for each $x$ , $L(x, \lambda, \nu)$ is an affine function, and the point-wise infimum of a family of affine functions is always concave.

Here’s a more explicit version of the proof. Let $\theta = (\lambda, \nu) \in \mathbb{R}^{m + p}$ . Fix $\theta_1, \theta_2 \in \mathbb{R}^{m + p}$ and $t \in [0, 1]$ . For each $x \in \mathcal{D}$ ,

$\begin{aligned} L(x, t\theta_1 + (1-t)\theta_2) &= t L(x, \theta_1) + (1-t) L(x, \theta_2) \\ &\geq t g (\theta_1) + (1-t) g(\theta_2), \end{aligned}$

where the first equality uses the definition of $L$ (or the fact that $L$ is affine in $\theta$ ). Since this holds for all $x \in \mathcal{D}$ , we can take an infimum over $x$ to obtain $g(t\theta_1 + (1-t)\theta_2) \geq t g (\theta_1) + (1-t) g(\theta_2)$ , i.e. $g$ is concave.