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$


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

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

I would write this as a comment but I don't have enough reputation.

In your claim $x$ is still undefined, is it $\forall x$ or $\exists x$ or what?

I think your claim should be:

$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.