sección dorada









Optimización





Búsqueda en una Dimensión


Dr. E Uresti

ITESM

























Búsqueda en una Dimensión Profr. E. Uresti - p. 1/19
Introducción



Algunos de los métodos numéricos de búsqueda de óptimos de una función en varias variables se basan en métodos de búsqueda de óptimos en una variable. Por ejemplo, el método deascenso más rápido elige un punto dado y determina la dirección de máximo crecimiento en tal punto. Esta dirección es la del gradiente de la función en dicho punto. Así, y partiendo del punto y siguiendo esta dirección, avanza para localizar el óptimo en dicha dirección. Imaginese avanzando en línea recta y tomando en cuenta sólo la evaluación de la función para determinar el punto en la línea con lamayor evaluación. Una vez alcanzado este punto, se determina la dirección de máximo crecimiento en tal punto y se repite el proceso de búsqueda. Por su valor práctico, los métodos de búsqueda en
una dimensión son dignos de revisar.

Introduccio´ n GS Bracketing
B y GS Ejemplos Tarea











Búsqueda en una Dimensión Profr. E. Uresti - p. 2/19Previo a revisar los métodos, es importante saber si el óptimo que buscamos existe y que no habrá más de uno. Una función que efectivamente tiene un sólo óptimo recibe un nombre especial:
Definicio´ n

Una función es unimodal si sólo tiene un óptimo (relativo o absoluto). En caso que tenga varios óptimos se dice multimodal.

Introduccio´ n GS Bracketing
B y GS Ejemplos TareaBúsqueda en una Dimensión Profr. E. Uresti - p. 3/19


Unimodal Multimodal
Introduccio´ n GS Bracketing
B y GS Ejemplos
Tarea





































Búsqueda en una Dimensión Profr. E. Uresti - p. 4/19
Método de la Sección Dorada



La estrategia de este método se basaen 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ón 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 ] endos partes: la parte [x1 : x3 ] es más pequeña que la parte [x3 : x2 ]: el segmento [x3 : x2 ] es el 61.80 % de [x1 : x2 ], mientras que [x1 : x3 ] tiene una
longitud que es el 38.19 %.









x1 x3 x2






Búsqueda en una Dimensión Profr. E. Uresti - p. 5/19


El método itera generando unsiguiente punto x4 en [x3 : x2 ] (la parte más amplia) de manera que se cumple:

x4 − x1 = τ x2 − x1


Note que las fórmulas convenientes para el cálculo de x3 y x4 son:

Introduccio´ n GS Bracketing
B y GS Ejemplos Tarea



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 .








x1 x3 x4x2


Observemos las siguientes razones:

Introduccio´ n
GS

x4 −x1
x2 −x1

((1−τ ) x1 +τ x2 )−x1
x2 −x1
Bracketing B y GS Ejemplos
τ x2 −τ x1
2 1
Tarea

x2 −x3
x2 −x1
x2 −(τ x1 +(1−τ ) x2 )
x2 −x1


τ x2 −τ x1
= −x = τ
x3 −x1
x4 −x1
(τ x1 +(1−τ ) x2 )−x1
(1−τ ) x1 +τ x2 −x1

= (1−τ )(x2 −x1 )
2 1

1−τ τ

x2 −x4
x2 −x3
x2 −((1−τ ) x1 +τ x2 )
x2 −τ x1−(1−τ ) x2

= (1−τ ) (x2 −x1 )
2 1

1−τ τ




I1



τ = I3
1
I4 I2
I1 I4

I3 = 0.6180 . . .

1 − τ = I2 I5 I6
1 1 4
I6 = 0.3819 . . .
3




x1 x3 x4 x2


Dependiendo de la función a maximizar, el algoritmo escoge tres puntos de los cuatro disponibles de manera que la situación se repite en las...