Seccion dorada

B´squeda en una Dimensi´n u o
Departamento de Matem´ticas, CSI/ITESM a 1 de noviembre de 2009

´ Indice
14.1. Introducci´n . . . . . . . . . . . o 14.2. M´todo de la Secci´n Dorada . e o 14.3. Ubicaci´n del Intervalo . . . . . o 14.4. Algoritmo Basado en la Secci´n o 14.5. Ejemplos . . . . . . . . . . . . 14.6. Tarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dorada . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 3 3 4 414.1.

Introducci´n o

Algunos de los m´todos num´ricos de b´squeda de optimos de una funci´n en varias variables se basan e e u ´ o en m´todos de b´squeda de ´ptimos en una variable. Por ejemplo, el m´todo de ascenso m´s r´pido elige un e u o e a a o punto dado y determina la direcci´n de m´ximo crecimiento en tal punto. Esta direcci´n es la del gradiente de o a o ´ la funci´n en dicho punto. As´y partiendo del punto y siguiendo esta direcci´n avanza para localizar el optimo o ı en dicha direcci´n. Imaginese avanzando en l´ o ınea recta y tomando en cuenta s´lo la evaluaci´n de la funci´n o o o para determinar el punto en la l´ ınea con la mayor evaluaci´n. Una vez alcanzado este punto, se determina la o direcci´n de m´ximo crecimiento en tal punto y se repite el proceso de b´squeda. Porsu valor pr´ctico, los o a u a m´todos de b´squeda en una dimensi´n son dignos de revisar. e u o Previo a revisar los m´todos, es importante saber si el optimo que buscamos existe y que no habr´ m´s de e ´ a a uno. Una funci´n que efectivamente tiene un s´lo optimo recibe un nombre especial: o o ´ Definici´n o Una funci´n es unimodal si s´lo tiene un optimo (relativo o absoluto). En caso que tengavarios o o ´ o ´ptimos se dice multimodal. Unimodal Multimodal

En general, tener la certeza de que el ´ptimo buscado existe y es unico, normalmente se asume que la funci´n o ´ o es unimodal y se revisan las respuestas del que entrega la aplicaci´n del algoritmo a problemas espec´ o ıficos. Veamos ahora uno de los m´todos m´s usados para b´sca de optimos en una variable. e a u ´

14.2.M´todo de la Secci´n Dorada e o

El M´todo de la Secci´n Dorada es un m´todo de b´squeda iterativo en una dimensi´n (1 variable) donde e o e u o se trata de ir aproximando un punto por medio de anidamiento. La estrategia de este m´todo se basa en tres e 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´nentre la distancia de este punto interno al extremo x2 (x2 − x3 ) y la distancia entre o los extremos (x2 − x1 ) es siempre una constante: √ 5−1 x2 − x3 = = τ = 0.618034 . . . x2 − x1 2 Note que el punto x3 divide al segmento [x1 : x2 ] en dos partes: la parte [x1 : x3 ] es m´s peque˜a que la parte a n [x3 : x2 ]: el segmento [x3 : x2 ] es el 60.80 % de [x1 : x2 ], mientras que [x1 : x3 ] tiene unalongitud que es el 38.19 %. El m´todo itera generando un siguiente punto x4 en [x3 : x2 ] (la parte m´s amplia) de manera que e a se cumple: x4 − x1 =τ x2 − x1 Note que las f´rmulas convenientes para el c´lculo de x3 y x4 son: o a x4 = (1 − τ ) x1 + τ x2 . y x3 = τ x1 + (1 − τ ) x2 . Y la raz´n es porque en estas f´rmulas no se requiere que x1 < x2 . o o
x4 −x1 x2 −x1

(1)

(2) Observemos lassiguientes razones:

= =

((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−τ τ...