Búsqueda exhaustiva y muestreo en una grilla

01 · Optimizar mediante evaluaciones

Cuando solo podemos consultar la función

En muchos problemas conocemos la fórmula y podemos derivarla. En otros, el valor objetivo proviene de ejecutar un programa, simular un sistema o consultar una medición. Allí la derivada puede ser desconocida, costosa o incluso no existir.

La búsqueda exhaustiva en una grilla reemplaza el intervalo continuo por una colección finita de candidatos. Evalúa la función en cada uno y conserva el mejor resultado observado.

02 · Discretizar un intervalo

Puntos igualmente espaciados

Dividimos el intervalo cerrado [a,b] en n subintervalos de igual longitud:

La grilla contiene n+1 puntos:

Esta construcción incluye exactamente las dos fronteras: x₀=a y xₙ=b. El número h es el paso o resolución espacial.

03 · Procedimiento básico

Evaluar y conservar el mínimo

1. Validar el intervalo y la cantidad de subintervalos.
2. Evaluar la función en el extremo izquierdo.
3. Recorrer los restantes puntos de la grilla.
4. Reemplazar el mejor candidato cuando aparece un valor menor.
5. Devolver la posición, el valor y la resolución utilizada.

Para buscar un máximo solo cambia la comparación. El método no necesita continuidad ni derivadas para ejecutarse, aunque esas propiedades sí permiten formular garantías sobre la aproximación.

04 · Ejemplo de referencia

Un mínimo que no coincide con la grilla

Consideremos:

Analíticamente, f′(x)=2(x−2,37), por lo que el mínimo continuo está en x*=2,37 y vale 1. La búsqueda numérica no utilizará ese dato: solo evaluará f.

Reducir el paso mejora la resolución, aunque la mejora no tiene que ser estricta en cada refinamiento: depende de cómo se alineen los puntos con el óptimo.

05 · Precisión espacial

Qué garantiza el paso

Todo punto del intervalo se encuentra a distancia no mayor que h/2 de algún punto de una grilla uniforme que incluye ambos extremos. Por lo tanto, existe un punto muestreado xg cercano al óptimo continuo x*:

Esto no implica automáticamente que el algoritmo identifique una posición a menos de h/2 si hay varios mínimos, ruido o valores iguales lejos entre sí. La garantía geométrica habla de la existencia de un punto cercano.

Para lograr una resolución espacial máxima ε, basta elegir:

06 · Error en la función

Distancia y valor no son lo mismo

Un error pequeño en x puede generar un error grande o pequeño en f(x), según la forma de la curva. Si f es Lipschitz con constante L:

Si además x* es un mínimo interior, f′(x*)=0 y |f″(x)|≤M cerca del óptimo, la aproximación cuadrática produce:

La segunda cota explica por qué una función suave puede aproximarse muy bien en valor aun cuando la posición muestreada no sea exacta.

07 · Intervalo cerrado

Las fronteras también son candidatas

El máximo o mínimo absoluto puede estar en a o en b. Una implementación que genera puntos sumando repetidamente h puede omitir el extremo derecho por errores de coma flotante.

Es más seguro elegir una cantidad entera de subintervalos y calcular cada punto mediante:

Así, cuando i=n, la expresión construye directamente el extremo derecho. No dependemos de que muchas sumas decimales alcancen exactamente b.

08 · Resultados equivalentes

Empates, tolerancias y mesetas

Dos evaluaciones pueden ser exactamente iguales o diferir menos que la precisión relevante. Si se actualiza solo con <, el algoritmo conserva el primer mínimo. Con <=, conserva el último.

Cuando interesan todos los candidatos equivalentes, podemos usar una tolerancia τ:

• si y < mejor−τ, aparece un nuevo mínimo;
• si |y−mejor|≤τ, agregamos un empate;
• si y > mejor+τ, descartamos el punto.

La tolerancia debe responder a la escala de la función o al ruido de medición, no elegirse arbitrariamente.

09 · Evaluaciones problemáticas

NaN, infinito y errores de ejecución

Una función real puede fallar en ciertos parámetros, devolver NaN, agotar memoria o exceder un tiempo límite. La política debe estar definida:

• rechazar toda la búsqueda si una evaluación inválida indica un error del modelo;
• tratar el punto como no factible y continuar;
• asignar una penalización como Infinity al minimizar;
• registrar el fallo para no confundirlo con una evaluación nunca realizada.

10 · Costo del algoritmo

Más resolución exige más evaluaciones

Con n subintervalos se realizan n+1 evaluaciones:

Reducir h a la mitad aproximadamente duplica el trabajo en una dimensión. Si cada evaluación ejecuta un benchmark de varios segundos, el costo de la función domina por completo al costo del bucle.

Las evaluaciones independientes pueden distribuirse entre procesos o equipos, siempre que el entorno de medición sea comparable y la función no dependa del orden.

11 · Máximos y mínimos

Una comparación configurable

No hace falta duplicar el algoritmo. Podemos parametrizar el criterio de mejora:

Otra opción matemática es minimizar −f(x) para hallar un máximo de f. Sin embargo, devolver el valor original y nombrar explícitamente el objetivo suele producir una API más clara.

12 · Usar mejor las evaluaciones

Grilla gruesa y refinamiento local

Una estrategia práctica ejecuta primero una grilla gruesa en todo el intervalo y luego crea una grilla fina alrededor del mejor punto observado. Esto concentra trabajo donde parece estar el óptimo.

1. Evaluar [a,b] con paso grande.
2. Seleccionar el mejor punto xg.
3. Refinar en [xg−h, xg+h], recortado al dominio.
4. Repetir hasta alcanzar la resolución o el presupuesto deseado.

El ahorro tiene un precio: si la grilla inicial no detecta una región angosta con mejores valores, el refinamiento local puede abandonarla. Ya no conserva la misma cobertura global que una grilla fina completa.

13 · Más de un parámetro

La maldición de la dimensionalidad

Con m valores por variable, una grilla de d parámetros contiene:

Con 100 valores, una variable requiere 100 evaluaciones, dos requieren 10 000 y cuatro requieren 100 millones. La búsqueda exhaustiva es transparente y paralelizable, pero escala mal en muchas dimensiones.

En cursos posteriores, métodos aleatorios, gradientes y estrategias adaptativas permitirán explorar espacios grandes sin evaluar todas las combinaciones.

14 · Exploración interactiva

Laboratorio: resolución y aproximación

Cambiá la cantidad de subintervalos y la posición del mínimo. Los puntos representan las únicas evaluaciones disponibles para el algoritmo.

La curva continua muestra la función completa; los círculos son los puntos evaluados y el marcador amarillo identifica la mejor muestra.

Preguntas para explorar

1. Aumentá gradualmente n. ¿El error disminuye en todos los pasos?
2. Buscá una posición donde la grilla contenga exactamente el mínimo.
3. Compará el error de posición con el error en el valor de la función.
4. ¿Cuántas evaluaciones hacen falta para obtener h≤0,05 en [0,5]?

15 · Implementación

Buscar un mínimo de manera robusta

function buscarMinimoGrilla(fn, a, b, subintervalos) {
  if (typeof fn !== "function") throw new TypeError("fn debe ser una función");
  if (!Number.isFinite(a) || !Number.isFinite(b) || a > b) {
    throw new RangeError("Intervalo inválido");
  }
  if (!Number.isInteger(subintervalos) || subintervalos < 1) {
    throw new RangeError("subintervalos debe ser un entero positivo");
  }

  const paso = (b - a) / subintervalos;
  let mejorX = null;
  let mejorY = Infinity;
  let validas = 0;

  for (let i = 0; i <= subintervalos; i++) {
    const x = a + (b - a) * i / subintervalos;
    const y = fn(x);
    if (!Number.isFinite(y)) continue;
    validas++;
    if (y < mejorY) {
      mejorX = x;
      mejorY = y;
    }
  }

  if (mejorX === null) throw new Error("No hubo evaluaciones válidas");
  return { x: mejorX, valor: mejorY, paso, evaluaciones: subintervalos + 1, validas };
}

const f = x => (x - 2.37) ** 2 + 1;
console.log(buscarMinimoGrilla(f, 0, 5, 10));
// { x: 2.5, valor: 1.0169, paso: 0.5, evaluaciones: 11, validas: 11 }

Generalizar para máximos y mínimos

function buscarExtremoGrilla(fn, a, b, subintervalos, tipo = "min") {
  if (tipo !== "min" && tipo !== "max") {
    throw new RangeError("tipo debe ser min o max");
  }
  if (!Number.isInteger(subintervalos) || subintervalos < 1 || a > b) {
    throw new RangeError("Dominio o resolución inválidos");
  }

  const mejora = tipo === "min"
    ? (actual, mejor) => actual < mejor
    : (actual, mejor) => actual > mejor;
  let resultado = null;

  for (let i = 0; i <= subintervalos; i++) {
    const x = a + (b - a) * i / subintervalos;
    const valor = fn(x);
    if (!Number.isFinite(valor)) continue;
    if (resultado === null || mejora(valor, resultado.valor)) {
      resultado = { x, valor };
    }
  }

  if (resultado === null) throw new Error("No hubo evaluaciones válidas");
  return resultado;
}

const onda = x => Math.sin(x);
console.log(buscarExtremoGrilla(onda, 0, 2 * Math.PI, 1000, "max"));

16 · Funciones costosas y ruidosas

Buscar sobre experimentos reales

Si fn(x) ejecuta un benchmark, una sola observación puede no representar el desempeño esperado. Es recomendable que cada evaluación:

• realice calentamiento antes de medir;
• repita el experimento varias veces;
• resuma mediante mediana, promedio recortado o percentil;
• registre dispersión e intervalos de confianza;
• use semillas o cargas comparables;
• almacene resultados para evitar repeticiones innecesarias.

Cuando la diferencia entre candidatos es menor que la incertidumbre, declararlos equivalentes suele ser más honesto que elegir un ganador aparente.

17 · Comprensión

Confusiones frecuentes

18 · Práctica guiada

Ejercicios de aplicación

Ejercicio 1: construir la grilla

Dividí [−2,2] en ocho subintervalos. Indicá h y la cantidad de evaluaciones.

Ejercicio 2: aproximar un mínimo

Para f(x)=(x−1,3)² en [0,3], usá h=0,5. ¿Qué punto resulta mejor?

Ejercicio 3: presupuesto de precisión

¿Cuántos subintervalos se necesitan en [0,10] para garantizar que algún punto quede a no más de 0,01 del óptimo?

Ejercicio 4: complejidad en dos dimensiones

Una grilla utiliza 200 valores para cada uno de dos parámetros. ¿Cuántas combinaciones evalúa?

Ejercicio 5: revisar un bucle

¿Qué riesgo tiene for (let x=a; x<b; x+=h)?

19 · Síntesis

Ideas para recordar

En el próximo tema estudiaremos la búsqueda ternaria, que reduce el intervalo de forma iterativa cuando la función es unimodal.