OPTIMIZACIÓN VECTORIAL
Métodos de Búsqueda Directa Utilizan sólo valores de la función
Métodos del Gradiente Requieren valores aproximados de la primera
derivada de f(x)
Métodos de Segundo OrdenAdemás de utilizar la
primera derivada también utilizan la segunda
derivada de f(x)
OPTIMIZACIÓN VECTORIAL
Métodos de Búsqueda Directa Utilizan sólo valores de la función
Métodos del Gradiente Requieren valores aproximados de la primera
derivada de f(x)
Métodos de Segundo OrdenAdemás de utilizar la
primera derivada también utilizan la segunda
derivada de f(x)
Métodos de búsqueda directa
Son útiles cuando no se conoce el gradiente de la función
Existen técnicas:
Heurísticas: El método del simplex
Teóricas: Método de las direcciones conjugadas de Powell
Método Simplex
Geométricamente el elemento que requiere menos puntos para su construcción => Simplex regular, que en dimensión N es un poliedro compuesto de N+1 puntos equidistantes que forman sus vértices (triángulo, tetraedro,...).
Método Simplex 1
X(1)
X(2)
X(3)
X(1)
X(2)
X(3)
X(4)
Se sitúa un simple regular en el espacio de las variables independientes
El vértice con mayor valor de la función se refleja a través del centroide
Este punto se utiliza para formar un nuevo simplex
Este procedimiento se repite hasta que se encuentre el mínimo o se encuentre uno de los siguientes casos:
Método Simplex 2
1. El valor de la función en el peor punto y el punto reflejado sea el mismo.
2. Cuando se llega a un cicloEn este caso se debe reducir el simplex en un determinado factor y empezar el procedimiento a partir del simplex nuevo
3. Criterio de terminación
x1
x2
x3
x4
En este caso se debe elegir el siguiente vértice que tenga el valor de la función más elevado
Implementación del Método Simplex 1
Requiere de dos cálculos:
1. Generación de un simplex regular de dimensión N, dado un punto base x0 y un factor de escala
⎪⎩
⎪⎨
⎧
=
≠+
=+
=
N,,2,1j,i
jiδx
jiδx
x 2)0(
j
1)0(
j
)i(j
K
α
( )
( )α⎟⎟
⎠
⎞
⎜⎜
⎝
⎛ −+=δ
α⎟⎟
⎠
⎞
⎜⎜
⎝
⎛ −++=δ
2N11N
2N1N1N
21
2
21
1
Implementación del Método Simplex 2
2. Cálculo del punto reflejado: Supongamos que x(j) es el punto que será reflejado. Entonces el centroide de los restantes N puntos será
( )∑≠=
=N
ji0i
ic x
N1x
Todos los puntos sobre la línea desde x(j) hasta xc vienen dados por:
( ) ( ))j(c
j xxλxx −+=
0=λ )j(xx =1=λ cxx =
2=λ )j(anteriorc
)j(nueva xx2x −=
Ventajas y desventajas del Método
1. Cálculos simples y lógica no complicada
2. Los requerimientos de almacenamiento son bajos (array de (N+1,N+2))
3. Pocos parámetros de ajuste (factor de escala y parámetros de terminación)
Ventajas
Desventajas
1. Problemas de escala, todos los vértices utilizan la misma
2. El algoritmo es lento, no utiliza información pasada
3. No existe una forma simple de expandir el simplex sin calcular el patrón completo. Si se reduce la búsqueda tiene que continuar con este tamaño de paso.
α
α
Método del simplex modificado
• Método de Nedler y Mead: no hay que mantener la regularidad del simplex en el procedimiento de búsqueda: expansiones y contracciones.
• x(h) es el punto con mayor valor de la función, x(g) el siguiente punto más grande y x(l) el punto con menor valor de la función.
• El punto reflejado es: x = x(h) + (1+ θ) (xc - x(h))
– θ =1 => algoritmo original; θ = α– -1 ≤ θ ≤ 1 => contracción; θ = β = 0.5– θ > 1 => expansión; θ = γ = 2
• Se hace una reflexión normal y se chequea por una contracción o expansión según las condiciones:
Método del simplex modificado
X(h)
a) Reflexión normal:
f(x(l)) < f(xnew) < f(x(g))
XnewX(h)
b) Expansión:
f(xnew) < f(x(l))
Xnew
z
X(h)
c) Contracción:
f(x(g)) < f(xnew) < f(x(h))
Xnew
z X(h)
d) Contracción negativa:
f(xnew) > f(x(g)) y
f(xnew) ≥ f(x(h))
Xnew
z
Direcciones conjugadas de Powell (I)
• Se aproxima la función objetivo por una función cuadrática.
• Si una función cuadrática de N variables puede transformarse en la suma de N cuadrados perfectos, el óptimo se encuentra con N búsquedas de una variable.
q(x) = a + bT x + 1/2 xT C x
• Hay que encontrar una matriz de transformación T tal que el término cuadrático sea diagonal:
x = Tz Q(x) = xT C x = zT T T C T z = zT D z
• Se está escribiendo el vector x en un nuevo sistema de coordenadas tj, llamadas direcciones conjugadas. Sólo queda encontrar estas direcciones.
x = Tz = t1 z1 + t2 z2+ ... + tnzn
Direcciones conjugadas de Powell (II)
• Propiedad del subespacio paralelo: dada una función cuadrática q(x), dos puntos arbitrarios x(1) y x(2) y una dirección d; si y(1) es la solución al problema min q(x(1) + λd) e y(2) es la solución de min q(x(2) + λd) entonces la dirección (y(2) - y(1)) es C conjugada de d.
x(1)
y(1)
x(2)y(2)
d
• Direcciones C-conjugadas: es un conjunto de vectores linealmente independientes que diagonalizan la matriz C, es decir:
SiT C Sj = 0 ∀ i ≠ j
Direcciones conjugadas de Powell (III)
• Propiedad extendida del subespacio paralelo:
• Calcular:• λ(0) → mínimo f( x(1)= x(0) + λ(0)e1)• λ(1) → mínimo f( x(2)= x(1) + λ(1)e2)• λ(2) → mínimo f( x(3)= x(2) + λ(2)e1)• s1 = x(3) - x(1) es C-conjugada de e1
y e2
• Repetir procedimiento con e2 y s1
e(2)
x(0)
e(1)
x(1)
x(2)x(3)
• Algoritmo:– 1.- Definir x(0) y un conjunto de direcciones independientes s(i) =
e(i), i=1,...,N– 2.- Minimizar a lo largo de N+1 direcciones usando el mínimo
anterior y poner s(N) como primera y última dirección de búsqueda– 3.- Construir la nueva dirección conjugada – 4.- Borrar s(1), reemplazarla por s(2), etc. Poner la nueva dirección
en s(N) e ir al paso 2.
Direcciones conjugadas de Powell (IV)
• Incluir:– Un chequeo de convergencia – Test para asegurar la independencia lineal de las direcciones
conjugadas
Métodos de solución de problemas sin restricciones (optimización vectorial)
Métodos de Búsqueda Directa Utilizan los valores de la función
Métodos del Gradiente Requieren valores aproximados de la primera
derivada de f(x)
Métodos de Segundo OrdenAdemás de utilizar la
primera derivada también utilizan la segunda
derivada de f(x)
Métodos del Gradiente
X(k+1) = x(k) + α(k) s (x(k))
1. Tamaño del paso del algoritmo: α(k)
2. Vector de Dirección de búsqueda: s(x(k))
3. Algoritmo del gradiente y método del Descenso más pronunciado
Significado Geométrico del vector gradiente
• Expansión en serie de Taylor de la función alrededor de x*:
f(x) = f(x*) + ∇f(x*) Δx
• f(x*) es fijo por tanto el segundo término dictaráel descenso de f(x) =>
s(x(k)) = - ∇f(x(k))
Tamaño del paso del algoritmo
x1
x2
d
α xk
xk+1
α
( )αf
( ) ( )kk1k dαxfxf +=+ ( )kkαdαxfmin +
α(k) puede ser constante (método del gradiente) o calcularse en cada iteración de forma que f(x(k+1)) sea mínimo a lo largo de la dirección -∇f(x(k)) (método del descenso más pronunciado)
Algoritmo del Método del Descenso más pronunciado
1. Selección de un punto inicial x0, eg. La iteración k=0
2. Calcular ∇f (xk). Parar si || ∇f (xk) || ≤ eg . De lo contrario, definir el vector : sk = s(xk) = - ∇f (xk)
3. Obtener αk de minimizar f (α) = f (xk + α sk) . Actualizar
xk+1 = xk + αk sk
4. k = k+1 y xk = xk+1 . Ir al paso 2.
Inconveniente: Lentitud del algoritmo cerca del mímimo ya que ∇f(x(*)) = 0.
Métodos de solución de problemas sin restricciones (optimización vectorial)
Métodos de Búsqueda Directa Utilizan los valores de la función
Métodos del Gradiente Requieren valores aproximados de la primera
derivada de f(x)
Métodos de Segundo OrdenAdemás de utilizar la
primera derivada también utilizan la segunda
derivada de f(x)
Método de Newton (I)
Consideramos la expansión de Taylor de la función objetivo:
( ) ( )( ) ( )( ) ( )( ) ( )3k2TTkk xΔOxΔxfxΔ21xΔxfxfxf +∇+∇+=
Hacemos una aproximación cuadrática de f(x) eliminando el término de tercer orden
( )( ) ( )( ) ( )( ) ( )( ) xΔxfxΔ21xΔxfxfx;xf~ k2TTkkk ∇+∇+=
El siguiente punto se calcula suponiendo que el gradiente de la aproximación cuadrática es igual a cero
Método de Newton (II)
Utilizamos la aproximación cuadrática de f(x) para construir una secuencia de iteración, forzando a x(k+1), como el siguiente punto en la secuencia.
( )( ) ( )( ) ( )( ) 0xΔxfxfx;xf~ k2kk =∇+∇=∇
De aquí que: ( )( ) ( )( )k1k2 xfxfxΔ ∇−∇=−
( ) ( ) ( )( ) ( )( )k1k2k1k xfxfxx ∇∇−=−+
Método de Optimización de
Newton
Método de Newton (III)
• Método modificado de Newton:– α(k) es tal que f (x(k+1)) sea mínimo– s(x(k)) = - [∇2 f(x(k))]-1 ∇f(x(k))
• Características: asegura la dirección descendente, pero la evaluación de [∇2 f(x(k))]-1 es difícil y puede ser singular.
• Método de Marquardt-Lavenberg:– α(k) =1.– s(x(k)) = - [∇2 f(x(k)) + λ(k) I ]-1 ∇f(x(k))– λ(k) controla la dirección de búsqueda y mejora la
singularidad de la Hessiana. Se chequea la dirección descendente, si f(xk+1) < f( xk) => λ(k+1) < λ(k), si no se cumple: λ(k) = β λ(k) con β > 1 y se repite el paso otra vez.
Método de Marquadt-Lavenberg
• Algoritmo:– 1.- Definir x0, estima inicial de x*, M el número máximo de
iteraciones y ε criterio de convergencia.– 2.- k= 0. λ0 = 104
– 3.- ⎟⎟ ∇f (xk)⎟⎟ < ε ?. Si ir a 10, No continuar– 4.- K ≥ M ?. Si ir a 10. No: continuar– 5.- Calcular s(xk) = - [∇2 f(x(k)) + λ(k) I ]-1 ∇f(x(k))– 6.- Hacer xk+1 = xk + s(xk)– 7.- f(xk+1) < f(xk) ?. Si ir a 8, No: ir a 9– 8.- Hacer λk+1 = 0.5* λk; k = k+1; Ir a 3– 9.- Hacer λk = 2*λk. Ir a 5– 10.- Parar.
Método del gradiente conjugado• Se calculan direcciones conjugadas utilizando el gradiente.• Aproximando la función objetivo por una función cuadrática:
q(x) = a + bT x + 1/2 xT C x
∇q(x) = g(x) = Cx + b Δg(x) = C Δx
• s(xk) = - g(k) + ∑i=0k-1 γ(i) s(i) con s(0) = - g(0)
• γ(i) se calculan tal que sk sea C- conjugado a todas las direcciones anteriores calculadas: s0, s1, ..., sk-1
• Varias soluciones:– Fletcher- Reeves: s(k) = - g(k) + [⎟⎟g(k)⎟⎟2 / ⎟⎟g(k-1)⎟⎟2 ] sk-1
– Polak y Ribiere: s(k) = - ∇f(xk) + γk s(k-1) con
γk = Δg(xk)T g(xk) / ⎟⎟g( xk-1)⎟⎟2
Métodos de Quasi-Newton (I)
• Se diseñan para tener las mismas características de los métodos de Newton pero usando sólo derivadas primeras.
• La dirección de búsqueda es:Sk = - Ak ∇f (xk) con Ak métrica
• Ak se calcula de forma recursiva: Ak+1 = Ak + Ack
• Ack se calcula de forma que la secuencia A0, A1, ..., Ak+1
aproxime la inversa de la matrix hesiana: H-1 = [∇2f (xk)]-1
• Si la función es cuadrática la matrix hessiana es C, por tanto se quiere aproximar:
C-1 = β Ak+1
y que cumpla la propiedad cuadrática: Δxk = C-1 Δgk
Métodos de Quasi-Newton (II)
Δxk = β Ak+1 Δgk;
Ack Δgk = 1/ β Δxk – AkΔgk
La solución es:
• Método de Davidon-Fletcher-Powell: y = Δxk y z = Ak Δgk
⎟⎟⎠
⎞⎜⎜⎝
⎛
ΔΔ
−⎟⎟⎠
⎞⎜⎜⎝
⎛
ΔΔ
= kT
Tkk
kT
Tkkc gz
zgAgyyxA
β1
⎟⎟⎠
⎞⎜⎜⎝
⎛
ΔΔΔΔ
−⎟⎟⎠
⎞⎜⎜⎝
⎛
ΔΔΔΔ
+= −−−
−−−−
−−
−−−
11)1(
1)1(11
1)1(
)1(11
kkTk
kTkkk
kTk
Tkkkk
gAgAggA
gxxxAA
Métodos de Quasi-Newton (III)• Conserva las propiedades de simetría y definida positiva => Si
A0 es simétrica y definida positiva, A1, A2,... También. => Una solución A0 =I
• Método de Boyden-Fletcher-Shannon (BFS)
⎟⎟⎠
⎞⎜⎜⎝
⎛
ΔΔΔΔ
+⎟⎟⎠
⎞⎜⎜⎝
⎛
ΔΔΔΔ
−⎟⎟⎠
⎞⎜⎜⎝
⎛
ΔΔΔΔ
−=+kTk
Tkk
kTk
Tkkk
kTk
Tkkk
gxgx
gxgxIA
gxgxIA )(
)(
)(
)(
)(
)(1
Algoritmo general
• 1.- Definir M: número máximo de iteraciones, x0 estima inicial, ε1: criterio de convergencia, ε2 criterio de convergencia lineal.
• 2.- K=0• 3.- Calcula ∇f (xk)• 4.- || ∇f (xk) || ≤ ε1.. Si => ir a 12. No => continuar• 5.- K > M. Si => ir a 12. No => continuar• 6.- Calcular s(k)
• 7.- Encontrar un αk / f (xk + αk sk) sea mínimo, usando ε2
• 8.- Hacer xk+1 = xk + αk sk
• 9.- f (xk+1 ) < f (xk). Si => continuar. No =>Ir a 12• 10.- || Δx || / || xk || ≤ ε1.. Si => Ir a 12. No => continuar• 11.- Hacer K=K+1. Ir a 3• 12.- Parar
Formas de calcular el gradiente
• Calcular el gradiente de forma numérica:
εε
ε
)()*(lim
0
xfexfdxdf i
xxi
−+=
→=
εεε
ε 2)*()*(
lim0
ii
xxi
exfexfdxdf −−+
=→=
Ejemplo 1