duality

Lagrange Dual Problem

Given the Lagrange Dual Function, we can formulate the Lagrange Dual Problem:

\begin{align} \max_{\lambda, v}\quad & g\qty(\lambda,v) \\ \textrm{s.t.} \quad & \lambda \succeq 0 \end{align}

  • finds the best lower bound on \(p^{*}\), obtained from Lagrange dual function
  • a convex optimization problem, even if original primal fiction is not
  • dual optimal value denoted \(d^{*}\)

\(\lambda, v\) as “dual feasible” if \(\lambda \succeq 0, \qty(\lambda, v) \in \text{dom } g\).

Example Dual Problems

LPs

\begin{align} \min_{x}\quad & c^{T}x \\ \textrm{s.t.} \quad & Ax = b \\ & x \succeq x \end{align}

The dual problem is:

\begin{align} \max_{\lambda, v}\quad & g\qty(\lambda, v) \\ \textrm{s.t.} \quad & \lambda \succeq 0 \end{align}

where the function is finite \(g\qty(\lambda,v) = -b^{T}v\) IFF \(A^{T}v - \lambda + c = 0\).

Thus we can write with explicitly—

\begin{align} \max_{\lambda, v}\quad & -b^{T}v \\ \textrm{s.t.} \quad & A^{T}v + c \succeq 0 \end{align}

QPs

\begin{align} \min_{x}\quad & x^{T}Px \\ \textrm{s.t.} \quad & A x \preceq b \end{align}

Dual function:

\begin{equation} g\qty(\lambda) = inf_{x}\qty(x^{T}Px + \lambda^{T}\qty(Ax-b)) = -\frac{1}{4} \lambda^{T} AP^{-1}A^{T}\lambda - b^{T} \lambda \end{equation}

Strong and Weak Duality

Let \(d^{* }\) be the optima of the dual problem, and \(p^{*}\) of the optima of the original problem.

  • weak duality: usually true for non-convex problem, \(d^{*} \leq p^{*}\)
  • strong duality: usually true only for most convex problems, \(d^{*} = p^{*}\); conditions that guarantee this for convex problems called “constraint qualifications”

constraint qualifications

slater’s constraint satisfaction—

Strong duality holds for a convex problem:

\begin{align} \min_{x}\quad & f_{0}\qty(x) \\ \textrm{s.t.} \quad & f_{i}\qty(x) \leq 0, i = 1 \dots m \\ & Ax = b \end{align}

if its strictly feasible, such that there’s an \(x \in \text{interior } \mathcal{D}\) with \(f_{i}\qty(x) < 0, i = 1, …, m, Ax = b\).

  • also gaurantees that the dual optimum is attaned (if \(p^{*} > -\infty\))
  • can be sharpened: \(\text{int} \mathcal{D}\) with \(\text{reint} \mathcal{D}\)