Búsqueda lineal (matemáticas)

En optimización, la estrategia de búsqueda lineal es uno de los dos enfoques iterativos básicos para encontrar un mínimo local $\mathbf {x} ^{*}$ de una función objetivo $f:\mathbb {R} ^{n}\to \mathbb {R}$. El otro enfoque es la región de confianza.

El enfoque de búsqueda lineal primero encuentra una dirección de descenso a lo largo de la cual la función objetivo $f$ se reducirá y luego calcula un tamaño de paso que determina qué tan lejos $\mathbf {x}$ 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.

Ejemplo de uso

Un método de gradiente de ejemplo que usa una búsqueda de línea en el paso 4.

1. Establecer contador de iteraciones $\displaystyle k=0$, y hacer una suposición inicial $\mathbf {x} _{0}$ por lo mínimo
2. Repetir:
3.     Calcular una dirección de descenso $\mathbf {p} _{k}$
4.     Elegir $\displaystyle \alpha _{k}$ minimizar aproximadamente $h(\alpha _{k})=f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})$ donde $\alpha _{k}\in \mathbb {R} _{+}$
5.     Actualizar $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}$, y ${\textstyle k=k+1}$
6. Hasta que $\|\nabla f(\mathbf {x} _{k+1})\|$ < tolerancia

En el paso de búsqueda de línea (4), el algoritmo podría minimizar exactamente h, resolviendo $h'(\alpha _{k})=0$, o aproximando una disminución suficiente en h. Un ejemplo del primero es el método del gradiente conjugado. Esta última se denomina búsqueda lineal inexacta y se puede realizar de varias maneras, como una búsqueda lineal de retroceso o utilizando las condiciones de Wolfe.

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

Algoritmos

Métodos de búsqueda directa

En este método, primero se debe poner entre paréntesis el mínimo, por lo que el algoritmo debe identificar los puntos x₁ y x₂ de modo que el mínimo buscado se encuentre entre ellos. Luego se divide el intervalo calculando $f(x)$ en dos puntos internos, x₃ y x₄, rechazando cualquiera de los dos puntos externos que no sea adyacente al de x₃ y x₄ que tiene el valor de función más bajo. En los pasos posteriores, solo es necesario calcular un punto interno adicional. De los diversos métodos para dividir el intervalo,​ la búsqueda de la sección áurea es particularmente simple y efectiva, ya que las proporciones del intervalo se conservan independientemente de cómo proceda la búsqueda:

${\frac {1}{\varphi }}(x_{2}-x_{1})=x_{4}-x_{1}=x_{2}-x_{3}=\varphi (x_{2}-x_{4})=\varphi (x_{3}-x_{1})=\varphi ^{2}(x_{4}-x_{3})$

dónde

$\varphi ={\frac {1}{2}}(1+{\sqrt {5}})\approx 1.618$

Véase también

• Búsqueda de la sección dorada
• Búsqueda de cuadrícula
• Tasa de aprendizaje
• Búsqueda de patrones (optimización)
• Método de la secante

Bibliografía

• Dennis, J. E., Jr.; Schnabel, Robert B. (1983). «Globally Convergent Modifications of Newton's Method». Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice-Hall. pp. 111–154. ISBN 0-13-627216-9. 
• Nocedal, Jorge; Wright, Stephen J. (1999). «Line Search Methods». Numerical Optimization. New York: Springer. pp. 34-63. ISBN 0-387-98793-2. 
• Sun, Wenyu; Yuan, Ya-Xiang (2006). «Line Search». Optimization Theory and Methods : Nonlinear Programming. New York: Springer. pp. 71-117. ISBN 0-387-24975-3. 

Enlaces externos

• Datos: Q3278015