Lagrangian

Consider a not-necessarily convex:

\begin{align} \min_{x}\quad & f_{0}\qty(x) \\ \textrm{s.t.} \quad & f_{i}\qty(x) \leq 0 \\ & h_{i}\qty(x) = 0 \end{align}

The Lagrangian is:

\begin{equation} L\qty(x,\lambda, v) = f_{0}\qty(x) = \sum_{i=1}^{m} \lambda_{i}f_{i}\qty(x) + \sum_{i=1}^{p} v_{i}h_{i}\qty(x) \end{equation}

its essentially a weighted sum of objective and constraint functions. We call

• \(\lambda_{i}\) is a Lagrange multiplier associated with \(f_{i}\qty(x) \leq 0\)
• \(v_{i}\) is a Lagrange multiplier associated with \(h_{i}\qty(x) = 0\)

Lagrange Dual Function

\begin{equation} g\qty(\lambda, v) = \text{inf}_{x \in \mathcal{D}} L\qty(x,\lambda, v) = \text{inf}_{x \in \mathcal{D}} \qty (f_{0} \qty(x) + \sum_{i=1}^{m} \lambda_{i} f_{i}\qty(x) + \sum_{i=1}^{p} v_{i} h_{i}\qty(x)) \end{equation}

where \(\text{inf}\) is the infinimum i.e. the minimum.

• \(g\) is concave: since the function inside is affine in \(\lambda, v\).
• lower bound property: if \(\lambda \succeq 0\), then \(g\qty(\lambda, v) \leq p^{*}\) for all \(\lambda, v\) where \(p^{*}\) is the optimal objective