I am looking for a reference/a hint to the following problem:


We are given $f\_1(x),f\_2(x)$ convex functions (say, on $\mathbb R^d$) such that $f\_1(x) \to\infty$ for $\|x\|\to\infty$. Also there is an $\alpha > 0$ such that $f\_1(x) - \alpha f\_2(x) \geq 0$.


A first consequence is that for any $\epsilon > 0$,
$$f\_1(x) - (\alpha - \epsilon)f\_2(x) \to \infty, \quad \|x\|\to \infty$$
because $f\_1(x) - (\alpha - \epsilon)f\_2(x) = \frac{\epsilon}{\alpha }f\_1(x) + \frac{a-\epsilon}{\alpha }(f\_1 - \alpha f\_2(x)) \geq \frac{\epsilon}{\alpha}f\_1(x) \to \infty$ for $\|x\|\to \infty$.


Now **my question** is whether (and maybe under which circumstances) it is possible to find a local approximation $g\_2(x)$ such that $|g\_2(x)-f\_2(x)| \to 0$ for $\|x\|\to \infty$ and


$$f\_1(x) - \beta g\_2(x)$$ is **convex** for some $\beta \in (0,\alpha]$.




---


The concrete example I have in mind is the following: $X = \mathbb R^d$ and $f\_1(x) = \sum\_{k=1}^d \frac{x\_k^2}{\sigma\_k^2}$ (a weighted squared $l^2$-norm) and $f\_2(x) = \|x\|\_1^2$ (the squared $l^1$-norm).


It can be shown that $f\_1(x) - \alpha f\_2(x) \geq 0$ for $\alpha \leq (\sum\_{k=1}^d \sigma\_k^2)^{-1}$.


Unfortunately, $f\_1(x) - \beta\cdot f\_2(x)$ is not convex for any $\beta\in (0,\alpha]$. My question in this specific example corresponds to finding a function $g\_2(x)$ such that $|g\_2(x)-f\_2(x)|$ is "asymptotically small", e.g. $g\_2(x) \geq f\_2(x)$ and $|g\_2(x)-f\_2(x)|\to 0$ for $\|x\|\_1\to\infty$. In addition for some $\beta \in (0,\alpha]$, I want


$$f\_1(x) -\beta f\_2(x)$$


to be **convex**. Note again that $f\_1(x)$ is convex, and I only need convexity of $f\_1 - \beta f\_2$ for an arbitrarily small $\beta \in (0,\alpha)$.




---


PS: I have thought a bit more about this problem and it looks like the following might work (at least in this specific setting):


$g\_2(x) := \left(\sum\_{k=1}^d (\sqrt{\sigma\_k^2 + |x\_k|^2} - \sigma\_k)\right)^2$



Convexification of difference of convex functions
$\newcommand\R{\mathbb R}$In general, the answer is no.


E.g., let $d=1$,
\begin{equation}
 f\_1(x):=\sum\_{j=1}^\infty(|x|-2j)\_+,\quad f\_2(x):=\sum\_{j=1}^\infty(|x|-2j-1)\_+,
\end{equation}
where $u\_+:=\max(0,u)$ --
so that $f\_1$ and $f\_2$ are convex functions, $f\_1(x)\to\infty$ as $|x|\to\infty$, and $f\_1\ge f\_2$.


However, for any $b\in(0,1)$, for the function
$$h:=f\_1-bf\_2,$$
and for any natural $n$, we have
\begin{equation}
 h(2n)-2h(2n+1)+h(2n+2)=-b<0.
\end{equation}
So, if a function $g\_2$ is such that $g\_2(x)-f\_2(x)\to0$ as $|x|\to\infty$, then for $g:=f\_1-bg\_2$ we have $g(x)-h(x)\to0$ as $|x|\to\infty$, whence
\begin{equation}
 g(2n)-2g(2n+1)+g(2n+2)<0
\end{equation}
for all large enough natural $n$.
So, $g$ is not convex for any $b\in(0,1)$.




---


In your concrete example, the answer is no as well. Indeed, let $\sigma\_k=1$ for all $k$, and let $x:=(-1,u,0,\dots,0)\in\R^d$, $y:=(1,u,0,\dots,0)\in\R^d$, and $z:=(x+y)/2=(0,u,0,\dots,0)$, with $u\to\infty$. Then
\begin{equation}
 f\_1(x)-2f\_1(z)+f\_1(y)=2(1+u^2)-2u^2=2,
\end{equation}
whereas
\begin{equation}
 f\_2(x)-2f\_2(z)+f\_2(y)=2(1+u)^2-2u^2\to\infty. 
\end{equation}
So, if $g\_2(v)-f\_2(v)\to0$ as $\|v\|\to\infty$, then for any $b\in(0,1)$ and for the function
$g:=f\_1-bg\_2$, we have $g(x)-2g(z)+g(y)\to-\infty$, so that $g$ is not convex for any $b\in(0,1)$.


