Tipos de Métodos de Búsqueda Lineal
Directos
Gradiente
Newton
Quasi-Newton
Secante
Interpolación Polinómica
Cuadrática
Cúbica
DSC (Davies, Swann y Campey)
Basados en intervalos
Bisección
Búsqueda de Fibonacci
Búsqueda Dorada
Métodos Inexactos
Armijo
Goldstein
Búsqueda de Fibonacci
Este método determina el mínimo valor de una función f sobre un intervalo cerrado [c1, c2]
Esta función puede estar definida en un dominio más amplio, pero el método requiere que dicho intervalo de búsqueda sea definido
Se asume que f es unimodal
El mínimo es determinado (al menos aproximadamente) mediante la evaluación en un cierto número de puntos
Se pretende definir una estrategia de búsqueda que seleccione la observación siguiente basada en los valores funcionales de las observaciones anteriores
Búsqueda de Fibonacci
Esto se define según el siguiente problema:
Encontrar como seleccionar sucesivamente N observaciones, sin contar con un conocimiento explícito de la función, de forma tal que podamos encontrar la más pequeña región de incertidumbre posible en donde se encuentre el mínimo
Esta región de incertidumbre es determinada en cualquier caso por: las observaciones (sus valores funcionales) y la suposición de que f es unimodal.
Luego que encontremos los valores funcionales en N puntos dentro del intervalo cerrado [c1, c2]
c1 ? x1 ? … ? xN-1 ? xN ? c2
La región de incertidumbre es el intervalo [xk-1, xk+1] donde xk es el mínimo de los N puntos evaluados. En ese intervalo se encuentra el mínimo
Búsqueda de Fibonacci
La estrategia para seleccionar sucesivamente observaciones para obtener la región de incertidumbre más pequeña se describe a continuación:
d1 = c2 – c1; es la amplitud inicial de la incertidumbre
dk ? es la amplitud de la región de incertidumbre luego de k observaciones
Si son realizadas N observaciones se tiene que
Donde Fk son los números de la secuencia Fibonacci generados por la relación:
FN = FN -1 + FN -2 donde F0 = F1 = 1
Donde cada número después de los dos primeros representa la suma de los dos precedentes
Búsqueda de Fibonacci
Procedimiento para la reducción de la sección de incertidumbre:
Especificar N, y calcular los números de la serie Fibonacci {F0, F1,…, FN}
Calcular
Colocar simétricamente desde los extremos del intervalo inicial a distanciados observaciones
De acuerdo a donde se encuentre la muestra con menor valor funcional se determina la región de incertidumbre,
La tercera muestra es colocada simétricamente dentro de este nuevo intervalo con respecto a la observación ya incluida en el intervalo, de forma tal que la amplitud de la región de incertidumbre sea
Búsqueda de la Sección Dorada
La primera condición específica que la suma de las dos sublongitudes l1 y l2 debe ser igual a la longitud original del intervalo
La segunda indica que el cociente o razón de las longitudes debe ser igual
La Razón Dorada
Búsqueda de la Sección Dorada
Se comienza con los valores extremos del intervalo xl, xu que contienen el extremo local de f(x)
Dos puntos interiores de escogen de acuerdo a
x1 = xl + d
x2 = xu – d
Se evalúa la función en los dos puntos interiores
Si f(x1) < f(x2) ? xl = x2; x2 = x1;
Si f(x2) < f(x1) ? xu = x1; x1 = x2;
x1
x2
xu
x1
xl
Ajuste Cuadrático (Método DSC, Davies, Swann y Campey)
El método DSC es un método de búsqueda lineal por ajuste de curvas (interpolación polinómica), es recomendado para determinar la región donde se encuentra el mínimo en funciones de una sola variable
En la búsqueda unidimensional DSC, se toman pasos cuya dimensión se va incrementando sucesivamente hasta que el mínimo es sobrepasado y luego se realiza una interpolación cuadrática
Ajuste Cuadrático (Método DSC, Davies, Swann y Campey)
Se evalúa f(x) en el punto inicial x(0) – Si f(x(0) + ?x) ? f(x(0)), pase al paso 2- Si f(x(0) + ?x) > f(x(0)), haga ?x = ?x/2 y repita el paso 1
Calcule x(k+1) = x(k) + ?x
Calcule f(x(k+1))
Si f(x(k+1)) ? f(x(k)), duplique ?x (?x = 2?x) y regrese al paso 2 con k = k+1Si f(x(k+1)) > f(x(k)), denote x(k+1) como x(m), x(k) como x(m-1), etc., se reduce ?x a la mitad y se regresa al paso 2 y 3 para un solo cálculo adicional
Ajuste Cuadrático (Método DSC, Davies, Swann y Campey)
De los 4 valores igualmente espaciados de x en el conjunto {x(m+1), x(m), x(m-1), x(m-2)}, descarte x(m) o x(m-2), el que esté más lejano de la x de menor valor funcional. Los tres valores restantes del conjunto pueden ser denotados como x(a), x(b), x(c), donde x(b) es el punto central y x(a) = x(b) – ?x y x(c) = x(b) + ?x
Se realiza una interpolación cuadrática para estimar x* (el valor de la variable independiente correspondiente al mínimo de f(x))
donde ?x = x(a) – x(b)
Ajuste Cúbico
Dados xk-1 y xk junto a f(xk-1), f ’(xk-1), f(xk), y f ’(xk) es posible ajustar una ecuación cúbica en los puntos
El punto xk+1 (mínimo) puede ser determinado como el punto mínimo relativo de esta ecuación cúbica
donde,
Método del Gradiente
Supongamos que f(x) es una función de una variable a ser minimizada y que f(x) y f ’(x) existen
xk+1 = xk – f ’(xk)
Un factor de escalamiento es empleado para escalar el gradiente
xk+1 = xk – ?f ’(xk) ? Método del gradiente modificado
El valor de ? ? (0,1], es decir, es un parámetro ajustable seleccionado por el usuario
Es deseable que ? decrezca a medida que progresa la búsqueda, lo que hace que tengamos dos parámetros por ajustar: ?0 y la tasa de disminución de ?
Con el método de Newton tales parámetros son calculados directamente en cada iteración
Método de Newton
Supongamos una función f de una variable a ser minimizada y supongamos que en xk es posible evaluar f(xk), f ’(xk) y f ”(xk)
Entonces es posible construir una función cuadrática a partir del desarrollo de Taylor:
Se puede estimar xk+1 determinando el punto donde la derivada de q se hace cero
Método de Newton
Implementación
Para la implementación de este método en una función de varias variables es necesario calcular la primera y segunda derivada de la función como derivadas direccionales, obteniendo un valor escalar, de la siguiente manera, donde d es el vector unitario de la dirección de descenso
Método Quasi-Newton
Cuando no es posible evaluar analíticamente las primeras y segundas derivadas, se pueden emplear métodos de diferencias finitas para calcularlas:
Búsqueda Lineal Inexacta
En la práctica no se determina el mínimo de la búsqueda lineal en forma exacta
En este sentido, es deseable sacrificar precisión en la búsqueda lineal con el propósito de favorecer el tiempo de computo general
Recordemos que el mínimo en una búsqueda local no tiene porque ser el mínimo de la función
La imprecisión es generalmente introducida simplemente terminando la búsqueda lineal antes de que converja
La naturaleza exacta de la imprecisión depende de:
La técnica de búsqueda empleada
El criterio de parada
Búsqueda Lineal Inexacta
Criterios de terminación de la búsqueda lineal
Prueba de porcentaje: Sea xk+1 = xk + ?d; este criterio determina ? para estar dentro de un porcentaje del verdadero valor
Específicamente, se selecciona una constante c tal que 0 < c < 1 (típicamente c = 0.1) y el parámetro ? en la búsqueda lineal es determinado de forma tal que satisfaga |? – ?*| = c?* donde ?* es el verdadero valor de minimización
Búsqueda Lineal Inexacta
Regla de Armijo
Primero garantiza que ? no sea muy grande y luego que no sea muy pequeño
La regla de Armijo es implementada al considerar la función
?(0) + ? ?’(0)? para 0 < ? < 1
Esta función está representada por la línea segmentada en la figura
Búsqueda Lineal Inexacta
Regla de Armijo
Un valor de ? se considera que no es muy grande si el valor de la función cae debajo de la línea punteada; es decir, si
?(?) ? ?(0) + ? ?’(0) ?
Para asegurar que ? no sea muy pequeño, se selecciona un valor de ? > 1, y se considera que ? no es muy pequeño si
?(??) > ?(0) + ? ?’(0) ?? ,
Esto quiere decir que si ? es aumentado por un factor ?, falla el criterio anterior que requería que el valor de la función estuviera por debajo de la línea punteada
La región aceptable definida por la regla de Armijo en la figura corresponde a un valor de ? igual a 2
Búsqueda Lineal Inexacta
Regla de Armijo
En la práctica, la regla de Armijo es utilizada para definir una técnica de búsqueda lineal simplificada que no utiliza el ajuste de curvas
Se define un ? arbitrario
Si se satisface ?(?) ? ?(0) + ? ?’(0) ? ; el valor de ? es aumentado repetidas veces por ? hasta que ya no se satisface esta desigualdad y se selecciona el penúltimo ?
Si ?(?) > ?(0) + ? ?’(0) ? ; el ? inicial se considera muy grande y se divide repetidas veces por ? hasta que se consiga un ? apropiado
Valores típicos: ? = 2, y ? = 0.2
Método del Descenso más Rápido
Ejemplo 1:
Evolución del método para un ? = 0.25
Evolución del método para un ? = 0.9
Método del Descenso más Rápido
Ejemplo 2: Se desea minimizar la función
Esta función es unimodal
El mínimo está ubicado en el punto (0,0)
Supongamos que se asume como punto inicial, el punto (-1.7, 1.7)
El gradiente en un punto cualquiera es,
?f = {6x, 2y}
Método del Descenso más Rápido
Ejemplo 2: Se desea minimizar la función
Las curvas de nivel de esta función son de forma elíptica, y el cambio de la dirección de búsqueda de una iteración a otra, se observa en la trayectoria en forma de zigzag
Método de Newton
En este caso, la dirección de búsqueda se determina utilizando la segunda derivada de la función objetivo
El método aproxima la función objetivo f en la vecindad de un mínimo con una serie de Taylor truncada hasta el término de segundo orden,
Dado que la aproximación fa es una función de segundo orden, ésta es unimodal, y su mínimo es una buena aproximación del mínimo de la función objetivo
El mínimo de la función fa se determina haciendo fa´= 0 y calculando el valor de xi que satisface la ecuación
Método de Newton
Si la inversa de Hf existe, se tiene que:
Que es el denominado método de Newton o de Newton-Raphson
Direcciones de búsqueda calculada por los métodos de descenso más rápido y de Newton
Método de Newton
Ejemplo 3: Se desea minimizar la función utilizando el método de Newton
El gradiente en un punto cualquiera es,
?f = {6x, 2y}
mientras que el Hessiano es la matriz
La aproximación de esta función utilizando la serie de Taylor es exacta, debido a que es una función cuadrática
Método de Newton
En los casos en los que la función no es cuadrática, se hacen aproximaciones sucesivas del mínimo utilizando la ecuación
donde ? es positivo, hasta que se encuentra un valor cercano al extremo mínimo relativo, según una tolerancia especificada
En cada punto en los que se evalúe la ecuación anterior, debe ocurrir que el Hessiano sea una matriz positiva definida, para que la dirección de búsqueda sea una dirección descendente
En general, la condición de matriz positiva definida se cumple en la vecindad del mínimo, pero no existe garantía que ocurra en puntos lejanos al mismo
Método de Levenberg-Marquardt
Está dado por la ecuación
donde ? y ? son positivos e I es la matriz identidad
La idea es seleccionar ? de manera que la matriz ?I – Hf sea positiva definida
La ecuación anterior se aproxima al método del descenso más rápido si ? ? ?, y al método de Newton ? ? 0
Estrategia de descenso
En la práctica se utilizan estrategias de descenso que utilizan varios métodos, de la siguiente manera:
Se inicia con el método de Newton, si no hay descenso (la matriz Hessiano NO es definida positiva)
Se emplea el método de Levenberg-Marquardt con un ? inicial, por ejemplo ?k = 0.001, se realiza la factorización de Cholesky a la matriz para verificar si es definida positiva. Si la factorización de Cholesky falla (i.e. la matriz no es definida positiva) se incrementa en una razón, ?k = ???k
Si no hay descenso después de varios intentos (por ejemplo 10), se emplea el método del descenso más rápido
ANEXO
Descomposición de Cholesky
La descomposición o factorización de Cholesky expresa una matriz simétrica como el producto de una matriz triangular y su transpuesta
A = L·LT ? L: matriz triangular inferior
No todas las matrices simétricas se pueden factorizar de esta forma
Las matrices que tienen este tipo de factorización son las matrices simétricas definidas positivas. Esto implica que todos los elementos de la diagonal sean positivos y que los elementos fuera de la diagonal no sean muy grandes
Seudo código para la descomposición de Cholesky
for k = 1:n
for i = 1:k-1
sum = 0;
for j = 1:i-1
sum = sum + A(i,j)*A(k,j);
end
A(k,i) = (A(k,i) – sum)/A(i,i);
end
sum = 0;
for j = 1:k-1
sum = sum + A(k,j)^2;
end
A(k,k) = sqrt(A(k,k) – sum);
end
 Página anterior | Volver al principio del trabajo | Página siguiente  |