# Optimization over union of convex sets

Let's say I would like to minimize a convex function $f(x)$ over a set $C$. $C$ is not convex but a union of a finite number of convex sets $C_i$: $C = C_1 \cup \dots \cup C_m$ where each $C_i$ is convex. Then can I minimize $f(x)$ over each $C_i$ and take the minimum of the results to obtain the minimum of $f(x)$ over $C$?

Also, is it true that any bounded set $C \subset \mathbb{R}^n$ can be written as a union of a finite number of convex sets?

-

The answer to the first question is basically yes. But you must be careful - you say "minimum" for example, rather than "infimum," but the minimum of a convex function over a convex set is not always attained. Consider, for example, minimizing $e^x$ over $(0,1)$. On the other hand, it is true that $$\inf_{C} ~f(x) = \min_{i=1, \ldots, m} ~~\inf_{C_i} ~~f(x).$$
The answer to the second question is no. Let $C$ be the set of rational numbers in $[0,1]$; then $C$ cannot be written as a union of finitely many convex sets. Indeed, a convex set in $R$ which is not a singleton is necessarily an interval; if your union of finitely many convex sets includes at least one interval, you've included some irrational numbers in there and the result can't equal $C$. The other case - when your union does not have any intervals, i.e., its all singletons - will not work either because $C$ has infinitely many elements while a finite union of singletons only has finitely many elements.
Great answer. The answer to the first question also applies to supremum: $\sup_C f(x) = \max_{i=1,\dots,m} \sup_{C_i} f(x)$. – Truong Aug 29 '11 at 2:26