A130 17

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 de ascenso más
rápido elige un punto dado y determina la dirección de máximo

´
Introduccion
GSBracketing
B y GS
Ejemplos
Tarea

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 la
mayor evaluación. Una vez alcanzadoeste 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.

Búsqueda en una Dimensión

Profr. E. Uresti - p. 2/19

Previo 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 tieneun sólo óptimo recibe un nombre especial:

´
Introduccion
GS
Bracketing
B y GS
Ejemplos
Tarea

´
Definicion

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

Búsqueda en una Dimensión

Profr. E. Uresti - p. 3/19

Unimodal

Búsqueda en una Dimensión

Multimodal

´
Introduccion
GS
Bracketing
B y GS
Ejemplos
Tarea

Profr. E.Uresti - p. 4/19

Método de la Sección Dorada
La estrategia de este método 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ó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
5−1
=
= τ =0.618034 . . .
x2 − x1
2

´
Introduccion
GS
Bracketing
B y GS
Ejemplos
Tarea

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 [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

Búsqueda en una Dimensión

x3

x2

Profr. E. Uresti - p. 5/19

El método iteragenerando un siguiente punto x4 en [x3 : x2 ] (la
parte más amplia) de manera que se cumple:
x4 − x1
=τ
x2 − x1

´
Introduccion
GS
Bracketing
B y GS
Ejemplos
Tarea

Note que las fórmulas convenientes para el cálculo de x3 y x4 son:
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

Búsqueda en una Dimensión

x3

x4

x2Profr. E. Uresti - p. 6/19

Observemos las siguientes razones:
x4 −x1
x2 −x1

x2 −x3
x2 −x1

x3 −x1
x4 −x1

x2 −x4
x2 −x3

=

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

=

τ x2 −τ x1
x2 −x1

=

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

=

τ x2 −τ x1
x2 −x1

=τ

=τ

=

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

=

(1−τ )(x2 −x1 )
τ (x2 −x1 )

=

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

=

(1−τ ) (x2 −x1 )
τ (x2 −x1 )Búsqueda en una Dimensión

´
Introduccion
GS
Bracketing
B y GS
Ejemplos
Tarea

=

=

1−τ
τ

1−τ
τ

=τ

=τ

Profr. E. Uresti - p. 7/19

I1
I4

I5

I2

τ =

I3
I1

=

I4
I1

=

I2
I4

=

I5
I3

= 0.6180 . . .

1−τ =

I2
I1

=

I5
I1

=

I6
I4

=

I6
I3

= 0.3819 . . .

I3

I6
x1

x3 x4

Búsqueda en una Dimensión

x2

Profr. E. Uresti - p. 8/19

Dependiendo de la función a maximizar, el algoritmoescoge tres
puntos de los cuatro disponibles de manera que la situación se
repite en las proporciones de los intervalos. En general, si Ii es la
longitud del intervalo en la iteración i se cumple que:

´
Introduccion
GS
Bracketing
B y GS
Ejemplos
Tarea

In = τ n−1 I1
Por tanto, conociendo el intervalo inicial (I1 ) y sabiendo a qué
precisión se desea estimar el punto (In ), es fácil estimar el total...