El Método de la Sección Dorada

´ Indice

14.1. Introduccio´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 14.2. M´etodo de la Seccio´n Dorada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 14.3. Ubicaci´on del Intervalo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 14.4. Algoritmo Basado en la Seccio´n Dorada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 14.5. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 14.6. Tarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

14.1. Introducci´on

Algunos de los m´etodos num´ericos de bu´squeda de o´ptimos de una funcio´n en varias variables se basan en m´etodos de bu´squeda de ´optimos en una variable. Por ejemplo, el m´etodo de ascenso ma´s ra´pido elige un punto dado y determina la direcci´on de m´aximo crecimiento en tal punto. Esta direcci´on es la del gradiente de la funcio´n en dicho punto. As´ı y partiendo del punto y siguiendo esta direcci´on avanza para localizar el o´ptimo en dicha direcci´on. Imaginese avanzando en l´ınea recta y tomando en cuenta s´olo la evaluaci´on de la funcio´n para determinar el punto en la l´ınea con la mayor evaluaci´on. Una vez alcanzado este punto, se determina la direcci´on de m´aximo crecimiento en tal punto y se repite el proceso de bu´squeda. Por su valor pr´actico, los m´etodos de bu´squeda en una dimensio´n son dignos de revisar. Previo a revisar los m´etodos, es importante saber si el o´ptimo que buscamos existe y que no habra´ ma´s de uno. Una funcio´n que efectivamente tiene un s´olo o´ptimo recibe un nombre especial: Definicio´n

Una funcio´n es unimodal si s´olo tiene un o´ptimo (relativo o absoluto). En caso que tenga varios ´optimos se dice multimodal.

Unimodal Multimodal

En general, tener la certeza de que el ´optimo buscado existe y es u´nico, normalmente se asume que la funcio´n es unimodal y se revisan las respuestas del que entrega la aplicaci´on del algoritmo a problemas espec´ıficos. Veamos ahora uno de los m´etodos m´as usados para bu´sca de o´ptimos en una variable.

14.2. M´etodo de la Secci´on Dorada

El M´etodo de la Secci´on Dorada es un m´etodo de bu´squeda iterativo en una dimensio´n (1 variable) donde se trata de ir aproximando un punto por medio de anidamiento. La estrategia de este m´etodo se basa en tres puntos iniciales: dos considerados los extremos de un intervalo (x1 y x2) y el tercero (x3) entre los dos primeros de tal suerte que relaci´on entre la distancia de este punto interno al extremo x2 (x2 −x3) y la distancia entre los extremos (x2 −x1) es siempre una constante: x2 −x3 x2 −x1 = √5−1 2 = τ = 0.618034... Note que el punto x3 divide al segmento [x1 : x2] en dos partes: la parte [x1 : x3] es ma´s pequen˜a que la parte [x3 : x2]: el segmento [x3 : x2] es el 60.80% de [x1 : x2], mientras que [x1 : x3] tiene una longitud que es el 38.19%. El m´etodo itera generando un siguiente punto x4 en [x3 : x2] (la parte ma´s amplia) de manera que se cumple: x4 −x1 x2 −x1 = τ Note que las f´ormulas convenientes para el c´alculo de x3 y x4 son:

x4 = (1−τ)x1 + τ x2. (1)

y

x3 = τ x1 + (1−τ)x2. (2) Y la raz´on es porque en estas f´ormulas no se requiere que x1 < x2. Observemos las siguientes razones:

x4 −

x1

x2 −

x1 = ((1 −

τ) x1+τ x2) −

x1

x2 −

x1

= τ x2 −

τ x1

x2 −

x1 = τ

x2 −

x3

x2 −

x1 = x2 −

(τ x1+(1 −

τ) x2)

x2 −

x1

= τ x2 −

τ x1

x2 −

x1 = τ

x3 −

x1

x4 −

x1 = (τ x1+(1 −

τ) x2) −

x1

(1 −

τ) x1+τ x2 −

x1

= (1 −

τ)(x2 −

x1)

τ (x2 −

x1) = 1 −

τ τ = τ

x2 −

x4

x2 −

x3 = x2 −

((1 −

τ) x1+τ x2)

x2 −

τ x1 −

(1 −

τ) x2

= (1 −

τ)(x2 −

x1)

τ (x2 −

x1) = 1 −

τ τ = τ

x1 x2 x4

I6

x3

I1

I4 I5 I2 I3 τ =

I 3

I

...