3
$\begingroup$

I have been asked to prove that, given a convex set $C$, its intersection with a line is also convex.

From convexity definition, I have that $\forall x_1,x_2\in C, \alpha x_1+\beta x_2 \in C$ with $\alpha,\beta\ge0, \alpha+\beta=1$.

If I have $x_3,x_4 \in C \cap L$, every point in the line can be expressed as $x = x_4 + t (x_3-x_4)=tx_3+(1-t)x_4$. If the convex combination $\alpha x_3+(1-\alpha) x_4$ belongs to $C$, then it is trivial to show that, just by making $t=\alpha$, it also belongs to L, hence to $C \cap L$.

As always, I think I am oversimplifying or forgetting something. Is my proof right, or am I missing the crucial point?

Thanks in advance.

  • 1
    convex optimization tag was not good for this question, so I removed it.2011-09-30

3 Answers 3

1

That looks about right. If you want it slightly slicker, you can also observe that a line is itself a convex set and the intersection of convex sets is convex.

  • 0
    Yes. That was the point. Maybe I forgot to put that in the question. :-(2011-09-30
3

In general, the intersection of two convex sets is again a convex set. To do this, pick $x,y \in C_1 \cap C_2$ and $\alpha \in (0,1)$. Then by convexity of $C_1$ we have that $\alpha x +(1-\alpha)y \in C_1$. The same argument proves that $\alpha x +(1-\alpha)y \in C_2$ so $\alpha x +(1-\alpha)y \in C_1\cap C_2$ and by definition $C_1 \cap C_2$ is convex.

A line is a convex set, so the intersection of a line and a convex set is again convex.

3

You need to do just a little more work: it’s possible that $C$ and $L$ intersect in a single point; of course in that case $C\cap L$ is trivially convex, so let’s assume now that there are at least two distinct points in $C\cap L$, say $p$ and $q$. Then you can argue pretty much as you did, though it could be phrased more clearly.

Added: Here’s one slightly smoother way to phrase your argument.

Suppose that $p$ and $q$ are distinct points of $C\cap L$ and that $\alpha\in\mathbb{R}$ satisfies $0\le \alpha \le 1$; we must show that $\alpha p + (1-\alpha)q \in C\cap L$. Certainly $\alpha p + (1-\alpha)q \in C$, since $p,q\in C$ and $C$ is convex. Moreover, we know that $L = \{tp+(1-t)q:t\in\mathbb{R}\}$, so $\alpha p + (1-\alpha)q \in L$: just take $t=\alpha$. Thus, $\alpha p + (1-\alpha)q \in C\cap L$, as desired, and $C\cap L$ is convex.

  • 0
    Wow! That was a great example. I can see the difference now. Thank you very much.2011-09-30