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 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. ${\displaystyle \mathbf {x} ^{*}}$ ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle \mathbf {x} }$

Búsqueda lineal unidimensional

Supongamos que f es una función unidimensional, , y que es unimodal , es decir, que 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] : sec.5} ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$

Métodos de orden cero

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

• Búsqueda ternaria : escoja 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 )≥f( c ), entonces x* debe estar en [ b , z ]. En ambos casos, podemos reemplazar el intervalo de búsqueda por uno más pequeño. Si escogemos b , c muy cerca del centro del intervalo, entonces el intervalo se contrae en ~1/2 en cada iteración, pero necesitamos dos evaluaciones de función por iteración. Por lo tanto, el método tiene convergencia lineal con tasa . Si escogemos b,c tal que la partición a,b,c,z tenga tres intervalos de igual longitud, entonces el intervalo se contrae en 2/3 en cada iteración, por lo que el método tiene convergencia lineal con tasa . ${\displaystyle {\sqrt {0.5}}\approx 0.71}$ ${\displaystyle {\sqrt {2/3}}\approx 0.82}$
• Búsqueda de Fibonacci: Es una variante de la búsqueda ternaria en la que se seleccionan los puntos b , c en función de la sucesión de Fibonacci . En cada iteración, solo se necesita una evaluación de la función, ya que el otro punto ya era un punto final de un intervalo anterior. Por lo tanto, el método tiene convergencia lineal con tasa . ${\displaystyle 1/\varphi \approx 0.618}$
• Búsqueda de la sección áurea : esta es 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 la función en cada iteración y el método tiene convergencia lineal con tasa . Esta proporció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] : sec.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 tasa 0,5.

Métodos de ajuste de curvas

Los métodos de ajuste de curvas intentan alcanzar la 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 procedemos a la siguiente iteración: ^{[1] : sec.5}

• El método de Newton es un caso especial de un método de ajuste de curvas, en el que la curva es un polinomio de grado dos, construido utilizando las derivadas primera y segunda 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 superlineal de orden . ${\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 convergencia superlineal cuando se inician lo suficientemente cerca del mínimo local, pero pueden divergir en caso contrario. Los métodos de ajuste de curvas con salvaguarda 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 salvaguarda; si no lo está, entonces se utiliza el método de salvaguarda para calcular la siguiente iteración. ^{[1] : 5.2.3.4}

Búsqueda de línea multidimensional

En general, tenemos una función objetivo multidimensional . El método de búsqueda lineal 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 cuánto se debe mover 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 ejemplo de método de gradiente que utiliza una búsqueda lineal en el paso 5: ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle \mathbf {x} }$

1. Establezca un 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. Encuentra 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ínea (2.3), el algoritmo puede minimizar h exactamente , resolviendo , o aproximadamente , utilizando uno de los métodos de búsqueda de línea unidimensional mencionados anteriormente. También se puede resolver de forma flexible , solicitando una disminución suficiente en h que no se aproxime necesariamente al óptimo. Un ejemplo del primero es el método del gradiente conjugado . El último se denomina búsqueda de línea inexacta y se puede realizar de varias formas, como una búsqueda de línea de retroceso o utilizando las condiciones de Wolfe . ${\displaystyle h'(\alpha _{k})=0}$

Superando los mínimos locales

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

Véase también

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

Referencias

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

Lectura adicional

• 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 . Englewood Cliffs: Prentice-Hall. págs. 111–154. ISBN 0-13-627216-9.
• Nocedal, Jorge; Wright, Stephen J. (1999). "Métodos de búsqueda lineal". Optimización numérica . Nueva York: Springer. pp. 34–63. ISBN 0-387-98793-2.
• Sun, Wenyu; Yuan, Ya-Xiang (2006). "Búsqueda lineal". Teoría y métodos de optimización: programación no lineal . Nueva York: Springer. págs. 71–117. ISBN 0-387-24975-3.