Método de Davidon-Fletcher-Powell

Métodos Indirectos en Optimización

1. TecNM/Instituto Tecnológico de Cd. Madero

MÉTODOS INDIRECTOS

MÉTODO DE
DAVIDON-FLETCHER-POWELL
(APROXIMACIÓN DE LA INVERSA DE H)
Roger Fletcher
(1939-2016)
Michael James
David Powell
(1936-2015)
William C.
Davidon
(1927-2013)
Dr. David Macias Ferrer

Centro de Investigación
en Petroquímica

2. MÉTODO DE DAVIDON-FLETCHER-POWELL
Direcciones de Búsqueda, basada en la relación: 
1
ˆ
s H x
k k k
f

  

Donde es una aproximación de la inversa de H, para abreviar: 
1
xx ηx
k k k k k
f

  
Para k = 0: 1
ˆ
H
k


 1
ˆ
ηH
kk


 



1
xx η g g η
ηη
x g g ηg
T T T
k k k k k k
kk
TT
k k k k k

   
  
   
La relación recurrente es
de la forma: 0
ηI
Para
k  0:
Donde:
El escalar 
k
puede estar
determinado por la
optimización de:  xs
kk
f
Un Criterio de convergencia adecuado
que puede ser aplicado desde el
comienzo es: x
k
f   

1
1
g x x
x x x
k k k
k k k
ff
ff


    
  

3. Vector Inicial x
0

Optimizar f(x
k
+  s
k
), para encontrar 
k
Generar el vector x
k+1
Encontrar el vector de dirección s
k

Vector Óptimo x
opt
Evaluar la Función Objetivo en x
opt
, es decir f(x
opt
)
Solución Óptima f(x
opt
) 
1
ˆ
s H x
k k k
f

  

|f(x
k
)|<

1
xx ηx
k k k k k
f

  
k = k + 1
Sí
No
MÉTODO DE DAVIDON-FLETCHER-POWELL
Actualizar 
k+1

4. EJEMPLO
Encuentre el vector x que minimice la función   
22
1 2 1 2
, 4 5 6f x x x x   
Si: 
0
89x
T

MÉTODO DE DAVIDON-FLETCHER-POWELL

5. EJEMPLO
Encuentre el vector x que minimice la función   
22
1 2 1 2
, 4 5 6f x x x x   
Si: 
0
89x
T

MÉTODO DE DAVIDON-FLETCHER-POWELL

6. EJEMPLO
Aplicando la relación de recurrencia: 
1 0 00 0
xx ηxf donde: 0
ηI
El gradiente es: 
 
 
1
2
85
26
x
x
f
x

 
 
0
24
6
xf

 
 Por lo tanto, para x
0
:
Encuentre el vector x que minimice la función   
22
1 2 1 2
, 4 5 6f x x x x   
Si: 
0
89x
T

De aquí que: 1
1
1
2
824
96
x
x



 Luego entonces: 1
81024
9016
x 



Optimizando f():     
22
2
48245966234061245f    
MÉTODO DE DAVIDON-FLETCHER-POWELL

7. CONTINUACIÓN
Derivando respecto de : 4680 612
df
d


 4680 612 0
Si f’() = 0 entonces:
Sustituyendo en la relación recurrente: 1 0 0 0
x x s
De aquí que: 0
0.13076923
Luego entonces: 1
8 1 0 24
0.13076923
9 0 1 6
x
    
    
     1
4.861538462
8.21538462
x


 
 
 
1
8 4.861538462 5 1.10769231
4.430769232 8.21538462 6
xf
 
   

 
El gradiente para x
1
es:
Donde: 
0 0 0
sηxf  
A diferencia del método de
Broyden, aquí tomaremos 8
decimales:
MÉTODO DE DAVIDON-FLETCHER-POWELL

8. Aplicando la relación de recurrencia para k = 0: 



0 0 0 0 0 0
10
0 0 0 0 0
xx η g g η
ηη
x g g ηg
T T T
TT
   
  
   
De aquí que: 0
1.10769231 24 25.1076923
4.43076923 6 1.56923077
g
     
        
      0
4.861538462 8 3.13846154
8.21538462 9 0.78461538
x
     
        
     
Por otro lado, para x
0
:
CONTINUACIÓN  
0
25.10776923 1.56923077g
T
     
0
3.13846154 0.78461538x
T
   
También:
También:
MÉTODO DE DAVIDON-FLETCHER-POWELL

9. Sustituyendo lo anterior: 



0
0 0 0 0 0 0
0 0 0 0 0
1
1 0 0.117664706 0.02941176 0.99610895 0.06225 681
0 1 0.02941176 0.00735294 0.06225681 0.003891 05
η
xx η g g η
x g g ηg
η
T T T
TT
   
   
     
       
     
De aquí que: 

00
00
3.13846154 3.13846154
0.117664706 0.029411760.78461538 0.78461538
0.02941176 0.007352943.13846154 25.1076923
0.78461538 1.56923077
xx
xg
T
T
TT
  
  
    
 
    
   
    

0 0 0 0
0 0 0
1 0 25.1076923 25.1076923 1 0
0.99610895 0.062256810 1 1.56923077 1.56923077 0 1
0.06225681 0.25.1076923 1 0 25.1076923
1.56923077 0 1 1.56923077
η g g η
gηg
TT
TT
TT
     
     
      

    
    
    
00389105



El cálculo de 
1
lo haremos por partes:
CONTINUACIÓN
MÉTODO DE DAVIDON-FLETCHER-POWELL

10. 1
0.12153811 0.03284504
0.03284504 1.00346189
η


 Finalmente:
Aplicando la relación de recurrencia: 
2 1 1 1 1
xx ηxf   2
4.861538462 0.12153811 0.03284504 1.1076692 31
8.21538462 0.03284504 1.00346189 4.43076923
x 
    
    
    
CONTINUACIÓN 2
1
2
2
4.861538462 0.28015564
8.21538462 4.48249027
x
x




Luego entonces:
Optimizando f():   
22
2
4 4.861538462 0.28015564 5 8.21538462 4.48249027 6
20.406667 20.171206 4.9846153
f  

     
  
MÉTODO DE DAVIDON-FLETCHER-POWELL

11. CONTINUACIÓN
Derivando respecto de : 40.813335 20.171206
df
d


 40.813335 20.171206 0
Si f’() = 0 entonces:  1
0.4942307693
Sustituyendo el valor de 
1
:
Luego entonces: 2
5.0008
6.0001
x


  
 
2
1
2
2
4.8632 0.2771 0.4967
8.2157 4.4605 0.4967
x
x

 
 
 
2
8 5.0008 5 0.0064
2 6.0001 6 0.0002
xf
   
   
 
El gradiente para x
2
es:
Aquí el resultado numérico difiere un
poco del obtenido en la hoja de Excel
ya que en estos cálculos se truncó a 4
decimales
MÉTODO DE DAVIDON-FLETCHER-POWELL

12. CONTINUACIÓN
Por lo tanto el vector óptimo es: 5
6
x
opt


Sustituyendo el valor de 
1
:
Luego entonces: 2
5
6
x


  
 
2
1
2
2
4.861538462 0.28015564 0.494207693
8.21538462 4.48249027 0.494207693
x
x

 


2
8 5 5 0
2 6 6 0
xf
   
   
 
El gradiente para x
2
es:
Aquí el resultado numérico es exacto
debido a que se manejaron 8 decimales
como en el obtenido en la hoja de Excel
y 
2
xf 
MÉTODO DE DAVIDON-FLETCHER-POWELL

13. En 2 etapas tenemos los siguientes resultados :
RESÚMEN
MÉTODO DE DAVIDON-FLETCHER-POWELL
k  x
1 x
2 f(x
k
) |f(x
k
)|
0 0.130769 8.000000 9.000000 45.0000 24.738633
1 0.494230 4.861538 8.215384 4.984615 4.567132
2 ---- 5.000000 6.000000 0.000000 0.000000

14. Por lo tanto el vector óptimo que corresponde al extremo mínimo es: 5
6
x
opt


Extremo Mínimo Local
Punto Óptimo
de la Función   
22
1 2 1 2
, 4 5 6f x x x x   
MÉTODO DE DAVIDON-FLETCHER-POWELL
RESÚMEN

15. BIBLIOGRAFÍA
T.F. Edgar, D.M. Himmelblau, L.S. Lasdon, “Optimization of Chemical Processes”, 2nd
Edition, New York, USA, McGraw Hill Inc., 2001