Foros de matemática
22/08/2017, 06:10:40 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: LISTADO ACTUALIZADO DE CURSOS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Máximos de una partición  (Leído 232 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Quema
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.270


Ver Perfil
« : 20/07/2017, 04:28:35 pm »

Hola

Supongamos que tengo un vector de números reales [texx]x=(x_1,x_2,...,x_n)[/texx] y sea [texx]u(x))=v(x)[/texx] si [texx]x>0[/texx] siendo  [texx]v[/texx] una función contínua, creciente y cóncava y [texx]u(x)=-\lambda v(-x)[/texx] si [texx]x<0[/texx] con [texx]v(0)=0[/texx] y [texx]\lambda>0[/texx].

Supongamos que genero particiones de sumas de los elementos de este vector, cantidad que es igual al número de Bell. Para que se entienda voy a poner un ejemplo. Supongamos que tengo el vector [texx](x_1,x_2,x_3)[/texx] de ahí puedo formar cinco casos y debo determinar el mayor:

1) [texx]u(x_1+x_2+x_3)[/texx]
2) [texx]u(x_1+x_2)+u(x_3)[/texx]
3  [texx]u(x_2+x_3)+u(x_1)[/texx]
4) [texx]u(x_1+x_3)+u(x_2)[/texx]
5) [texx]u(x_1)+u(x_2)+u(x_3)[/texx]

Si todos los [texx]x_i[/texx] son positivos, claramente por concavidad de [texx]v[/texx] la opción 5) es la que da el mayor valor. El problema se presenta cuando hay algún valor negativo, ahí la opción máxima dependerá del valor de [texx]\lambda[/texx] y quedarán solamente dos casos.

Supongamos que tengo [texx](10,1,-2)[/texx] entonces claramente dependiendo del valor que tome [texx]\lambda[/texx] las opciones que quedan son la 1) y 4). Sin embargo, si tenemos el vector [texx](4,3,-5)[/texx] los dos vectores posibles son el 5) y el 1).

Yo quiero encontrar un algoritmo que me permita encontrar esos dos posibles resultados que dependerá del valor que toma el [texx]\lambda[/texx]. Yo creo que el algoritmo es como sigue (supondré que [texx]\displaystyle\sum_{i=1}^n{x_1>0}[/texx]:

1) Se trata de ir eliminando los elementos negativos del vector con el mayor de sus elementos, siempre y cuando quede un valor positivo o cero.
2) Y así sucesivamente.
3) Y los elementos negativos se suman entre sí.

Es decir, supongamos que tenemos un vector de cinco elementos, por ejemplo [texx](10,9,8,7,-5)[/texx]. Como tengo cinco elementos los casos a considerar serían 52 (número de Bell), pero aseguro que el máximo saldrá de considerar

[texx]u(10)+u(9)+u(8)+u(7)+u(-5)[/texx] o [texx]u(5)+u(9)+u(8)+u(7)[/texx], dependiendo del valor que tome [texx]\lambda[/texx], está bien? Y no necesitaría ni considerar el resto de los 50 casos.

Ahora supongamos que tengo [texx](10,9,8,7,-5-,10)[/texx] los casos posibles son 203, sin embargo, creo que el valor máximo estará entre [texx]u(10)+u(9)+u(8)+u(7)+u(-15)[/texx] y [texx]u(8)+u(7)+u(4)[/texx], dependiendo de nuevo del valor que tome [texx]\lambda=1.025[/texx]. Está bien este método? Una posible explicación?

Lo interesante es que siempre quedarán dos posibles soluciones y no tenemos que analizar el resto de las combinaciones.

Creo que el método para determinar estos vectores es el siguiente (supongo que [texx]\displaystyle\sum_{i=1}^n{x_i>0}[/texx]. Un vector surgirá de cancelar los valores máximos positivos con los valores mínimos negativos, hasta que no haya más valores negativos. El otro vector surgirá de simplemente juntar (sumar) los elementos negativos, sin tocar los elementos positivos. Me falta una prueba formal de esto.

Es decir, si tengo el vector original [texx](1,1,1,1,1,1,-2,-3)[/texx] se que el máximo será entre [texx]u(1)[/texx] y [texx]6u(1)+u(-5)[/texx], dependiendo del valor que tome [texx]\lambda[/texx].


Saludos



En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 39.369


Ver Perfil
« Respuesta #1 : 24/07/2017, 07:27:21 am »

Hola

 Veamos esta idea. Para cada vector [texx]X[/texx] sea [texx]X^+[/texx] su vector de términos positivos y [texx]X^-[/texx] su vector de términos negativos.

 Entonces (espero que se entienda el abuso de notación):
 
[texx] u(X)=v(X^+)-\lambda v(-X^-)[/texx]

 Entonces si tomamos [texx]\lambda[/texx] como parámetro para cada vector fijo [texx]X[/texx] lo anterior es la ecuación de una recta.

 Con la notación típica de rectas:

[texx] y=Ax+B con A=- v(-X^-) [/texx] y [texx]B=v(X^+)[/texx]

 En concreto para el vector [texx]P[/texx] que se obtiene eliminando todos los negativos como dices, la recta correspondiente es horizontal, es constante ya que [texx]v(-P^-)=0[/texx]. Y si no me equivoco es la forma de eliminar los negativos que maximiza la parte positiva.

 Para el vector [texx]Q[/texx] que se obtiene agrupando los negativos como dices, el valor de la recta cuando [texx]\lambda[/texx] es cero es el máximo posible.

 Estas dos cosas garantizan que para [texx]\lambda=0[/texx] el máximo se alcanza para el vector [texx]Q[/texx] y para [texx]\lambda[/texx] suficientemente grande el máximo se alcanza para el vector [texx]P[/texx]. Sea [texx]\lambda_0[/texx] el valor que hace que [texx]u(Q)[/texx] y [texx]u (P)[/texx] coincidan.

 Habría que probar que para cualquier otro vector [texx]X[/texx] el punto de corte de la recta [texx]u(Q)[/texx] con la recta [texx]u(X)[/texx] da un valor de [texx]\lambda[/texx] menor que el [texx]\lambda_0[/texx].

 Es decir:

[texx] \dfrac{v(P^+)-v(Q^+)}{v(P^-)}\geq \dfrac{v(X^+)-v(Q^+)}{v(X^-)}[/texx]

 Cuando escribí esto pensé que salía fácil, pero ahora no lo veo claro.

Saludos.
En línea
Quema
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.270


Ver Perfil
« Respuesta #2 : 24/07/2017, 09:36:24 am »

Hola

Me parece que hay que usar el hecho que [texx]u[/texx] es cóncava para valores positivos y convexa para valores negativos.

Por ejemplo, si tengo [texx](10,9,-5)[/texx] se que es mejor eliminar el valor negativo con el máximo valor positivo, pues

[texx]u(5)+u(9)>u(10)+u(4)[/texx] por concavidad de [texx]u[/texx] para valores positivos.

Saludos
En línea
Quema
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.270


Ver Perfil
« Respuesta #3 : 24/07/2017, 09:30:01 pm »

Hola

Sea [texx]x=(x_1,x_2,...,x_n)[/texx] el vector con elementos todos positivos o ceros obtenido sucesivamente de cancelar el máximo valor positivo y el mínimo valor negativo. Se puede probar (no?) que para un [texx]\lambda[/texx] grande ese vector es el que maximiza [texx]\displaystyle\sum_{i=1}^n{u(x_i)}[/texx], ahora queremos hallar un valor de [texx]\lambda[/texx] lo más grande posible. Llamemos a [texx]y=(y_1,y_2,...,y_n)[/texx] al poder decirlo de alguna forma al vector que le sigue en valor, con [texx]\displaystyle\sum_{i=1}^n{y_i}=\displaystyle\sum_{i=1}^n{x_i}[/texx] y con algunos elementos positivos [texx]y[/texx] y algunos negativos [texx]y_i^{-}[/texx]. Ese lambda será igual a

[texx]\displaystyle\frac{\displaystyle\sum_{i=1}^n{u(y_i^{+})-u(x_i))}}{\displaystyle\sum_{i=1}^n{u(y_i^{-})}}[/texx].

Debemos elegir un [texx]y[/texx] tal que [texx]\displaystyle\sum_{i=1}^n{u(y_i^{+})}[/texx] sea grande y que [texx]\displaystyle\sum_{i=1}^nu(y_i^{-})[/texx] sea chico. Como [texx]\displaystyle\sum_{i=1}^n{y_i}=\displaystyle\sum_{i=1}^n{x_i}[/texx] el candidato ideal es cuando los valores negativos se concentran en un solo valor y el resto de los valores positivos siguen como en el vector original.

Está bien?
En línea
Quema
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.270


Ver Perfil
« Respuesta #4 : 26/07/2017, 11:06:53 am »

Hola

Si [texx]N=3[/texx] y supongamos tenemos [texx]x=(x,y,z)[/texx] siendo [texx]x>0>y>z[/texx] con [texx]m=x+y+z>0[/texx] entonces sabemos que el mejor vector, para un determinado [texx]\lambda[/texx] será [texx](m,0,0)[/texx] y el mejor vector para un determinado [texx]\lambda[/texx] será [texx](x,y+z,0)[/texx], ahora planteo

[texx]\lambda(a)=\displaystyle\frac{u(a)-u(m)}{u(a-m)}[/texx] con [texx]m<a\leq{}x[/texx] y debo hallar el [texx]a[/texx] que maximiza esta función y como esta es creciente en [texx]a[/texx] se cumple que [texx]a=x[/texx] y por lo tanto nos da el vector [texx](x,y+z,0)[/texx] que es el que maximiza el [texx]\lambda[/texx]. No me queda claro cómo proceder cuando tengo más dimensiones. Intuitivamente pienso que para maximizar ese [texx]\lambda[/texx] debo dejarlos separados los valores positivos y tratar de minimizar los valores negativos que se da cuando se juntan.



Está bien?

Saludos
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 39.369


Ver Perfil
« Respuesta #5 : 27/07/2017, 06:28:40 am »

Hola

[texx]\lambda(a)=\displaystyle\frac{u(a)-u(m)}{u(a-m)}[/texx] con [texx]m<a\leq{}x[/texx] y debo hallar el [texx]a[/texx] que maximiza esta función y como esta es creciente en [texx]a[/texx] se cumple que [texx]a=x[/texx] y por lo tanto nos da el vector [texx](x,y+z,0)[/texx] que es el que maximiza el [texx]\lambda[/texx]. No me queda claro cómo proceder cuando tengo más dimensiones. Intuitivamente pienso que para maximizar ese [texx]\lambda[/texx] debo dejarlos separados los valores positivos y tratar de minimizar los valores negativos que se da cuando se juntan.

Me queda la duda de como justificas que esa función es creciente.

Saludos.
En línea
Quema
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.270


Ver Perfil
« Respuesta #6 : 27/07/2017, 08:52:28 am »

Hola

Lo he hecho gráficamente para una función potencia.

Saludos
En línea
Quema
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.270


Ver Perfil
« Respuesta #7 : 28/07/2017, 09:15:08 am »

Hola

Pero si [texx]u[/texx] es cóncava no se cumple que [texx]\displaystyle\frac{u'(x)}{u(x)}>\displaystyle\frac{u'(x-m)}{u(x-m)}[/texx] con [texx]m>0[/texx]?

Yo usé [texx]u(x)=x^b[/texx] con [texx]0<a<1[/texx] y [texx]\lambda(a)[/texx] es creciente si [texx]\displaystyle\frac{a}{m}>(\displaystyle\frac{a}{m})^b[/texx], que lo es pues [texx]a>m[/texx].


Saludos
En línea
Quema
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.270


Ver Perfil
« Respuesta #8 : 07/08/2017, 10:22:23 am »

Hola

Si defino

[texx]\lambda(y)=\displaystyle\frac{{u(y_i^{+})-u(a)}}{{u(y_i^{-})}}[/texx], siendo [texx]a[/texx] el vector con los elementos que quedan luego de eliminar el mayor elemento positivo con el menor elemento positivo. Debemos probar que el vector [texx]y[/texx] que surge de dejar los elementos positivos tal cual están en el vector original y los elementos negativos sumados, manteniendo la suma de todos los elementos iguales a los del vector original. Sea un vector cualquiera [texx]x[/texx] debemos probar que no puede obtenerse una [texx]\lambda(x)>\lambda(y)[/texx]. Es claro que si  [texx]\displaystyle\sum_{i=1}^n{y_i^+}=\displaystyle\sum_{i=1}^n{x_i^+}[/texx], pues [texx]u(y_i^+)[/texx] es el máximo valor que se puede obtener y además [texx]u(y_i^-)[/texx] es el mínimo valor que se puede obtener entonces [texx]\lambda(y)[/texx] será el máximo entre los vectores que cumplan [texx]\displaystyle\sum_{i=1}^n{y_i^+}=\displaystyle\sum_{i=1}^n{x_i^+}[/texx] y obviamente también se cumple que [texx]\displaystyle\sum_{i=1}^n{y_i^-}=\displaystyle\sum_{i=1}^n{x_i^-}[/texx].
Como [texx]u(y_i^+)[/texx] no se puede mejorar, el problema surge en el denominador, pues pueden ocurrir que [texx]u(y_i^-)>u(x_i^-)[/texx].

De todas formas el problema consiste en mostrar que

[texx]\displaystyle\frac{{(u(y_i^{+})-u(a))}}{{u(y_i^{-})}}>\displaystyle\frac{{(u(x_i^{+})-u(a))}}{{u(x_i^{-})}}[/texx]

que es equivalente a probar que

[texx]u(y_i^-)(u(a)-u(x_i^+))+u(x_i^-)(u(y_i^+)-u(a))>0[/texx]. Notemos que [texx]u(y_i^+)>u(a)[/texx], pero [texx]u(a)-u(x_i^+)[/texx] puede ser positivo o negativo.

El caso que interesa es cuando [texx]u(y_i^-)>u(x_i^-)>0[/texx] y [texx]u(a)<u(x_i^+)[/texx]...

Entonces?




Saludos












En línea
Quema
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.270


Ver Perfil
« Respuesta #9 : 09/08/2017, 10:03:52 am »

Hola

Voy a mejorar un poco la notación para aclarar bien la pregunta. Dado un vector de números reales [texx]x=(x_1,x_2,...,x_n)[/texx] con algunos elementos positivos y otros negativos, tal que [texx]\displaystyle\sum_{i=1}^n{x_i>0}[/texx], debo hallar de los subconjuntos que surgen de la partición de [texx]x[/texx] aquellos que maximicen

[texx]v(x)=\displaystyle\sum_{i=1}^n{u(x_i)}[/texx], siendo [texx]u[/texx] definida anteriormente. Vimos que hay dos candidatos a ser los óptimos, dependiendo del valor que tome [texx]\lambda[/texx]. Un candidato surge de mantener los [texx]x_i[/texx] positivos tal cual surge del [texx]x[/texx] original y sumar todos los valores negativos, llamemos a este vector [texx]y=(y_1,y_2,...,y_n)[/texx] tal que [texx]x_i^+=y_i^+[/texx] para cada elemento de [texx]x[/texx] positivo y [texx]y_j=\displaystyle\sum_{i=1}^n{x_j^-}[/texx] para cada elemento de [texx]x[/texx] negativo. El otro candidato surge de ir cancelando los máximos elementos de [texx]x[/texx] con los menores elementos de [texx]x[/texx] negativos, hasta que no existan más elementos negativos, llamemos a ese vector [texx]z[/texx].

Por lo tanto de la comparación del valor que tomen estos vectores [texx]y[/texx] y [texx]z[/texx] obtendremos un

[texx]\lambda(y)=\displaystyle\frac{v(y^+)-v(z)}{v(y^-)}[/texx], entendiéndose por [texx]v(y^+)=\displaystyle\sum_{i=1}^n{u(y_i^+)}[/texx], lo mismo para los valores negativos. Ahora como [texx]\displaystyle\sum_{i=1}^n{y_i}=\displaystyle\sum_{i=1}^n{y_i^++y_i^-}=\displaystyle\sum_{i=1}^n{x_i}=C[/texx] siendo [texx]C[/texx] una constante, podemos expresar a

[texx]\lambda(y^+)=\displaystyle\frac{v(y^+)-v(z)}{v(C-y^+)}[/texx]. Vamos a suponer que [texx]u(x)=x^a[/texx] con [texx]0<a<1[/texx], entonces al [texx]\lambda(y^+)[/texx] crecer con [texx]y^+[/texx], no? entonces el vector [texx]y[/texx] debe tener el máximo posible de la suma de elementos positivos, que se da manteniendo la parte de elementos positivos del vector [texx]x[/texx] intacta. Ahora el denominador [texx]v(y^-)[/texx] se minimiza cuando se suman todos los elementos negativos de [texx]x[/texx] y eso hace maximizar [texx]\lambda(y)[/texx].

En realidad, creo que debería decir que [texx]\lambda(y_i^+)[/texx] crece con [texx]\displaystyle\sum_{i=1}^n{y_i^+}[/texx]. Es decir, el máximo [texx]\lambda[/texx] se dará cuando no se toquen los elementos positivos originales.  Aunque en realidad dado que el [texx]\lambda(y_i^+)[/texx] puede tomar varios valores para el mismo [texx]\displaystyle\sum_{i=1}^n{y_i^+}[/texx] no es una función. Pero he comprobado al menos para N=5 que el [texx]max\lambda(y_i^+)[/texx] crece a medida que lo hace [texx]\displaystyle\sum_{i=1}^n{y_i^+}[/texx].

Saludos





En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!