⊕ Optimización Matemática

Métodos para encontrar máximos y mínimos en problemas de ingeniería, ciencia de datos y sistemas complejos. De la programación lineal a la optimización estocástica.

📋 Contenido

🎯 1. Fundamentos de Optimización

La optimización matemática es el proceso de encontrar el mejor elemento (máximo o mínimo) de un conjunto de alternativas disponibles. En términos formales, buscamos resolver problemas de la forma:

$$\begin{align} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{sujeto a} \quad & g_i(x) \leq 0, \quad i = 1, \ldots, m \\ & h_j(x) = 0, \quad j = 1, \ldots, p \end{align}$$
Definición: Problema de Optimización

Un problema de optimización consiste en:

  • Función objetivo $f(x)$: función a minimizar (o maximizar)
  • Variables de decisión $x \in \mathbb{R}^n$: variables sobre las que tenemos control
  • Restricciones de desigualdad $g_i(x) \leq 0$: limitaciones del problema
  • Restricciones de igualdad $h_j(x) = 0$: condiciones que deben cumplirse exactamente

Clasificación de Problemas

Optimización Lineal
Función objetivo y restricciones lineales. Incluye programación lineal y sus extensiones.
Optimización No Lineal
Al menos una función (objetivo o restricción) es no lineal. Requiere métodos especializados.
Optimización Estocástica
Involucra incertidumbre en los datos o en la evaluación de la función objetivo.
Optimización Combinatoria
Variables de decisión son discretas, generalmente enteras o binarias.
Teorema: Existencia de Soluciones Óptimas

Sea $f: \mathbb{R}^n \to \mathbb{R}$ continua y $S \subset \mathbb{R}^n$ compacto no vacío. Entonces el problema $\min_{x \in S} f(x)$ tiene al menos una solución óptima.

Demostración: Se sigue del teorema de Weierstrass para funciones continuas en conjuntos compactos.

📏 2. Optimización Lineal

Programación Lineal

La programación lineal (LP) es el caso más simple donde tanto la función objetivo como las restricciones son lineales:

$$\begin{align} \min \quad & c^T x \\ \text{s.a.} \quad & Ax \leq b \\ & x \geq 0 \end{align}$$
Forma Estándar de un Problema Lineal

Todo problema de programación lineal puede escribirse en forma estándar:

$$\begin{align} \min \quad & c^T x \\ \text{s.a.} \quad & Ax = b \\ & x \geq 0 \end{align}$$

donde $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$.

Método Simplex

El método simplex, desarrollado por George Dantzig en 1947, es el algoritmo fundamental para resolver problemas de programación lineal.

Algoritmo Simplex
  1. Encontrar una solución básica factible inicial
  2. Verificar optimalidad: si todos los costos reducidos son no negativos, parar
  3. Seleccionar variable entrante (costo reducido más negativo)
  4. Realizar test de ratio para encontrar variable saliente
  5. Realizar operaciones de pivoteo para actualizar la tabla simplex
  6. Volver al paso 2
Ejemplo: Problema de Producción

Una empresa produce dos productos A y B. Las restricciones son:

$$\begin{align} \max \quad & 3x_1 + 2x_2 \\ \text{s.a.} \quad & x_1 + 2x_2 \leq 8 \\ & 2x_1 + x_2 \leq 10 \\ & x_1, x_2 \geq 0 \end{align}$$

Donde $x_1$ y $x_2$ son las cantidades a producir de A y B respectivamente.

Teoría de Dualidad

A todo problema de programación lineal (primal) le corresponde un problema dual asociado:

$$\begin{array}{c|c} \textbf{Problema Primal} & \textbf{Problema Dual} \\ \hline \min \; c^T x & \max \; b^T y \\ \text{s.a. } Ax \geq b & \text{s.a. } A^T y \leq c \\ x \geq 0 & y \geq 0 \end{array}$$
Teorema de Dualidad Fuerte

Si el problema primal tiene solución óptima finita, entonces el problema dual también tiene solución óptima finita, y los valores óptimos de ambos problemas son iguales:

$$c^T x^* = b^T y^*$$

📈 3. Optimización No Lineal

Condiciones de Optimalidad

Para problemas no lineales sin restricciones, las condiciones de optimalidad se basan en las derivadas de la función objetivo.

Condiciones de Primer Orden (Necesarias)

Si $x^*$ es un mínimo local de $f$ y $f$ es diferenciable en $x^*$, entonces:

$$\nabla f(x^*) = 0$$
Condiciones de Segundo Orden (Suficientes)

Si $\nabla f(x^*) = 0$ y $\nabla^2 f(x^*)$ es definida positiva, entonces $x^*$ es un mínimo local estricto.

Métodos de Gradiente

Los métodos de gradiente utilizan la información de primera derivada para encontrar direcciones de descenso.

Algoritmo de Descenso por Gradiente
  1. Inicializar $x_0$, establecer $k = 0$
  2. Calcular $d_k = -\nabla f(x_k)$ (dirección de descenso)
  3. Encontrar $\alpha_k > 0$ mediante búsqueda lineal
  4. Actualizar $x_{k+1} = x_k + \alpha_k d_k$
  5. Si no converge, hacer $k = k + 1$ y volver al paso 2
$$x_{k+1} = x_k - \alpha_k \nabla f(x_k)$$
Ejemplo: Gradiente Descendente

Para minimizar $f(x, y) = x^2 + 4y^2$:

$$\nabla f = \begin{pmatrix} 2x \\ 8y \end{pmatrix}$$

El algoritmo converge al punto óptimo $(0, 0)$ desde cualquier punto inicial.

Métodos de Newton y Quasi-Newton

El método de Newton utiliza información de segunda derivada para lograr convergencia cuadrática.

$$x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$$
Método BFGS (Quasi-Newton)

Aproxima la matriz Hessiana usando diferencias de gradientes:

$$B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T s_k} - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k}$$

donde $s_k = x_{k+1} - x_k$ y $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$.

🔗 4. Optimización con Restricciones

Multiplicadores de Lagrange

Para problemas con restricciones de igualdad, el método de multiplicadores de Lagrange transforma el problema restringido en uno sin restricciones.

Función Lagrangiana

Para el problema:

$$\begin{align} \min \quad & f(x) \\ \text{s.a.} \quad & h_j(x) = 0, \quad j = 1, \ldots, p \end{align}$$

La función Lagrangiana es:

$$L(x, \lambda) = f(x) + \sum_{j=1}^p \lambda_j h_j(x)$$
Condiciones de Primer Orden (KKT para Igualdades)

Si $x^*$ es un mínimo local, entonces existen $\lambda_j^*$ tales que:

$$\begin{align} \nabla f(x^*) + \sum_{j=1}^p \lambda_j^* \nabla h_j(x^*) &= 0 \\ h_j(x^*) &= 0, \quad j = 1, \ldots, p \end{align}$$

Condiciones KKT

Las condiciones de Karush-Kuhn-Tucker extienden el método de Lagrange a problemas con restricciones de desigualdad.

Condiciones KKT

Para el problema general con restricciones de igualdad y desigualdad, un punto $x^*$ es óptimo si existen multiplicadores $\lambda^*, \mu^*$ tales que:

$$\begin{align} \nabla f(x^*) + \sum_{j=1}^p \lambda_j^* \nabla h_j(x^*) + \sum_{i=1}^m \mu_i^* \nabla g_i(x^*) &= 0 \\ h_j(x^*) &= 0, \quad j = 1, \ldots, p \\ g_i(x^*) &\leq 0, \quad i = 1, \ldots, m \\ \mu_i^* &\geq 0, \quad i = 1, \ldots, m \\ \mu_i^* g_i(x^*) &= 0, \quad i = 1, \ldots, m \end{align}$$

Métodos de Penalización

Los métodos de penalización transforman problemas con restricciones en una secuencia de problemas sin restricciones.

Método de Penalización Exterior

Se resuelve una secuencia de problemas:

$$\min_{x} \phi(x, \rho_k) = f(x) + \rho_k \left[ \sum_{j=1}^p h_j(x)^2 + \sum_{i=1}^m \max(0, g_i(x))^2 \right]$$

donde $\{\rho_k\}$ es una secuencia creciente de parámetros de penalización.

🎲 5. Optimización Estocástica

Gradiente Descendente Estocástico

El gradiente descendente estocástico (SGD) es fundamental en el entrenamiento de modelos de machine learning, especialmente cuando el conjunto de datos es muy grande.

SGD con Mini-lotes

En lugar de calcular el gradiente sobre todo el conjunto de datos:

$$\nabla f(x) = \frac{1}{n} \sum_{i=1}^n \nabla f_i(x)$$

SGD usa una muestra aleatoria (mini-lote) $\mathcal{B}_k$:

$$x_{k+1} = x_k - \alpha_k \frac{1}{|\mathcal{B}_k|} \sum_{i \in \mathcal{B}_k} \nabla f_i(x_k)$$
Adam (Adaptive Moment Estimation)
  1. Inicializar $m_0 = 0$, $v_0 = 0$, $t = 0$
  2. Para cada iteración:
    • $t = t + 1$
    • $g_t = \nabla f(x_{t-1})$ (gradiente)
    • $m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t$ (momento)
    • $v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2$ (segundo momento)
    • $\hat{m}_t = m_t / (1 - \beta_1^t)$ (corrección de sesgo)
    • $\hat{v}_t = v_t / (1 - \beta_2^t)$ (corrección de sesgo)
    • $x_t = x_{t-1} - \alpha \hat{m}_t / (\sqrt{\hat{v}_t} + \epsilon)$

Algoritmos Genéticos

Los algoritmos genéticos son métodos de optimización inspirados en la evolución natural, útiles para problemas complejos y no convexos.

Algoritmo Genético Básico
  1. Inicializar población aleatoria de soluciones
  2. Evaluar función de aptitud para cada individuo
  3. Selección: elegir padres basándose en aptitud
  4. Cruzamiento: combinar padres para crear descendencia
  5. Mutación: introducir variaciones aleatorias
  6. Reemplazo: formar nueva generación
  7. Repetir hasta convergencia o número máximo de generaciones

Optimización Bayesiana

La optimización bayesiana es especialmente útil cuando la evaluación de la función objetivo es costosa, como en la optimización de hiperparámetros.

Proceso Gaussiano como Modelo Sustituto

Se modela la función objetivo $f(x)$ como un proceso gaussiano:

$$f(x) \sim \mathcal{GP}(\mu(x), k(x, x'))$$

donde $\mu(x)$ es la función media y $k(x, x')$ es la función de covarianza.

Optimización Bayesiana con Expected Improvement
  1. Evaluar $f$ en puntos iniciales para formar conjunto de datos $D_t$
  2. Entrenar modelo sustituto (GP) con $D_t$
  3. Optimizar función de adquisición (EI) para encontrar $x_{t+1}$
  4. Evaluar $f(x_{t+1})$ y actualizar $D_{t+1} = D_t \cup \{(x_{t+1}, f(x_{t+1}))\}$
  5. Repetir hasta convergencia

🔧 6. Aplicaciones Prácticas

La optimización tiene aplicaciones en prácticamente todas las áreas de la ingeniería, ciencias y negocios. Aquí presentamos algunos ejemplos representativos.

Machine Learning
Entrenamiento de redes neuronales, SVM, regresión logística. Optimización de hiperparámetros y arquitecturas de modelos.
Finanzas
Optimización de portafolios, gestión de riesgos, pricing de derivados, optimización de estrategias de trading.
Ingeniería
Diseño óptimo de estructuras, optimización de procesos, control óptimo, diseño de experimentos.
Logística
Optimización de rutas, gestión de inventarios, planificación de la producción, asignación de recursos.
Ciencia de Datos
Feature selection, clustering óptimo, reducción de dimensionalidad, optimización de pipelines de datos.
Energía
Optimización de redes eléctricas, gestión de recursos renovables, scheduling de generación, eficiencia energética.
Ejemplo: Optimización de Portafolio (Markowitz)

El modelo clásico de Markowitz busca minimizar el riesgo para un retorno esperado dado:

$$\begin{align} \min \quad & w^T \Sigma w \\ \text{s.a.} \quad & w^T \mu = r_0 \\ & w^T \mathbf{1} = 1 \\ & w \geq 0 \end{align}$$

donde $w$ son los pesos del portafolio, $\Sigma$ es la matriz de covarianza de retornos, $\mu$ son los retornos esperados, y $r_0$ es el retorno objetivo.

Consideraciones Computacionales

La elección del método de optimización depende de las características del problema:

  • Linealidad: Usar simplex para problemas lineales
  • Convexidad: Métodos de gradiente son eficientes
  • Restricciones: Métodos de punto interior o SQP
  • Ruido: Métodos estocásticos o libre de derivadas
  • Dimensión: Métodos especializados para alta dimensión
  • Multimodal: Algoritmos globales como genéticos
Principio: No Free Lunch Theorem

No existe un algoritmo de optimización que sea superior para todos los problemas. La efectividad de un método depende de las características específicas del problema que se está resolviendo.