Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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