1
$\begingroup$

Given any set of complex numbers (or 2D vectors) $x_1,x_2,...x_n$ and real numbers $w_1,w_2,...,w_n$ if we have $\bar{x} = \frac{w_1x_1 + w_2x_2 ... + w_nx_n}{w_1 + w_2 ... + w_n}$, we will find that $\bar{x}$ is inside of the convex hull formed by $x_1, x_2,..., x_n$.

I guess I can sort of see why this is true but I don't know how to prove it. My main problem right now is that although I can imagine what a conex hull would look like, I don't know how to mathematically define it to determine whether or not $\bar{x}$ is in fact, in there.

I feel like this ought to be an easy problem, but I'm having some difficulty figuring it out.

$\endgroup$
  • 1
    $\begingroup$ Your $\bar x$ is just a convex combination of your $x_i$. Hence, it belongs per definition to the convex hull (in your case: set of all convex combinations). $\endgroup$ – gerw Apr 11 '13 at 18:06
  • 1
    $\begingroup$ @gerw: I think you're implicitly assuming that the $w_i$ all have the same sign; that wasn't given. $\endgroup$ – joriki Apr 11 '13 at 18:33
  • $\begingroup$ Counter example: $x_1 = 0$ $x_2= 10 $, $w_1=-1$ $w_2=2$. You forgot to specify that the weight $w_i$ are all positive (or all negative). $\endgroup$ – leonbloy Apr 11 '13 at 18:44
1
$\begingroup$

The convex hull of vectors $x_i$ is the set of vectors of the form $\sum_i\lambda_ix_i$ with $\lambda_i\ge0$ and $\sum_i\lambda_i=1$. In your case, the coefficients are $\lambda_i=w_i/\sum_iw_i$, and their sum is $1$. The $\lambda_i$ will be non-negative if and only if the $w_i$ all have the same sign, so in that case $\bar x$ is in the convex hull. If the $w_i$ have different signs, it will be more difficult to determine whether $\bar x$ is in the convex hull, since it may or may not be possible to express it as a different linear combination with non-negative coefficients.

$\endgroup$
  • $\begingroup$ Thank you. Come to think of it, I only really need it for the case where all the w's are positive, so this pretty much covers it. $\endgroup$ – Rioghasarig Apr 11 '13 at 19:08
0
$\begingroup$

Assuming the weights are all positive, here is an answer to your question:

A convex set $C$ is a set for which the line connecting any two points $x,y\in C$ is contained in the set, i.e. $\lambda x + (1-\lambda) y\in C$ for all $0\leq \lambda \leq 1$.
If we could show that this implies $\sum_{i=1}^n \lambda_i x_i$ for $x_i\in C$ and $\sum_{i=1}^n \lambda_i=1$ then your question is answered. This can be accomplished using induction. It holds for $n=1,2$ by definition, so assume it holds for all $n<m$ then we write $$ \sum_{i=1}^m \lambda_i x_i = w_1 y_1 + w_2 y_2, $$ where we define $y_1 = \sum_{i=1}^{m-1} \frac{\lambda_i}{\sum_{i=1}^{m-1}\lambda_i} x_i$, $w_1 = \sum_{i=1}^{m-1}\lambda_i$, $y_2=x_m$, $w_2=\lambda_m$. By the induction hypothesis we have $y_1\in C$ and we also have $w_1+w_2=1$, so it follows by convexity that $ w_1 y_1 + w_2 y_2$ is also in $C$.

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