Notes on duality

Given a standard form problem (not necessarily convex)
$$\begin{align*} \text{minimize} \quad  &f_0(x) \\ \text{subject to} \quad &f_i(x)\leq 0, &i=1,\cdots,m \\                             &h_i(x) = 0,    &i=1,\cdots,p \end{align*}$$
variable $x\in \mathbb{R}^n$, domain $\mathcal{D}$, optimal value $p^*$
with Lagrangian:
$$L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x)$$
and the (Lagrange) dual function:
$$g(\lambda,\nu) = \inf_{x\in \mathcal{D}} L(x,\lambda,\nu)$$
Properties:

• $g$ is concave over $\lambda, \nu$ since it is the infimum of a family of affine functions.
• Lower bound property: if $\lambda \succeq 0$ then $g(\lambda,\nu) \leq p^*$

since, if $\tilde{x}$ is feasible and $\lambda \succeq 0$, then
$$g(\lambda,\nu) = \inf_{x\in \mathcal{D}} L(x,\lambda,\nu) \leq L(\tilde{x}, \lambda, \nu) \leq f_0(\tilde{x})$$ minimizing over all feasible $\tilde{x}$ gives $g(\lambda,\nu) \leq p^*$

Lagrange dual and conjugate function

Given an optimization problem with linear inequality and equality constraints
$$\begin{align*}      \text{minimize}\quad &f_0(x) \\      \text{subject to}\quad &Ax\preceq b \\                                  &Cx=d. \end{align*}$$
Using the definition of $f^* = \sup_{x\in \text{dom }f} (y^T x - f(x))$, we can write the dual function as:
$$\begin{align*}     g(\lambda,\nu)\quad &= \quad \underset{x}{\inf} (f_0(x) + \lambda^T (Ax-b) + \nu^T(Cx=d)) \\                              &= \quad -b^T \lambda - d^T \nu + \underset{x}{\inf} (f_0(x) + (A^T \lambda + C^T \nu)^T x)\\                              &= \quad -b^T \lambda - d^T \nu - f^* (-A^T \lambda - C^T \nu) \end{align*}$$ with domain
$$\text{dom }g = \{ (\lambda,\nu) \;|\; -A^T \lambda - C^T \nu \in \text{dom } f_0^* \}$$

• simplifies derivation of dual if conjugate of $f_0$ is known

The dual problem (finding the greatest lower bound for the primal problem)
$$\begin{align*}     \text{maximize}\quad &g(\lambda,\nu) \\     \text{subject to}\quad  &\lambda \succeq 0 \end{align*}$$

• a convex optimization problem; optimal value denoted $d^*$
• $\lambda,\nu$ are dual feasible if $\lambda \succeq 0, (\lambda,\nu)\in \text{dom }g$

Weak duality: $d^* \leq p^*$

• always holds (for convex and nonconvex problems)
• can be used to find lower bounds for difficult problems

Strong duality: $d^* = p^*$ (zero duality gap)

• does not hold in general
• (usually) holds for convex problems
• constraint qualifications assert conditions that guarantee strong duality in convex problems (e.g. Slater's constraint qualification)