Esto va a ser un poco ondulado, pero aquí va:
El problema es que la optimización sobre regiones viables no convexas también puede conducir a mínimos locales, incluso con funciones objetivas convexas.
Voy a ilustrar esto aplicando el método simplex, un esquema de resolución de estilo de descenso de gradiente, a una región no convexa, para mostrar cómo puede suceder esto.
- ¿Debería obtener un título en matemáticas o matemáticas aplicadas?
- ¿El PageRank nunca puede converger para algunas entradas (después de un punto hay el mismo conjunto de vértices activos / programados)? En caso afirmativo, ¿cómo debería determinarse la convergencia?
- ¿Puedes derivar nuevas teorías en física solo mirando las matemáticas? Ejemplos de estado por favor.
- ¿Existe algún término o clasificación para este tipo de secuencia de Fibonacci? (1 2 3 4 6 9 13 19 28)
- ¿Cuál es el significado de los diagramas de Hasse?
Vamos a configurar una región factible en un plano 2D, con X e Y como las dos dimensiones, según las siguientes restricciones:
X <5, Y <5
si X = 2, de lo contrario X sin restricciones
si Y = 2, de lo contrario, Y sin restricciones
Esto le da una región factible donde el cuadrado de (0,0) a (5,5) es factible, a excepción de la región cuadrada más pequeña de (0,0) a (2,2). Puede ver visualmente que esto no es convexo, no todos los puntos entre (0,2) y (2,0) son factibles.
Digamos que nuestra función objetivo es 2 * X + Y, que es convexa. Tenga en cuenta también que el objetivo prefiere minimizar X sobre Y, por lo que el punto (0,2) es preferible a (2,0), y es globalmente óptimo.
Dibuje esto rápidamente en una hoja de papel y calcule los valores objetivos a mano si lo desea.
Digamos que nuestro método simplex se inicializa en el punto (5,0). Calcula el costo reducido, la tasa de mejora de la función objetivo, para los dos vértices vecinos (5,5) y (2,0), y encuentra que (2,0) tiene el costo reducido más negativo.
(Me estoy saltando el trabajo para esto, pero puede ver que esto es cierto porque solo un movimiento a (2,0) mejora la función objetivo).
Progresando a (2,0), los puntos vecinos son (5,0) y (2,2). Ninguno de estos son mejoras a la función objetivo, por lo que el algoritmo declara una solución óptima y se detiene incorrectamente. Se pierde el óptimo real, (0,2).
Puede preguntar por qué no incluimos el punto (0,2) en nuestra verificación final, ¿por qué no es un vecino? La razón (nuevamente, manual) es que, a menos que limitemos los puntos que evaluamos a las Soluciones viables básicas adyacentes (los vértices de esta forma), el tamaño del problema se vuelve intratable a medida que crece en número de variables.
No hay garantía de que estas extrusiones no convexas sean solo una iteración simple “profunda”, como lo son en este ejemplo. En el caso general, necesitaría buscar una gran cantidad de soluciones básicas factibles para verificar que esto no haya sucedido, por lo que el enfoque de descenso de gradiente simple no es útil para una región factible no convexa.
Si sabemos que el espacio de la solución es convexo, nos permite resolver las cosas más rápido, porque podemos suponer que tomar una sucesión de pasos cuesta abajo conducirá al óptimo global, sin el riesgo de quedar atrapado en los bolsillos de factibilidad como lo hicimos aquí.
Estoy seguro de que hay una prueba de por qué esto no funciona en general: un contraejemplo es lo mejor que tengo. ¡Espero que esto ayude!
