UN COÑO

Pr´actica 2
M´etodos de b´usqueda para funciones de una variable

Introducci´
on
Definici´
on 1. Una funci´on real f se dice que es fuertemente cuasiconvexa en el intervalo (a, b) si para cada par de puntos x1 , x2 ∈ (a, b) con x1 = x2 se verifica que:
f (λx1 + (1 − λ)x2 ) < m´ax{f (x1 ), f (x2 )},

∀λ ∈ (0, 1).

Se puede demostrar que si f es una funci´on continua y fuertementeconvexa en el
intervalo (a, b), entonces f tiene un m´ınimo en este intervalo y es u
´nico.
Proposici´
on 2. Sea f una funci´on fuertemente cuasiconvexa en (a, b) y sea y, z tales
que a < y < z < b. Entonces, se verifica que:
1. Si f (y) ≥ f (z) ⇒ f (x) ≥ f (z), ∀x ∈ [a, y]
2. Si f (y) ≤ f (z) ⇒ f (x) ≥ f (y), ∀x ∈ [z, b]
Demostraci´
on.

1. Por reducci´on al absurdo. Supongamos que existe x∈ [a, y] tal

que f (x) < f (z). Entonces, para el intervalo [x, z] se verifica que
f (λx + (1 − λ)z) < m´ax{f (x), f (z)} = f (z),
1

∀λ ∈ (0, 1).

2
En particular, como y ∈ [x, z], f (y) < m´ax{f (x), f (z)} = f (z). Contradicci´on
2. Demostraci´on an´aloga al caso anterior.

La consecuencia del resultado anterior es que basta con controlar lo que vale f
en dos puntos y, z. Si f (y)≥ f (z), entonces f (x) ≥ f (z) para todo x ∈ [a, y], luego
podemos restringir la b´
usqueda del m´ınimo al intervalo [y, b]. Sucesivamente iremos
reduciendo la longitud de nuestro intervalo de incertidumbre hasta que sea menor que
un cierto nivel .
Realmente para los m´etodos que vamos a presentar, basta con que la funci´on sea
unimodal. Una funci´on es unimodal en una cierta regi´on si s´olotiene un o´ptimo
en dicha regi´on. Una funci´on unimodal podr´ıa ser continua o discontinua; incluso se
podr´ıan desarrollar m´etodos de b´
usqueda para funciones unimodales definidas s´olo
sobre un conjunto de valores discretos.
Definici´
on 3. Una funci´on real f es unimodal en el intervalo [a, b] si existe un punto
x∗ ∈ [a, b] tal que f es decreciente en [a, x∗ ] y f es creciente en [x∗, b].

Los m´etodos que se van a presentar para funciones unimodales podr´ıan funcionar
tambi´en sobre funciones multimodales, pero en este caso s´olo localizar´ıan uno de los
o´ptimos. En lo que sigue consideraremos una funci´on unimodal con un u
´nico m´ınimo
en el interior del intervalo o en su frontera.

B´
usqueda Dicot´
omica
Consiste en reducir al m´aximo la longitud delintervalo de incertidumbre en cada
iteraci´on.

3
Paso Inicial
Fijar > 0, h > 0. Hacer [a1 , b1 ] = [a, b] y k = 1.
Paso General
Repetir:
1. Si bk − ak < h, PARAR. [ak , bk ] es el intervalo buscado.
2. Si bk − ak ≥ h, hacer yk =

ak +bk
2

− , zk =

ak +bk
2

+ y comparar los valores f (yk )

y f (zk ).
Si f (yk ) ≥ f (zk ), hacer ak+1 = yk y bk+1 = bk . Hacer k = k + 1. Ir a 1Si f (yk ) < f (zk ), hacer ak+1 = ak y bk+1 = zk . Hacer k = k + 1. Ir a 1

M´
etodo de la secci´
on ´
aurea
La idea del m´etodo es la siguiente. Dado un intervalo (a, b) generamos inicialmente
dos nuevos puntos y1 = a + (1 − α)(b − a) y z1 = a + α(b − a), para alg´
un α ∈

1
,1
2

convenientemente elegido. Seg´
un los valores que tomen f (y) y f (z), el intervalo de
incertidumbreen el siguiente paso ser´a (a, z) o (y, b). Pues bien, la idea del m´etodo es
elegir α de forma que seg´
un el caso que corresponda el valor yk coincida con el zk−1 , o
bien zk coincida con yk−1 .
Por ejemplo, si f (y1 ) ≥ f (z1 ), entonces el nuevo intervalo de incertidumbre es
(a2 = y1 , b2 = b) y α debe ser tal que y2 = a2 + (1 − α)(b − a2 ) = z1 . Puesto que

4
a2 = y1 , la relaci´onanterior quedar´ıa
a + (1 − α)(b − a) + (1 − α)(b − (a + (1 − α)(b − a)) = a + α(b − a)
2(1 − α)(b − a) − (1 − α)2 (b − a) = α(b − a)
2(1 − α) − (1 − α)2 = α
(1 − α) − (2 − (1 − α)) = α
(1 − α)(1 + α) = α
1 − α2 = α
α2 + α − 1 = 0
cuya soluci´on (positiva) es
α=

(5)

1+
2

∼ 0,618033989

Obs´ervese que con este m´etodo se tiene siempre que la longitud de un intervalo Lk...