1
$\begingroup$

I'm trying to establish the existance of $u \in K \subset V$, a closed convex subset of vector space with an inner product, such that for a fixed $q \in V$: $$(u-q,v-u) \geq 0 \quad \forall v \in K$$ The proof I'm reading proceeds as follows:

Note that the inequality holds iff $\|u-q\| \leq \|v-q\|$. Since $K$ is a closed convex subset, there exists a unique element of $K$ that minimizes $\|v-q\|$, namely $u = P_Kq$ where $P_K$ is the projection of $q$ onto $K$.

This was a bit terse for me. Why does the inequality hold? From what fact does $u = P_Kq$ follow?

$\endgroup$
  • 2
    $\begingroup$ Puh, what is $q$? $\endgroup$ – amsmath Mar 24 at 18:52
  • $\begingroup$ my bad $q \in V$ $\endgroup$ – yoshi Mar 24 at 19:03
  • $\begingroup$ You should note that $V$ has to be complete, otherwise the projection might not exist. $\endgroup$ – gerw Mar 25 at 7:10
1
$\begingroup$

There's an error in the first statement of the proof. The variational inequality proves the inequality in norms, but the converse simply doesn't hold. For example, in $\Bbb{R}^2$ under the dot product, take $u = (0, 0)$, $v = (0, 3)$, and $q = (1, 1)$. Then $$\|u - q\|^2 = 2 \le 5 = \|v - q\|^2,$$ but $$\langle u - q, v - u \rangle = (-1, -1) \cdot (0, 3) = -3 < 0.$$ I suggest finding another proof of this inequality.

But, as for your second question, if you can show that $\|u - q\| \le \|v - q\|$ for all $v \in K$ (and where $u$ is assumed to be in $K$), then you've found a point $u \in K$ that is of minimal distance from $q$. This, by definition, makes $u$ the metric projection of $q$ onto $K$.

EDIT: Actually, I have a proof of this inequality that I wrote up on hand:

Theorem: Suppose $X$ is a real Hilbert space, and $C$ is closed, non-empty, and convex. Let $x \in X$ and $z \in C$. Then, $$\langle x - z, c - z \rangle \le 0 \quad \forall \, c \in C$$ if and only if $z = p_C(x)$.

Proof: Suppose $z, c \in C$, with $z \neq c$. Let $f : \mathbb{R} \to \mathbb{R}$ be defined by \begin{align*} f(\lambda) &= \|x - \lambda c - (1 - \lambda)z\|^2 - \|x - z\|^2 \\ &= 2 \lambda \langle x - z, z - c \rangle + \lambda^2 \|z - c\|^2. \end{align*} Note that this is a convex quadratic in $\lambda$.

Suppose that $z = p_C(x)$. When $\lambda \in [0, 1]$, we have $\lambda c + (1 - \lambda)z \in C$, hence $f(\lambda) \ge 0 = f(0)$. The minimum value of $f$ must be achieved at some $\lambda^* \le 0$. Thus, $$0 \ge \lambda^* = \frac{-\langle x - z, z - c \rangle}{\|z - c\|^2} \iff \langle x - z, c - z \rangle \le 0.$$ Note that the final inequality also holds for when $c = z = p_C(x)$.

Conversely, suppose $z \in C$ such that $\langle x - z, c - z \rangle \le 0$ for all $c \in C$. Therefore, when $c \neq z$, $\lambda^* \le 0$. This implies that $f$ is increasing on the interval $[0, 1]$. Hence, $$\|x - c\| = f(1) \ge f(0) = \|x - z\|.$$ As this holds for arbitrary $c \in C$, we have $z = p_C(x)$.

$\endgroup$
  • 1
    $\begingroup$ What is $K$ in your example? $\endgroup$ – amsmath Mar 24 at 19:27
  • $\begingroup$ $K$ is the closed, non-empty, convex set onto which we are projecting, as in the question. $\endgroup$ – Theo Bendit Mar 24 at 19:28
  • $\begingroup$ You should specify it in your example. Otherwise it is incomplete. $\endgroup$ – amsmath Mar 24 at 19:29
  • $\begingroup$ @amsmath Actually, in my counterexample, there is no such $K$ (I thought you were referring to the second paragraph). My point was that the two inequalities were not equivalent; in particular, if the OP was trying to manipulate one inequality into the other, they were not going to succeed. $\endgroup$ – Theo Bendit Mar 24 at 20:03
  • $\begingroup$ Of course they are not equivalent. But the points $u$ and $v$ are supposed to be in a closed convex set. However, in your example you can just choose the segment from $u$ to $v$ as $K$. Since one always can do that, your counterexample is actually valid without specifying $K$. $\endgroup$ – amsmath Mar 24 at 21:02
1
$\begingroup$

The statement is incorrect. Consider $V = \mathbb R^2$ and $K = \overline{B}_1(0)$, $u=(0,0)$, $v=(\epsilon,1-\epsilon)$ for some small $\epsilon > 0$ and $q = (2,0)$. Then $\|u-q\|\le\|v-q\|$ and $(u-q,v-u) = -2\epsilon < 0$.

$\endgroup$
1
$\begingroup$

I think the proof is missing an important detail: What we actually have is that for $u \in K$ and $q \in V$ the statement $$ (u - q, v - u ) \ge 0 \qquad \forall v \in K$$ is equivalent to $$ \|u - q \| \le \| v - q \| \qquad \forall v \in K.$$

The proof is given in the answer by Theo Bendit.

The second statement is just $u = \operatorname{proj}_K(q)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.