Búsqueda ternaria en funciones unimodales

01 · Reducir en vez de recorrer

Una búsqueda que aprovecha la forma

La grilla del tema anterior evalúa candidatos en todo el intervalo. Es robusta, pero para obtener más resolución necesita aumentar proporcionalmente la cantidad de puntos.

Si sabemos que la función tiene una sola región óptima, podemos comparar dos puntos interiores y descartar una parte completa del dominio. La búsqueda ternaria conserva un intervalo que contiene al óptimo y lo reduce en cada iteración.

02 · Hipótesis fundamental

Qué significa que una función sea unimodal

Para buscar un mínimo, una función unimodal primero no aumenta y luego no disminuye. Existe una posición o intervalo mínimo que separa ambas fases.

En el caso estricto con mínimo único x*:

• f decrece para x<x*;
• f crece para x>x*.

Para un máximo ocurre lo contrario: la función crece y luego decrece. Una función convexa en una variable es unimodal para minimización, pero la unimodalidad no exige que la curva sea derivable ni globalmente convexa.

03 · Intervalo de búsqueda

Mantener al óptimo dentro de [a,b]

El algoritmo comienza con un intervalo cerrado [a,b] que contiene al óptimo. Esa afirmación es su invariante: después de cada descarte, el nuevo intervalo debe seguir conteniéndolo.

Elegimos dos puntos que lo dividen en tres partes iguales:

Siempre se cumple a<m₁<m₂<b, salvo que la precisión numérica ya no permita representar puntos distintos.

04 · Regla para mínimos

Comparar f(m₁) y f(m₂)

En una función estrictamente unimodal para mínimo:

• si f(m₁)<f(m₂), el óptimo no puede estar a la derecha de m₂; conservamos [a,m₂];
• si f(m₁)>f(m₂), el óptimo no puede estar a la izquierda de m₁; conservamos [m₁,b];
• si son iguales, el óptimo queda contenido en [m₁,m₂] en el caso unimodal ideal.

Una implementación sencilla puede incluir el empate en una de las dos ramas y conservar dos tercios. Contraer al tercio central es más agresivo, pero requiere confiar en la unimodalidad y en que la igualdad no proviene del ruido o del redondeo.

05 · Por qué funciona

La comparación revela de qué lado estamos

Supongamos que buscamos un mínimo y que f(m₁)<f(m₂). Si ambos puntos estuvieran a la izquierda del mínimo, la función todavía estaría decreciendo y debería cumplirse f(m₁)>f(m₂). Como ocurre lo contrario, el mínimo no puede estar después de m₂.

El razonamiento simétrico justifica el otro descarte. No usamos el valor de la pendiente; usamos el orden de dos valores y la forma global de la función.

06 · Variante para máximos

Invertir la comparación

Para una función que crece y luego decrece:

• si f(m₁)>f(m₂), conservamos [a,m₂];
• si f(m₁)<f(m₂), conservamos [m₁,b].

También se puede maximizar f minimizando −f. En código suele ser más legible parametrizar el tipo de extremo y conservar los valores originales.

07 · Ejemplo paso a paso

Aproximar el mínimo de una parábola

Usamos nuevamente:

La tabla muestra las primeras decisiones, redondeadas:

Cada intervalo sigue conteniendo a x*=2,37. El punto final se aproxima con el centro del último intervalo.

08 · Velocidad de contracción

Conservar dos tercios por iteración

Si el intervalo inicial tiene longitud L₀=b−a, después de k iteraciones su longitud es:

Al devolver el punto medio, el error de posición queda acotado por la mitad del ancho final:

Para asegurar un ancho no mayor que ε, alcanza con:

La cantidad de iteraciones crece logarítmicamente al exigir más precisión.

09 · Criterios de finalización

Tolerancia o presupuesto fijo

Hay dos formas habituales de detener el algoritmo:

• por precisión: repetir mientras b−a>tolerancia;
• por presupuesto: ejecutar una cantidad fija de iteraciones.

La primera expresa directamente la resolución deseada. La segunda permite predecir el costo y evita bucles inesperadamente largos. En aplicaciones robustas se pueden combinar: tolerancia como objetivo y máximo de iteraciones como protección.

Una tolerancia absoluta debe tener las unidades de x. En intervalos de escalas muy diferentes también puede usarse una tolerancia relativa.

10 · Límite numérico

Cuando el intervalo deja de cambiar

Con números de coma flotante, llega un momento en que m₁ o m₂ se redondea a una frontera. Seguir iterando ya no aporta información.

Conviene detenerse si:

• m₁===a o m₂===b;
• el punto medio no cambia respecto de la iteración anterior;
• se alcanza el máximo de iteraciones;
• el ancho satisface una tolerancia absoluta o relativa.

No tiene sentido pedir una tolerancia mucho menor que la precisión representable alrededor de los valores estudiados.

11 · Mesetas y valores iguales

El óptimo puede ser un intervalo

Una función unimodal no estricta puede tener una meseta mínima. En ese caso no existe una única posición óptima. La búsqueda puede converger a una zona o a uno de sus extremos según la regla usada para los empates.

Si f(m₁)===f(m₂) en una función exacta y unimodal, es válido conservar [m₁,m₂]. Con mediciones ruidosas, una igualdad aproximada no justifica necesariamente ese descarte: podría ser mejor conservar un intervalo mayor o repetir las evaluaciones.

12 · Dominios enteros

La versión continua no basta

Si x debe ser entero, podemos contraer el intervalo mientras sea amplio y luego evaluar exhaustivamente todos los enteros restantes. Esto evita bucles causados por divisiones y redondeos.

Otra estrategia es ejecutar la búsqueda continua y comparar los enteros factibles próximos al resultado. Sin embargo, para garantizar el óptimo discreto de una secuencia unimodal, el barrido final del intervalo pequeño es más claro.

Si el parámetro solo acepta una lista irregular —por ejemplo tamaños de bloque específicos—, conviene buscar sobre sus índices o comparar directamente la lista.

13 · Mediciones reales

El ruido puede invertir una comparación

La decisión de cada iteración depende del signo de f(m₁)−f(m₂). Si ambos valores son cercanos y contienen ruido, una inversión accidental puede descartar el lado correcto de forma irreversible.

Para reducir ese riesgo:

• repetir cada evaluación y comparar estimadores robustos;
• usar intervalos de confianza antes de descartar;
• repetir especialmente cuando la diferencia es pequeña;
• guardar en caché mediciones equivalentes;
• hacer primero una grilla que compruebe aproximadamente la unimodalidad.

La búsqueda ternaria clásica está diseñada para funciones deterministas. Una función ruidosa requiere una política estadística adicional.

14 · Exploración interactiva

Laboratorio: contracción del intervalo

Elegí la cantidad de iteraciones y desplazá el mínimo. La zona sombreada representa el intervalo que todavía puede contenerlo.

La curva muestra la función completa; el área vertical resalta el intervalo conservado y el marcador amarillo indica su punto medio.

Preguntas para explorar

1. ¿Qué ocurre con el ancho al aumentar una iteración?
2. Comprobá que el mínimo real permanece dentro del intervalo.
3. ¿El error del punto medio disminuye estrictamente en cada paso?
4. ¿Cuántas iteraciones hacen falta para que el ancho sea menor que 0,01?

15 · Implementación

Buscar un mínimo con tolerancia

function minimoTernario(fn, izquierda, derecha, {
  tolerancia = 1e-7,
  maxIteraciones = 200
} = {}) {
  if (typeof fn !== "function") throw new TypeError("fn debe ser una función");
  if (!Number.isFinite(izquierda) || !Number.isFinite(derecha) || izquierda > derecha) {
    throw new RangeError("Intervalo inválido");
  }
  if (!(tolerancia > 0) || !Number.isInteger(maxIteraciones) || maxIteraciones < 1) {
    throw new RangeError("Criterio de parada inválido");
  }

  let iteraciones = 0;
  while (derecha - izquierda > tolerancia && iteraciones < maxIteraciones) {
    const tercio = (derecha - izquierda) / 3;
    const m1 = izquierda + tercio;
    const m2 = derecha - tercio;
    if (m1 === izquierda || m2 === derecha) break;

    const y1 = fn(m1);
    const y2 = fn(m2);
    if (!Number.isFinite(y1) || !Number.isFinite(y2)) {
      throw new Error("La función produjo un valor no finito");
    }

    if (y1 < y2) derecha = m2;
    else izquierda = m1;
    iteraciones++;
  }

  const x = (izquierda + derecha) / 2;
  return { x, valor: fn(x), izquierda, derecha, iteraciones };
}

const f = x => (x - 2.37) ** 2 + 1;
console.log(minimoTernario(f, 0, 5));

Una función configurable para máximos y mínimos

function extremoTernario(fn, a, b, tipo = "min", iteraciones = 80) {
  if (tipo !== "min" && tipo !== "max") throw new RangeError("Tipo inválido");
  if (!Number.isInteger(iteraciones) || iteraciones < 0 || a > b) {
    throw new RangeError("Parámetros inválidos");
  }
  const esMejor = tipo === "min"
    ? (y1, y2) => y1 < y2
    : (y1, y2) => y1 > y2;

  for (let i = 0; i < iteraciones; i++) {
    const m1 = a + (b - a) / 3;
    const m2 = b - (b - a) / 3;
    if (esMejor(fn(m1), fn(m2))) b = m2;
    else a = m1;
  }

  const x = (a + b) / 2;
  return { x, valor: fn(x), intervalo: [a, b] };
}

const onda = x => Math.sin(x);
console.log(extremoTernario(onda, 0, Math.PI, "max"));

16 · Elegir el método

Grilla frente a búsqueda ternaria

Una combinación útil consiste en explorar primero con una grilla y aplicar búsqueda ternaria dentro de una región que parezca unimodal.

17 · Comprensión

Confusiones frecuentes

18 · Práctica guiada

Ejercicios de aplicación

Ejercicio 1: primer descarte

Al minimizar una función unimodal se obtiene f(m₁)=4 y f(m₂)=7. ¿Qué intervalo se conserva?

Ejercicio 2: ancho después de iterar

Si el intervalo inicial mide 12, ¿cuánto mide después de cinco iteraciones?

Ejercicio 3: cantidad de iteraciones

¿Cuántas iteraciones se necesitan para reducir un intervalo de longitud 10 a un ancho no mayor que 0,01?

Ejercicio 4: detectar un mal uso

Una función tiene dos mínimos locales separados. ¿Es suficiente que sea continua para aplicar búsqueda ternaria global?

Ejercicio 5: máximo

Al maximizar una función unimodal se cumple f(m₁)<f(m₂). ¿Qué tercio se descarta?

19 · Síntesis

Ideas para recordar

En el próximo tema usaremos el valor de la derivada para construir métodos de ascenso y descenso iterativos.