metodos de optimmizacion

Raices de una ecuación y optimización de funciones
1 Introducción, caracterización de puntos singulares
2 Raíces de una ecuación (ceros de f’(x))
2.1 Teorema de Bolzano
2.2 Método de Newton-Raphson
3 Mínimos de funciones de una variable
3.1 Métodos de interpolación
3.2 Método del gradiente
4 Optimización de funciones de varias variables
4.1 Métodos basados en el gradiente y en elHessiano
4.2 Métodos basados en la función: método simplex
4.3 Localización de estados de transición
4.4 Simulated annealing

1 Introducción
Dos problemas relacionados
•! Obtención de las raices f(x) = 0
•! Obtención del mínimo de una función f’(x)=0
Minimización: problema fundamental en Química Computacional
•! HF: mínimo energía respecto a variación de orbitales (estabilidad del HF)
•!CASSCF: mínimo de energía frente a coeficientes (CI) y orbitales
•! Exploración de superficies de potencial: mínimos (isómeros), puntos silla (TS)..
•! Análisis topológico de la densidad (Teoría AIM de Bader)
Problema muy complejo
•! Muchas variables y/o restricciones (CASSCF)
•! Mínimos múltiples (local o global) (localización de isómeros)
•! Mínimos bien diferenciados, separados por barrerasaltas (C60 – 1812) o con
alta degeneración en la energía y barreras pequeñas (proteina)
•! Puntos silla de diversos órdenes
•! Cada paso de evaluación de f muy costoso, en ocasiones es posible obtener
primeras y segundas derivadas (de forma analítica o numérica)

Caracterización de puntos singulares
Gradiente: vector formado por las primeras derivadas de la función con respecto de lasvariables:
!f/!x1, !f/!x2, !f/!x3, ... , !f/!xn, {xi}i=1,n
Condición de estado estacionario: el vector gradiente ha de tener módulo cero
Hessiano: matriz formada por el conjunto de derivadas segundas con respecto a las
distintas variables

•! La naturaleza del punto estacionario viene fijada por el Hessiano
•! Valores propios positivos: mínimo local
•! Un valor propio negativo y el restopositivos: punto en silla de primer orden
•! “n” valores propios negativos y el resto positivos: punto en silla de orden n

2 Raices de una ecuación
Métodos basados en el Teorema de Bolzano
El teorema de Bolzano asegura que si una función f(x) es continua en un intervalo
cerrado [a,b] y tiene valores de signo contrario en ambos extremos (f(a)f(b) y(c)=0 es

c=a!

f (a)(b ! a)
f (b) ! f (a)2 Raices de una ecuación
Método de Newton-Raphson
•! Seguir la curva tangente, calcular la primera derivada de la función
•! Desarrollo en serie Taylor hasta segundo orden
g(x+d) = g(x) + g ’(x) d + ! g ”(x) d2
•! Si la función se comporta bien, la segunda derivada es despreciable. Si g(x+d)=0, el
valor d que nos tenemos que desplazar es:
d = - g(x) / g’(x)
•! Proceso iterativo, se escogeun xk razonablemente cerca del cero y calcula xk+1
xk+1 = xk - g(xk)/g’(xk)
•! Proceso finaliza cuando
| dk | = | xk+1-xk | < E
•! Convergencia cuadrática, método muy eficiente
•! Convergencia no está asegurada
•! Evaluación de la derivada puede ser muy costosa
o sujeta a mucho error si se hace analíticamente.
g'(x) !

g(x + "x)# g(x)
"x

Método de Newton-Raphson
Fácilmentegeneralizable a solución simultanea de n ecuaciones no lineales con n variables.
gi(x) = gi(x1, x2, ... , xn) = 0
Mismo razonamiento pero con desarrollo en Taylor de n variables para cada gi
n
$ #g '
!
!
0= gi ( x )= gi ( x k )+ !(xj " xjk )& i )
+ ...
% #xj ( x =x k
! !
j =1
n

!(x
j =1

j

$ #g '
!
" xjk )& i )
= "gi ( x k )
% #xj ( x =x k
! !

i = 1,2...n

En formamatricial J dxk = - gk donde J es la matriz Jacobiana evaluada en x=xk
" !g1 / !x1 !g1 / !x2 ... !g1 / !xn %
$ !g2 / !x1 !g2 / !x2 ... !g2 / !xn '
$
'
$....................................................'
$
'
# !gn / !x1 !gn / !x2 ... !gn / !xn & x =x
! !

dxjk = xjk +1 ! xjk
k

!
!
! !
x k +1 = x k ! J x!1x k " g( x k )
! !
=

3 Mínimos de funciones de una variable
Interpolación...