optimización de funciones sin restricciones
DESCRIPTION
Optimización de funciones sin restriccionesTRANSCRIPT
5. Optimización de funciones sin restricciones: búsqueda unidimensional
1. Método de Newton
xkxk+1
x*
x
f’(x)
)x(f)x('f
xx k''kk1k −=+
Ventajas:1. El procedimiento presenta convergencia cuadrática2. Para una función cuadrática, el mínimo se obtiene en un solo paso.
Desventajas:1. Es necesario calcular f’(x) y f’’(x)2. Si f’’(x)→0 el método converge lentamente.3. Si el punto inicial no se encuentra cerca al mínimo, el método podría no converger
xk
2. Aproximación de diferencias finitas para la derivada
x
f(x)
f(xk+h)
f(xk-h)
h
[ ][ ] 2
kkk
kkk1k
h/)hx(f)x(f2)hx(fh2/)hx(f)hx(f
xx−+−+
−−+−=+
xqxp
x
f’(x)Pendiente=m
*x~x *
3. Método de Quasi - Newton (Método de la secante)
mxx)x('f
k
k
=−
pq
pq
xx)x('f)x('fm
−−
=
[ ] )xx/()x('f)x('f)x('fxx~ pqpq
−−−=
4. Métodos de aproximación polinomialInterpolación cuadrática
2cxbxa)x(f ++=
c2bx~ −=
Etapa 1
Etapa 2
2333
2222
2111
cxbxa)x(f
cxbxa)x(f
cxbxa)x(f
++=
++=
++=
x1 x
f(x)
x2 x3x~
x2 x3x~ x
x
f(x)
x~x1 x2 x3
Iteración k+1: x2,x,x3
x
f(x)
x~x1 x2 x3
Iteración k+1: x1,x2,x
x2 x
f(x)
x~x1 x3
Iteración k+1: x1,x,x2
x2 x
f(x)
x~x1 x3
Iteración k+1: x2,x,x3
Newton de método el mediante óptimos los Calcularxx·4xf(x)
función la deiosestacionarpuntoslos Encontrar23 +−=
Ejercicio
Solución
Optim1DMetodoNewton.m%Capítulo 5. Optimización de funciones sin restricciones: Búsqueda% unidimensional%Aplicación del método de Newton para encontrar puntos óptimos de funciones%unidimensionales%Minimizar: f(x)=x^3-4*x^2+x%Fórmula recursiva: xk1=xk-(f'(x)/f''(x))%Evaluando la primera derivada: f'(x)=3·x^2-8·x%Evaluando la segunda derivada: f''(x)=6·x-8%Nombre de archivo: Optim1DMetodoNewton.mfunction f=Optim1DMetodoNewton(x0,epsilon)% x0 = Punto de partida, cercano al óptimo. Por ejemplo 8 o -4%epsilon = test de convergencia. Por ejemplo 0.00001xk=x0; Test=epsilon+1;while Test>=epsilon
xk1=xk-((3*xk^2-8*xk+1)/(6*xk-8));Test=abs((xk1-xk)/xk);xk=xk1;
endfprintf('X óptimo = %5.5f\n',xk);
Optim1DMetodoNewtonDifFinit.m%Capítulo 5. Optimización de funciones sin restricciones: Búsqueda% unidimensional%Aplicación del método de Newton con diferencias finitas para encontrar%puntos estacionarios de funciones unidimensionales%Minimizar: f(x)=x^3-4*x^2+x%Fórmula recursiva: xk1=xk-(f'(x)/f''(x))%Evaluando la primera derivada: f'(x)=(f(x+h)-f(x-h))/2h%Evaluando la segunda derivada: f''(x)=(f(x+h)-2·f(x)+f(x-h))/(h^2)%Nombre de archivo: Optim1DMetodoNewtonDifFinit.mfunction f=Optim1DMetodoNewtonDifFinit(x0,h,epsilon)% x0 = Punto de partida, cercano al óptimo. Por ejemplo 8 o -4%epsilon = test de convergencia. Por ejemplo 0.00001xk=x0; Test=epsilon+1;while Test>=epsilon
%Evaluación de derivadas mediante diferencias finitasdF=(Funcion(xk+h)-Funcion(xk-h))/(2*h); %Primera derivadad2F=(Funcion(xk+h)-2*Funcion(xk)+Funcion(xk-h))/(h^2); %Segunda derivada%Cálculo de x(k+1)xk1=xk-(dF/d2F);Test=abs((xk1-xk)/xk);xk=xk1;
endfprintf('X óptimo = %5.5f\n',xk);
Funcion.m%Evaluación de la función f(x)=x^3-4*x^2+xfunction f=Funcion(x)f=x^3-4*x^2+x;
4. Cómo se aplica la búsqueda unidimensional a un problema multidimensional.
búsqueda dedirección paso de Tamaño
viejonuevo
≡≡α
α+=
s
sxx
x0
x2
x1
s
Ejemplo 5.5 Ejecución de una búsqueda unidimensional%Ejercicio5_5.m%Cómo aplicar la búsqueda unidimensional a problemas multidimensionales%Minimizar la función%f(x)=x1^4 - 2·x2·x1^2 + x2^2 + x1^2 -2·x1 + 5%Punto de partida: x0=[1;2]%Dirección: s=-gradiente(f(x0))=-[-4;2]%Algoritmo de búsqueda: Xnuevo=Xviejo+alfa*Sclear;clf; %Borrado de variables y ventanas gráficasX0=[1;2]; %Vector de partidaS=-[-4;2]; %Dirección de búsquedaXviejo=X0;alfa=[0:0.005:0.12];limite=length(alfa);%Iteracionesfor i=1:limite
X1(i)=Xviejo(1,1)+alfa(i)*S(1,1);X2(i)=Xviejo(2,1)+alfa(i)*S(2,1);f(i)=X1(i)^4-2*X2(i)*X1(i)^2+X2(i)^2+X1(i)^2-2*X1(i)+5;
endplot(alfa,f);xlabel('alfa');ylabel('f(x1,x2)');
[fmax,i]=min(f);AlfaOptimo = alfa(i);fprintf('Alfa óptimo = %5.5f\n',AlfaOptimo);
%Curvas de nivelfigure(2)x1=0:0.05:2;x2=0:0.05:3;[X1g,X2g] = meshgrid(x1,x2);F=X1g.^4-2*X2g.*X1g.^2+X2g.^2+X1g.^2-2*X1g+5;contour(X1g,X2g,F,40);xlabel('x1');ylabel('x2')hold online([X1(1),X1(1)+AlfaOptimo*S(1,1)],[X2(1),X2(1)+AlfaOptimo*S(2,1)])
