Duality

For any optimization problem, there is an associated dual problem, for which the original problem is called the primal problem.

$$ \begin{align*} \min_{x \in \R^n} \space & f_0(x) \\ \text{subject to} \space & f_i(x) \le 0, \space i \in [m] \\ & h_j(x) = 0, \space j \in [k] \end{align*} \space \xleftrightarrow{\hspace{15pt}} \space \begin{align*} \max_{\lambda \in \R^m, \space \mu \in \R^k} \space & d(\lambda, \mu) \\ \text{subject to} \space & \lambda \geq 0 \\ & \end{align*} \text{ w/ } d := \min_{x\in \R^n} L(x, \cdot , \cdot) $$

The dual problem comes up because of the fact that the minimum value of the Lagrangian for any pair $(\lambda, \mu)$ is a lower bound for the optimal objective value. Taking the maximum of these minimum values finds the tightest lower bound obtainable from the Lagrangian.

Duality Gap. The duality gap refers to how tight this bound is and is defined as $p^* - d^*.$

Duality Gap. The duality gap refers to how tight this bound is and is defined as $p^* - d^*.$

Since $d$ is the minimum of an affine function in $\lambda$ and $\mu$, it is thus a concave function. This means that any arbitrary optimization problem has a convex dual problem (if we negate $d$).

Weak Duality. The optimal objective value of the dual is always at least the optimal objective value of the primal.

$$ p^* - d^* \geq 0 $$

Proof </aside>

Duality in Convex Optimization

Convexity and Slater’s Condition implies Strong Duality. For any convex problem for which Slater’s condition holds, the optimal objective values of the dual and primal agree.

$$ p^* - d^* = 0 $$

This condition is called strong duality.

</aside>

Convexity and Slater’s Condition implies Solution through KKT. For any convex problem for which Slater’s condition holds, $x^$ and $(\lambda ^, \mu ^)$ are solutions to the primal and dual, respectively, if and only if $(x^, \lambda ^, \mu ^)$ is a solution to KKT on the primal.

</aside>

Duality in Programs

Dual of an LP is LP.

Proof </aside>

Feasible LPs have Strong Duality. This follows from the fact that LPs have only affine constraints, so Slater’s condition follows from feasibility.

</aside>

Dual of a QP is QP.

Proof </aside>