🧮 Computational Mathematics

Inicio · Parte 12 — Optimización matemática y computacional

254 — Line search

avanzado clase 14 de 20 4 horas demostración line_search

Armijo pide una reducción proporcional a lo que el gradiente prometía, no cualquier reducción.

Fórmulas

condición de Armijo: f(x + αd) ≤ f(x) + c₁·α·∇fᵀd
retroceso: empezar en α = 1 y multiplicar por 0,5 hasta cumplirla
c₁ típico: 10⁻⁴

Desarrollo

Elegir el tamaño de paso a mano es frágil: demasiado grande diverge, demasiado pequeño malgasta iteraciones. La búsqueda de línea automatiza esa elección probando valores y quedándose con uno que garantice progreso suficiente.

El criterio ingenuo —aceptar cualquier α que reduzca f— no basta. Se pueden construir sucesiones de pasos que reducen la función cada vez y aun así no convergen al mínimo, porque la reducción se hace arbitrariamente pequeña. Hace falta exigir un progreso proporcional al prometido por el gradiente.

Esa exigencia es la condición de Armijo: la reducción debe ser al menos una fracción c₁ de la que predice la aproximación lineal. Con c₁ = 10⁻⁴ la exigencia es muy laxa —se pide capturar la diezmilésima parte del descenso prometido— y aun así basta para garantizar convergencia.

La implementación estándar es el retroceso: empezar con α = 1, y mientras no se cumpla Armijo multiplicar por 0,5. Termina en pocas iteraciones y solo requiere evaluar la función. Las condiciones de Wolfe añaden una segunda desigualdad sobre la curvatura para evitar pasos demasiado cortos, y son las que necesita BFGS para mantener válida su aproximación.

Ejemplo trabajado

Retroceso desde un punto con gradiente muy desequilibrado.

punto (−2, 3)      f = 184,0
dirección d = −∇f = (4, −120)      c₁ = 1e-4

α        f(x + αd)      ¿Armijo?
1,000    273 784,0         no
0,500     64 900,0         no
0,250     15 016,0         no
0,125      3 271,0         no
0,0625       634,0         no
0,03125      146,3         sí   ← aceptado

6 evaluaciones de f y ningún hiperparámetro que ajustar.

Sin línea de búsqueda, α = 1 habría multiplicado
la función por 1 488.

Qué calcula el laboratorio

Búsqueda de línea con la condición de Armijo.

python classes/part-12-optimizacion-matematica-y-computacional/254-line-search/lab.py
compmath run 254

Salidas del laboratorio (8)

Muestra de la ejecución real

{
  "punto": [
    -2.0,
    3.0
  ],
  "f(x)": 184.0,
  "direccion": [
    4.0,
    -120.0
  ],
  "c1": 0.0001,
  "intentos": [
    {
      "alpha": 1.0,
      "f": 273784.0,
      "armijo": false
    },
    {
      "alpha": 0.5,
      "f": 64980.0,
      "armijo": false
    },
    {
      "alpha": 0.25,
      "f": 14581.0,
      "armijo": false
    },
    {
      "alpha": 0.125,
      "f": 2882.25,
      "armijo": false
    },
    {
      "alpha": 0.0625,
      "f": 408.0625,
      "armijo": false
    },
    {
      "alpha": 0.03125,
      "f": 14.765625,
      "armijo": true
    }
  ],
  "alpha_aceptado": 0.03125
}

Errores comunes

Dónde se usa

Métodos cuasi-Newton, optimización sin ajuste manual de paso, entrenamiento con paso adaptativo y solvers de propósito general.

Idea rectora de la parte

Regularizar es añadir un término al objetivo, no un truco de implementación.

Error a evitar

Aplicar weight decay dentro del gradiente en Adam (y no como AdamW).

Conexión con IA

AdamW es el optimizador por defecto del entrenamiento moderno; entender su actualización explica el weight decay, el warmup y el gradient clipping.

Bibliografía de la clase

Archivos de la clase

← 253 Quasi-Newton y BFGS 255 Regularización como optimización →