Is some convex combination of vectors in the same direction as all those vectors?

Question

Let $S$ be a finite set of vectors in $\mathbb{R}^d$. Suppose there exists a vector $w$ such that $a^Tw > 0$ for all $a ∈ S$. Then does there exist a vector $\widehat{w}$ such that $a^T\widehat{w} > 0$ for all $a ∈ S$ and $\widehat{w}$ is a convex combination of $S$?

Intuitively, it seems to me like this should be true. But I can't prove this or find a counterexample.

Answer 1

Interesting question! I think it is possible. My construction is not very linear algebraic, though!

The existence of your $w$ tells us that all of $S$ (and therefore all of the convex hull of $S$) lies strictly in one "half" of $\Bbb R^d$. Therefore, the convex hull of $S$ has a face that's closest to the origin (possibly a face with a large number of dimensions!). Then we can just use the orientation of this face to get a new vector $\hat w$, which defines a plane parallel to this face. By convexity, the convex hull of $S$ is still on one side of this plane.

More formally: The convex hull of $S$ is a compact set, because $S$ is finite. Therefore there is a point $x$ in the convex hull closest to the origin. We may write $x = \sum_i \lambda_i x_i$ as a convex combination of the elements $x_i$ of $S$ (so $0 \le \lambda_i \le 1$ and $\sum_i \lambda_i = 1$). Note that $x \ne 0$, because $w \cdot x > 0$ (by using this expression for $x$). I'll show that $x$ is the $\hat w$ that you seek.

Indeed, suppose there was some $y \in S$ with $x \cdot y \le 0$. This will be absurd because if we perturb a little bit in the direction of $y$, we'll get a new point in the convex hull closer to the origin. Indeed, consider the vector $x + \varepsilon (y - x)$ for $0 < \varepsilon \le 1$. Clearly this is still in the convex hull. But also,

\begin{align*} \lVert x + \varepsilon (y - x) \rVert^2 &= \lVert (1 - \varepsilon)x + \varepsilon y \rVert^2 \\ &= (1 - \varepsilon)^2 \lVert x \rVert^2 + \varepsilon^2 \lVert y \rVert^2 + 2 \varepsilon(1 - \varepsilon) x \cdot y \\ &= \lVert x \rVert^2 + \varepsilon((\varepsilon - 2)\lVert x \rVert^2 + \varepsilon\lVert y \rVert^2 + 2 (1 - \varepsilon) x \cdot y) \end{align*}

Taking $\varepsilon$ small enough, we see that the term $(\varepsilon - 2)\lVert x \rVert^2 + \varepsilon\lVert y \rVert^2 + 2 (1 - \varepsilon) x \cdot y$ will be negative (since it tends to $-2\lVert x \rVert^2 + 2x \cdot y < 0$ as $\varepsilon$ tends to $0$. This is where we need $x \ne 0$). So we've found something closer to $0$, which is a contradiction! So we had $x \cdot y > 0$ and we're done.

In the last part, equivalently we worked out that the derivative of the function $\varepsilon \mapsto \lVert x + \varepsilon (y - x) \rVert^2$ is negative at $\varepsilon = 0$.

The only part where we used the existence of $w$ was to guarantee $x \ne 0$, and indeed this answer shows that if $0$ is not in the convex hull of $S$, then there is such a vector $\hat w$ in the convex hull. Therefore in fact the existence of any such $w$ is equivalent to $0$ not being in the convex hull of $S$.

Answer 2

I found that we can prove this via the Perceptron Convergence Theorem. (The accepted answer is cleaner and more direct, but it's interesting that a very different proof exists.)

The Perceptron algorithm takes the a set $S$ of inputs and outputs a vector $w$ such that $a^Tw > 0$ for all $a ∈ S$, if such a $w$ exists. Here's the algorithm in python-like pseudocode:

w = 0
while ∃ a ∈ S such that aᵀw ≤ 0:
    w += a/‖a‖
return w

The output of this algorithm is always a non-negative linear combination of $S$, which can be scaled to give a convex combination of $S$.

Finally, it was proved by Block and Novikoff in 1962 that this algorithm always terminates. Here's a more readable proof I found in Section 5.2 of this essay:

Suppose a vector $w^*$ exists such that $a^Tw^* > 0$ for all $a ∈ S$. Without loss of generality, assume $\|w^*\| = 1$ and $\|a\| = 1$ for all $a ∈ S$. Let $$\nu := \min_{a ∈ S} a^Tw^*.$$

Then $\nu > 0$. In each iteration,

1. $w^Tw^*$ increases by at least $\nu$, since $(w + a)^Tw^* = w^Tw^* + a^Tw^* ≥ w^Tw^* + \nu$.
2. $\|w\|^2$ increases by at most 1, since $a^Tw ≤ 0$ and $\|w + a\|^2 = \|w\|^2 + 1 + 2a^Tw ≤ \|w\|^2 + 1$.

Hence, after $t$ iterations, we get (using the Cauchy-Schwarz inequality) $$\nu t ≤ w^Tw^* ≤ \|w\| ≤ \sqrt{t}.$$ Hence, the algorithm terminates in at most $1/\nu^2$ iterations.

Answer 3

Assume that $w = (0,0,\ldots, 0, 1)$. Then our vectors have the last component positive.

We may replace our set of vectors with a closed convex subset of the affine hyperplane $\mathcal{H} \colon x_d = 1$. Now we want a vector $v$ in $S$ such that $\langle v, w\rangle > 0$ for all $w \in S$.

It turns out that $v_0$ -- the closest point in $S$ to the origin-- satisfies it. Now, how do we get $v_0$? First we project $0$ on the $\mathcal{H}$, that is get the point $v_1\colon =(0,0,\ldots, 1)$.

1. If $v_1 \in S$, stop, you got your $v_0= v_1$.

2. If $v_1\not \in S$, get closest point in $S$ to $v_1$. This turns out to be $v_0$. Check again that the angles are $< \frac{\pi}{2}$. ( it is a calculation of dot products).

I think this is basically the method of Izaak van Dongen. The closest point $v_0\in S$ to a point $v_1 \in \mathcal{H}\backslash S$ satisfies: $\langle \overrightarrow{v_1, v_0}, \overrightarrow{v_0, w}\rangle > 0$ for all $w \in S$.

I think ( not sure) that the algorithm presented by Eklavya Sharma is something like this: try to find $v_0$. Initialize $v_0$ with any point from the finite set $S$. Now if for some $w\in S$ we have $\langle v_0, w \rangle < 0$, replace $v_0$ with the projection of $0$ onto the segment $v_0 w$. Continue with this procedure.