8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think your proof is good. In statement Our assumption implies ... it's better to add for a $\lambda_0\in\mathbb{R}$. $\endgroup$ – Nosrati Jan 19 '17 at 21:23
  • $\begingroup$ @MyGlasses thanks. I added your statement, although since I'm working with convex sets, I restricted lambda to the unit interval. $\endgroup$ – user408433 Jan 19 '17 at 21:25
  • 1
    $\begingroup$ No, This $\lambda$ is $\exists\lambda$ which $0<\lambda<1$. $\endgroup$ – Nosrati Jan 19 '17 at 21:27
  • $\begingroup$ @MyGlasses Oh...yes! Thanks! It wont be true for ALL lambdas. $\endgroup$ – user408433 Jan 19 '17 at 21:28
  • $\begingroup$ I can't remember on which thread, but this question has already been asked (and answered) here on SE in the past... $\endgroup$ – dohmatob Jan 20 '17 at 8:54
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! Your approach is certainly more succinct. $\endgroup$ – user408433 Jun 17 '17 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy