La optimización es omnipresente en los ámbitos de la informática, la física, las matemáticas y la economía. Se presenta como una herramienta esencial para los profesionales de la IA y el aprendizaje automático (ML), aplicable en diversos dominios, incluida la toma de decisiones, la planificación de rutas y los parámetros de aprendizaje en modelos de ML, como las máquinas de vectores de soporte (SVM) y las redes neuronales. La forma más general de optimización es encontrar un mínimo/máximo de una función con respecto a sus variables independientes, lo que se puede lograr aplicando conceptos básicos del cálculo diferencial. Matemáticamente, en estos extremos la pendiente (primera derivada) de una función es cero, lo que se conoce como puntos estacionarios. La determinación de si dicho punto representa un máximo o un mínimo se realiza evaluando la curvatura (segunda derivada).
Llevando esto un paso más allá, podemos agregar restricciones al problema de optimización que definen un dominio específico en el espacio donde se optimizará la función. En consecuencia, en lugar de determinar el máximo y el mínimo de una función en todo el espacio real (o complejo), la optimización ahora se limita a este dominio específico. El enfoque convencional de calcular puntos estacionarios ya no es una solución, ya que estos puntos pueden quedar fuera del límite establecido por las restricciones. En las siguientes secciones, analizaremos las complejidades de los problemas de optimización restringida y exploraremos estrategias para su resolución.
Los problemas de optimización con restricciones de igualdad son de la forma
dónde f(x) es la función que buscamos minimizar y la restricción g(x) = 0 define el dominio dentro del cual se llevará a cabo la minimización. En estos casos, el foco de la minimización está inherentemente confinado al dominio específico definido por la restricción. No obstante, como se señaló anteriormente, la aplicación convencional del cálculo diferencial para determinar puntos estacionarios no tiene en cuenta la restricción, por lo que se necesita un enfoque alternativo.
función lagrangiana
Dado que se trata de un problema de minimización, una forma de adaptar el método convencional es asignar un valor de infinito a la función fuera del dominio especificado. Para lograr esto, presentamos una nueva función. f'(x) caracterizado por la siguiente expresión:
Dicha modificación elimina la posibilidad de que ocurran mínimos fuera del dominio, asegurando así que el punto óptimo ocurra dentro de él. En consecuencia, ahora podemos reformular la optimización restringida en un problema de optimización no restringida.
Sin embargo, este enfoque conlleva un desafío. No es posible utilizar el cálculo diferencial para optimizar el problema anterior, ya que la función f'(x) no es diferenciable debido a una discontinuidad repentina en el límite del dominio. Aquí es donde entra en juego el lagrangiano. En lugar de definir la función f'(x) como en (2), lo formulamos como un problema de maximización.
La expresión en el lado derecho se llama función lagrangiana y la nueva variable 𝞴 es la multiplicador de Lagrange. De (4) se desprende claramente que en las regiones donde {g(x)<0, g(x)>0}𝞴 puede tomar los valores {-∞, ∞} para maximizar la expresión a ∞.
Como resultado, la optimización en (3) toma la siguiente forma.
Vale la pena señalar que el problema de la no diferenciabilidad todavía existe ya que la maximización interna da como resultado la misma función discontinua. Sin embargo, con la representación lagrangiana, podemos usar la desigualdad máximo-mínimo para convertir el problema máximo-mínimo en el problema mínimo-máximo para solucionar este problema.
Aquí, primero optimizamos con respecto a la variable independiente. X y luego con respecto al multiplicador de Lagrange 𝞴.
Ahora analizaremos los escenarios en los que la restricción no es una ecuación sino una desigualdad. Estas optimizaciones son de la forma:
Podemos resolver esto usando un enfoque similar: definimos f'(x) ser igual que f(x) dentro del dominio definido por las restricciones e infinito en otros lugares:
Y correspondientemente, la función lagrangiana se define como:
Los multiplicadores de Lagrange correspondientes a las restricciones de desigualdad se denotan por 𝝻. La ecuación (9) es diferente porque también tiene restricciones en los multiplicadores de Lagrange, lo que no estaba en (4). Ahora el problema de optimización en (7) toma la forma
Aplicando la desigualdad mínima-máxima,
Condiciones del KKT (Karush-Kuhn-Tucker)
La optimización en (10) se llama versión primaria y (11) es su versión dual. Según la desigualdad mín-máx, la versión dual limita la versión primaria, lo que sugiere que las dos versiones no son necesariamente iguales. Sin embargo, existen condiciones en las que las versiones primaria y dual son iguales, lo que se denomina condición de regularidad. Suponiendo regularidad, para (X*, 𝝻*) para ser el punto de solución tiene que satisfacer lo siguiente Condiciones KKT:
- Viabilidad primaria
Se desprende de la definición del problema.
2. Doble viabilidad
La doble viabilidad se desprende de (9).
3. Estacionariedad
Esta es una propiedad interesante. Dado que 𝞴* es cero o positivo, la condición de estacionariedad implica esencialmente que en el punto óptimo, los gradientes de f(x) y gramo(x) deben orientarse en direcciones opuestas. La razón detrás de esto es la siguiente: si los gradientes de f(x) y gramo(x) estaban alineados en la misma dirección en el punto x = x*entonces ambos f(x) y gramo(x) disminuirían simultáneamente en una dirección opuesta a sus gradientes. Este escenario permitiría f(x) seguir disminuyendo más allá del valor f(x*) sin violar la restricción, en cuyo caso X* ya no califica como el punto óptimo. Por lo tanto, para que un punto sea óptimo, debe cumplirse la propiedad de estacionariedad.
4. Flacidez complementaria
Ésta es otra propiedad interesante que se deriva directamente de la ecuación (9). Cuando la restricción g(x*) < 0, el multiplicador de Lagrange 𝝻* debe ser igual a cero. Dado que el multiplicador de Lagrange también indica qué tan sensible es nuestra solución a la restricción asociada, un valor de * = 0 significa que la restricción asociada no tiene influencia en la determinación de la solución. En otras palabras, ya sea que consideremos la solución con o sin restricción, el resultado permanece inalterado. Un ejemplo sencillo es cuando f(x) tiene un mínimo global en el dominio donde gramo(x) ≤ 0. Para el otro ejemplo, considere la minimización de la función f(x) sujeto a dos restricciones: gramo¹(x) < 5 y g²(x) < -1. En este caso, el multiplicador de Lagrange²* correspondiente a la restricción g² es cero, como g¹ ya cubre las condiciones de g²representación g² insignificante como limitación.
Aplicación: Máquina de vectores de soporte (SVM)
Un ejemplo de optimización restringida con restricciones de desigualdad en el aprendizaje automático es la máquina de vectores de soporte (SVM). Cuando se le da un conjunto de datos de puntos de datos {(x¹, y¹), (x², y²),…} con y ∈ {-1, 1} Al representar las dos clases, el objetivo es identificar un clasificador que maximice el margen entre las clases. Específicamente, formulamos SVM como el siguiente problema de minimización:
El término ||w|| en la ecuación representa la inversa del margen. Es evidente que existen numerosas restricciones de desigualdad: de hecho, tenemos una restricción vinculada a cada punto de datos. Sin embargo, en la práctica, la solución sólo se guía por unos pocos puntos de datos que se encuentran cerca del límite del clasificador; estos se conocen como vectores de apoyo. Como comentamos en flacidez complementaria, sólo los multiplicadores de Lagrange correspondientes a las restricciones vinculadas a los vectores de soporte poseen valores distintos de cero. Para todos los demás puntos de datos, sus restricciones asociadas tienen valores de multiplicador de Lagrange de cero, lo que los hace insignificantes para determinar el límite del clasificador.
Conclusión
Comenzamos con una breve introducción sobre el problema de optimización sin restricciones y lo ampliamos gradualmente para incorporar las restricciones de igualdad y desigualdad. Además, discutimos cómo la función lagrangiana resuelve los desafíos introducidos por las restricciones. Al profundizar en la optimización del Lagrangiano, obtuvimos información sobre las condiciones de KKT. Por último, proporcionamos una descripción general sucinta de cómo se formulan las SVM como problemas de optimización restringida y analizamos brevemente sus soluciones.