Optmizacion Numerica

El m´todo del descenso m´s pronunciado e a
Octavio Alberto Agust´ Aquino ın 4 de junio de 2005 Grupo 705

´ Indice
1. Optimizaci´n no lineal sin restricciones o 1.1. Direcciones de b´squeda . . . . . . . . . u 1.2. C´lculo del tama˜o de paso . . . . . . . a n 1.3. Implementaci´n . . . . . . . . . . . . . . o 1.4. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 2 4 8

´ Indice de figuras
1. 2. 3. Funci´n de Rosenbrock. . . . . . . . . . . . . . . . . . . o Convergencia del m´todo del descenso m´s pronunciado e a funci´n de Rosenbrock. . . . . . . . . . . . . . . . . . . . o M´ximo descenso con aproximaci´n del gradiente. . . . a o . . . para . . . . . . . . la . . . . 5 68

1.

Optimizaci´n no lineal sin restricciones o

Problema 1 Dada una funci´n diferenciable f : R2 → R, hallar x∗ ∈ R2 de o modo que existe una vecindad N de x∗ tal que f (x∗ ) ≤ f (x) para todo x ∈ N . Tal punto se llama m´ ınimo local de f . Los algoritmos para resolver este problema, dada una aproximaci´n x0 al o k m´ ınimo local, generan una sucesi´n de iteraciones {xi }i=0 que terminacuando o no se puede mejorar la aproximaci´n o se alcanza alguna precisi´n prestablecida. o o Para moverse de un punto xk al siguiente xk+1 en la iteraci´n, se utiliza la o informaci´n de f en xk (y ocasionalmente la de los valores previos x0 , . . . , xk ). o Hay dos formas de lograr esta sucesi´n. La estrategia que analizaremos o aqu´ brevemente es la de b´squeda de l´ ı u ınea. En este caso,el algoritmo escoge una direcci´n pk y busca a lo largo de esta direcci´n desde el punto actual o o por un nuevo punto que reduzca el valor de f . Se necesita, adem´s, calcular la a

1

distancia que recorrerse en esta direcci´n, lo cual se puede conseguir resolviendo o el siguiente problema de minimizaci´n o m´ f (xk + αpk ). ın
α>0

Sin embargo, resolver este problema exactamente esmuchas veces innecesario, y basta con aproximarse a una soluci´n para calcular un nuevo punto de la o sucesi´n. o

1.1.

Direcciones de b´ squeda u

La direcci´n de m´ximo descenso − fk es la elecci´n m´s obvia para buscar o a o a el m´ ınimo, pues es la direcci´n en la que f decrece m´s r´pidamente. Este o a a esquema nos conduce al m´todo del descenso m´s pronunciado. En efecto, por e a elteorema de Taylor, tenemos que para cualquier direcci´n de b´squeda p y o u par´metro de tama˜o de paso α, tenemos a n 1 f (xk + αp) = f (xk ) + αpT fk + α2 pT 2
2

f (xk + tp) p,

para alg´n p ∈ (0, α). La tasa de crecimiento de f a lo largo de p en xk es el u coeficiente de α, es decir, pT fk . Por lo tanto, la direcci´n unitaria p de m´ximo o a decrecimiento es la soluci´n del problema o m´pT fk . ın
p =1

En virtud de que pT fk = p donde θ es ´ngulo entre p y a fk cos θ, fk , se infiere que el m´ ınimo se alcanza cuando p=− fk . fk

Aunque con el m´todo del descenso m´s pronunciado no necesita calcular e a segundas derivadas. De hecho, con cualquier direcci´n de descenso producir´ un o a decremento en f , siempre que el tama˜o de paso sea suficientemente peque˜o. n n Para veresto, acudimos al teorema de Taylor, f (xk + pk ) = f (xk ) + pT fk + O k
2

. fk es

Si pk es una direcci´n de descenso, el coseno del ´ngulo entre pk y o a negativo, luego pT fk < 0, as´ que ı k f (xk + pk ) < f (xk ) .

2

1.2.

C´lculo del tama˜ o de paso a n

Tomar simplemente como direcci´n de descenso al vector unitario en direco ci´n contraria al gradiente no es una buenaelecci´n pues puede no converger. o o En efecto, para una funci´n tan simple como f (x) = x2 + y 2 + 1, el gradieno te f = (2x, 2y) evaluado en (0,5, 0) vale (1, 0). Al movernos en la direcci´n o opuesta a la este vector (es decir, buscando el mayor descenso), llegamos al punto (−0,5, 0). Repitiendo el proceso de calcular el gradiente y moverse en direcci´n o opuesta, nos mantendremos oscilando...