3.1 Conceptos básicos de problemas de programación no lineal

3.1 Conceptos básicos de problemas de programación no lineal 

La programación no lineal (PNL) estudia cómo encontrar el mejor resultado posible (óptimo) en problemas donde:

• La función objetivo no sigue una relación lineal entre variables.
• Las restricciones también pueden ser no lineales.

Diferencias clave con la programación lineal (PL):

Aspecto	PL	PNL
Función objetivo	Lineal	No lineal
Restricciones	Lineales	Lineales o no lineales
Solución	Generalmente única y en vértices	Puede haber múltiples óptimos (locales/globales).
Métodos de resolución	Simplex, gráficos	Gradientes, Lagrange, heurísticas.

Características de problemas PNL:

1. No convexidad: Una función no convexa puede tener varios puntos donde parece "mínima" o "máxima", complicando encontrar el óptimo global.
2. Dependencia del inicio: Los métodos iterativos pueden converger a diferentes soluciones dependiendo de los valores iniciales.
3. Superficies complejas: Las restricciones y la función objetivo generan geometrías complicadas, como superficies curvas o regiones irregulares.

Ejemplo básico:

Minimizar $f(x, y) = x^2 + y^2$, sujeto a $x + y \geq 1$ y $x, y \geq 0$.

1. La función objetivo $x^2 + y^2$ es una parábola en 3D (forma de cuenco).
2. La restricción $x + y \geq 1$ forma una línea en el plano $xy$.
3. El objetivo es encontrar el punto más cercano al origen que cumpla con las restricciones.

---

3.2 Ilustración gráfica de problemas de programación no lineal

En la programación no lineal, las gráficas son herramientas poderosas para comprender la relación entre la función objetivo y las restricciones.

Visualización de PNL en 2D y 3D:

1. Curvas de nivel: Representan los valores constantes de la función objetivo en un plano $xy$.
   Ejemplo: Si $f(x, y) = x^2 + y^2$, las curvas de nivel son círculos centrados en el origen.
2. Superficie de la función objetivo: En 3D, $f(x, y)$ se visualiza como una superficie curva.
   • En $z = x^2 + y^2$, cada punto en la superficie representa un valor de la función para una combinación de $x, y$.
3. Restricciones: Las restricciones se visualizan como áreas válidas (factibles).
   • Ejemplo: $x^2 + y^2 \leq 1$ (un círculo) limita la región factible.

Ejemplo gráfico detallado:

Problema:
Maximizar $f(x, y) = 2x + y$, sujeto a:

• $x^2 + y^2 \leq 4$ (círculo de radio 2).
• $y \geq x$.

1. Región factible:

   • La restricción $x^2 + y^2 \leq 4$ define un círculo.
   • La restricción $y \geq x$ es una región por encima de la línea $y = x$.
   • La intersección de estas restricciones es la región válida.

2. Curvas de nivel:
   Las líneas rectas de $2x + y = c$ (valores constantes de $f$) se desplazan en dirección del gradiente hasta tocar el borde de la región factible.

3. Solución óptima:
   Ocurre en el punto de tangencia entre la curva de nivel más alta y la región factible.

---

3.3 Tipos de problemas de programación no lineal

La programación no lineal se clasifica según las características de la función objetivo y las restricciones:

1. Problemas sin restricciones:

Aquí, la función objetivo se optimiza sin límites externos.

• Método típico: Derivadas para hallar puntos críticos y clasificar máximos/mínimos.
• Ejemplo: Minimizar $f(x) = x^3 - 3x^2 + 2x$.
  • $f'(x) = 3x^2 - 6x + 2$, igualando a 0: $x = 1, x = \frac{2}{3}$.
  • Usando $f''(x) = 6x - 6$, se determina que $x = 1$ es un mínimo y $x = \frac{2}{3}$ es un máximo.

2. Problemas con restricciones:

Se optimiza la función objetivo bajo condiciones específicas.

• Método típico: Lagrange, Kuhn-Tucker, penalización.
• Ejemplo: Maximizar $f(x, y) = x^2 + y^2$, sujeto a $x + y = 1$.
  • Usando Lagrange:
    $\mathcal{L} = x^2 + y^2 + \lambda (x + y - 1)$.
    Resolviendo, se obtiene $x = y = 0.5$.

3. Problemas convexos vs. no convexos:

• Convexos: Tienen una única solución óptima global (son más fáciles de resolver).
  Ejemplo: $f(x) = x^2 + y^2$.
• No convexos: Pueden tener múltiples óptimos locales.
  Ejemplo: $f(x) = x^4 - x^2$.

---

3.4 Optimización clásica

Puntos críticos:

Los puntos críticos son lugares donde la derivada de la función objetivo se anula ($f'(x) = 0$) o no existe. Se clasifican en:

• Máximos locales: El valor de la función es mayor que en puntos cercanos.
• Mínimos locales: El valor de la función es menor que en puntos cercanos.
• Puntos de silla: No es ni máximo ni mínimo; ocurre un cambio en la curvatura.

Métodos clásicos:

1. Primera derivada: Identifica posibles puntos críticos.
2. Segunda derivada: Evalúa la curvatura para clasificar el punto crítico:
   • $f''(x) > 0$: Mínimo local.
   • $f''(x) < 0$: Máximo local.
   • $f''(x) = 0$: Indeterminado (posible punto de inflexión).

Puntos de inflexión:

Un punto donde la función cambia de concavidad, identificado cuando la segunda derivada cambia de signo.

Ejemplo completo:

$f(x) = x^3 - 6x^2 + 9x$.

1. Primera derivada: $f'(x) = 3x^2 - 12x + 9$, igualando a 0: $x = 1, x = 3$.
2. Segunda derivada: $f''(x) = 6x - 12$.
   • $f''(1) = -6$: Máximo local en $x = 1$.
   • $f''(3) = 6$: Mínimo local en $x = 3$.

---

Métodos avanzados en PNL

1. Método de Lagrange:
   Se introduce un multiplicador ($\lambda$) para manejar restricciones igualitarias.

   • Optimiza $\mathcal{L}(x, y, \lambda) = f(x, y) + \lambda \cdot g(x, y)$.

2. Kuhn-Tucker (KKT):
   Extensión de Lagrange para desigualdades. Útil en problemas con restricciones complejas.

3. Método de gradiente descendente:
   Encuentra mínimos ajustando iterativamente los valores en la dirección de mayor descenso.

4. Algoritmos heurísticos:
   Métodos como optimización por enjambre de partículas (PSO) y algoritmos genéticos se usan para resolver problemas no convexos.