---
title: "duality"
type: concept
source: https://www.jemoka.com/posts/kbhduality/
confidence: high
status: active
---

Lagrange Dual Problem Given the Lagrange Dual Function, we can formulate the Lagrange Dual Problem:
\begin{align} \max_{\lambda, v}\quad &amp; g\qty(\lambda,v) \\ \textrm{s.t.} \quad &amp; \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 &ldquo;dual feasible&rdquo; if \(\lambda \succeq 0, \qty(\lambda, v) \in \text{dom } g\).
Example Dual Problems LPs \begin{align} \min_{x}\quad &amp; c^{T}x \\ \textrm{s.t.} \quad &amp; Ax = b \\ &amp; x \succeq x \end{align}
The dual problem is:
\begin{align} \max_{\lambda, v}\quad &amp; g\qty(\lambda, v) \\ \textrm{s.t.} \quad &amp; \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&mdash;
\begin{align} \max_{\lambda, v}\quad &amp; -b^{T}v \\ \textrm{s.t.} \quad &amp; A^{T}v + c \succeq 0 \end{align}
QPs \begin{align} \min_{x}\quad &amp; x^{T}Px \\ \textrm{s.t.} \quad &amp; 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 &ldquo;constraint qualifications&rdquo; constraint qualifications slater&rsquo;s constraint satisfaction&mdash;
Strong duality holds for a convex problem:
\begin{align} \min_{x}\quad &amp; f_{0}\qty(x) \\ \textrm{s.t.} \quad &amp; f_{i}\qty(x) \leq 0, i = 1 \dots m \\ &amp; Ax = b \end{align}
if its strictly feasible, such that there&rsquo;s an \(x \in \text{interior } \mathcal{D}\) with \(f_{i}\qty(x) &lt; 0, i = 1, &hellip;, m, Ax = b\).
also gaurantees that the dual optimum is attaned (if \(p^{*} &gt; -\infty\)) can be sharpened: \(\text{int} \mathcal{D}\) with \(\text{reint} \mathcal{D}\)
