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


1 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.

  • $\begingroup$ 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. ) $\endgroup$
    – Kurt. Z
    Jun 15, 2020 at 1:13
  • $\begingroup$ @Kurt Z: As far as I know: No. Convexity implies that local minima are global minima. There is a huge literature about finding global minima for the general case. $\endgroup$ Jun 15, 2020 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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