búsqueda de línea

Algoritmo de optimización

En optimización , la búsqueda lineal es un enfoque iterativo básico para encontrar un mínimo local de una función objetivo . Primero encuentra una dirección de descenso a lo largo de la cual se reducirá la función objetivo y luego calcula un tamaño de paso que determina qué tan lejos debe moverse en esa dirección. La dirección de descenso se puede calcular mediante varios métodos, como el descenso de gradiente o el método cuasi-Newton . El tamaño del paso se puede determinar de forma exacta o inexacta. ${\displaystyle \mathbf {x} ^{*}}$ ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle \mathbf {x} }$

Búsqueda de líneas unidimensionales

Supongamos que f es una función unidimensional, y supongamos que es unimodal , es decir, contiene exactamente un mínimo local x * en un intervalo dado [ a , z ]. Esto significa que f es estrictamente decreciente en [a,x*] y estrictamente creciente en [x*, z ]. Hay varias formas de encontrar un punto mínimo (aproximado) en este caso. ^{[1] : sección 5} ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$

Métodos de orden cero

Los métodos de orden cero utilizan sólo evaluaciones de funciones (es decir, un oráculo de valores ), no derivados: ^{[1] : sec.5}

• Búsqueda ternaria : elija dos puntos b,c tales que a < b < c < z . Si f( b )≤f( c ), entonces x* debe estar en [ a , c ]; si f( b )≥( c ), entonces x* debe estar en [ b , z ]. En ambos casos podemos sustituir el intervalo de búsqueda por uno más pequeño. Si elegimos b , c muy cerca del centro del intervalo, entonces el intervalo se reduce ~1/2 en cada iteración, pero necesitamos dos evaluaciones de funciones por iteración. Por tanto, el método tiene convergencia lineal con la tasa . Si elegimos b,c de modo que la partición a,b,c,z tenga tres intervalos de igual longitud, entonces el intervalo se reduce en 2/3 en cada iteración, por lo que el método tiene convergencia lineal con la tasa . ${\displaystyle {\sqrt {0.5}}\approx 0.71}$ ${\displaystyle {\sqrt {2/3}}\approx 0.82}$
• Búsqueda de Fibonacci: Esta es una variante de la búsqueda ternaria en la que los puntos b , c se seleccionan en función de la secuencia de Fibonacci . En cada iteración, sólo se necesita una evaluación de función, ya que el otro punto ya era un punto final de un intervalo anterior. Por tanto, el método tiene convergencia lineal con la tasa . ${\displaystyle 1/\varphi \approx 0.618}$
• Búsqueda de sección áurea : Se trata de una variante en la que los puntos b , c se seleccionan en función de la proporción áurea . Nuevamente, solo se necesita una evaluación de función en cada iteración y el método tiene convergencia lineal con la tasa . Esta relación es óptima entre los métodos de orden cero. ${\displaystyle 1/\varphi \approx 0.618}$

Los métodos de orden cero son muy generales: no suponen diferenciabilidad ni siquiera continuidad.

Métodos de primer orden

Los métodos de primer orden suponen que f es continuamente diferenciable y que podemos evaluar no sólo f sino también su derivada. ^{[1] : sección 5}

• El método de bisección calcula la derivada de f en el centro del intervalo, c : si f'(c)=0, entonces este es el punto mínimo; si f'( c )>0, entonces el mínimo debe estar en [ a , c ]; si f'( c )<0, entonces el mínimo debe estar en [ c , z ]. Este método tiene convergencia lineal con una tasa de 0,5.

Métodos de ajuste de curvas

Los métodos de ajuste de curvas intentan lograr una convergencia superlineal suponiendo que f tiene alguna forma analítica, por ejemplo, un polinomio de grado finito. En cada iteración, hay un conjunto de "puntos de trabajo" en los que conocemos el valor de f (y posiblemente también su derivada). Con base en estos puntos, podemos calcular un polinomio que se ajuste a los valores conocidos y encontrar su mínimo analíticamente. El punto mínimo se convierte en un nuevo punto de trabajo y pasamos a la siguiente iteración: ^{[1] : sec.5}

• El método de Newton es un caso especial de método de ajuste de curvas, en el que la curva es un polinomio de grado dos, construido utilizando la primera y segunda derivadas de f . Si el método se inicia lo suficientemente cerca de un mínimo local no degenerado (= con una segunda derivada positiva), entonces tiene convergencia cuadrática .
• Regula falsi es otro método que ajusta la función a un polinomio de grado dos, pero utiliza la primera derivada en dos puntos, en lugar de la primera y la segunda derivada en el mismo punto. Si el método se inicia lo suficientemente cerca de un mínimo local no degenerado, entonces tiene convergencia de orden superlineal . ${\displaystyle \varphi \approx 1.618}$
• El ajuste cúbico se ajusta a un polinomio de grado tres, utilizando tanto los valores de la función como su derivada en los dos últimos puntos. Si el método se inicia lo suficientemente cerca de un mínimo local no degenerado, entonces tiene convergencia cuadrática .

Los métodos de ajuste de curvas tienen una convergencia superlineal cuando se inician lo suficientemente cerca del mínimo local, pero de lo contrario pueden divergir. Los métodos de ajuste de curvas protegidos ejecutan simultáneamente un método de convergencia lineal en paralelo al método de ajuste de curvas. Comprueban en cada iteración si el punto encontrado por el método de ajuste de curvas está lo suficientemente cerca del intervalo mantenido por el método de salvaguardia; si no es así, se utiliza el método de protección para calcular la siguiente iteración. ^{[1] : 5.2.3.4}

Búsqueda de líneas multidimensionales

En general, tenemos una función objetivo multidimensional . El método de búsqueda de líneas primero encuentra una dirección de descenso a lo largo de la cual se reducirá la función objetivo y luego calcula un tamaño de paso que determina qué tan lejos debe moverse a lo largo de esa dirección. La dirección de descenso se puede calcular mediante varios métodos, como el descenso de gradiente o el método cuasi-Newton . El tamaño del paso se puede determinar de forma exacta o inexacta. A continuación se muestra un método de gradiente de ejemplo que utiliza una búsqueda de líneas en el paso 5: ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle \mathbf {x} }$

1. Configure el contador de iteraciones y haga una estimación inicial del mínimo. Elija una tolerancia. ${\displaystyle k=0}$ ${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle \epsilon }$
2. Bucle:
   1. Calcular una dirección de descenso . ${\displaystyle \mathbf {p} _{k}}$
   2. Defina una función unidimensional , que represente el valor de la función en la dirección de descenso dado el tamaño del paso. ${\displaystyle h(\alpha _{k})=f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})}$
   3. Encuentre un que minimice sobre . ${\displaystyle \displaystyle \alpha _{k}}$ ${\displaystyle h}$ ${\displaystyle \alpha _{k}\in \mathbb {R} _{+}}$
   4. Actualizar y ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}$ ${\textstyle k=k+1}$
3. Hasta ${\displaystyle \|\nabla f(\mathbf {x} _{k+1})\|<\epsilon }$

En el paso de búsqueda de líneas (2.3), el algoritmo puede minimizar h exactamente , resolviendo , o aproximadamente , usando uno de los métodos de búsqueda de líneas unidimensionales mencionados anteriormente. También se puede resolver de manera vaga , pidiendo una disminución suficiente en h que no necesariamente se aproxima al óptimo. Un ejemplo del primero es el método del gradiente conjugado . Esto último se denomina búsqueda de líneas inexactas y se puede realizar de varias maneras, como una búsqueda de líneas hacia atrás o utilizando las condiciones de Wolfe . ${\displaystyle h'(\alpha _{k})=0}$

Superar los mínimos locales

Al igual que otros métodos de optimización, la búsqueda de líneas se puede combinar con el recocido simulado para permitirle saltar algunos mínimos locales .

Ver también

• Región de confianza : un enfoque dual para encontrar un mínimo local: primero calcula el tamaño del paso y luego determina la dirección de descenso.
• Búsqueda de cuadrícula
• Tasa de aprendizaje
• Búsqueda de patrones (optimización)
• método secante

Referencias

1. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .

Otras lecturas

• Dennis, JE Jr.; Schnabel, Robert B. (1983). "Modificaciones globalmente convergentes del método de Newton". Métodos numéricos para optimización sin restricciones y ecuaciones no lineales . Acantilados de Englewood: Prentice-Hall. págs. 111-154. ISBN 0-13-627216-9.
• Nocedal, Jorge; Wright, Stephen J. (1999). "Métodos de búsqueda de líneas". Optimización numérica . Nueva York: Springer. págs. 34–63. ISBN 0-387-98793-2.
• Sol, Wenyu; Yuan, Ya-Xiang (2006). "Búsqueda de líneas". Teoría y métodos de optimización: programación no lineal . Nueva York: Springer. págs. 71-117. ISBN 0-387-24975-3.