Búsqueda lineal (matemáticas)
# 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.

* Establecer contador de iteraciones $\displaystyle k=0$, y hacer una suposición inicial $\mathbf {x} _{0}$ por lo mínimo
* Repetir:
* Calcular una dirección de descenso $\mathbf {p} _{k}$
* Elegir $\displaystyle \alpha _{k}$ minimizar aproximadamente $h(\alpha _{k})=f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})$ donde $\alpha _{k}\in \mathbb {R} _{+}$
* Actualizar $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}$, y k=k+1{\textstyle k=k+1}
* 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_1$ y $x_2$ de modo que el mínimo buscado se encuentre entre ellos. Luego se divide el intervalo calculando $f(x)$ en dos puntos internos, $x_3$ y $x_4,$ rechazando cualquiera de los dos puntos externos que no sea adyacente al de $x_3$ y $x_4$ 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$
