I'm working through Convex Optimization by Boyd, and want to check my answer to the above question. Is the following reasoning correct?
Let $L$ be an arbitrary line.
For $\Rightarrow$:
Case 1: $C \cap L = \emptyset$
This is convex by definition.
Case 2:$C \cap L \neq \emptyset$
$x,y \in C$ and $x,y \in L \implies \lambda x + (1- \lambda)y \in C$ (by assumption) for $\lambda \in [0,1]$
Also, $\lambda x + (1- \lambda)y$ lies on the line segment between $x,y$, which is in $L$.
For $\Leftarrow$:
I decided to try proof by contradiction:
We are given that $C\cap L$ is convex for all lines. Assume $C$ is not convex.
Our assumption implies $\exists x,y \in C$ and $\lambda_0\in [0,1]: \lambda_0 x + (1-\lambda_0)y \notin C$. However, the line formed by $ax+(1-a)y,\;\;a\in \mathbb{R}$ will have a nonempty intersection with $C$ and yet the resulting set will not be convex (i.e, it will not contain $\lambda x + (1-\lambda)y$). Hence, we must negate our assumption, which means that $C$ must be convex.
I think this is correct as per this question:Poof- A function is convex iff it is convex when restricted to a any line that intersects its domain.
I also justified it by noting that if we let $A$ be the proposition "$C \cap L$ is convex for all lines $L$", and $B$ be the proposition "$C$ is convex" then what I showed was:
$A \wedge \neg B \implies \neg A$ which is equivalent to:
$\neg (A \wedge \neg B) \vee \neg A$ which (via DeMorgan's Laws) is $\neg A \vee B$.
This last statement can also be expressed $A \implies B$, hence I think I've shown the converse.
Best Answer
So your proof is correct, but a little confusing -- especially the second part. It's easier to do directly instead of via contradiction. A little simplification:
$\Leftarrow$: Let $x,y\in C$ and let $\lambda\in[0,1]$. We wish to prove $\lambda x + (1-\lambda)y\in C$.
Let $L$ be the line through $x$ and $y$. $x$ and $y$ are in $C\cap L$. By convexity of $C\cap L$, we have that $\lambda x + (1-\lambda)y\in C\cap L$ and hence clearly $\lambda x + (1-\lambda)y\in C$.