¿Cuándo la simetría en un problema de optimización implica que todas las variables son iguales en la optimización?

Question

Hay muchos problemas de optimización en los que las variables son simétricas en el objetivo y las restricciones; es decir, se pueden intercambiar dos variables cualesquiera y el problema sigue siendo el mismo. Llamemos a estos problemas problemas de optimización simétrica. La solución óptima de un problema de optimización simétrico -como muchos de los que aparecen en los textos de cálculo- suele tener todas las variables iguales. Por poner algunos ejemplos sencillos,

• El rectángulo con área fija que minimiza el perímetro es un cuadrado. (Minimizar $2x+2y$ con sujeción a $xy = A$ y $x,y \geq 0$ .)
• El rectángulo con perímetro fijo que maximiza el área es un cuadrado. (Maximizar $xy$ con sujeción a $2x + 2y = P$ y $x,y \geq 0$ .)
• La diferencia entre la media aritmética y la media geométrica de un conjunto de números se minimiza (y es igual a $0$ ) cuando todos los números son iguales.

También hay problemas de optimización simétricos más complicados para los que las variables son iguales en el momento de la optimización, como el de esta pregunta reciente de math.SE .

Sin embargo, no es cierto que todos los problemas de optimización simétricos tengan todas las variables iguales en el punto óptimo. Por ejemplo, el problema de minimizar $x +y$ con sujeción a $x^2 + y^2 \geq 1$ y $x, y \geq 0$ tiene $(0,1)$ y $(1,0)$ como las soluciones óptimas.

¿Conoce alguien las condiciones generales de un problema de optimización simétrico que garanticen que la solución óptima tiene todas las variables iguales?

La existencia de tales condiciones podría ser muy agradable. A menos que las condiciones en sí mismas sean feas, deberían simplificar enormemente la resolución de una gran clase de problemas de optimización simétrica.

(¿Quizás la convexidad juega un papel importante? Mi último ejemplo tiene una región factible no convexa).

Answer 1

El artículo del mes " ¿Los problemas simétricos tienen soluciones simétricas? ", de William Waterhouse, analiza esta cuestión. Para la optimalidad global se necesitan realmente fuertes restricciones globales sobre la función objetivo, como la convexidad (como en la respuesta de Igor), y no hay nada que se pueda decir de otra manera. Sin embargo, los resultados locales se mantienen en una generalidad considerablemente mayor. Waterhouse lo denomina principio de Purkiss: en un problema de optimización simétrico, los puntos simétricos tienden a ser máximos o mínimos locales.

En concreto, supongamos que estamos optimizando una función suave $f$ en un colector $M$ . La simetría puede expresarse diciendo algún grupo finito $G$ actúa sobre $M$ y conserva $f$ . Si $x$ es un punto en $M$ que se fija por $G$ nos gustaría entender el comportamiento de $f$ cerca de $x$ . Para analizarlo, podemos estudiar la acción de $G$ en el espacio tangente $T_x M$ . La hipótesis clave es que $T_x M$ debe ser una representación irreducible no trivial de $G$ . En ese caso, $x$ es automáticamente un punto crítico para $f$ y si es un punto crítico no degenerado, entonces debe ser un máximo o un mínimo local (es decir, no un punto de silla de montar). De hecho, aún es más cierto: la matriz hessiana sólo tendrá un valor propio, que es cero (degenerado), positivo (mínimo local) o negativo (máximo local).

Este es uno de esos resultados en los que encontrar la declaración correcta es el verdadero problema, y una vez que se ha encontrado la declaración, sólo hacen falta unas pocas líneas para demostrarlo. En su artículo, Waterhouse llega a esta formulación en varios pasos, y muestra cómo abarca varios casos y aplicaciones más concretos. También ofrece un magnífico resumen histórico.

Si la representación en el espacio tangente es reducible, entonces el Principio de Purkiss puede fallar. Si rompemos la representación en una suma directa de subrepresentaciones irreducibles, entonces la matriz hessiana para $f$ tendrá un valor propio para cada irreducible (con multiplicidad igual a la dimensión del irreducible), y no hay razón para que todos tengan el mismo signo. Sin embargo, esta descomposición es muy útil para hacer cálculos locales, porque aunque $M$ es de alta dimensión, $T_x M$ puede descomponerse en unos pocos irreducibles.

El resultado es el siguiente: si se aplica la prueba de la segunda derivada a un problema de optimización simétrico, la teoría de la representación dirá lo que implica la simetría, y la irreductibilidad conduce a la respuesta más sencilla posible.

Answer 2

La condición más común para la simetría en mi experiencia es la convexidad: si la región factible es simétrica y convexa, y la función objetivo es convexa, es inmediato que argmin tiene todas las variables iguales (o invariantes por cualquiera que sea su grupo de simetría).

Answer 3

La suposición de convexidad puede debilitarse a cuasiconvexidad.

Answer 4

Demasiado largo para un comentario: L $$ \min_x f(x)\quad \text{s.t.}\quad x\in C. $$

Si ahora consideramos la "simetría" un poco más abstracta diciendo que se tiene un grupo $G$ actuación en el plató $C$ tal que el objetivo es invariante bajo la acción del grupo, es decir, para $g\in G$ tenemos $f(gx) = f(x)$ entonces se ve que el conjunto de minimizadores también es invariante bajo la acción del grupo.

Answer 5

Suponga que tiene un problema de optimización cualquiera que es simétrico. En cierto modo, la pregunta más débil es: ¿cuánto de la simetría original se traslada a las soluciones? Para el grupo simétrico $S_n$ si el grado $d$ de los polinomios que describen el problema es bajo (comparado con el número de variables) el "principio de grado y medio" dice que siempre se encuentran minimizadores contenidos en el conjunto de puntos invariantes por un grupo $S_{l_1}\times\ldots\times S_{l_d}$ donde $l_1+\ldots+l_d=n$