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

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.

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$$.

• +1 No reason to expect a linear algebra approach when the question is really about convex geometry. Mar 27 at 23:13
• @Ethan Bolker (Hello Ethan, we met in 1969 in Vancouver) Apr 16 at 9:47

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.

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.