Encontrar una combinación convexa de escalares dado un punto dentro de ellos.

Question

He estado golpeando mi cabeza en esto todo el día! Voy a hacer mi mejor esfuerzo para explicar el problema, pero tengan paciencia conmigo.

Dado un conjunto de números de $S = \{X_1, X_2, \dots, X_n\}$ y un escalar $T$, donde se garantiza que no hay al menos un miembro de $S$ menos de lo que se $T$ y al menos un miembro que es mayor que $T$,

Estoy en busca de un algoritmo para crear una Combinación Convexa de estos escalares que es igual a $T$.

Por ejemplo, para el conjunto de $\{2,4\}$ y el escalar $3$, la respuesta es:

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

Creo que en muchos casos no son infinitos infinitamente muchas soluciones.

Estoy buscando un algoritmo generalizado/la fórmula para encontrar estos coeficientes.

Además, me gustaría que para el coeficiente de pesos para ser distribuidos uniformemente como sea posible (por supuesto sin dejar de añadir hasta 1.) Por ejemplo, para el conjunto de $\{1,2,4\}$ y el escalar $3$, una solución técnicamente válida sería el mismo que en el primer ejemplo, pero con el coeficiente de $1$ le asigna un peso de 0 - pero sería prefferable para asignar un valor distinto de cero peso. No puede ser de pensamiento a través de esta última parte muy claramente :)

Answer 1

Hay un montón de funciones que puede utilizar para definir "distribuido uniformemente como sea posible."

Por ejemplo, se podría definir "distribuido uniformemente como sea posible" para significar que usted desea reducir al mínimo el total del cuadrado de la desviación de los coeficientes a partir de su media. Esta definición tiene la ventaja de ser particularmente manejable analíticamente. Si usted va esta ruta, y dejas $c_1, c_2, \ldots, c_n$ ser los coeficientes, usted necesita para resolver el problema $$ \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}$$

Esta es una programación cuadrática problema. Hay un montón de común paquetes de software (por ejemplo, Matlab) que fácilmente resolver un problema de programación cuadrática para usted. Estándar QP formulario requiere que la función objetivo de parecerse a $$\min {\bf c}^T Q {\bf c}.$$ Para tu problema de la forma de $Q$ termina siendo particularmente agradable: los elementos de La diagonal de a$Q$$\frac{n-1}{n}$, y los elementos de la diagonal son todos los $-\frac{1}{n}$.

Answer 2

Intenta demostrar el teorema de Caratheodory por espacio de 1 dimensión. El algoritmo se puede encontrar en su prueba. Ver wikipedia.

Answer 3

Si $X_1<T<X_2$, $T$ es un promedio ponderado de las $X_1$ $X_2$ pesos $\dfrac{X_2-T}{X_2-X_1}$$\dfrac{T-X_1}{X_2-X_1}$, como se puede comprobar por un poco de álgebra.

Ahora supongamos $X_3$$>T$. A continuación, $T$ es un promedio ponderado de las $X_1$$X_3$, y usted puede encontrar los pesos de la misma manera.

Ahora tome $40\%$ de la ponderación asignada a $X_2$ en el primer caso, y asignarlo a $X_2$, e $60\%$ de la ponderación asignada a $X_3$ en el segundo caso y asignar a $X_3$ y dejar que el peso asignado a $X_1$ $40\%$ del peso se obtuvo en el primer caso, además de a $60\%$ el peso se obtuvo en el primer caso, y tienes otra solución. Y como con $40$$60$, así también con $41$$59$, y así sucesivamente, y usted tiene una infinidad de soluciones.

Pero no dicen "infinitas soluciones" si te refieres a "infinitamente muchas soluciones". "Infinitas soluciones" significa "soluciones, cada una de las cuales, por sí mismo, es infinito".

Nota posterior en respuesta a los comentarios:

Dicen que escribir $4$ como promedio de $3$ $5$ con pesas $1/2$, $1/2$.

Y escribes $4$ como promedio de $3$ $7$ con pesas $3/4$, $1/4$.

Entonces usted tiene $4$ como promedio ponderado de $3$, $5$, y $7$ pesos $1/2,\ 1/2,\ 0$.

Y usted tiene $4$ como promedio ponderado de $3$, $5$, y $7$ pesos $3/4,\ 0,\ 1/4$.

Así, encontramos un promedio ponderado de las $(1/2,\ 1/2,\ 0)$$(3/4,\ 0,\ 1/4)$. Por ejemplo, $40\%$ de la primera ventaja $60\%$ el segundo es $(0.65,\ 0.2,\ 0.15)$.

Entonces usted tiene $4$ como promedio ponderado de $3$, $5$, y $7$ con pesas $0.65$, $0.2$, y $0.15$.

Y usted puede venir para arriba con una infinidad de otras formas de escribir $4$ como promedio ponderado de $3$, $5$, y $7$ mediante el uso de otros pesos de $0.4$$0.6$.

Answer 4

Denota el conjunto de números de $S$ por el vector columna $x=[x_1,x_2,\ldots,x_N]^T$. Deje que nos denota el conjunto de números que estamos buscando por el vector columna $a=[a_1,a_2,\ldots,a_N]^T$. También, denotan $b=[1,1,\ldots,1]^T$, Entonces el conjunto de todas las soluciones para tu problema puede ser encontrada mediante la resolución de \begin{align} \min_a 0 \\ \text{subject to }&a^Tx=T \\ &a^Tb=1\\ &a\geq0 \end{align}

Digamos que usted desea dar ningún peso especial a cada uno de la solución, dicen que el vector $w=[w_1,w_2,\ldots,w_N]^T$. A continuación, la solución se puede encontrar mediante la resolución de \begin{align} \min_a w^Ta \\ \text{subject to }&a^Tx=T \\ &a^Tb=1\\ &a\geq0 \end{align} Ambos de estos problemas son problemas de programación lineal y, por tanto, deben ser resueltos por el algoritmo del simplex.

Answer 5

gracias por las sugerencias detalladas. Se me ocurrió una solución que utiliza algunas de sus sugerencias y pensaba que iba a ser el mejor post como respuesta. De esta forma, se utiliza de Michael Hardy sugerencias y explicación, así que muchas gracias hay. También gracias a aquellos de ustedes que propuso el MatLab soluciones - en este caso, quería algo que pudiera código fácilmente y que se ejecutan de manera eficiente en C#.

En última instancia, a lo que me refería de forma intuitiva por "distribuido uniformemente coeficientes" era, simplemente, que yo quería incluir las contribuciones de cada número en el conjunto, como contraposición a la solución trivial en la que asignar los pesos de 0 a todo, pero dos de los números. No estoy seguro de cuál es el nombre de lo que mi solución en última instancia, minimiza, pero el resultado final es que todos los números mayores que T tienen el mismo peso, y todos los números menores que T tienen el mismo peso. Esto funciona muy bien para mis propósitos.

Así que aquí está la solución que se usa:

1. Dividir el conjunto en dos partes: los números menores que T (vamos a llamar a este conjunto de $L$) y mayor que T (vamos a llamar a este conjunto de $G$)
2. Calcular la media de L ( $mL$ ) y el promedio de G ($mG$)

3. El uso de estas dos medias como si fueran las únicas dos números en el conjunto, calcular su peso (w1, w2) tal que $mL*w1 + mG*w1 = T$. Este es un simple interpolación lineal como Michael Hardy de la respuesta proporcionada por el principio.

4. Asignar todos los valores en $L$ un peso de $w1/(size of L)$, y todos los valores en $G$ un peso de $w2/(size of G)$.

Yo no puedo demostrar por qué esto funciona - pero, intuitivamente tiene sentido, ya que son simplemente distribuyendo el peso necesario para tirar de la general promedio ponderado hacia T a través de todos los números en cada lado de la T.

De nuevo gracias por toda su ayuda, yo no habría sido capaz de hacer esto sin ustedes amigos! Y por favor, hágamelo saber si hay algo que debo hacer de manera diferente, tan lejos como el formato etc.