I have often heard people say that the set of integers is automatically a non-convex set.
This idea often comes up in Optimization – suppose there is some function you are trying to optimize (e.g. the objective function in the Travelling Salesman Problem). Suppose we know that this function is "convex" because it can be written as a linear function, and all linear functions are convex.(Is linear function convex or concave?)
In the Travelling Salesman Problem, we add "integer constraints" to this problem function (https://en.wikipedia.org/wiki/Travelling_salesman_problem#Miller%E2%80%93Tucker%E2%80%93Zemlin_formulation[23]) . Since we are adding integer constraints to this problem, and the set of integers is said to be non-convex – we are now dealing with the optimization of a convex function over a non-convex set.
I am told that any time we have integer constraints – this effectively turns the optimization problem into a non-convex problem: Similarly, a Convex Function over a Non-Convex Set is said to automatically become Non-Convex (I don't know if there is a mathematical for this fact, but it sounds logical).
My Question: I am still struggling to understand why any set of integers (this includes integer constraints) are automatically non-convex?
Again, I can understand why this might be on an informal level – in a set of integers, we can not go from the number 2 to any number between 3, except the number 3 itself. That is, we can not access the numbers 2.1, 2.11, 2.111, 2.21, 2.9999 etc. This creates a "break"/"gap" in the set which if we were to visualize would end up looking like a typical non-convex set:
Is my intuition correct about this? Or am I missing something?
Thanks!
Best Answer
You should return to the definition of convex sets.
We say set $C$ is a convex set if and only if for every $\lambda \in [0,1]$, $x\in C$, and $y \in C$, we have $$ \lambda x + (1-\lambda) y \in C. $$
For your example we have $C=\mathbb{N}$, then consider $x=1$, $y=2$, and $\lambda=1/2$. In this case $\lambda x + (1-\lambda)y =3/2$ which obviously is not a member of $C$.