# Find a convex combination of scalars given a point within them.

I've been banging my head on this one all day! I'm going to do my best to explain the problem, but bear with me.

Given a set of numbers $S = \{X_1, X_2, \dots, X_n\}$ and a scalar $T$, where it is guaranteed that there is at least one member of $S$ that is less than $T$ and at least one member that's greater than $T$,

I'm looking for an algorithm to create a Convex Combination of these scalars that equals $T$.

For example, for the set $\{2,4\}$ and the scalar $3$, the answer is:

$$.5 \cdot 2 + .5 \cdot 4 = 3.$$

I believe in many cases there are infinite infinitely many solutions.

I'm looking for a generalized algorithm/formula to find these coefficients.

Additionally, I would like for the coefficient weights to be distributed as evenly as possible (of course while still adding up to 1.) For instance, for the set $\{1,2,4\}$ and the scalar $3$, a technically valid solution would be the same as the first example but with the coefficient for $1$ assigned a weight of 0 - but it would be prefferable to assign a non-zero weight. I may not be thinking through this last part very clearly :)

-
As even a distribution as possible of what? –  Qiaochu Yuan Nov 30 '12 at 2:33
Your intuition is correct. If S contains just two real numbers, one strictly less and one strictly more than T, then the convex combination is unique. Otherwise there will be infinitely many ways to do it (provided, as you state, at least one below and one above). –  hardmath Nov 30 '12 at 2:34
@QiaochuYuan - edited the question to clarify. For instance, I'd rather not assign a 0 weight to coefficients unless necessary. –  Aaron San Filippo Nov 30 '12 at 2:43
A possible algorithm I've been formulating in my head is to assign 1/N to all coefficient values, and then try and incrementally adjust until it's within some error threshold. But I'm hoping there's a cleaner solution! –  Aaron San Filippo Nov 30 '12 at 2:50
@Aaron: even by what criterion? –  Qiaochu Yuan Nov 30 '12 at 2:53

If $X_1<T<X_2$, then $T$ is a weighted average of $X_1$ and $X_2$ with weights $\dfrac{X_2-T}{X_2-X_1}$ and $\dfrac{T-X_1}{X_2-X_1}$, as can be checked by a bit of algebra.

Now suppose $X_3$ is also $>T$. Then $T$ is a weighted average of $X_1$ and $X_3$, and you can find the weights the same way.

Now take $40\%$ of the weight assigned to $X_2$ in the first case, and assign it to $X_2$, and $60\%$ of the weight assigned to $X_3$ in the second case and assign it to $X_3$ and let the weight assigned to $X_1$ be $40\%$ of the weight it got in the first case plus $60\%$ of the weight it got in the first case, and you've got another solution. And as with $40$ and $60$, so also with $41$ and $59$, and so on, and you've got infinitely many solutions.

But don't say "infinite solutions" if you mean "infinitely many solutions". "Infinite solutions" means "solutions, each one of which, by itself, is infinite".

Later note in response to comments:

Say you write $4$ as an average of $3$ and $5$ with weights $1/2$, $1/2$.

And you write $4$ as an average of $3$ and $7$ with weights $3/4$, $1/4$.

Then you have $4$ as a weighted average of $3$, $5$, and $7$ with weights $1/2,\ 1/2,\ 0$.

And you have $4$ as a weighted average of $3$, $5$, and $7$ with weights $3/4,\ 0,\ 1/4$.

So find a weighted average of $(1/2,\ 1/2,\ 0)$ and $(3/4,\ 0,\ 1/4)$. For example, $40\%$ of the first plus $60\%$ of the second is $(0.65,\ 0.2,\ 0.15)$.

Then you have $4$ as a weighted average of $3$, $5$, and $7$ with weights $0.65$, $0.2$, and $0.15$.

And you can come up with infinitely many other ways to write $4$ as a weighted average of $3$, $5$, and $7$ by using other weights than $0.4$ and $0.6$.

-
Michael, the first part of your explanation is very helpful to me, thanks. However you kind of lost me with the 60%/40% breakdown. Where are those values coming from? Good catch on the "infinite solutions" vs. "infinitely many" –  Aaron San Filippo Nov 30 '12 at 3:54
Say you've got $4$ as a weighted average of $3$ and $5$. The weights must be $1/2$ and $1/2$. Then write $4$ as a weighted average of $3$ and $7$. The weights must be $3/4$ and $1/4$. Now take $40\%$ of the weight assigned to $3$ in the first case and $60\%$ of the weight assigned to $3$ in the second case. You get $(0.4)(1/2)+(0.6)(3/4) = 0.65$. And take $40\%$ of the weight assigned to $5$ in the first case and (but not "plus") $60\%$ of the weight assigned to $7$ in the second case. You get $(0.4)(1/2)-0.2$ and (but not plus) $(0.6)(1/4)=0.15$. So then........ –  Michael Hardy Nov 30 '12 at 4:06
......you have three weights: $0.65$ assigned to $3$, $0.2$ assigned to $5$, and $0.15$ assigned to $7$. The three weights sum to $1$, and the weighted average is still $4$. So you have more than one way to write $4$ as a weighted average of $3$, $5$, and $7$. And you can find as many of those as there are numbers between $0\%$ and $100\%$. Thus infinitely many solutions. –  Michael Hardy Nov 30 '12 at 4:09

There are lots of functions you could use to define "distributed as evenly as possible."

For example, you could define "distributed as evenly as possible" to mean that you want to minimize the total squared deviation of the coefficients from their mean. This definition has the advantage of being particularly tractable analytically. If you go this route, and you let $c_1, c_2, \ldots, c_n$ be the coefficients, you would need to solve the problem \begin{align} \min \sum_{i=1}^n (c_i - \bar{c})^2& \\ \text{subject to } \sum_{i=1}^n c_i X_1 &= T, \\ \sum_{i=1}^n c_i &= 1, \\ c_i& \geq 0, \text{ for each } i \end{align}

This is a quadratic programming problem. There are plenty of common software packages (e.g., Matlab) out there that will easily solve a quadratic programming problem for you. Standard QP form requires that the objective function look like $$\min {\bf c}^T Q {\bf c}.$$ For your problem the form of $Q$ ends up being particularly nice: The diagonal elements of $Q$ are $\frac{n-1}{n}$, and the off-diagonal elements are all $-\frac{1}{n}$.

-

You try to prove the Caratheodory theorem for 1-dimensional space. The algorithm can be found in its proof. See wikipedia.

-

Denote the set of numbers $S$ by the column vector $x=[x_1,x_2,\ldots,x_N]^T$. Let us denote the set of numbers we are looking for by the column vector $a=[a_1,a_2,\ldots,a_N]^T$. Also, denote $b=[1,1,\ldots,1]^T$ Then the set of all solutions for your problem can be found by solving \begin{align} \min_a 0 \\ \text{subject to }&a^Tx=T \\ &a^Tb=1\\ &a\geq0 \end{align}

Let us say, you wish to give any particular weight to each of the solution, say the vector $w=[w_1,w_2,\ldots,w_N]^T$. Then the solution can be found by solving \begin{align} \min_a w^Ta \\ \text{subject to }&a^Tx=T \\ &a^Tb=1\\ &a\geq0 \end{align} Both of this problems are linear programming problems and hence should be solvable by simplex algorithm.

-

thanks for the detailed suggestions. I came up with a solution that uses some of your suggestions and thought it'd be best to post it as an answer. This uses much of Michael Hardy's suggestions and explanation, so big thanks there. Also thanks to those of you who suggested the MatLab solutions - in this case I wanted something I could code up easily and that would run efficiently in C#.

Ultimately, what I meant intuitively by "evenly distributed coefficients" was simply that I wanted to include contributions from every number in the set, as opposed to the trivial solution where you assign weights of 0 to everything but two of the numbers. I'm not sure what the name is for what my solution ultimately minimizes, but the end result is that all numbers greater than T have equal weights, and all numbers less than T have equal weights. This works out nicely for my purposes.

So here's the solution I used:

1. Divide the set into two parts: numbers less than T (let's call this set $L$) and those greater than T (let's call this set $G$)
2. Calculate the mean of L (call it $mL$) and the mean of G (call it $mG$)
3. Using these two averages as if they were the only two numbers in the set, calculate their weights (w1, w2) such that $mL*w1 + mG*w1 = T$. This is a straightforward linear interpolation as Michael Hardy's answer provided at the beginning.

4. Assign all values in $L$ a weight of $w1/(size of L)$, and all values in $G$ a weight of $w2/(size of G)$.

I can't prove why this works - but intuitively it makes sense, as you are simply distributing the weight needed to pull the overall weighted average towards T across all numbers on each side of T.

Again - thanks for all your help, I wouldn't have been able to do this without you folks! And please let me know if there's anything I should do differently as far as formatting etc.

-
The one more thing you should probably do is formally accept an answer as the "best" answer to your question. For instance, you could accept your own answer, since it's the solution you ended up using, or perhaps Michael's since you found it so helpful. –  Mike Spivey Nov 30 '12 at 17:55
Done. Thanks again for the help! –  Aaron San Filippo Nov 30 '12 at 19:06