Búsqueda de la sección dorada

Definición y concepto

La búsqueda de la sección dorada se define como una técnica algorítmica diseñada específicamente para localizar el extremo, ya sea un mínimo o un máximo, de una función unimodal. Este método opera mediante la ejecución de reducciones sucesivas del rango de valores dentro del cual se establece con certeza la presencia del punto óptimo. Al ser un concepto académico fundamental en el campo de la optimización numérica, su eficacia radica en la capacidad de acotar sistemáticamente la región de búsqueda sin requerir derivadas continuas en todos los puntos, lo que la convierte en una herramienta versátil para diversos contextos matemáticos y de ingeniería.

Fundamento geométrico y la proporción dorada

La denominación de este algoritmo deriva directamente de la propiedad geométrica que mantiene durante su ejecución: la conservación de la proporción dorada en las distancias entre los puntos de evaluación. El algoritmo organiza los valores de la función en tríos de puntos cuyas separaciones espaciales guardan una relación constante idéntica a la proporción dorada, representada por el símbolo φ y aproximada numéricamente como 1.618033988. Esta característica estructural permite que, en cada iteración, el intervalo de incertidumbre se reduzca manteniendo la misma relación de simetría interna, lo que optimiza la distribución de las evaluaciones de la función.

El uso de la proporción dorada como factor de reducción garantiza que uno de los puntos internos del intervalo actual se convierta en un punto interno del intervalo siguiente, minimizando así el número de nuevas evaluaciones necesarias. Esta eficiencia geométrica es el núcleo conceptual que distingue a la búsqueda de la sección dorada de otros métodos de reducción de intervalo, proporcionando una estructura predecible y matemáticamente elegante para el proceso de convergencia hacia el extremo de la función objetivo.

Historia y origen

El desarrollo de la búsqueda de la sección dorada está intrínsecamente ligado a los avances en la teoría de la optimización unidimensional durante la primera mitad del siglo XX. Este algoritmo, diseñado específicamente para localizar el extremo de una función unimodal mediante la reducción sucesiva del intervalo de incertidumbre, fue formalizado y descubierto por el matemático Jack Kiefer en el año 1953. Este hallazgo no surgió de forma aislada, sino como parte de un esfuerzo más amplio por establecer métodos eficientes para la minimización de funciones cuando la derivada de la función objetivo no es continua o es costosa de calcular.

Contexto del descubrimiento de Kiefer

En 1953, Kiefer presentó tanto la búsqueda de la sección dorada como la búsqueda de Fibonacci como contribuciones fundamentales al campo de la optimización. Es crucial entender que estas dos técnicas fueron descubiertas simultáneamente por el mismo autor, lo que refleja una visión unificada del problema de la reducción de intervalos. La búsqueda de la sección dorada se distingue por su propiedad geométrica única: mantiene las distancias entre los puntos de evaluación en una proporción constante conocida como la proporción dorada, cuyo valor aproximado es φ ≈ 1.618033988. Esta característica permite que el algoritmo sea particularmente elegante y eficiente en términos de la cantidad de evaluaciones de la función requeridas.

Relación con la búsqueda de Fibonacci

La búsqueda de Fibonacci, también ideada por Kiefer en 1953, fue concebida originalmente como una búsqueda minimax. El objetivo de esta técnica era encontrar el máximo o mínimo de una función unimodal en un intervalo dado, optimizando el peor caso posible para un número fijo de evaluaciones. Existe una relación matemática profunda entre ambas técnicas: la búsqueda de la sección dorada puede interpretarse como el límite asintótico de la búsqueda de Fibonacci cuando el número de evaluaciones tiende a infinito. Esta conexión teórica es fundamental para comprender la eficiencia de ambos métodos y su aplicación práctica en diferentes contextos de optimización.

El trabajo de Kiefer estableció las bases para que estas técnicas se convirtieran en herramientas estándar en la ingeniería y las ciencias de la computación. La capacidad de reducir el intervalo de búsqueda de manera sistemática, aprovechando las propiedades de la proporción dorada, ofrece ventajas significativas sobre otros métodos como la búsqueda ternaria, logrando un ahorro del 50% en las llamadas a la función objetivo. Este descubrimiento de 1953 sigue siendo relevante en la actualidad, demostrando la durabilidad de las soluciones matemáticas bien fundamentadas.

¿Cómo funciona el algoritmo paso a paso?

La búsqueda de la sección dorada opera mediante reducciones sucesivas del rango de valores en el cual se conoce que se encuentra el extremo de una función unimodal. El algoritmo mantiene los valores de la función en tríos de puntos cuyas distancias forman una proporción dorada. Esta estructura permite reducir el intervalo de búsqueda de manera eficiente sin perder la información acumulada en las evaluaciones anteriores.

Proceso de reducción del intervalo

El método comienza evaluando la función en tres puntos iniciales dentro del intervalo dado. Estos puntos están dispuestos de tal manera que las distancias entre ellos siguen la proporción dorada. A partir de estas evaluaciones iniciales, el algoritmo selecciona un cuarto punto para continuar la reducción del intervalo de búsqueda.

La decisión de cuál subintervalo conservar depende de la comparación entre el valor de la función en el nuevo punto y los valores ya conocidos. Si el nuevo valor es menor que el valor de referencia en el intervalo actual, el mínimo se encuentra en el subintervalo que contiene este nuevo punto. Por el contrario, si el nuevo valor es mayor, el mínimo se localiza en el subintervalo opuesto. Este proceso de comparación y reducción se repite sucesivamente hasta alcanzar la precisión deseada.

Paso	Acción	Resultado en el intervalo
1	Evaluación inicial en tres puntos con distancias en proporción dorada	Establecimiento del intervalo inicial con tres valores conocidos
2	Selección y evaluación de un cuarto punto dentro del intervalo	Adición de un nuevo valor de función para comparación
3	Comparación del nuevo valor con los valores de referencia	Determinación del subintervalo que contiene el mínimo
4	Reducción del intervalo al subintervalo seleccionado	Convergencia progresiva hacia el extremo de la función

Esta técnica fue descubierta por Kiefer en 1953, quien también identificó la búsqueda de Fibonacci. La búsqueda de la sección dorada representa el límite de la búsqueda de Fibonacci para un largo número de evaluaciones de la función. La eficiencia del método radica en su capacidad para mantener la proporción dorada a lo largo de las iteraciones, lo que permite un ahorro significativo en las llamadas a la función comparado con otros métodos de búsqueda.

Fundamento matemático y proporción dorada

El fundamento matemático de la búsqueda de la sección dorada radica en la selección estratégica de puntos de prueba dentro de un intervalo dado, con el objetivo de reducir el rango de búsqueda de manera eficiente. Este método se aplica específicamente a funciones unimodales, donde el extremo se encuentra en un intervalo conocido. La clave del algoritmo es mantener las distancias entre los puntos de evaluación en una proporción específica, conocida como la proporción dorada, denotada por φ (aproximadamente 1.618033988).

Selección de puntos y proporción dorada

Para garantizar una reducción eficiente del intervalo de búsqueda, el algoritmo selecciona dos puntos interiores, llamémoslos x1 y x2, dentro del intervalo [a, b]. La elección de estos puntos debe asegurar que las distancias entre ellos y los extremos del intervalo sigan una relación constante. Esta relación se expresa mediante la ecuación:

b - a x - a = x - a b - x = φ

Donde φ es la proporción dorada. Esta ecuación asegura que la relación entre la longitud total del intervalo y la longitud de los subintervalos sea constante, lo que permite una reducción uniforme del rango de búsqueda en cada iteración.

Derivación de la proporción dorada

Para obtener la relación b/a = φ, se elimina la variable intermedia c del sistema de ecuaciones. Supongamos que tenemos un intervalo [a, b] y dos puntos interiores x1 y x2. Las distancias entre estos puntos y los extremos deben cumplir con la proporción dorada. Al resolver el sistema de ecuaciones resultante, se obtiene la relación:

b - a x - a = φ

Esta relación garantiza que los puntos de evaluación estén distribuidos de manera que eviten la convergencia lenta y mantengan una reducción constante del intervalo de búsqueda.

Evitar la convergencia lenta

Mantener la proporción dorada entre los puntos de evaluación es crucial para evitar que los puntos estén demasiado cerca de los extremos del intervalo. Si los puntos de evaluación se acercan excesivamente a los extremos, la reducción del intervalo se vuelve menos eficiente, lo que puede llevar a una convergencia lenta. La proporción dorada asegura que los puntos estén distribuidos de manera equilibrada, lo que optimiza la reducción del intervalo en cada iteración.

En resumen, la búsqueda de la sección dorada utiliza la proporción dorada para seleccionar puntos de prueba que garantizan una reducción eficiente del intervalo de búsqueda. La selección adecuada de puntos y la mantención de la proporción dorada son fundamentales para la eficiencia del algoritmo.

Condición de terminación y precisión

La implementación práctica de la búsqueda de la sección dorada requiere establecer criterios rigurosos para detener el proceso iterativo y garantizar que el extremo hallado cumpla con los requisitos de precisión del problema. La condición de terminación no depende únicamente del número de iteraciones, sino de la relación entre la distancia entre los puntos de evaluación actuales y la magnitud de dichos puntos. Este enfoque permite adaptar la precisión relativa al tamaño de la variable independiente, lo cual es fundamental cuando la escala de la función varía significativamente.

Criterio de precisión relativa

Según la metodología descrita en la referencia académica 'Numerical Recipes in C', la condición de terminación se basa en una cota de precisión relativa. El algoritmo evalúa si la diferencia absoluta entre los dos puntos internos de la sección dorada es menor que un umbral calculado dinámicamente. Este umbral se define como el producto de un parámetro de tolerancia, denotado como τ, y la suma de los valores absolutos de ambos puntos de evaluación. Esta fórmula asegura que la precisión sea proporcional a la magnitud de la variable, evitando errores relativos excesivos en escalas grandes o pequeñas.

La condición matemática se expresa mediante la siguiente desigualdad:

| x 1 - x 2 | < τ · ( | x 1 | + | x 2 | )

En esta expresión, x₁ y x₂ representan las coordenadas de los dos puntos internos actuales donde se ha evaluado la función unimodal. La diferencia |x₁ - x₂| representa el tamaño del intervalo de incertidumbre restante. Al compararlo con τ(|x₁| + |x₂|), se normaliza el error respecto a la escala de la variable independiente.

Selección del parámetro de tolerancia

La elección del valor de τ es crítica para equilibrar la eficiencia computacional y la exactitud del resultado. 'Numerical Recipes in C' recomienda establecer τ como la raíz cuadrada de la precisión absoluta requerida para el valor de la función objetivo. Esta recomendación se basa en la suposición de que la función es suficientemente suave y que el error en la variable independiente se traduce en un error cuadrático en el valor de la función, especialmente cerca del extremo donde la primera derivada tiende a cero.

Si la precisión absoluta deseada para la función es ε, entonces se recomienda usar τ = √ε. Este enfoque permite que la búsqueda termine cuando el intervalo de incertidumbre es lo suficientemente pequeño para que la variación en el valor de la función sea menor que ε. Esta estrategia evita tanto la sobre-evaluación, que desperdicia llamadas a la función unimodal, como la sub-evaluación, que deja un intervalo de incertidumbre mayor al necesario. La aplicación de este criterio garantiza que el ahorro del 50% de llamadas comparado con la búsqueda ternaria se traduzca en una precisión controlada y predecible.

¿Qué diferencia a la búsqueda de la sección dorada de la búsqueda de Fibonacci?

La búsqueda de la sección dorada y la búsqueda de Fibonacci son dos técnicas fundamentales dentro del campo de la optimización unidimensional, diseñadas para localizar el extremo de una función unimodal mediante la reducción sucesiva del intervalo de búsqueda. Aunque comparten el objetivo común de encontrar un único mínimo o máximo local con eficiencia, difieren en su enfoque matemático y en los requisitos de implementación. Comprender estas diferencias es esencial para seleccionar el algoritmo adecuado según las restricciones del problema, como el número de evaluaciones disponibles o la necesidad de una longitud de intervalo fija.

Relación límite entre ambos algoritmos

La conexión más significativa entre ambas técnicas radica en su comportamiento asintótico. La búsqueda de la sección dorada puede considerarse como el límite de la búsqueda de Fibonacci cuando el número de evaluaciones de la función tiende a infinito. En la búsqueda de Fibonacci, la reducción del intervalo depende de los números de la secuencia de Fibonacci (F_n), donde la relación entre longitudes consecutivas del intervalo se aproxima progresivamente a la proporción dorada (φ ≈ 1.618033988). A medida que aumenta el número de iteraciones, la diferencia entre la estrategia de Fibonacci y la de la sección dorada se vuelve mínima, haciendo que esta última sea una aproximación continua y muy precisa para grandes conjuntos de datos.

Mecanismo de reducción del intervalo

La búsqueda de Fibonacci opera manteniendo un intervalo cuya longitud está directamente relacionada con un número específico de la secuencia de Fibonacci. Este enfoque permite una planificación precisa del número de pasos necesarios para alcanzar una tolerancia dada, lo que resulta ventajoso cuando el costo de evaluar la función es alto y se desea minimizar el número total de llamadas. En contraste, la búsqueda de la sección dorada utiliza una proporción constante (φ) para ubicar los puntos de prueba dentro del intervalo, lo que simplifica la implementación ya que no requiere calcular números de Fibonacci sucesivos, aunque puede requerir un número ligeramente mayor de iteraciones para alcanzar la misma precisión en casos finitos.

Aplicabilidad y eficiencia

Ambos métodos buscan optimizar el proceso de búsqueda en secuencias con un único extremo local, pero la elección entre ellos depende del contexto. La búsqueda de Fibonacci es preferible cuando se conoce de antemano el número exacto de evaluaciones permitidas, ya que permite una reducción óptima del intervalo en cada paso. Por otro lado, la búsqueda de la sección dorada ofrece una implementación más sencilla y un ahorro significativo del 50% en llamadas a la función en comparación con la búsqueda ternaria, lo que la hace ampliamente utilizada en aplicaciones prácticas donde la simplicidad y la eficiencia computacional son prioritarias. Ambos algoritmos fueron descubiertos por Kiefer en 1953, estableciendo las bases para la optimización unidimensional moderna.

Ventajas sobre la búsqueda ternaria

La búsqueda de la sección dorada presenta una ventaja algorítmica significativa frente a la búsqueda ternaria, principalmente en términos de eficiencia computacional. Esta eficiencia se manifiesta en un ahorro del 50% del número de llamadas a la función objetivo f(x) por iteración, así como en un número ligeramente inferior de pasos necesarios para alcanzar una precisión dada en la optimización numérica.

Mecanismo de ahorro computacional

En la búsqueda ternaria tradicional, cada iteración requiere evaluar la función en dos puntos nuevos dentro del intervalo actual. Esto se debe a que, tras reducir el intervalo, ninguno de los puntos evaluados previamente se conserva como punto de evaluación válido para la siguiente iteración. En consecuencia, el costo por iteración es de dos evaluaciones de función.

Por el contrario, la búsqueda de la sección dorada aprovecha la simetría inherente a la proporción dorada (φ ≈ 1.618033988). Al mantener las distancias entre los puntos de evaluación en esta proporción específica, uno de los dos puntos evaluados en la iteración actual se convierte automáticamente en uno de los dos puntos necesarios para la siguiente iteración. Este mecanismo permite reutilizar una evaluación previa, reduciendo el costo por iteración a una sola llamada a la función f(x) después de la primera iteración.

Relevancia en la optimización numérica

Esta reducción del 50% en las llamadas a la función es particularmente relevante cuando la evaluación de la función objetivo es costosa en términos de tiempo de cómputo o recursos. En problemas de optimización donde la función no es necesariamente derivada continuamente, o donde el cálculo de la derivada implica un costo adicional significativo, minimizar el número de evaluaciones directas de f(x) se convierte en un factor determinante para la eficiencia del algoritmo.

Además, el número ligeramente inferior de pasos necesarios para alcanzar una precisión dada en comparación con la búsqueda ternaria contribuye a una convergencia más rápida. Esta característica hace que la búsqueda de la sección dorada sea una técnica preferible en contextos donde la función objetivo es unimodal y la evaluación de la función representa el cuello de botella principal del proceso de optimización.

La eficiencia de este algoritmo se ve reforzada por su relación con la búsqueda de Fibonacci, de la cual constituye el límite para un largo número de evaluaciones de la función. Esta conexión teórica, establecida por Kiefer en 1953, proporciona un fundamento sólido para la aplicación de la búsqueda de la sección dorada en diversos problemas de optimización unidimensional.

Ejercicios resueltos

Ejemplo teórico de aplicación del algoritmo

A continuación, se presenta una aplicación teórica simplificada de este método, basado en los fundamentos establecidos por Kiefer (1953).

Considérese un intervalo inicial definido por los límites inferiores y superiores genéricos. El algoritmo requiere la selección de dos puntos internos que dividan el intervalo según la proporción dorada. La posición de estos puntos se determina mediante las fórmulas derivadas de la constante φ ≈ 1.618033988. Para un intervalo dado, los puntos de evaluación se calculan para mantener la simetría y la eficiencia en la reducción del rango.

En la primera iteración, se evalúa la función en ambos puntos internos. Al ser la función unimodal, la comparación de los valores de la función permite descartar una porción del intervalo. Si el valor en el punto izquierdo es mayor que el valor en el punto derecho (en una búsqueda de mínimo), el extremo se encuentra en la mitad derecha, y viceversa. Esta propiedad permite que una de las evaluaciones se mantenga para la siguiente iteración, optimizando el proceso.

La búsqueda de la sección dorada ofrece un ahorro del 50% de llamadas a la función comparado con la búsqueda ternaria. Esto se debe a que en cada paso, solo se necesita calcular un nuevo punto, mientras que el otro punto ya fue evaluado en la iteración anterior. El algoritmo es el límite de la búsqueda de Fibonacci para un largo número de evaluaciones de la función, lo que lo hace particularmente útil cuando el número de iteraciones no es de antemano conocido o es grande.

Comparación con la búsqueda de Fibonacci

Es importante distinguir la búsqueda de la sección dorada de la búsqueda de Fibonacci. Ambas técnicas fueron descubiertas por Kiefer (1953) y comparten la estrategia de reducción sucesiva del intervalo. Sin embargo, la búsqueda de Fibonacci requiere un número fijo de evaluaciones de antemano, mientras que la búsqueda de la sección dorada es más flexible, siendo el límite cuando el número de evaluaciones tiende a la infinitud.

En la práctica, la elección entre ambas depende de las características específicas del problema de optimización. La búsqueda de la sección dorada es preferible cuando se busca una simplicidad en la implementación y cuando el número de iteraciones no está estrictamente acotado. La precisión de la solución mejora con cada iteración, reduciendo el rango de incertidumbre en una proporción constante relacionada con φ.

La implementación del algoritmo requiere cuidados en la precisión numérica para evitar errores de redondeo que puedan afectar la convergencia. Los criterios de parada suelen basarse en el tamaño del intervalo final o en la diferencia entre los valores de la función en los puntos internos. La técnica es ampliamente utilizada en ingeniería y ciencias aplicadas para la optimización de funciones unimodales.

Véase también

Referencias

#Algoritmo de optimización #Proporción dorada #Función unimodal #Búsqueda de Fibonacci #Optimización numérica