En optimización , la estrategia de búsqueda de líneas es uno de los dos enfoques iterativos básicos para encontrar un mínimo local de una función objetivo . El otro enfoque es la región de confianza .
El enfoque de búsqueda de línea primero encuentra una dirección de descenso a lo largo de la cual la función objetivo se reducirá 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.
Uso de ejemplo
A continuación, se muestra un ejemplo de método de degradado que utiliza una búsqueda de línea en el paso 4.
- Establecer contador de iteraciones y haz una suposición inicial por el mínimo
- Repetir:
- Calcular una dirección de descenso
- Escoger para minimizar 'libremente' encima
- Actualizar , y
- Hasta que
En el paso de búsqueda de línea (4), el algoritmo podría minimizar exactamente h , resolviendo, o libremente , pidiendo una disminución suficiente de h . Un ejemplo del primero es el método de gradiente conjugado . Esta última 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 .
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 por encima de algunos mínimos locales .
Algoritmos
Métodos de búsqueda directa
En este método, primero se debe poner entre corchetes el mínimo, por lo que el algoritmo debe identificar los puntos x 1 y x 2 de manera que el mínimo buscado se encuentre entre ellos. Luego, el intervalo se divide calculandoen dos puntos internos, x 3 y x 4 , y rechazando cualquiera de los dos puntos externos que no sea adyacente al de x 3 y x 4 que tenga el valor de función más bajo. En los pasos siguientes, solo se debe calcular un punto interno adicional. De los diversos métodos para dividir el intervalo, [1] la búsqueda de la sección áurea es particularmente simple y eficaz, ya que las proporciones del intervalo se conservan independientemente de cómo se desarrolle la búsqueda:
dónde
Ver también
Referencias
- ^ Caja, MJ; Davies, D .; Swann, WH (1969). Técnicas de optimización no lineal . Oliver y Boyd.
Otras lecturas
- Dennis, JE, Jr .; Schnabel, Robert B. (1983). "Modificaciones globalmente convergentes del método de Newton". Métodos numéricos para optimización no restringida 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ínea". Optimización numérica . Nueva York: Springer. págs. 34–63. ISBN 0-387-98793-2.
- Sun, Wenyu; Yuan, Ya-Xiang (2006). "Búsqueda de línea". Teoría y métodos de optimización: Programación no lineal . Nueva York: Springer. págs. 71-117. ISBN 0-387-24975-3.