This is part (b) of exercise 3.28 from Boyd & Vandenberghe's Convex Optimization:
Let $f:\mathbb{R}^n \to \mathbb{R}$ be a closed convex function (i.e. $\textbf{epi}f$ is closed). Define $\tilde{f} : \mathbb{R}^n \to \mathbb{R}$ as the pointwise supremum of all affine functions that are global underestimators of $f$: $$\tilde{f}(x) = \sup\left\{g(x) \mid g\text{ affine, } g(z)\leq f(z) \text{ for all } z \right\}$$ Prove that $f=\tilde{f}$.
If $f$ is not assumed closed, the result holds for all $x \in \textbf{int }\textbf{dom}f$. A proof of the special case when $\textbf{dom}f = \mathbb{R}^n$ can be found on page 83 and the general case is almost the same. When $f$ is assumed closed, the solution manual (which I am not going to link here as it is not provided officially by the authors) presents a very convoluted, one-page argument. I think I came up with a much simpler argument but I would like to know if there is a flaw:
My proof relies on the strict separation theorem of a point and a closed convex set (Example 2.20 in the book). Let $\varepsilon > 0$. The point $(x, f(x)-\varepsilon)$ is not in $\textbf{epi}f$ so there exists $(a,b)\neq (0,0)$ such that
$$\begin{bmatrix}a \\ b\end{bmatrix}^T\begin{bmatrix}x \\ f(x)-\varepsilon\end{bmatrix} < \begin{bmatrix}a \\ b\end{bmatrix}^T\begin{bmatrix}z \\ t\end{bmatrix}$$
for all $(z, t) \in \textbf{epi}f$. By noticing that $(z,t)\in \textbf{epi}f \Longleftrightarrow t = f(z)+s$ for some $s\geq 0$ we can rewrite the above as
$$a^T(x-z) + b(f(x)-f(z)-s-\varepsilon) < 0 \quad \forall \, z\in \textbf{dom}f, s\geq 0$$
Since $s$ can be arbitrarily large we must have $b\geq 0$ and if $b=0$ we would have $a^T(x-z) < 0$ for all $z\in \textbf{dom}f$ which cannot hold for $z=x$, so $b>0$. Dividing by $b$ and setting $s=0$ we get
$$g_{\varepsilon}(z) = (a/b)^T (x-z) + f(x)-\varepsilon < f(z)\quad \forall\,z\in \textbf{dom}f$$
and by definition (since $g_\varepsilon$ is affine) $\tilde{f}(x)\geq g_\varepsilon(x)=f(x)-\varepsilon$. Since $\varepsilon$ is arbitrary we have $\tilde{f}(x)\geq f(x)$. The reverse inequality is obvious so $f=\tilde{f}$.
Is this proof valid? If yes, can it be improved further?
Best Answer
Some suggestions to improve the proof: You need to say that $x\in dom \ f$. The proof of $b\ne 0$ is unnecessarily complicated. In the inequality from separation, one can set $z:=x$, $s:=0$ directly to get $b(-\epsilon)<0$, hence $b>0$.