# How to compare the minimums of two discrete convex functions?

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$$?

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.
• Thank you very much. I find my big mistake that $\Delta h$ is not increasing! Your answer reminds me. One more question, what if $h$ is not convex, are there any approaches to find bounds for minimum point of $h$? (I'm just curious about this. ) Jun 15, 2020 at 1:13