Autor Tema: Máximo de una partición

0 Usuarios y 1 Visitante están viendo este tema.

09 Septiembre, 2022, 09:34 pm
Leído 203 veces

Quema

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,879
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Supongamos que tengo una función creciente tal que \( f(x) \) es subaditiva para \( x>0, \) \( f(0)=0 \) y \( f(x)\leq{}-f(-x) \) para \( x>0. \) Se puede mostrar que si \( x>0>y, x+y>0 \) entonces \( f(x+y)\geq{}f(x)+f(y). \)

Ahora supongamos que tengo un vector de valores reales \( \mathbf{x}=(x_1,x_2,...,x_n) \) con \( x_1\geq{}x_2\geq{}...\geq{}x_n \). Supongamos que puedo generar más vectores a partir de este vector, simplemente sumando dos elementos del mismo, de manera sucesiva y le llamo \( S \) al conjunto de esos vectores generados a partir de \( \mathbf{x} \). Sería una partición  siendo la cantidad de vectores de \( S  \) sería el número de Bell según la dimensión del vector inicial. 

Defino \( g:\mathbf{x}\rightarrow{}R \) tal que \( g(\mathbf{x})=f(x_1)+f(x_2)+...+f(x_n). \) Quiero hallar el vector perteneciente a \(  S \) que maximice \( g(\mathbf{x}). \)

Para que quede más claro el planteo, supongamos que el vector original es \( \mathbf{x}=(3,2,1) \) entonces a partir de este vector \( S \) estaría formado por los vectores \( (3,2,1), (4,2,0),(5,1,0), (6,0,0), (3,3,0).  \)Creo que en este caso el vector de arranque es el que maximizaría \( g(\mathbf{x}) \) por la subaditividad de \( f. \)

Ahora, si algunos de los elementos del vector de inicio es negativo, las cosas se complican un poco más. Supongamos que \( \mathbf{x}=(5,4,3,-1,-2) \) entonces \( S \) tendría 52 elementos, pero usando el resultado de más arriba, me animaría a decir que \( (3,3,3,0,0) \) es el vector que maximiza \( g(\mathbf{x}). \) Simplemente usando un algoritmo generando nuevos vectores sumando el mayor elemento  y el menor elemento del vector, siempre que esta suma no sea negativa. Es decir, arrancando de \( (5,4,3,-1,-2) \) se que por el resultado de más arriba \( (4,3,3,0,-1) \) es mejor que el anterior y \( (3,3,3,0,0) \) mejor aún. Una vez que tenga todos los elementos del vector no negativos, se que no se podrá mejorar, simplemente por la subaditividad de \( f. \)

Falta algo más?

12 Septiembre, 2022, 09:30 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 51,826
  • País: es
  • Karma: +0/-0
Hola

Supongamos que tengo una función creciente tal que \( f(x) \) es subaditiva para \( x>0, \) \( f(0)=0 \) y \( f(x)\leq{}-f(-x) \) para \( x>0. \) Se puede mostrar que si \( x>0>y, x+y>0 \) entonces \( f(x+y)\geq{}f(x)+f(y). \)

Ahora supongamos que tengo un vector de valores reales \( \mathbf{x}=(x_1,x_2,...,x_n) \) con \( x_1\geq{}x_2\geq{}...\geq{}x_n \). Supongamos que puedo generar más vectores a partir de este vector, simplemente sumando dos elementos del mismo, de manera sucesiva y le llamo \( S \) al conjunto de esos vectores generados a partir de \( \mathbf{x} \). Sería una partición  siendo la cantidad de vectores de \( S  \) sería el número de Bell según la dimensión del vector inicial. 

Defino \( g:\mathbf{x}\rightarrow{}R \) tal que \( g(\mathbf{x})=f(x_1)+f(x_2)+...+f(x_n). \) Quiero hallar el vector perteneciente a \(  S \) que maximice \( g(\mathbf{x}). \)

Para que quede más claro el planteo, supongamos que el vector original es \( \mathbf{x}=(3,2,1) \) entonces a partir de este vector \( S \) estaría formado por los vectores \( (3,2,1), (4,2,0),(5,1,0), (6,0,0), (3,3,0).  \)Creo que en este caso el vector de arranque es el que maximizaría \( g(\mathbf{x}) \) por la subaditividad de \( f. \)

Ahora, si algunos de los elementos del vector de inicio es negativo, las cosas se complican un poco más. Supongamos que \( \mathbf{x}=(5,4,3,-1,-2) \) entonces \( S \) tendría 52 elementos, pero usando el resultado de más arriba, me animaría a decir que \( (3,3,3,0,0) \) es el vector que maximiza \( g(\mathbf{x}). \) Simplemente usando un algoritmo generando nuevos vectores sumando el mayor elemento  y el menor elemento del vector, siempre que esta suma no sea negativa. Es decir, arrancando de \( (5,4,3,-1,-2) \) se que por el resultado de más arriba \( (4,3,3,0,-1) \) es mejor que el anterior y \( (3,3,3,0,0) \) mejor aún. Una vez que tenga todos los elementos del vector no negativos, se que no se podrá mejorar, simplemente por la subaditividad de \( f. \)

Cuando dices "creo" hay que concretar el porqué.

No obstante si no me equivoco, lo que tienes es una propiedad que te permite, dado un vector, construir otro de la familia \( S \) que lo "mejora"; tu idea es reiterando ese proceso llegar a uno que no puede ser mejorado con ese proceso.

El problema de esa idea es que podríamos tener un esquema como el que se ilustra en este gráfico. Las flechas van de un vector a otro que lo mejora; entonces puede haber varios caminos que llevan a vectores maximales, es decir, que no pueden ser mejorados. ¿Pero cuál de ellos se supone que es "el mejor"?.



Saludos.

12 Septiembre, 2022, 03:32 pm
Respuesta #2

Quema

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,879
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Es que el creo que es una afirmación. Fijate que si tenemos un vector donde todos los elementos no son positivos, entonces por la subaditividad de \( f \) ese vector es el máximo posible de una partición. El tema está cuando hay elementos positivos y negativos. Ahora supongo que si en cada paso de un nuevo vector el mayor elemento positivo más el menor elemento negativo es positivo entonces, el vector final de sumar estos dos elementos hasta terminar con todos los elementos negativos es el máximo posible. Es medio evidente esto. Hay que eliminar todos los elementos negativos y la mejor forma de hacerlo es sumando el elementos más grande con el más chico sucesivamente. Lo pruebo para \( n=3 \) supongamos que tengo un vector ordenado de forma decreciente \( (x_1,x_2,x_3) \) con \( x_1,x_2>0 \) y \( x_3<0 \) tal que \( x_1+x_3>0. \) Supongamos al ser \( f \) creciente, tendremos \( f(x_1+x_3)>f(x_2+x_3) \) entonces siempre conviene ir sumando el mayor positivo con el menor negativo, siempre y cuando la suma sea positiva.

12 Septiembre, 2022, 05:03 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 51,826
  • País: es
  • Karma: +0/-0
Hola

Es que el creo que es una afirmación. Fijate que si tenemos un vector donde todos los elementos no son positivos, entonces por la subaditividad de \( f \) ese vector es el máximo posible de una partición.

Si; lo que quiero decir es que hay que escribir rigurosamente el resultado.

Citar
El tema está cuando hay elementos positivos y negativos. Ahora supongo que si en cada paso de un nuevo vector el mayor elemento positivo más el menor elemento negativo es positivo entonces, el vector final de sumar estos dos elementos hasta terminar con todos los elementos negativos es el máximo posible. Es medio evidente esto. Hay que eliminar todos los elementos negativos y la mejor forma de hacerlo es sumando el elementos más grande con el más chico sucesivamente. Lo pruebo para \( n=3 \) supongamos que tengo un vector ordenado de forma decreciente \( (x_1,x_2,x_3) \) con \( x_1,x_2>0 \) y \( x_3<0 \) tal que \( x_1+x_3>0. \) Supongamos al ser \( f \) creciente, tendremos \( f(x_1+x_3)>f(x_2+x_3) \) entonces siempre conviene ir sumando el mayor positivo con el menor negativo, siempre y cuando la suma sea positiva.

A ver si logro explicarme. Fíjate en primer lugar hay que separar dos cosas:

- Qué el método que indicas  para construir el óptimo sea el correcto (no te digo que no; probablemente lo sea)
- Qué esté correctamente justificado que efectivamente el método funciona.

Entonces la idea de mi crítica es. Supongamos que a partir de un vector tenemos dos o más formas de obtener otro que lo mejora. Eso equivale en mi árbol a una ramificación; a un punto donde salen dos o más flechas que lo mejoran. Entiendo que eso es algo que ocurre.

En cuanto vamos por dos caminos distintos al final llegaremos a dos vectores que no pueden ser mejorados; es decir a partir de ellos no se puede construir con otra reagrupación otro mejor. ¿Pero como comparar cuál de los dos es el mejor? ¿Cómo demostrar que el mejor es el que desde el principio siguió el criterio que indicas?.

Saludos.