Optimizacion
Posgrado en Ing. Electronica
Capitulo 7
Metodos Quasi-Newton
D.U. Campos-Delgado
Facultad de Ciencias
UASLP
Enero-Junio/2017
1
CONTENIDO
Metodo BFGS
Metodo SR1
Clase de Broyden
Convergencia
Ejercicios
2
Metodo BFGS
En los metodos de Newton se necesita la in-
formacion de 2do orden de la funcion de costo
∇2f(xk) para calcular el paso de actualizacion
ası como su inversa.
En los metodos Quasi-Newton se aproxima la
matriz Hessiana a partir de la informacion ac-
tual y previa del gradiente ∇f(xk).
El metodo mas popular se debe a Broyden,
Fletcher, Goldfarb y Shanno → BFGS.
Para motivar esta metodologıa considerar la
aproximacion cuadratica en la iteracion k +1
mk+1(p) = fk+1 +∇f⊤k+1p+1
2p⊤Bk+1p
donde se asume una actualizacion
xk+1 = xk + αkpk,
αk satisface las condiciones de Wolfe y Bk se
calcula en cada iteracion.
3
Idea General: el gradiente de mk+1(·) debe
coincidir con el gradiente de la funcion de costo
f(·) en las ultimas aproximaciones xk y xk+1.
Entonces observar que
∇mk+1(p) = ∇fk+1 +Bk+1p
y ademas
xk = xk+1 − αkpk,
por lo que las condiciones a cumplir son
∇mk+1(0) = ∇fk+1 +Bk+10 = ∇fk+1
∇mk+1(−αkpk) = ∇fk+1 − αkBk+1pk = ∇fk.
La primera condicion se satisface de forma au-
tomatica y solo tenemos que garantizar (ecua-
cion secante):
Bk+1sk = yk
donde
sk = xk+1 − xk = αkpk
yk = ∇fk+1 −∇fk.
Ya que se requiere Bk+1 > 0 entonces se tiene
la condicion de curvatura
s⊤k Bk+1sk = s⊤k yk > 0
Esta condicion se cumple si f(·) es convexa o
se aplican las condiciones de Wolfe para obte-
ner αk, ya que se satisface
∇f⊤k+1pk ≥ c2∇f⊤k pk
⇒ ∇f⊤k+1sk ≥ c2∇f⊤k sk
∴ (∇fk+1 −∇fk)⊤
︸ ︷︷ ︸
y⊤k
sk ≥ (c2 − 1)︸ ︷︷ ︸
<0
αk∇f⊤k pk︸ ︷︷ ︸
<0
> 0
ya que c2 ∈ (0,1) y αk > 0.
Por lo tanto el metodo BFGS plantea el pro-
blema de sıntesis
Bk+1 = arg mınB=B⊤
‖B−Bk‖F
tal que
Bsk = yk & B > 0.
en este problema de optimizacion al utilizar una
matriz de peso (Hessiana promedio) que cum-
pla la ecuacion secante obtenemos una solu-
cion unica
Bk+1= (I− γkyks⊤k )Bk(I− γksky
⊤k ) + γkyky
⊤k (DFP)
= Bk −1
s⊤k BkskBksks
⊤k Bk + γkyky
⊤k (BFGS)
con
γk , 1/y⊤k sk,
y definiendo Hk = B−1k al aplicar el lema de la
inversa de una matriz
(A+UCV)−1 = A−1−A−1U(C−1+VA−1U)−1VA−1
se obtiene
Hk+1 = Hk −1
y⊤k HkykHkyky
⊤k Hk +
1
y⊤k sksks
⊤k (DFP).
Observar que la formula para Bk+1 y Hk+1 se
tienen actualizaciones de rango-2. Una repre-
sentacion alterna y mas eficiente se logar al
replantear el problema de optimizacion
Hk+1 = arg mınH=H⊤
‖H−Hk‖F
tal que
Hyk = sk & H > 0.
Nuevamente al utilizar una matriz de peso ob-
tenemos una solucion unica
Hk+1 = (I− γksky⊤k )Hk(I− γkyks
⊤k ) + γksks
⊤k (BFGS).
Recomendaciones de implementacion
Al evaluar la condiciones de Wolfe para se-
leccionar el paso de busqueda αk, comenzar
con un paso unitario, i.e. αk = 1. En esta
etapa considerar las constantes c1 = 10−4
y c2 = 0.9.
La matriz inicial H0 se selecciona usual-
mente como un escalamiento de la identi-
dad βI, donde β > 0. Otra opcion es se-
leccionar H0 = I y calcular la primera ite-
racion k = 0 para que antes de actualizar
H1, reseleccionar
H0 =y⊤0 s0
y⊤0 y0I,
Algorithm 1 Metodo BFGSRequire: Dado x0 ∈ R
n, umbral de convergen-
cia ǫ > 0 y una aproximacion a la inversa
H0 ∈ Rn×n.
1: Definir k = 0,
2: while ‖∇fk‖ > ǫ do
3: Calcular la direccion de actualizacion
pk = −Hk∇fk,
4: Encontrar el tamano del paso de ajuste
αk de acuerdo a las condiciones de Wolfe
y definir
xk+1 = xk + αkpk
5: Calcular sk = xk+1−xk y yk = ∇fk+1−
∇fk.
6: Obtener Hk+1 segun la formula de
BFGS.
7: Definir k = k +1.
8: end while
y comenzar de nuevo.
En el metodo BFGS se puede actualizar la
Hessiana Bk en cada paso en lugar de su
inversa Hk, pero se almacena en memoria
su factorizacion de Choleski Bk = LkDkL⊤k
(es decir Lk y Dk), de manera que se pue-
da modificar Dk en caso de no cumplir la
condicion de positividad.
Si durante el proceso iterativo no se cumple
la condicion de curvatura, es decir y⊤k sk ≤
0, entonces se omite la actualizacion Hk+1 =
Hk; aunque en general este proceso no es
recomendable.
Metodo SR1
El metodo se basa en una actualizacion simetri-
ca de rango-1, symmetric rank-1, (SR1) de la
matriz Hessiana Bk:
Bk+1 = Bk + σvv⊤,
donde σ ∈ −1,1, y (σ,v) se seleccionan tal
que se cumpla la ecuacion secante yk = Bk+1sk
yk = Bksk + σv(v⊤sk).
Por lo que v debe ser multiplo de yk−Bksk, es
decir ∃δ ∈ R tal que
v = δ · (yk −Bksk)
y se obtiene al sustituir
σ = signo[(yk −Bksk)⊤sk],
δ = ±∣∣∣(yk −Bksk)
⊤sk
∣∣∣−1/2
,
lo que es equivalente a
σ · δ2 =1
(yk −Bksk)⊤sk
.
4
La formula final de actualizacion SR1 para la
matriz Hessiana es
Bk+1 = Bk +(yk −Bksk)(yk −Bksk)
⊤
(yk −Bksk)⊤sk
,
y al aplicar la formula Sherman-Morrison-Woodbury
(A+UV⊤)−1 = A−1−A−1U(I+V⊤A−1U)−1V⊤A−1
se obtiene la actualizacion para la inversa
Hk+1 = Hk +(sk −Hkyk)(sk −Hkyk)
⊤
(sk −Hkyk)⊤yk
.
Propiedad: si Bk es positiva definida no existe
garantıa de que Bk+1 tambien lo sera, ası como
para Hk.
Casos Especiales:
Si (yk − Bksk)⊤sk 6= 0 ⇒ existe una ac-
tualizacion unica de rango-1 que cumple la
ecuacion secante.
Si yk = Bksk ⇒ la unica actualizacion que
cumple la ecuacion secante es Bk+1 = Bk.
Si yk 6= Bksk y (yk − Bksk)⊤sk = 0 ⇒ no
existe una solucion simetrica de rango-1 a
la ecuacion secante.
Para evitar estos casos de inestabilidad numeri-
ca, la actualizacion SR1 se aplica si
|(yk −Bksk)⊤sk| ≥ r‖sk‖‖yk −Bksk‖
donde r ∈ (0,1) y generalmente es un numero
pequeno (r = 10−8).
Este metodologıa se aplica generalmente en las
estrategias de region de confianza.
Algorithm 2 Region de Confianza SR1Require: Dado x0 ∈ R
n, umbral de convergencia ǫ > 0,una aproximacion a la Hessiana B0 ∈ R
n×n y parame-tros η ∈ (0,10−3) y r ∈ (0,1).
1: Definir k = 0,2: while ‖∇fk‖ > ǫ do3: Calcular sk a traves de resolver
sk = mıns
∇f⊤k s+
1
2s⊤Bks ‖s‖ ≤ ∆k
4: Calcular yk = ∇f(xk + sk)−∇f(xk) y
ρk =f(xk)− f(xk + sk)
−(∇f⊤k sk +
12s⊤k Bksk)
5: if ρk > η then6: xk+1 = xk + sk,7: else8: xk+1 = xk
9: end if10: if ρk > 0.75 then11: if ‖sk‖ ≤ 0.8∆k then12: ∆k+1 = ∆k
13: else14: ∆k+1 = 2∆k;15: end if16: else if 0.1 ≤ ρk ≤ 0.75 then17: ∆k+1 = ∆k
18: else19: ∆k+1 = 0.5∆k;20: end if21: if |(yk −Bksk)
⊤sk| ≥ r‖sk‖‖yk −Bksk‖ then22: Actualizar Bk+1 segun SR123: else24: Bk+1 = Bk
25: end if26: Definir k = k +1.27: end while
Teorema 5.2: asumir que f(·) es doblemente
continuamente diferenciable, y que la matriz
Hessiana es acotada y Lipschitz continua en
una vecindad del mınimo x∗. Definir xk como
una secuencia convergente a x∗, es decir xk →
x∗. Asumir que se cumple
|(yk −Bksk)⊤sk| ≥ r‖sk‖‖yk −Bksk‖
for algun r ∈ (0,1), y que los pasos sk son
uniformemente linealmente independientes ⇒
la secuencia de matrices Bk generadas por
SR1 satisface
lımk→∞
‖Bk −∇2f(x∗)‖ = 0.
Clase de Broyden
Aparte de los algoritmos de actualizacion BFGS,
DFP y SR1 existe otro tipo importante → Cla-
se de Broyden
Bk+1 = Bk−Bksks
⊤k Bk
s⊤k Bksk+γkyky
⊤k +φk(s
⊤k Bksk)vkv
⊤k ,
donde φk(s⊤k Bksk) ∈ R y
vk ,yk
y⊤k sk−
Bksk
s⊤k Bksk. ∈ R
n
De manera que se cumple
Si φk = 0 ⇒ Bk+1 corresponde a BFGS
(BBFGSk+1 ),
Si φk = 1 ⇒ Bk+1 equivale a DFP (BDFPk+1 ).
Por lo tanto la Clase de Broyden se puede in-
terpretar como una combinacion lineal de BFGS
5
y DFP
Bk+1 = (1− φk)BBFGSk+1 + φkB
DFPk+1
Ya que BBFGSk+1 y BDFP
k+1 cumplen la ecuacion se-
cante, y ambas soluciones seran positivas defi-
nidas si se cumple s⊤k yk > 0, entonces las mis-
mas propiedades las hereda la clase de Broyden
si φk ∈ [0,1] (clase de Broyden restringida).
Finalmente observar que la actualizacion SR1
tambien pertenece a la clase de Broyden con
φk =s⊤k yk
s⊤k yk − sk⊤Bksk
aunque en este caso φk puede encontrarse fue-
ra del intervalo [0,1].
Propiedad: si Bk > 0 (y⊤k sk > 0) y φk ∈ [0,1]
⇒ la actualizacion de Broyden restringida sa-
tisface Bk+1 > 0.
Convergencia
Enseguida se describen 3 resultados importan-
tes acerca de la convergencia de las metodo-
logıas BFGS y SR1.
Teorema 8.5: definir una matriz inicial B0 > 0
y cualquier punto de inicio x0 ∈ Rn. Asumir que
f(·) es doblemente continuamente diferencia-
ble, que el conjunto Ω = x ∈ Rn | f(x) ≤
f(x0) es convexo y que la matriz Hessiana es
acotada de forma cuadratica en Ω ⇒ la secuen-
cia xk obtenida al aplicar BFGS converge al
mınimo x∗ de f(·).
Teorema 8.6: suponer que f(·) es doblemente
continuamente diferenciable, que la iteracion
xk obtenida por BFGS converge al mınimo
x∗ de f(·) y que la matriz Hessiana es Lips-
chitz continua en x∗ ⇒ xk converge a una tasa
superlineal a x∗.
6
Teorema 8.7: suponer a xk como la itera-
cion generada por la metodologıa de region de
confianza SR1. Ademas suponer
i. La secuencia xk permanece en un con-
junto convexo, cerrado y acotado donde la
funcion f(·) es doblemente continuamente
diferenciable y donde tiene un unico punto
estacionario x∗.
ii. La matriz Hessiana ∇2f(x∗) > 0 y ∇2f(x) >
0 es Lipschitz continua en una vecindad de
x∗.
iii. La secuencia de matrices Bk es acotada
en norma.
iv. La condicion
|(yk −Bksk)⊤sk| ≥ r‖sk‖‖yk −Bksk‖
se cumple en cada iteracion k, donde r ∈
(0,1).
⇒ lımk→∞ xk = x∗ y ademas
lımk→∞
‖xk+n+1 − x∗‖
‖xk − x∗‖= 0.
Ejercicios
(A) Para las formulas de actualizacion BFGS
para Bk+1 y Hk+1 demostrar que son inversas
entre si, es decir Bk+1Hk+1 = I y Hk+1Bk+1 =
I.
(B) Demostrar por medio de la formula de
Sherman-Morrison-Woodbury la expresion re-
sultante para Hk+1 en SR1.
(C) Implementar los algoritmos quasi-Newton
por BFGS y SR1 para las siguientes funciones:
1. Funcion de Rosenbrock
f(x1, x2) = 100(x2 − x21)2 + (1− x1)
2
Considerar como puntos de inicio x0 = [1.2,1.2]⊤
y x0 = [−1.2,1.0]⊤.
2. Funcion exponencial
f(x1, x2) = ex1+3x2−0.1+ex1−3x2−0.1+e−x1−0.1
7
3. Funcion de Branin
f(x1, x2) = (x2 − 0.129x21 +1.6x1 − 6)2
+6.07 cosx1 +10
considerando como punto de inicio x =
[6 14]⊤.
¿Cuales son los puntos de convergencia x∗ para
cada funcion? ¿En cuantas iteraciones se logra
la convergencia?