# Help understanding the Separating Hyperplane theorem.

In Chapter 2, section 2.5.1, Boyd and Vandenberghe give a proof of the Separating Hyperplane theorem. They base their proof on two points, $$c \in \mathcal{C}$$ and $$d \in \mathcal{D}$$, that are the pair of points in the two convex sets that are the closest to each other.

The hyperplane that separates the sets is expressed as $$a^\top x = b$$. Then, they define $$a = d - c$$ and $$b = \frac{||d||_2^2 - ||c||_2^2}{2}$$

Then they set up to show that the function $$f(x) = a^\top x - b = (d - c)^\top(x - (1/2)(d-c))$$ is nonpositive on C and nonegative on D. They show that $$f$$ is nonnegative on D the following way:

Suppose there were a point $$u \in \mathcal{D}$$ for which $$f(u) = (d - c)^\top(u - (1/2)(d-c)) <0$$. We can express $$f(u)$$ as $$f(u) = (d - c)^\top (u - d + (1/2)(d-c)) = (d-c)^\top (u-d) + (1/2)||d-c||_2^2$$. That implies $$(d-c)^\top (u-d) < 0$$.

Then, they make the following statement: "We observe that $$\frac{d}{dt} ||d + t(u-d) - c||_2^2\Bigr|_{\substack{t=0}} = 2(d-c)^\top (u-d) <0$$

Up until the last equation I followed the proof with no issue. But I can't see the reason they had to introduce a derivative on $$t$$. Is that something natural to the proof or was that an artifice to help them show their point (which I missed)?

• I am a little surprised at how complex the presentation is, I had not looked at it closely before. First, $f(u) < 0$ means $(d-c)^T (u-d) < {1 \over 2} \| d-c\|^2$. Second, if you let $\phi(t) = \|d+t(u-d)\|^2$, then $\phi'(0) = 2(d-c)^T (u-d) <0$ and $\phi(0) = \|d-c\|^2$, and since for small $t>0$, $\phi(t) \approx \phi(0) + \phi'(0) t$, we can find some $t\in (0,1)$ such that $\phi(t) < \phi(0)$, which is same as the equation at the bottom of the page. Dec 6, 2023 at 5:48
• Uurgh, I missed a minus sign on the $(d-c)^T (u-d) < -{1 \over 2} \| d-c\|^2$. Dec 6, 2023 at 16:49
• Hello, copper.hat. Thank you for the contribution. I don't immediately follow your explanation (for instance, why would I come up with a function like $\phi(t)$?). I'll read it more closely. Should I eventually get it, I'll let you know in case you would like to post it as an answer. Dec 6, 2023 at 23:40
• They want to find a point in $D$ (on the line segment $[d,u]$) that has smaller norm. Some of these tricks are fairly standard in convex analysis. Dec 7, 2023 at 1:11