Optimización Global y Real de la Geometría Algebraica

Question

Wikipedia sugiere que:

"Los métodos basados en la geometría algebraica real" son algunas de las "más exitosa de las estrategias generales" para la solución global de los problemas de optimización.

Podría alguien sugerir una referencia para el aprendizaje acerca de cómo la geometría algebraica puede ser utilizado para resolver problemas de optimización? Preferiblemente uno que no presuponen un conocimiento avanzado más allá de que de vosotros promedio de postgrado de Matemáticas grado.

Por supuesto, si alguien quiere añadir una breve explicación de su propio de por qué y cómo se usa este método, son más que bienvenidos.

Answer 1

Esta es una pregunta muy buena y se puede responder más concretamente si decidimos limitarnos a ciertos tipos de problemas.

Supongamos que tenemos un sistema que queremos maximizar o minimizar sujeta a ciertas igualdad y desigualdad de las limitaciones y de que los sistemas en cuestión son todos polinomio.

A continuación, podemos encontrar un global de la solución óptima utilizando el Karush-Kuhn-Tucker criterios (o, alternativamente, el Fritz-Juan condiciones).

Considere el siguiente ejemplo inventado.

Supongamos que queremos maximizar $x_1^2 + 2x_1x_2 + x_2x_3 + 2x_1 - 4$ sujeto a puntos en la unidad de la esfera, es decir,$x_1^2 + x_2^2 + x_3^2 - 1$. En realidad, esto reduce el uso de multiplicadores de LaGrange.

Podemos entonces considerar el cero locus (el conjunto de ceros comunes, también conocida como la variedad) de el siguiente sistema de ecuaciones:

$f_1(x_1,x_2,x_3,\mu_1) = 2x_1 + 2x_2 + 2 + 2\mu_1x_1 = 0$

$f_2(x_1,x_2,x_3,\mu_1) = 2x_1 + x_3 + 2\mu_1x_2 = 0$

$f_3(x_1,x_2,x_3,\mu_1) = x_2 + 2\mu_1x_3 = 0$

$f_4(x_1,x_2,x_3,\mu_1) = x_1^2 + x_2^2 + x_3^2 - 1 = 0$

La solución de este sistema con cualquier paquete de software que hace homotopy continuación (posiblemente HOMPACK o Phcpack) nos da dos soluciones que son aproximadamente

$(-.7179056815169287, .6495969519526578, -.2502703187745829, 1.29779063520861)$

y

$(.9205188417273060, .3831260888917872, .07654712297337447, -2.502550546707357)$.

(con la última de coordenadas que representa el multiplicador de lagrange)

Conectar estas en la ecuación que queremos maximizar nos da $-6.015696316725544$ por la primera solución y $-0.576930611565337$ para el segundo.

Como tal, $(.9205188417273060, .3831260888917872, .07654712297337447)$ es el aproximado punto de la esfera que maximiza el potencial de nuestra función.