[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/duality.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- 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 & 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}\)