Fundamentos de Optimización Matemática: Convexidad, Lagrange y KKT

Conceptos Fundamentales en Optimización

Conjunto Convexo y Funciones Convexas/Cóncavas

Un concepto crucial en optimización. Se determina mediante:

• 1. El Epígrafo (epi(f)) de una función f es convexo si y solo si f es una función convexa. El Hipógrafo (hip(f)) de una función f es convexo si y solo si f es una función cóncava.
• 2. Para funciones de una variable, el signo de la segunda derivada: si f''(x) ≥ 0, la función es convexa; si f''(x) ≤ 0, la función es cóncava.
• 3. Propiedades adicionales: Las funciones lineales son tanto convexas como cóncavas. La convexidad/concavidad también se puede estudiar analizando la matriz Hessiana para funciones multivariables.

Vector Direccional y Derivada Direccional

Para analizar el comportamiento de una función en una dirección específica:

• 1. Normalizar la dirección: Obtener un vector unitario u en la dirección de interés.
• 2. Calcular la derivada direccional: Producto escalar del gradiente de la función en el punto x (∇f(x)) por el vector de dirección normalizado u. D_uf(x) = ∇f(x) ⋅ u.

Optimización sin Restricciones

Identificación de Puntos Críticos

Pasos para encontrar candidatos a óptimos locales:

• 1. Calcular las derivadas parciales de la función respecto a cada variable.
• 2. Igualar todas las derivadas parciales a cero y resolver el sistema de ecuaciones resultante para encontrar los puntos críticos.
• 3. El plano tangente en un punto (a,b) es Z = f(a,b) + ∇f(a,b) ⋅ (x-a, y-b). En un punto crítico, ∇f(a,b) = 0, por lo que el plano tangente es horizontal: Z = f(a,b).
• Alternativa: Si se proporciona un punto, sustituir sus coordenadas en todas las derivadas parciales. Si todas las derivadas parciales se anulan en ese punto, es un punto crítico.

Clasificación de Puntos Críticos (Test de la Segunda Derivada)

Una vez identificados los puntos críticos, se clasifican usando la matriz Hessiana (H):

• 1. Calcular la matriz Hessiana de la función en el punto crítico.
• 2. Estudiar la definidez de la Hessiana en dicho punto:
  • Si H es definida positiva: el punto es un mínimo local.
  • Si H es definida negativa: el punto es un máximo local.
  • Si H es indefinida: el punto es un punto de silla.
  • Si H es semidefinida (positiva o negativa): el test no es concluyente y se requieren métodos adicionales.

Optimización con Restricciones

Cálculo de Óptimos Locales con Restricciones de Igualdad (Método de Lagrange)

Para problemas de la forma: optimizar f(x) sujeto a g_i(x) = c_i.

• 1. Regularidad: Verificar las condiciones de regularidad de las restricciones (ej., gradientes de las restricciones linealmente independientes).
• 2. Formular la función Lagrangiana: L(x, α) = f(x) - Σ α_i(g_i(x) - c_i).
• 3. Calcular las derivadas parciales de la Lagrangiana respecto a cada variable x_j y cada multiplicador α_i, e igualarlas a cero.
• 4. Resolver el sistema de ecuaciones para obtener los valores de x y α, que proporcionan los puntos candidatos a óptimos.
• 5. Evaluar la matriz Hessiana orlada (o la Hessiana de la Lagrangiana restringida al espacio tangente) en el punto candidato.
• 6. Estudiar el signo de la Hessiana orlada (o sus menores principales) para clasificar el punto (máximo, mínimo).
• 7. Alternativamente, estudiar el signo de la forma cuadrática asociada a la Hessiana de la función objetivo en el subespacio tangente a las restricciones: S = {d ∈ ℝⁿ | ∇g_i(x^*) ⋅ d = 0 para toda restricción g_i}.

Condiciones de Karush-Kuhn-Tucker (KKT) para Optimización con Restricciones de Desigualdad

Para problemas con restricciones de igualdad y/o desigualdad (ej., optimizar f(x) sujeto a g_j(x) ≤ 0, h_k(x) = 0, y x_i ≥ 0).

• 1. Regularidad: Verificar las condiciones de regularidad de las restricciones.
• 2. Convexidad/Concavidad (para optimalidad global): Para problemas de maximización, idealmente la función objetivo f(x) debe ser cóncava (analizar su Hessiana; si es estrictamente cóncava y se halla un máximo KKT, este es único y global bajo ciertas condiciones). Para minimización, f(x) debería ser convexa.
• 3. Las funciones de restricción de desigualdad g_j(x) (para g_j(x) ≤ 0) deben ser convexas para que la región factible sea convexa (analizar sus Hessianas).
• 4. Condiciones KKT (formuladas para un problema de maximización con L(x, α) = f(x) - Σ α_jg_j(x) y restricciones g_j(x) ≤ 0, x_i ≥ 0):
  • KKT1 (Estacionariedad): Las derivadas parciales de la Lagrangiana respecto a las variables de decisión x_i que no tienen restricción de signo explícita deben ser cero (∂L/∂x_i = 0). Si hay restricciones x_i ≥ 0, la condición puede ser ∂L/∂x_i ≤ 0.
  • KKT2 (Holgura complementaria para variables con x_i ≥ 0): x_i ⋅ (∂L/∂x_i) = 0. (Esto se combina con KKT1 si ∂L/∂x_i ≤ 0 y x_i ≥ 0).
  • KKT3 (Holgura complementaria para restricciones de desigualdad): α_j ⋅ g_j(x) = 0, donde α_j es el multiplicador de la restricción g_j(x) ≤ 0.
  • KKT4 (Factibilidad primal): Se deben cumplir todas las restricciones del problema (ej., g_j(x) ≤ 0, h_k(x) = 0).
  • KKT5 (No negatividad de variables, si aplica): x_i ≥ 0.
  • KKT6 (No negatividad de multiplicadores de desigualdad): Los multiplicadores α_j asociados a restricciones g_j(x) ≤ 0 deben ser α_j ≥ 0.
• 5. Resolver el sistema de condiciones KKT analizando casos basados en las condiciones de holgura complementaria (ej., si α_j = 0 o si g_j(x) = 0; y si x_i = 0 o la condición de estacionariedad para x_i se cumple con igualdad).

Propiedades y Teoremas Clave en Optimización

Determinación de Óptimos Globales vs. Locales

• Si se encuentra un mínimo local y la función objetivo es convexa en todo su dominio (y el dominio es convexo), entonces ese mínimo es global.
• Si se encuentra un máximo local y la función objetivo es cóncava en todo su dominio (y el dominio es convexo), entonces ese máximo es global.

Teorema de Weierstrass (Existencia de Óptimos Globales)

El Teorema de Weierstrass establece que: Toda función continua definida sobre un conjunto compacto (cerrado y acotado en ℝⁿ) alcanza sus máximos y mínimos globales en dicho conjunto.

La continuidad de una función se puede verificar si es resultado de sumas, restas, productos, cocientes (con denominador no nulo) y/o composiciones de funciones continuas.

Determinación de Concavidad o Convexidad de una Función

Métodos para analizar la curvatura de una función:

• 1. Para funciones de una variable compuestas, como h(x) = f(g(x)) (ejemplos: f(t)=√t o f(t)=e^t, donde t es una función g(x)): Analizar la concavidad/convexidad de la función externa f y la naturaleza de la interna g. Por ejemplo, si f es convexa y creciente y g es convexa, entonces h es convexa. Alternativamente, calcular directamente la segunda derivada h''(x).
• 2. Para funciones de varias variables g(x,y):
  • Calcular las derivadas parciales de primer y segundo orden.
  • Formar la matriz Hessiana y estudiar su definidez (definida positiva para convexa, definida negativa para cóncava, semidefinida positiva para convexa (no estricta), semidefinida negativa para cóncava (no estricta)).

Métodos Específicos de Optimización

Programación Lineal

Para problemas donde la función objetivo y las restricciones son lineales:

• 1. Dibujar las rectas correspondientes a las restricciones para definir la región factible.
• 2. Identificar los vértices (puntos extremos) de la región factible.
• 3. Evaluar la función objetivo en cada uno de los vértices.
• 4. El valor mínimo (o máximo) de la función objetivo se encontrará en uno de los vértices (si la región factible es no vacía y acotada). El óptimo puede no ser único si la función objetivo es paralela a una de las aristas de la región factible.
• 5. Si se solicita, formular y resolver el problema dual asociado.

Optimización mediante Curvas de Nivel

Principio General del Cálculo de Óptimos con Curvas de Nivel

Este método visual ayuda a entender la optimización, especialmente en dos dimensiones. Se buscan los puntos donde las curvas de nivel de la función objetivo son tangentes a la frontera de la región factible.

Resolución Gráfica de Problemas de Optimización (ej. con KKT) usando Curvas de Nivel

• 1. Dibujar la región factible definida por las restricciones.
• 2. Superponer las curvas de nivel de la función objetivo (conjuntos de puntos donde f(x) = constante).
• 3. El punto óptimo suele ser aquel donde una curva de nivel es tangente a la frontera de la región factible, o un vértice de la misma. Las condiciones KKT describen analíticamente estas condiciones de tangencia u optimalidad en vértices.

Cálculo de Máximos y Mínimos Globales (Enfoque General)

Un procedimiento general puede incluir:

• 1. Si la función objetivo h(X) es una composición monótona de otra función g(X) (ej., h(X) = √g(X), donde la raíz cuadrada es monótona creciente para argumentos positivos), se pueden buscar los óptimos de g(X) y luego transformarlos mediante f.
• 2. Encontrar los puntos críticos de la función (g(X) o h(X)) en el interior del dominio:
  • Calcular las derivadas parciales e igualarlas a cero.
• 3. Resolver el sistema para obtener los puntos candidatos (x^*) a máximos o mínimos.
• 4. Evaluar la función original en estos puntos candidatos y también en los puntos frontera del dominio (si el dominio es cerrado y acotado). El mayor valor será el máximo global y el menor valor el mínimo global (si existen, garantizado por Weierstrass si el dominio es compacto y la función continua).