¿Qué es un enfoque para la optimización de los valores de una matriz?

Question

Mis disculpas si me da algo de la terminología mal, no tengo formal de matemáticas de fondo; la mitad de mi problema es articular lo que yo estoy tratando de hacer y en la identificación del dominio de las matemáticas que se ocupa de este tipo de problema.

Estoy trabajando en un problema donde me gustaría ejecutar un algoritmo de optimización para encontrar los valores para un n-dimensional matriz densa (en realidad, la matriz es la probabilidad condicional de la tabla de un nodo en un probabilístico de modelos gráficos, pero no estoy seguro de si es pertinente)

Estoy familiarizado con algunos de los tipos básicos de optimización, tales como la restricción de la programación lógica y la programación lineal. Sin embargo, estoy teniendo un duro momento de formalizar mi problema porque no caen perfectamente en cualquier categoría; que intrínsecamente tiene tanto una dimensión continua y cualquier número de discretas dimensiones.

Te voy a dar un ejemplo concreto. Decir que tengo tres conjuntos, cada uno con tres miembros:

X = {x₀, x₁, x₂}
Y = {y₀, y₁, y₂}
Z = {z₀, z₁, z₂}

Si me tomo un elemento de cada conjunto, hay 27 permutaciones posibles (o de 27 elementos, si ver la establece como ejes de una matriz). Para cada una de esas permutaciones me gustaría asignar un número real p entre 0 y 1, sujeto a ciertas restricciones y una optimización de la función.

Por ejemplo, decir que me quería dar las siguientes limitaciones:

• Para cada x ∈ X y y ∈ Y, la suma de {x, y, z₀...z₂} = 1
• Para cada x ∈ X y y ∈ Y, {x, y, z₀} ≥ {x, y, z₁} + 0.5
• {x₂, y₁, z₂} = 0.5

Mediante una optimización de la función de mantener cada p tan cerca como sea posible, la siguiente matriz de la población podría ser una solución (hecho a mano, por lo que puede haber errores):

|----+-----+-----+-----+-----+-----+-----+-----+-----+-----|
|    |        x₀       |        x₁       |        x₂       |
|----+-----+-----+-----+-----+-----+-----+-----+-----+-----|
|    |  y₀ |  y₁ |  y₂ |  y₀ |  y₁ |  y₂ |  y₀ |  y₁ |  y₂ |
|----+-----+-----+-----+-----+-----+-----+-----+-----+-----|
| z₀ | 0.6 | 0.6 | 0.6 | 0.6 | 0.6 | 0.6 | 0.6 | 0.6 | 0.6 |
| z₁ | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 |
| z₂ | 0.3 | 0.3 | 0.3 | 0.3 | 0.3 | 0.3 | 0.3 | 0.3 | 0.3 |
|----+-----+-----+-----+-----+-----+-----+-----+-----+-----|

¿Qué es un enfoque matemático para la versión general de este problema, con el N discretos dimensión, N restricciones y arbitrario de la optimización de la función?

Answer 1

De acuerdo con los comentarios, me tome la función de ser minimizado como $\max (p)-\min(p)$, con máximo y mínimo que toma sobre todos los $p$-valores de las tablas. Si no tenemos la restricción $p(x_2,y_1,z_2)= 0.5$, una solución natural para la general $N$ sería: $$ p(x,y,z_0) =\frac{1}{2}+\frac{1}{2N}, \quad p(x,y,z_i) = \frac{1}{2N} \quad \text{ para } i\ge 1 $$ De hecho, las dos primeras restricciones son satisfechas por la anterior, y la diferencia entre la máxima y la mínima $p$$1/2$, que es tan pequeño como puede ser (debido a la segunda restricción).

Para $N=3$ el de arriba da $(2/3,1/6,1/6)$ en cada columna, que están más cerca de los valores en su ejemplo.

Pero además, existe la restricción $p(x_2,y_1,z_2)=0.5$. Inmediatamente se determina los valores en la $(x_2,y_1)$-columna, debido a que $p(x_2,y_1,z_0)\ge0.5$, y la suma de la columna debe ser $1$. Así, $p(x_2,y_1,z_0)=0.5$, $p(x_2,y_1,z_2)=0.5$, y todas las otras entradas de esa columna son cero.

La presencia de cero en algún lugar hace $\min (p)=0$. A continuación, la opción óptima es dejar que todas las columnas a ser el mismo: $(1/2,0,1/2,0,0,0,\dots,0)$. Ahora todos los $p$ de los valores están entre el$0$$1/2$. Sin embargo, teniendo más probabilidades como ceros probablemente no es lo que tenía en mente para su modelo. Puede que desee revisar la optimización del diseño.

Answer 2

Referencia: terminé la solución de mi problema mediante programación lineal para optimizar los valores de la matriz girando cada célula en su propia variable.

Como sucede, podría expresarse de todas las limitaciones que yo estaba interesada en términos de desigualdades lineales.

La optimización de la función fue un poco más difícil porque no me quiere maximizar o minimizar en cualquier eje. Más bien, yo quería encontrar el centro de la región factible. Sin embargo, resulta que es posible manipular todas las restricciones para introducir un Chebychev hypersphere (un hypersphere limitada para caber dentro de la región factible). Cuando se maximiza el radio de la hypersphere, el centro de la esfera será en algún lugar cerca del centro de la región factible.