Minimising a convex set. Is set of solutions convex?

Question

We are minimising a convex function on a non-empty set defined by linear constraints (equalities and inequalities). $X^O$ is the set of all optimal solutions and we assume it is non-empty. Is it true that $X^O$ is a convex set?

I think it is not as for example in the case of the function $f(x)=x^2$ defined on $X=(-\infty, -1]\cup[1,\infty)$ we have got minimas at $x=-1$ and $x=1$, however, clearly this set is not convex. Am I right and is my example correct? Is such function defined in such a way convex?

Answer 1

The statement is true.

As mentioned in the comments, your example constraint set cannot be generated by an intersection of linear constraints. The intersection of linear constraints must be a convex set:

• A linear inequality is a half-space which is a convex set.
• A linear equality is a hyperplane which is also convex.
• The intersection of convex sets is convex.

The minimizers of a convex function on a convex set are a convex set since the lower contour set of a convex function is convex.

Answer 2

In general, consider minimizing a convex function $f$ on a convex set $C$. Let $\mathcal M \subseteq C$ be the set of minimizers. Choose any $(a, b, t) \in \mathcal M^2 \times [0, 1]$. Then for any $x \in C$, we have

$$f(ta + (1-t)b) \le tf(a) + (1-t)f(b) \le tf(x) + (1-t)f(x) = f(x),$$ and so $ta + (1-t)b$ is a minimizer of $f$. Also, by convexity of $C$, we have $ta + (1-t)b \in C$, and so $ta + (1-t)b \in \mathcal M$. We conclude that $\mathcal M$ is indeed convex.