is weak duality – is satisfied by all pairs.

Most importantly, the duality gap acts as a certificate of approximation quality — the true optimum values ${\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}^*)$ and $-{\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}^*)$ (which are both unknown) will always lie within the (known) duality gap.

#### The Gap Function.

For the special case of differentiable function $f$, we can study a simpler duality gap $$\label{eq:gap}
{G}({\bm{x}}) := {\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}) + {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}({\bm{x}}))$$ purely defined as a function of ${\bm{x}}$, using the optimality relation , i.e. ${\bm{w}}({\bm{x}}) := \nabla f( A{\bm{x}})$.

#### The Wolfe-Gap Function.

For any constrained optimization problem defined over a bounded set ${\mathcal{C}}$ and ${\bm{x}}\in{\mathcal{C}}$, the Wolfe gap function (also known as Hearn gap or Frank-Wolfe gap) is defined as the difference of $f$ to the minimum of its linearization over the same domain. Formally, $$\label{eq:wolfe_gap}
{G_{\mathcal{C}}}({\bm{x}}) := \underset{{\bm{y}}\in {\mathcal{C}}}{\max}\; (A{\bm{x}}-A{\bm{y}})^\top\nabla f(A{\bm{x}}).$$ It is not hard to see that the convenient Wolfe gap function is a special case of our above defined general duality gap ${G}({\bm{x}}) := {\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}) + {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}({\bm{x}}))$, for $g$ being the indicator function of the constraint set ${\mathcal{C}}$, and ${\bm{w}}({\bm{x}}) := \nabla f(A{\bm{x}})$. For more details, see Appendix \[app:eq\_fw\_gd\], or also [@LacosteJulien:2013ue Appendix D].

Obtaining Information about the Optimal Points {#sec:info}
