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 GS Bracketing 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 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.

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 tiene un 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 itera generando 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

x2

Profr. 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 algoritmo escoge 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 de iteraciones requeridas para que este método se aproxime al valor requerido: ln(In ) − ln(I1 ) n=1+ ln(τ )

Búsqueda en una Dimensión

Profr. E. Uresti - p. 9/19

Ubicación del Intervalo El método de la sección dorada requiere de la ubicación de los tres primeros puntos x1 , x2 y x3 como se describen anteriormente. Cuando el método se aplica a la determinación de un máximo de una función f (x), los puntos deben satisfacer:

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

f (x1 ) < f (x3 ) y f (x3 ) ≥ f (x2 ). Es decir, la función sube y cae. Al procedimiento para encontrar tales puntos recibe el nombre de Ubicación del Intervalo de Trabajo (Bracketing).

x1

Búsqueda en una Dimensión

x3

x2

Profr. E. Uresti - p. 10/19

La estrategia inicia a partir de un punto x1 y teniendo un incremento de x inicial s. Se genera un siguiente punto x3 = x1 + s.

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

Si f (x1 ) ≥ f (x3 ) habrá que buscar hacia atrás cambiando intercambiando los puntos y el signo del incremento. Si f (x1 ) < f (x3 ), el incremento se agranda en la proporción τ por medio de la fórmula s = s/τ . f (x1 ) < f (x3 )

x1

x3

Búsqueda en una Dimensión

f (x1 ) ≥ f (x3 )

x3 = x1 x1 = x3 s = −s

Profr. E. Uresti - p. 11/19

Un siguiente punto se genera hacia adelante x2 = x3 + s. Si f (x3 ) ≥ f (x2 ) los tres puntos buscados están determinados. Si f (x3 ) < f (x2 ), entonces el procedimiento se repite tomando x1 = x3 , x2 = x3 y s = s/τ . Observe que el intervalo de bracketing va creciendo en la proporción 1/τ (≈ 1.618).

f (x3 ) ≥ f (x2 ) τs x1

f (x3 ) < f (x2 )

s x3

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

τs x2

Búsqueda en una Dimensión

x1

s x3 x1

s/τ x2 x3

x2

Profr. E. Uresti - p. 12/19

Crecimiento del intervalo de Bracketing

f (x1 ) < f (x3 )

f (x1 )

f (x3 ) ≥ f (x2 )

f (x3 )

f (x2 )

(1 + τ1 ) s 1 τ

s x1

Búsqueda en una Dimensión

x3

s x2

Profr. E. Uresti - p. 13/19

Algoritmo Basado en la Sección Dorada [1.] Inicie con un punto x1 y un incremento s; tome f1 ← f (x1 ). [2.] Tome x3 ← x1 + s y f3 ← f (x3 ). [3.] Si (f1 > f3 ), intercambie (x1 , f1 ) y (x3 , f3 ) y tome s ← −s. [4.] Tome s ← s/τ , x2 ← x3 + s, y f2 ← f (x2 ). [5.] Si (f3 > f2 ), vaya a [7.] [6.] Tome (x1 , f1 ) ← (x3 , f3 ) y (x3 , f3 ) ← (x2 , f2 ) y vaya a [4.] [7.] Tome x4 ← (1 − τ ) x1 + τ x2 y f4 ← f (x4 ). [8.] Si (f3 ≥ f4 ), tome (x2 , f2 ) ← (x1 , f1 ) y (x1 , f1 ) ← (x4 , f4 ); vaya a [10.] [9.] Tome (x1 , f1 ) ← (x3 , f3 ) y (x3 , f3 ) ← (x4 , f4 ); [10.] SiCriterio de paro = OK, termine; caso contrario vaya a [7.]

Búsqueda en una Dimensión

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

Profr. E. Uresti - p. 14/19

Casos en la comparación de f4 vs f3

I1

I1

I4 I2

x1

I5

I4

I3

I2

I5 I3

x3 x4

x2

x1

x3 x4

x1 x3

x2

x2

x3 x1

Búsqueda en una Dimensión

x2

Profr. E. Uresti - p. 15/19

Ejemplos Aplique el algoritmo anterior para encontrar el máximo de la función f (x) = −x2 − 1 partiendo de x1 = −1 y con un primer intervalo de s = 0.5.

Búsqueda en una Dimensión

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

Profr. E. Uresti - p. 16/19

Ejemplos Aplique el algoritmo anterior para encontrar el máximo de la función f (x) = −x2 − 1 partiendo de x1 = −1 y con un primer intervalo de s = 0.5.

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

´ de la direccion ´ de avance Determinacion

x1

f (x1 )

s

x3 = x1 + s

f (x3 )

¿f (x1 ) < f (x3 )?

-1.0

-2.0

0.5

-0.5

-1.25

sí

Búsqueda en una Dimensión

Profr. E. Uresti - p. 16/19

Ejemplos Aplique el algoritmo anterior para encontrar el máximo de la función

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

f (x) = −x2 − 1 partiendo de x1 = −1 y con un primer intervalo de s = 0.5. ´ de la direccion ´ de avance Determinacion

x1

f (x1 )

s

x3 = x1 + s

f (x3 )

¿f (x1 ) < f (x3 )?

-1.0

-2.0

0.5

-0.5

-1.25

sí

´ Ubicacion

x1

f (x1 )

s

x3

f (x3 )

s = s/τ

x2 = x3 + s

f (x2 )

f2 ≤ f3

-1.0

-2.0

0.5

-0.5

-1.25

0.80906

0.30906

-1.09552

no

-0.5

-1.25

0.80906

0.30906

-1.09552

1.30916

1.61822

-3.61864

sí

Búsqueda en una Dimensión

Profr. E. Uresti - p. 16/19

Ejemplos Aplique el algoritmo anterior para encontrar el máximo de la función

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

f (x) = −x2 − 1 partiendo de x1 = −1 y con un primer intervalo de s = 0.5. ´ de la direccion ´ de avance Determinacion

x1

f (x1 )

s

x3 = x1 + s

f (x3 )

¿f (x1 ) < f (x3 )?

-1.0

-2.0

0.5

-0.5

-1.25

sí

´ Ubicacion

x1

f (x1 )

s

x3

f (x3 )

s = s/τ

x2 = x3 + s

f (x2 )

f2 ≤ f3

-1.0

-2.0

0.5

-0.5

-1.25

0.80906

0.30906

-1.09552

no

-0.5

-1.25

0.80906

0.30906

-1.09552

1.30916

1.61822

-3.61864

sí

Refinamiento

s

x1

f (x1 )

x3

f (x3 )

x2

f (x2 )

x4 = (1 − τ ) x1 + τ x2

f (x4 )

2.1182

-.5

-1.25

.30915

-1.0956

1.61822

-3.6186

.80900

-1.6545

1.3090

.80900

-1.6545

.30915

-1.0956

-.5

-1.25

.00004

-1.

.80896

.30915

-1.0956

.00004

-1.

-.5

-1.25

-.19090

-1.0364

.49994

-.19090

-1.0364

.00004

-1.

.30915

-1.0956

.11813

-1.0140

.30896

.11813

-1.0140

.00004

-1.

-.19090

-1.0364

-.072854

-1.0053

.19094

-.072854

-1.0053

.00004

-1.

.11813

-1.0140

.045174

-1.0020

.11800

.045174

-1.0020

.00004

-1.

-.072854

-1.0053

-.027768

-1.0008

.072924

-.027768

-1.0008

.00004

-1.

.045174

-1.0020

.017311

-1.0003

Búsqueda en una Dimensión

Profr. E. Uresti - p. 16/19

Encuentre el punto óptimo (máximo) por el método de Mayor Ascenso combinado con el método de la sección dorada a las funciones: f (x, y, z) = −3 x2 − 2 x y − 6 x − 3 y 2 − 2 y − z 2

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

Partiendo de P (2, 2, 1) y tomando s = 1 en cada aplicación de la sección dorada.

Búsqueda en una Dimensión

Profr. E. Uresti - p. 17/19

Encuentre el punto óptimo (máximo) por el método de Mayor Ascenso combinado con el método de la sección dorada a las funciones: f (x, y, z) = −3 x2 − 2 x y − 6 x − 3 y 2 − 2 y − z 2

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

Partiendo de P (2, 2, 1) y tomando s = 1 en cada aplicación de la sección dorada. ´ Solucion

La dirección de máximo crecimiento es la del gradiente: ∇ f =< −6 x − 2 y − 6, −2 x − 6 y − 2, −2 z > Así ∇ f (P ) =< −22, −18, −2 >; por tanto, la dirección unitaria de máximo crecimiento es: v =< −0.77208, −0.63169, −0.070188 >. De donde, la función f (x, y, z) restringida a P + t · v queda: g(t) = f (x = P1 +t v1 , y = P2 +t v2 , z = P3 +t v3 ) = −49.0+28.497 t−3.9657 t2

Búsqueda en una Dimensión

Profr. E. Uresti - p. 17/19

Apliquemos ahora el método de la sección dorada a g(t) = −49.0 + 28.497 t − 3.9657 t2 partiendo de t = 0 y con s = 1.

Búsqueda en una Dimensión

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

Profr. E. Uresti - p. 18/19

Tarea 1. Use el método de la sección dorada para determinar con una tolerancia de 0.05 la solución óptima de : Max

x2 + 2 x

Sujeto a

−3 ≤ x ≤ 5

´ Introduccion GS Bracketing B y GS Ejemplos Tarea

2. Use el método de la sección dorada para determinar con una tolerancia de 0.05 la solución óptima de : Max

x − ex

Sujeto a

−1 ≤ x ≤ 3

3. Encuentre el punto máximo por el método de Mayor Ascenso combinado con el método de la sección dorada a las funciones: a) f (x, y) = −(x − 3)2 − (y − 1)2 partiendo de P (2, 2) y tomando s = 1 en cada aplicación de la sección dorada. b) f (x, y) = −3 x2 − 2 x y − 6 x − 3 y 2 − 2 y − 3 partiendo de P (2, 2) y tomando s = 1 en cada aplicación de la sección dorada.

Búsqueda en una Dimensión

Profr. E. Uresti - p. 19/19