0
$\begingroup$

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)?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – copper.hat
    Dec 6, 2023 at 5:48
  • $\begingroup$ Uurgh, I missed a minus sign on the $(d-c)^T (u-d) < -{1 \over 2} \| d-c\|^2$. $\endgroup$
    – copper.hat
    Dec 6, 2023 at 16:49
  • $\begingroup$ 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. $\endgroup$
    – Jxson99
    Dec 6, 2023 at 23:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – copper.hat
    Dec 7, 2023 at 1:11

0

You must log in to answer this question.

Browse other questions tagged .