# Minima of two convex functions that are “close” to each other

Consider two convex functions $f_1 : \mathbb{R}^n \to \mathbb{R}$ and $f_2 : \mathbb{R}^n \to \mathbb{R}$ such that

$\hspace{2cm} |f_1(x) - f_2(x)| \leq \epsilon \hspace{2cm} \forall x \in \mathbb{R}^n \hspace{2cm} - (1)$

Let the minimum of $f_1(x)$ and $f_2(x)$ be $x_1^*$ and $x_2^*$ respectively.

The question here is to find out what can we say about their minima. I found out a possible answer which I have written down as the claim below and I have provided a proof for the same.

I want to know if the proof makes sense or if there can be other better relations between the two minima. Any help in this regard is greatly appreciated! Thanks in advance.

Claim: $f_2(x_2^*)$, which is the minimum value of $f_2$, is such that:

$\hspace{2cm} f_1(x) - \epsilon \hspace{0.5cm} \leq \hspace{0.5cm} f_2(x_2^*) \hspace{0.5cm} \leq \hspace{0.5cm} f_1(x_1^*) + \epsilon$

Proof:

From $(1)$ we have, $\hspace{0.5cm} f_2(x) \hspace{0.5cm} \leq \hspace{0.5cm} f_1(x) + \epsilon$. Evaluating at $x_1^*$,

$\hspace{2cm} f_2(x_1^*) \hspace{0.5cm} \leq \hspace{0.5cm} f_1(x_1^*) + \epsilon \hspace{2cm} - (2)$

Consider $\tilde{x}$ such that

$\hspace{2cm} f_2(\tilde{x})\hspace{0.5cm} \geq \hspace{0.5cm} f_1({x_1^*}) + \epsilon \hspace{2cm} - (3)$

From $(2)$ and $(3)$,

$\hspace{2cm} f_2(\tilde{x}) \hspace{0.5cm} \geq \hspace{0.5cm} f_2(x_1^*)$

$\implies \tilde{x}$ is not the minima of $f_2$.

Therefore, $x_2^*$ is such that $f_2(x_2^*) \leq f_1(x_1^*) + \epsilon$. From $(1)$ we also have that $f_1(x) - \epsilon \leq f_2(x_2^*)$. Thus $x_2^*$ lies in the region defined in the claim.

Does this make sense? Is there a tighter relation between the two minima?

It will probably help to visualize the situation better if we consider the case $n = 1$. For this case the region given in the claim is shown in the attached image. enter image description here

• Did you mean $f_1(x_1^\ast)-\epsilon$ in the first term of your claim? – TZakrevskiy May 20 '16 at 11:02
• No, I meant $f_1(x) - \epsilon$. I understand it feels like it should be $x_1^*$, but it is $x$. – B.T May 20 '16 at 11:07
• Then where does this $x$ come from? Do you want the claim for $\forall x\in\Bbb R^n$? – TZakrevskiy May 20 '16 at 11:09
• Yes, $\forall x \in \mathbb{R}^n$. Kindly see the edited post for better visualization. – B.T May 20 '16 at 11:32

In your claim $x$ is still undefined, is it $\forall x$ or $\exists x$ or what?
$\hspace{2cm} f_1(x_2^*) - \epsilon \hspace{0.5cm} \leq \hspace{0.5cm} f_2(x_2^*) \hspace{0.5cm} \leq \hspace{0.5cm} f_1(x_1^*) + \epsilon$
because when you say "From $(1)$ we also have that $f_1(x) - \epsilon \leq f_2(x_2^*)$", you should really say "$f_1(x_2^*) - \epsilon \leq f_2(x_2^*)$" because in (1) both $f_1$ and $f_2$ are computed at the same point.