Conceptos y Métodos Fundamentales de Optimización Matemática

Métodos de Optimización Numérica

Método del Gradiente Descendente

Proporciona una buena dirección de descenso inicial, pero puede presentar baja convergencia cerca del óptimo. Su velocidad de convergencia es típicamente lineal (considerada lenta).

Método de Newton

Ofrece buena convergencia cerca de la solución, pero no garantiza la orientación hacia un mínimo (puede converger a máximos o puntos silla si no se toman precauciones). Su velocidad de convergencia es cuadrática (considerada rápida) bajo ciertas condiciones.

Conceptos Clave en Optimización

Moverse en la dirección del descenso dada por el negativo del gradiente (-∇f) es la mejor opción localmente (marginalmente), pero esto no determina la rapidez global de convergencia, la cual depende de la longitud del paso (tamaño de paso) que se pueda dar en esa dirección.

En un problema con restricciones, bajo condiciones de optimalidad (como las de KKT), el gradiente de la función objetivo (∇f) en un punto óptimo se puede expresar como una combinación lineal de los gradientes de las restricciones activas en ese punto. La regularidad del punto es importante para la unicidad de los multiplicadores asociados.

En un problema con restricciones, si una restricción está activa en la solución óptima, su correspondiente multiplicador de Lagrange (si es distinto de cero) indica la sensibilidad o tasa marginal de cambio del valor óptimo de la función objetivo respecto a una pequeña perturbación (relajación) del lado derecho de esa restricción.

Un problema de optimización donde todas las restricciones son lineales (igualdades o desigualdades) tiene la propiedad de que todo punto factible es regular, siempre que el conjunto factible no sea vacío y las restricciones sean linealmente independientes.

En Programación Lineal (PL), no todos los vértices (puntos extremos) del conjunto factible satisfacen necesariamente las condiciones de Karush-Kuhn-Tucker (KKT). Solo aquellos vértices que corresponden a soluciones óptimas las cumplen.

Definiciones Fundamentales

• Punto extremo: En el contexto de conjuntos convexos, es un punto que no puede representarse como una combinación convexa estricta (con pesos estrictamente entre 0 y 1) de otros dos puntos distintos del conjunto. En optimización lineal, las soluciones óptimas (si existen) se encuentran en puntos extremos.
• Solución factible: Cualquier punto x que satisface todas las restricciones del problema (pertenece al dominio o región factible).
• Solución óptima: Un punto factible x* tal que f(x*) ≤ f(y) para toda y factible (en un problema de minimización).
• Valor óptimo: El ínfimo (o mínimo, si se alcanza) del valor de la función objetivo f(x) sobre el conjunto factible.
• Conjunto convexo: Un conjunto D donde, para cualquier par de puntos x, y ∈ D, el segmento de línea que los une está completamente contenido en D. Formalmente, αx + (1-α)y ∈ D para todo α ∈ [0, 1].
• Punto regular (Condición LICQ): Un punto factible x donde los gradientes de las restricciones de igualdad activas y las restricciones de desigualdad activas en x son linealmente independientes. Existen otras condiciones de calificación de restricciones (CQ) además de LICQ.

Teoremas Relevantes en Optimización

• Teorema (Existencia basada en coercitividad): Sea f una función continua definida sobre un conjunto cerrado y no vacío D ⊆ ℝⁿ. Si f es coercitiva (es decir, f(x) → +∞ cuando ||x|| → +∞), entonces el problema de minimizar f sobre D admite al menos una solución óptima global.
• Teorema de Weierstrass: Sea f una función continua definida sobre un conjunto D ⊆ ℝⁿ que es compacto (cerrado y acotado) y no vacío. Entonces, f alcanza su mínimo y máximo global en D, es decir, el problema de optimización tiene al menos una solución óptima.
• Condición Necesaria de Segundo Orden (CN2 - sin restricciones): Si x* es un mínimo local de f y f es dos veces continuamente diferenciable en una vecindad de x*, entonces el gradiente ∇f(x*) = 0 y la matriz Hessiana H(f(x*)) es semidefinida positiva.
• Condición Suficiente de Segundo Orden (CS2 - sin restricciones): Si f es dos veces continuamente diferenciable en una vecindad de x*, ∇f(x*) = 0 y la matriz Hessiana H(f(x*)) es definida positiva, entonces x* es un mínimo local estricto de f.
• Teorema de Lagrange (Condiciones Necesarias de Primer Orden con Igualdades): Sea x* un mínimo local del problema de minimizar f(x) sujeto a h_i(x) = 0 para i=1,...,m. Si x* es un punto regular y las funciones f, h_i son continuamente diferenciables, entonces existen escalares λ_i (multiplicadores de Lagrange) tales que ∇f(x*) + Σᵢ λᵢ ∇hᵢ(x*) = 0. (Las condiciones KKT generalizan esto para incluir desigualdades).
• Condición de Slater: Considera un problema convexo con restricciones gⱼ(x) ≤ 0 (gⱼ convexas) y Ax = b (lineales). Si existe un punto x̃ factible tal que gⱼ(x̃) < 0 para todas las j correspondientes a restricciones de desigualdad no lineales (y Ax̃ = b), entonces se cumple la condición de Slater, que es una condición de calificación de restricciones que garantiza que las condiciones KKT son necesarias para la optimalidad.
• Propiedad de Problemas Convexos (Mínimos Locales): En un problema de optimización convexo (minimizar una función convexa sobre un conjunto convexo), cualquier mínimo local es también un mínimo global.
• Propiedad de Problemas Estrictamente Convexos (Unicidad): Si el problema de optimización consiste en minimizar una función estrictamente convexa sobre un conjunto convexo, entonces si existe una solución óptima global, esta es única.