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

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, \left(\lambda, v\right) \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:

where the function is finite g\left(\lambda,v\right) = -b^{T}v IFF A^{T}v - \lambda + c = 0. Thus we can write with explicitly—

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

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:

if its strictly feasible, such that there’s an x \in \text{interior } \mathcal{D} with f_{i}\left(x\right) < 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}