# Approximate convex function by affine minorants with rational coefficients

Suppose $\varphi \colon \mathbb{R} \to \mathbb{R}$ is a nonlinear convex function. We know $\varphi$ can be approximated by affine minorants. That is \begin{align*} \varphi(x) = \{ ax + b \colon \varphi(x) \ge a x + b, (a, b) \in \mathbb{R}^2 \}. \end{align*} Now let $S = \{ (a, b) \in \mathbb{Q}^2 \colon \varphi(x) \ge a x + b \}$. In a proof in Durrett's 'Probablity: Theory and Examples', the claim is $\varphi(x) = \sup \{ ax + b \colon {(a, b) \in S}\}$.

My argument is: let $E = \{ (a, b) \in \mathbb{R}^2 \colon \varphi(x) \ge ax + b \}$ and let $F = \{ (a, b) \in \mathbb{Q}^2 \colon \varphi(x) \ge ax + b\}$. We know from convex analysis $\varphi(x) = \sup \{ax+b \colon (a, b)\in E\}$. Let $\psi(x) = \sup \{ ax + b \colon (a,b) \in F\}$. Clearly $\varphi(x) \ge \psi(x)$ for every $x$ since $F \subseteq E$. Intuitively, for every $(a,b) \in E$, we should be able to produce a sequence $(a_n, b_n) \to (a, b)$ but I don't have a way to claim that properly.

Could anyone help me on this or there is some other clever trick to claim this? Thanks. Another question is: could this be generalized to $\varphi : \mathbb{R}^n \to \mathbb{R}$, that is $\varphi(x) = \sup\{ a^T x + b \colon a, b \text{ with rational entries }\}$?

### Special case

Suppose $\varphi(x)=\max(ax+b, cx+d)$ where $a,b,c,d\in\mathbb{R}$ and $a < c$. Let $(x_0,y_0)$ be the point where the lines $y=ax+b$ and $y = cx+d$ intersect. Then any line of the form $$y = y_0 + k(x-x_0), \quad a<k<c \tag1$$ is a minorant of $\varphi$, and $\varphi$ is the supremum of these minorants. Moreover, it suffices to use a dense set of slopes $k$, e.g. rational $k$. Also, by subtracting an arbitrarily small amount from the line (1) we can make its constant coefficient rational. This proves the special case.

### General case

Suppose $\varphi:\mathbb{R}\to\mathbb{R}$ is a nonlinear convex function. We know that there exists $S\subset\mathbb{R}^2$ such that $\varphi(x)=\sup \{ax+b : (a,b)\in S\}$. If all slopes $a$ were equal, the function $\varphi$ would be linear, contrary to the assumption. Thus, there exist at least two elements $(a_1,b_1), (a_2, b_2)\in S$ with $a_1\ne a_2$.

Given $x^*\in \mathbb{R}$ and $\epsilon>0$, pick $(a,b)\in S$ such that $ax^*+b>\varphi(x^*) -\epsilon/2$. There exists $j\in \{1,2\}$ such that $a_j\ne a$. By the special case above, the function $\psi(x) := \max(ax+b, a_jx+b_j)$ is the supremum of its rational minorants. Hence, there exists $(a',b')\in\mathbb{Q}^2$ such that
$$a'x+b'\le \psi(x) \le \varphi(x),\quad \forall x\in\mathbb{R}$$ and $$a'x^* + b' > \psi(x^*) - \epsilon/2 \ge ax^*+b -\epsilon/2 > \varphi(x^*)-\epsilon$$ proving the claim.

### Multivariable case

It's no longer enough to assume $\varphi$ nonlinear: for example, $\varphi(x_1, x_2) = \sqrt{2}\,x_1 + x_2^2$ is not the supremum of its rational minorants, as it does not have any. I think the appropriate assumption is that $\varphi$ admits affine minorants with coefficients vectors that do not lie in any proper affine subspace of $\mathbb{R}^n$. In other words, there are $(n+1)$ coefficient vectors whose convex hull has nonempty interior point. The approach of 1-dimensional case generalizes to this setting.

For the Special Case, consider the maximum of $(n+1)$ affine functions with the affine independence property stated above. They will all meet at some $(x_0, y_0)\in \mathbb{R}^{n+1}$. Then consider hyperplanes with various slopes passing through this point, and note we have an open set from which to choose the coefficient vector.

The General Case is essentially the same as in one dimension.

• Your example is completely correct. Sorry, I forgot putting the condition "nonlinear". – user1101010 Dec 5 '17 at 0:38

A question related to this topic, $$\phi : \mathbb{R} \to \mathbb{R}$$ let $$K$$ a compact of $$\mathbb{R}^{2}$$ and $$\phi(x)=\sup\{ax+b, (a,b) \in K\}$$, is it possible to find the domain where $$\phi$$ is differentiable and also find the dérivative ?