2

Let $f$ and $g$ be two strongly convex functions from a convex set $\mathcal{X}$ to $\mathbb{R}$, with minimum $x$ and $y$ respectively. Let us denote by $z$ the minimum of $f+g$, and by $\delta$ the distance $\lVert x-y\rVert$.

I would like to know if it is possible to prove that $\lVert x-z\rVert \leq \delta$ and $\lVert y-z\rVert < \delta$.

Rk:

  • This statement is true in one dimension (see here)

  • This statement is also true when $f$ and $g$ are two quadratic functions.

Etienne dM
  • 160
  • 1
    I think it would suffice to show that $z$ must reside in the convex hull of the minimizers of $f$ and $g$, right? – Zim Feb 25 '21 at 19:32
  • 1
    This is not always the case for dimension higher than 1. Take for example $f(x,y)=x^2+y^2$ and $g(x,y)=20(x-1)^2+(y-1)^2$. The minimum of $f$ is $z_f=(0, 0)$, and the minimum of $g$ is $z_g=(1, 1)$, but the minimum of $f+g$ is $(\frac{10}{11}, \frac{1}{2})$, which is not in the convex hull of ${x ,y}$. – Etienne dM Mar 01 '21 at 10:48
  • 1
    However, because it is true in one dimension, applying it on all coordinates, we get that $z_{f+g}$ will be in the hypercube defined by $z_f$ and $z_g$. That is to say, that for any $1\leq i \leq n$, $[\min(z_{f,i}, z_{g,i}) \leq z_{f+g, i} \leq \max(z_{f,i}, z_{f,j})]$, which solve the question. – Etienne dM Mar 01 '21 at 10:50
  • Interesting point! So, I suppose if we use the $|\cdot|_{\infty}$ metric then we are fine. What about others? – Zim Mar 01 '21 at 17:07
  • We are still fine with all of the $\lVert\cdot\rVert_p$ metrics, because $\left(\sum_{i=1}^n (z_{f,i}−z_{f+g,i})^p\right)^{(1/p)}\leq \left(\sum_{i=1}^n (z_{f,i}−z_{g,i})^p\right)^{(1/p)}=\delta$. – Etienne dM Mar 02 '21 at 18:21

1 Answers1

0

This result is true at least for any $p$-norm with $p\geq 1$. Indeed, we know that the result is true in one dimension (see here). Thus, the result is still true if we apply it to each of the coordinates of the functions $f$ and $g$.

In particular, we get: $$ \forall 1 \leq i \leq n,\ \min(x_i, y_i) \leq z_i \leq \max(x_i, y_i) $$

This shows us that $$ \lVert x-z \rVert_p = \left(\sum_{i=1}^n (x_i-z_i)^p\right)^{1/p} \leq \left(\sum_{i=1}^n (x_i-y_i)^p\right)^{1/p} = \lVert x_i - y_i \rVert_p =\delta $$ By symmetry, the same result holds for $y$: $\lVert y-z \rVert_p \leq \delta$.

Etienne dM
  • 160
  • 1
    From the counterexample in https://math.stackexchange.com/questions/3983368/the-minimum-of-the-sum-of-two-convex-functions, I think your statement about the range of $z_i$ is not true in general. – cicolus Jan 11 '22 at 08:17
  • Indeed, thank you very much, I will delete my answer. Sadly it is not a counter example to my question... – Etienne dM Jan 12 '22 at 09:09
  • 1
    You don't have to delete (and I didn't downvoted it either). I think it's still valuable to know that the OP's question is derivable from that particular assumption. – cicolus Jan 12 '22 at 21:51