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)