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.

References:

  1. Boyd, S., and Vandenberghe, L. (2004). Convex Optimization. Chapter 5.

1 thought on “The Lagrange dual function is always concave

  1. Pingback: Lagrange dual, weak duality and strong duality | Statistical Odds & Ends

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 )

Connecting to %s