Proof Using Shortest Distance

kaosAD

I encountered a problem in a book with a proof given. But I am a bit skeptic about it. I hope someone can help shed some light.

Let [tex]\{g_{i}\}[/tex] be a set of vectors and imagine a cone defined as [tex]K = \left\{v \,\bigg|\, v =-\sum_{i}\lambda_{i}g_{i}, \textup{ where }\lambda_{i}\geq 0 \ , \forall i \right\}[/tex].

Let [tex]f \notin K[/tex] and let [tex]u \in K[/tex] be the closest point to [tex]f[/tex]. Obviously [tex]u[/tex] is the projected point of [tex]f[/tex] onto [tex]K[/tex]. The objective is to prove that if [tex] d = u - f [/tex], then [tex]g_{i}^\top d \leq 0, \, \forall i[/tex]. (Note that [tex]d \neq 0[/tex].)

The proof given is by contradiction: Suppose that is not true, that is, [tex]\hat{g}_{i}^\top d = s_{i}[/tex] for some scalar [tex]s_{i} > 0, \, \forall i[/tex], where [tex]\hat{g}_{i}= g_{i}/\|g_{i}\|[/tex]. It is not difficult to see that [tex](u-s_{i}\hat{g}_{i}) \in K, \, \forall i[/tex], i.e., it remains in the cone even by small or large perturbation on the vector [tex]u[/tex]. Now, we shall show the perturbed point has smaller distance. Indeed this is the case since for any [tex]i[/tex],

[tex]
\begin{align*}
\|(u-s_{i}\hat{g}_{i})-f \|^{2} &= \|(u-f)-s_{i}\hat{g}_{i}\|^{2}= \|(u-f)\|^{2}-2 s_{i}\hat{g}_{i}^\top (u-f)+s_{i}^{2}\|\hat{g}_{i}\|^{2} \\
&= \|d\|-2s_{i}\hat{g}_{i}^\top d+s_{i}^{2} \\
&= \|d\|-2s_{i}^{2}+s_{i}^{2} \\
&= \|d\|-s_{i}^{2}\leq \|d\|,
\end{align*}
[/tex]

which contradicts with the assumption that [tex]u[/tex] is the nearest point in [tex]K[/tex] to [tex]f[/tex] -- done!!!.

All looks good, however if I let [tex]\hat{g}_{i}^\top d = t_{i}[/tex] for which the scalar [tex]t_{i}< 0,\, \forall i[/tex] but sufficiently close to 0 such that [tex](u-t_{i}\hat{g}_{i}) \in K[/tex] for any [tex]i[/tex], then using the same derivation I arrive at [tex]\|(u-t_{i}\hat{g}_{i})-f \|^{2}= \|d\|-t_{i}^{2}\leq \|d\|[/tex] too! This means it can contradict even for the case [tex]g_{i}^\top d < 0[/tex]. I now question the validity of this proof. I welcome your comment.

matt grime

Firstly, the negation of (for all i) is (there exists an i).

Secondly nothing states that the condition of g_i^Td<=0 for all i implies that this determines u uniquely. Thus given such a u with this condition, there may be points closer and lying in the cone. And if there isn't a closer point you won't be able to find things sufficiently close to zero.

kaosAD

You mean in the definition of K? But you can't change that.

Yes, I agree with you that nothing states about the implication but
since K is a cone which is closed and convex, [tex]u \in K[/tex] exists and must be a unique point.

matt grime

No, I do not mean the definition of K. You are doing a proof by contradiction, so what is the negation of the statement you're trying to prove? It is not what you wrote.

And you still haven't justified that in your 'second argument' that you can actually choose things as you claim you can. Just write down a simple example and work out where you go wrong. (For example there is nothing to stop you picking 1-d things, for example the cone {x : x=>1, x in R} and f=0, u=1)

kaosAD

Right you have the point there:there might not be any point [tex](u - t_i \hat{g}_i) \in K[/tex] such that it satisfies [tex]\hat{g}^\top d = t_i < 0[/tex]. This means the book cannot also claim that the point [tex](u - s_i \hat{g}_i) \in K[/tex] satisfyng [tex]\hat{g}^\top d = s_i > 0[/tex] always exist.

matt grime

It can because of the definition of K. (I admit I've not thought to carefully about this or your attempted counter example, but it is clear that what the line of argument is approximately: that all things are greater than or equal to zero, so if something is not strictly negative, then it is positive, and, say, 1/2 of a positive number is positive again, so in K as well. You really ought to work through an example to see what is going on. It is quite simple, I believe: if z is in K, then so is z+r_ig_i for any positive z_i by the definition of K.)