How to compare the minimums of two discrete convex functions?

Question

I have a question that troubled me for a long time.

If I have two convex discrete function $f(·)$ and $g(·)$ such that $f(·) \ge g(·)$. (may be not necessary?)

Let $x_1 = \text{argmin } f(·)$, and $x_2 = \text{argmin } g(·)$. How to prove that $x_1 \le x_2 $?

Actually, I want to find the upper bound of the minimum $x^*$ of $f(x)$ in order to reduce the enumeration scope to find a global minimum more efficiently.

One possible sufficient condition: if we prove $\Delta f(x) \ge \Delta g(x)$, then $x_1 \le x_2 $. (I hope it's true.)

Why the sufficient condition is correct? Or, there are other approaches to prove $x_1 \le x_2 $?

Answer 1

First a note: This is not a research level question. My answer is too long for a comment.

I think that by discrete function $h$ you mean that $h$ is defined on some $K := \{\ldots,k,k+1,k+2,\ldots\}$, possibly unbounded and that $\Delta h(x) = h(x+1)-h(x)$. Then $h$ is convex iff $\Delta h$ is not decreasing. To fix notation let $x^*$ be the largest minimum point of $h$. I now restrict to the case $K = \mathbb{N}_0$. Then $$x^* = \sup \{k \in K \colon \Delta h(k) \leq 0\}$$ if there is any $k \in \mathbb{N}$ with $\Delta h(k) > 0$. Otherwise $h$ may have a minimum point, but no largest. Now if $x_2 \in \mathbb{N}$ exists necessarily $\Delta f(x_2) \geq \Delta g(x_2) > 0$, from which $x_1 \leq x_2$ immediately follows. There are simple examples that this condition is not necessary.