programacion no lineal final

REPBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DE EDUCACIN SUPERIOR

I.U.P SANTIAGO MARIO

EXTENSIN MARACAIBO PROCEDIMIENTOS Y SISTEMAS ADMINISTRATIVOS.

T.S.U: Flavio Figueroa

Jhonny Espitia

M Pilar Jarabo Amores TCNICAS DE OPTIMIZACIN EN INGENIERA 2

ndice

1. Introduccin.

2. Optimizacin sin restricciones.1. Propiedades bsicas de las soluciones y los algoritmos.2. Ejemplos: filtros adaptativos y redes neuronales.3. Mtodos basados en el gradiente.

1. Mtodo de mxima pendiente. Filtro FIR adaptativo.2. Mtodo de Newton. Filtro FIR adaptativo.

4. Mtodos Quasi-Newton.

SupergeniuxResaltado


Introduccin

z OBJETIVO: Encontrar el mximo o el mnimo de una determinada funcin, llamada funcin objetivo"

z EJEMPLO: Sea la funcin objetivo f

S Rn: espacio de bsqueda, definido por un conjunto de restriccioneshi (x) = 0, i=1,2,,m gi (x) 0, i=1,2,,r x=[x1,,xn]

Solucin: encontrar un vector x* S /

z INCGNITAS A DETERMINAR: Las componentes del vector x*.

x*=[x*1,,x*n]

f(x*) f(x) x S (minimizacin)

f(x*) f(x) x S (maximizacin)


Tipos de problemas

Programacin lineal:

La funcin objetivo, f(), es una funcin lineal de las incgnitas: x=[x1,,xn].

Las restricciones son funciones lineales de las incgnitas: : x=[x1,,xn].

Programacin no lineal:

La funcin objetivo, f(), es una funcin no lineal de las incgnitas: x=[x1,,xn].

Programacin sin restricciones

Programacin con restricciones

x hi (x) = 0, i=1,2,,m

gi (x) 0, i=1,2,,rSon funciones no lineales de las incgnitas: x=[x1,,xn].

COMPLEJIDAD DE LOS PROBLEMAS: Se mide en trminos del nmero de variables a determinar (dimensin de S) y el nmero de restricciones.

x RnEspacio de bsqueda S=En general S=Rn (sin ningn tipo de restriccin)


Optimizacin sin restriccionesPropiedades de la solucin

Condiciones necesarias de primer orden: Tma. de Weierstras: si f es continua y S es compacto, f tiene un mnino en S, por lo que existe solucin.

Direcciones viables: Un vector d es una direccin viable respecto a x si

Si f es una funcin continua y sus primeras derivadas parciales tambin son continuas en S y x* es un mnimo relativo de f sobre S, para cualquier d Rn que sea una direccin viable, se cumple:

0 / 0S > + x d

( )* 0f x d


Optimizacin sin restricciones.Propiedades de la solucin

( ) ( ) ( ) ( )1 2

, ,...,n

f f ff

x x x = x x x

xGradiente de f en x:

Derivada de f en x segn d:

( ) ( ) ( )limt o

f f t ft

+ =x x d xd

Si h es unitario, es la derivada direccional de f en x segn el vector unitario d.

La derivada direccional segn d es de signo opuesto a la derivada direccional segn d.

( )fxd

( ) ( ) ( ) ( )f ff f = x x

x d xd d

( ) ( )1 2, ,..., nf f x x x=x

La igualdad slo se da cuando , luego la derivada direccional es mxima en la direccin del gradiente.( )( )

ff

= x

dx



Si f es una funcin continua y sus primeras derivadas parciales tambin son continuas en S y x* es un mnimo relativo de f sobre S, para cualquier d Rn que sea una direccin viable, se cumple:

Al considerar , es una medida del desplazamiento que he realizado en la direccin d (viable) y en funcin de ese desplazamiento puede definirse la funcin:

Como en x* hay un mnimo relativo:

( )* 0f x d

( ) ( ) ( ) ( )0

* 0dg

g f gd

== + +x d

( ) ( ) ( ) ( )0

0 0 0 * 0dg

g g fd

= x d

Si x* est en el interior de S (por ejemplo S=Rn), cualquier direccin d es viable. Por tanto:

( )* 0f =x

* = +x x d



Ejercicio 1: Minimice la funcin

( ) ( ) 2 21 2 1 1 2 2 2, 3f f x x x x x x x= = + xS=Rn

Ejercicio 2: Minimice la funcin

( ) ( ) 21 2 1 1 2 1 21 2

,0, 0

f f x x x x x x xx x

= = + + x

-10 -50 5

10

-10

0

10-50

0

50

100

150

200

250

300

350

x1x2

f

02

46

810

0

5

10-50

0

50

100

150

200

x1x2

f



Ejemplo 1:

Sea la funcin de produccin f(x1,,xn) que proporciona la cantidad de un producto en funcin de las cantidades de materias primas (xi). El precio unitario del producto es q, mientras que el precio unitario de las materias primas es p1,,pn. Para maximizar el beneficio:

( )1 2 1 1 2 2 , ,..., ...n n nMaximice q f x x x p x p x p x

( )1 21

, ,..., 1,...n i

i

f x x xq p x i n

x = =



Ejemplo 2:

Se ha observado el valor de una funcin g en m puntos z1,z2,,zm: g(z1), g(z2),,g(zm). A partir de estos datos se desea aproximar dicha funcin mediante un polinomio de orden (n-1)



Condiciones necesarias de segundo orden:

Sea f una funcin continua en S Rn. Si sus primeras y segundas derivadas parciales tambin son continuas en S (fC2) y x* es un mnimo relativo de f sobre S, para cualquier d Rn que sea una direccin viable, se cumple:

( )( ) ( )2

) * 0

) * 0, * 0Ta f

b Si f entonces f

= x d

x d d x d

( ) ( ) ( )22i j

ff

x x = =

xx F x

Si fC2, se define la matriz Hessiana de f en x, y se denota como , a una matriz nxn cuyos elementos se calculan como:

( ) ( )2 f =x F x

( ) ( ) ( ) ( ) ( )2 220 0

1* 02

dg d gg f g

d d

= == + + +x d* = + x x d Si ( ) ( )

0

* 0 0dg

fd

=

= =x d

(Condicin de primer orden)

( ) ( ) ( )2 220

102d g

g gd

= =

En x* hay un mnimo ( ) ( )2 220

* 0Td g

fd

=

= d x d



Ejercicio 3: Considere de nuevo la funcin:

( ) ( ) 21 2 1 1 2 1 21 2

,0, 0

f f x x x x x x xx x

= = + + x

Verifique que cumple las condiciones de segundo orden.

Condiciones necesarias de segundo orden en problemas sin restricciones:

Si x* es un punto interior de S y adems se supone que es un mnimo relativo de f C2 sobre S, entonces:

( )( )2

) * 0

) , * 0Ta f

b f

=

x

d d x d

Ejercicio 4: Considere la funcin:

( ) ( ) 3 2 21 2 1 1 2 21 2

,0, 0

f f x x x x x xx x

= = + x

Verifique que cumple las condiciones de segundo orden.



Ejercicio 4: ( ) ( ) 3 2 21 2 1 1 2 21 2

,0, 0

f f x x x x x xx x

= = + x

-1-0.5

00.5

1

-1-0.5

0

0.51

-2

-1

0

1

2

3

4

x1x2

f

5.75.8

5.96

6.16.2

8.88.9

99.1

9.29.3

9.453.5

54

54.5

55

x1

x2

f

-10 -50 5

10-10

0

10-2000

-1000

0

1000

2000

3000

x1x2

f



Nota: Caracterizacin de matrices

Una matriz A (nxn), hermtica, es definida positiva si y slo si:

, 0n TR >x x A x El determinante de la matriz es positivo. Los determinantes de las submatrices obtenidas al eliminar las n-k (k=1,n) ltimas filas y columnas, menores principales, son positivos.

Sus autovalores son positivos.

, 0n TR x x A x

El determinante de la matriz y sus n menores principales son no negativos (positivos o nulos).

, 0n TR


Condiciones suficientes para que exista un mnimo relativo:

Sea x* es un punto interior de S, si se cumplen las condiciones siguientes:

Entonces x*es un mnimo relativo estricto de f.


( )( )2

) * 0

) *

a f

b f es definida positiva

=

x

x


Minimizacin de funciones convexas

Definiciones previas:

Conjunto convexo: S Rn es convexo si y slo si, para todo x, y S, el segmento que los une estcontenido en S.

Funcin convexa: Sea S un espacio convexo y f C1 una aplicacin de S en R, f es convexa si y slo si:

f C2, es convexa en el conjunto convexo S, el cual contiene un punto interior, si y solo si la matriz hessiana de f es semidefinida positiva en todo S.


( ) ( ) ( )( ) ,f f f S + y x x y x x y

( ) ( ) ( )( ) ( ) ( )( ) ( )21 0 12

Tf f f f + + + y x x y x y x x y x y x( )2 , 0TS f x x x x

( ) ( ) ( )( ) ,f f f S + y x x y x x y

( )( ) ( ) ( ) ( )1 1 , 0 1f f f S + + <


Minimizacin de funciones convexas


Sea f una funcin convexa definida en el conjunto convexo S. El conjunto donde f alcanza su mnimo es convexo y cualquier mnimo relativo de f es un mnimo absoluto.

Si f C1, es convexa en el conjunto convexo S, y hay un punto x* S que cumple la condicin:

Entonces x* es un mnimo absoluto de f en S.

( ) ( )* * 0, f S x y x y

Si f C1, es convexa en el conjunto convexo S, y x* es un punto crtico, , f alcanza un mnimo absoluto en x*.

( )* 0f =x

Sea S un conjunto abierto y convexo de Rn y f una aplicacin de S en R diferenciable y convexa en S. La funcin f alcanza un mnimo relativo en x* S, si y solo si x* es un punto crtico, . Adems, por [1], f alcanza mnimo absoluto en x*.

( )* 0f =x

[1]

[2]

[3]

[4]


Optimizacin sin restricciones.Propiedades de los algoritmos

Algoritmos iterativos : El algoritmo genera una serie de puntos cada uno de los cuales se obtiene a partir de puntos obtenidos en iteraciones anteriores. Dos estrategias:

( )1k kA+ =x x

A partir de un punto inicial x0 S, el algoritmo A genera nuevos puntos que tambin pertenecen a S:

Objetivo: La secuencia de puntos obtenida debe converger en un nmero finito o infinito de iteraciones al valor deseado.

Algoritmo globalmente convergente: Para cualquier valor inicial, el algoritmo genera una secuencia de puntos que converge a la solucin.

A partir de un punto inicial x0 S, el algoritmo A genera un subconjunto de S, S1:

Se elije aleatoriamente un elemento x1S1 y se aplica de nuevo el algoritmo para obtener un S2S. En general:

( )1 0S A= x

( )11 1

donde se elige aleatoriamente en se elije aleatoriamente en

k k k k

k k

S A SS

+

+ +

= x xx

En la prctica se utiliza la primera estrategia, mientras que la segunda es una herramienta para analizar la convergencia de familias infinitas de algoritmos similares.



Algoritmos descendentes: Sea A un algoritmo definido sobre S y S el conjunto solucin. Una funcin continua y real Z en S es una funcin descendente para y A si:

( ) ( ) ( )

( ) ( ) ( )

)

)

a Z ZA

b Z ZA



Teorema de la convergencia global establece condiciones que garantizan la convergencia de un algoritmo:

Sea A un algoritmo en X y suponga que dado x0 se genera la secuencia { } ( )10 /k k kk A += x x x

Sea X un conjunto solucin y suponga que:

/ es compactok S X S xExiste una funcin continua Z en X tal que:

( ) ( ) ( )( ) ( ) ( )

) Si ,

) Si ,

a Z Z A

b Z Z A

< x y x y x

x y x y x

A est cerrado en puntos situados fuera de X

El lmite de cualquier subsecuencia convergente de es una solucin.

{ }kx



Ejercicio 5:

( ) ( )1 1 1 121 12

x xA x

x x

+ >=

{ }( )

0

Z x x

==

Ejercicio 6:

( ) [0,x) 1 00 x=0

xA x

>=

{ }( )

0

Z x x

==



Convergencia lineal:

Si la secuencia rk de nmeros reales converge a r* de modo que 1**

lim 1


Filtros adaptativosDefinicin: Un sistema adaptativo puede definirse como aquel capaz de alterar o ajustar su estructura para

mejorar su comportamiento a travs del contacto con el entorno en el que se desarrolla. Su comportamiento se evala de acuerdo a algn criterio que, generalmente, ser una funcin de error.

El proceso de adaptacin es un ejemplo de proceso de optimizacin para minimizar la funcin de error elegida (funcin objetivo).

Una de las funciones de error ms utilizadas es el error cuadrtico medio. Al tratarse de una funcin objetivo no lineal, el problema de optimizacin a resolver puede clasificarse como un caso de programacin no lineal.

Como adems, no vamos a imponer restricciones, estamos ante un ejemplo de programacin no lineal sin restricciones.

Filtro FIR

Sistemas adaptativos en lazo abierto:


Filtros adaptativosSistemas adaptativos en lazo cerrado:

Ventajas:

Aplicaciones para las que no existe o no se conoce ningn mtodo de sntesis analtico.

Ante un fallo parcial del sistema, el sistema en lazo cerrado seguir funcionando reajustando y reoptimizando los controles que permanezcan intactos.

Inconvenientes:

Puede que el criterio de funcionamiento, funcin objetivo, no tenga un nico mnimo.

Como en los sistemas de control en lazo cerrado, el sistema puede ser o hacerse inestable (el proceso adaptativo o de optimizacin diverge en lugar de converger).


Filtros adaptativosAplicaciones de los sistemas adaptativos en lazo cerrado:

Identificacin: Modelado inverso:

Prediccin: Cancelacin de interferencias:


Filtros adaptativos

Ejemplo: Combinador lineal adaptativo

0 , 1 ,...,T

k k k Lkw w w = W

T Tk k k k ky = =X W W X

0 , 1 ,...,T

k k k Lkx x x = X

T Tk k k k k k kd d = = X W W X2 2 2T T Tk k k k k k k k kd d = W X X W X W

2 2 2T T Tk k k k k k k k kE E d E E d = W X X W W X

2 2 2T T Tk k k k kMSE E E d = = XX XdW R W R W

Se asume que la secuencia de entrada, la salida deseada y el error son procesos estacionarios


Adems . En la prctica, Rxx ser casi siempre definida positiva, aunque en ocasiones es semi-definida positiva.

Filtros adaptativos

Ejemplo: Combinador lineal adaptativo

2 2 2Tk k k k kMSE E E d = = XX XdW R W R W

( ) ( ) ( ) ( )0 1

, ,..., 2 2 0T

Lw w w = = = XX XdW W W

W R W R

1* = XX XdW R R2

min * * 2 *T T

kE d = XX XdW R W R W( )2 2 = XXW R

( ) ( )min * *T = + XXW W R W W


Redes neuronalesDefinicin:

Procesador masivo paralelo distribuido, formado por unidades simples, con una propensin natural a almacenar conocimiento experimental y hacerlo disponible para ser usado.

Se asemeja al cerebro humano en dos aspectos:

La red adquiere el conocimiento del entorno a travs de un proceso de aprendizaje.La intensidad de las conexiones interneuronales, pesos sinpticos, se emplea para almacenar el conocimiento adquirido.


( )

( )

( ) ( )

1, x 00, x 0

11, x 21 1, 2 2

10, x 2

11 exp

g x

g x y x

g xax

>=

= > >

= +

Redes neuronales. Definicin y tipos

g()

x2 x3 xn

y

...

1

Neurona con funciones de base lineal:

( ) 01

nT

i ii

I x =

= + =x x w

Modelo de McCulloch y Pitts (1943): funcin escaln no simtrica

Limitador en rampa (aprox. a amplificador lineal):

Funciones sigmoide: funcin logsitca:

Todas estas funciones tienen sus versiones simtricas en torno al origen [-1,1]


Redes neuronales. Definicin y tipos

g()

x2 x3 xn

y

...( ) 2exp

2xg x

=

Neurona con funciones de base radial:Distancia de Mahalanobis de x a un vector de referencia, t, respecto de un amatriz de ponderacin C:

Si C es simtrica, las superficies definidas por una distancia constante a t son hiperelipsoides, cuyos ejes principales vienen dados por los autovectores de C.

Los autovalores de C determinan las varianzas a lo largo de cada uno de los ejes principales.

La funcin de activacin suele ser de tipo gaussiano:

( ) ( )2 1T = Cx t x t C x t

Otras funciones de activacin:

( ) ( ) ( ) 22 2 22 21; ; exp ; 0; 2xg x x g x g x x R

x

= + = = > +


Perceptrn multicapa

z1

zM

g()11 (1 )

21(1)

K 1(1)

1M (1 )2M (1 )

K 0(1)

10(1)

g()

g()

12(2) g()

11 (2 )1

20(1)

1

10(2)11

11

y

1K(2)

En general, en las redes neuronales las neuronas se organizan formando capas (redes de una capa o multicapa).

Atendiendo a cmo se conectan entre s las neuronas, las redes pueden ser de propagacin directa o recurrentes.

z1

zM

g ()I11(1)

21( 1)

K 1(1)

K neuronas1

1M( 1)M 2( 1)

K 0(1)

10( 1)

g ()I

g ()I

g ()211(2)

w22(1)

K neuronas2

K 1(2)

g ()2

g ()2

10( 2)

21( 2)

K K (2)

1

20( 1)

1 1

20( 2)11

11

K 0(2)

Capa 1 Capa 2

...

...

...

g ()LL1( L)

K neuronasL

K 1(L)

g ()L

g ()L

L0( L)

L1( L)

K K (L)

1

20( L)11

11

K 0(L)

Capa L

y1( L)

y2( L)

yK(L)11

y1( 1) y1

( 2)

y2( 1)

y2( 2)

yK(1)

yK(2)


Redes con funciones de base radial


Mtodos basados en el gradiente.Mtodos descendentes

Estructura bsica de estos algoritmos:

1. Dado un punto inicial, x0, se determina, de acuerdo a una regla prefijada, una direccin de movimiento, d1 (descendente).

2. Se determina la magnitud del desplazamiento (el paso) en esa direccin hacia un mnimo relativo de la funcin objetivo en esa direccin:

x1=x0+d1.3. En el punto nuevo, se determina una nueva direccin y se repiten los pasos 2 y 3. As:

xk+1=xk+dk+1Los algoritmos se diferencian en la regla que utilizan para determinar las sucesivas direcciones de movimiento.

LINE SEARCH : determinacin del mnimo en una direccin. Resolucin de un problema de minimizacin en una dimensin.

Soluciones:

Mtodo de mxima pendiente.

Mtodos basados en aproximacin de funciones: Mtodo de Newton.


Si Q es simtrica y definida positiva, todos sus autovalores son positivos y, adems, f es estrictamente convexa, por lo que su nico mnimo se obtiene igualando el gradiente a cero:

Mtodos basados en el gradiente.Mtodo de mxima pendiente

bQx* =

El mtodo de mxima pendiente tambin se conoce como mtodo del gradiente. Es el que se suele usar como primera estrategia ante un problema nuevo y es el estndar de referencia para evaluar otros mtodos.

k es un escalar no negativo que minimiza

Para minimizar una funcin f C1: ( )1 Tk k k kf+ = x x x( )( ) Tk k kf f x x

Caso particular: f es cuadrtica ( ) 1 2

T Tf = x x Q x x b( ) 2 2Tk k k kE d = XX XdW W R W R W

Recurdese el problema del diseo de filtros FIR adaptativosbajo el criterio de minimizacin del error cuadrtico medio:

Propiedades: Las regiones en las que f es constante son hiper-elipsoides en el espacio Rn. Los autovectores de Q son ortogonales (constituyen una base de Rn) e indican las direcciones de los ejes de los hiper-elipsoides. La magnitud de cada eje es inversamente proporcional al autovalor asociado al autovector que indica su direccin.



Funcin cuadrtica



Caso particular: f es cuadrtica ( ) 1 2

T Tf = x x Q x x b

En lugar de trabajar con f definimos la funcin: ( ) ( ) ( ) ( ) ****21 QxxxxxQxxx TT fE +==

( ) ( ) ( ) bQxxgxx === fE

kK

Tk

KTk

kk gQggggxx

=+1

El valor de k que minimiza puede obtenerse de forma explcita derivando respecto a k en la expresin:

( ) ( )( )bQxxgx = Kkkkkk ff

( ) ( ) ( ) ( ) bgxgxQgxgx TKkkKkkTKkkkkkf 21 =

KTk

KTk

k Qgggg=

( )bQxxgxx ==+ kkkkkkk 1

1=x* Q b



Caso particular: f no es cuadrtica

Caso particular: f es cuadrtica

Teorema: Para cualquier vector inicial x0, el mtodo de mxima pendiente converge al nico mnimo x* de f. Adems en cada iteracin k se cumple:

( ) ( )xx EaAaAE k

2

1

++

Donde a y A son, respectivamente, el menor y el mayor autovalor de Q.

En general, se puede decir que el mtodo de mxima pendiente se ralentiza cuando los contornos de f se hacen ms excntricos (mayor es la diferencia entre los autovalores mximo y mnimo). Si a=A (contornos circulares), la convergencia tiene lugar en un solo paso.

En general, se utiliza la matriz hessiana de la funcin objetivo en la solucin como si fuera la matriz Q del caso cuadrtico.

Teorema: Supngase que f C2, tiene un mnimo relativo en x* y que a>0 es el menor autovalor de su hessiana en x*, mientras que A>0 es el mayor. Si xk es una secuencia generada por el mtodo de mxima pendiente que converge a x*, entonces f(xk)converge linealmente a f(x*) con una velocidad de convergencia no superior a:

[(A-a)/(A+a)]2.



Ejemplo: Filtro adaptativo con un solo coeficiente

Si las seales son estacionarias, la superficie de error es una parbola cuya ecuacin puede escribirse como:

( ) [ ]kk xxEww =+= ,* 2min( ) ( ) *221*21 wwwwwdw

dww kkkk

kk +==

=+

( ) ( )100

1 2 2 * 1 2k

k nk

nw w w

== +

Ecuacin en diferencias, lineal, de primer orden y de coeficientes constantes, cuya solucin es:

( ) ( )*21* 0 wwww kk +=

Si |r|=|1-2|>o, el algoritmo es estable y *lim wwkk =

( ) ( )( )01 1 2

1 2 2 *1 1 2

kk

kw w w

= +




Siempre que |r|




Curva de aprendizaje:

( )( ) ( )

+=

+=*21*

*

0

2min

wwwwww

kk

kk

El error sigue una progresin geomtrica hacia su mnimo, de razn (1-2)2.

Como la razn no es negativa, el error cuadrtico medio nunca oscilar y ser estable si r=(1-2)2



Ejemplo: Filtro FIR adaptativo de orden L

2 2 2T T Tk k k k kMSE E E d = = XX XdW R W R W

( ) ( ) ( ) ( )0 1

, ,..., 2 2 0T

Lw w w = = = XX XdW W W

W R W R

1* = XX XdW R R

0 , 1 ,...,T

k k k Lkw w w = W0 , 1 ,...,T

k k k Lkx x x = X

( ) ( )1 2 2k k k k k + = = XX XdW W W W R W R

( ) ( )1 2 * 2 2 *k k k k + = + = +XX XX XXW W R W W I R W R W

( ) ( )( ) ( )

0( 1) 0

1( 1) 1

( 1)

1 2 0 2 12 1 1 2 0 2 *

k k

k k

L k Lk

w ww w

w w

+

+

+

= +

XX XX

XX XX XX

R RR R R W

LLM MM M M

Salvo que la matriz de autocorrelacin sea diagonal, cada wi(k+1) ser funcin de todos los componentes de Wk.




( ) * 2 21 WRWRIW XXkXXk +=+ Forma normalizada de la matriz de autocorrelacin de la seal de entrada:

1V =XXR V

Traslacin para que el origen de coordenadas est en W*:

( )' 1' * 2 'k k+= = XXW W W W I R W Rotacin para que los nuevos ejes de coordenadas coincidan con los ejes principales (autovectores) de la superficie de error:

( ) kk '' 2''' '' 1 WIWVWW == +

sautovalore losson elementos cuyos diagonal matriz esautovector de matriz

V




( ) kk '' 2''' '' 1 WIWVWW == +

=

+

+

+

Lk

k

k

LkL

k

k

w

ww

w

ww

''

''''

2100

210021

''

''''

1

0

1

0

)1(

)1(1

)1(0

MMMMLL

M

( ) ( ) ( )'' '' ''01 1 2 '' 0,1,... 2 ki ik ki kw w i L + = = = W I W( ) Likik ,...1,0 0 21lim == El algoritmo converge si

CONDICIN NECESARIA Y SUFICIENTE PARA LA CONVERGENCIA DEL ALGORITMO SOBRE UNA SUPERFICIE DE ERROR CUADRTICA:

max

10



Ejemplo: Filtro FIR adaptativo de orden L ( ) ( )0* 2 *kk = + XXW W I R W W( ) knnL

nnk w

2

0

20min 21'' +=

=

La curva de aprendizaje es la suma de L+1 progresiones

geomtricas con razones dadas por ( )221 n


Mtodos basados en el gradiente.Mtodo de Newton

Supngase que se desea minimizar una funcin de una variable f(x) y que en un punto xk, es posible evaluar f(xk), f (xk) y f (xk)

Es posible construir una funcin cuadrtica q(x) que en xktiene el mismo valor que f y las mismas derivadas de primer y segundo orden.

( ) ( ) ( )( ) ( )( )21' ''2k k k k k

q x f x f x x x f x x x= + +

El mnimo de f puede estimarse como el punto en el que la primera derivada de q se anula:

( ) ( ) ( )( )1 10 ' ' ''k k k k kq x f x f x x x+ += = + ( ) ( ) ( )( )' ' ''k k kq x f x f x x x= + ( )( )1'''

kk k

k

f xx x

f x+=

El mtodo puede interpretarse como una tcnica para resolver de forma iterativa ecuaciones de la forma: g(x)=f (x)=0

( )( )1 '

kk k

k

g xx x

g x+=

Supngase que g(x) es continua y que g(x*)=0 y g(x*)0. Si x0 est suficientemente cerca de x*, la secuencia {xk}k=0generada por el mtodo de Newton converge a x*, con, al menos, un orden de convergencia igual a 2.



Clculo del punto en el que la primera derivada de q se anula:

( ) ( ) ( )( )2' k k kq f f= + x x x x x

( ) ( ) ( ) ( )( ) ( ) ( ) ( )21 2

Tk k k k k kf q f f f = + + x x x x x x x x x x x

En general, si x Rn:

( ) ( ) ( ) ( )21 1' 0k k k k kq f f+ += + =x x x x x

Condiciones suficientes para que exista un mnimo relativo:

Sea x* es un punto interior de S, si se cumplen las condiciones siguientes:

Entonces x* es un mnimo relativo estricto de f.

( )( )2

) * 0

) *

a f

b f es definida positiva

=

x

x

Entonces, si la hessiana es definida positiva en un mnimo relativo, x*, y f tiene derivadas segundas continuas, su hessiana es definida positiva en las proximidades de la solucin, x*, y el mtodo estbien definido en esa regin.

( ) ( )121 Tk k k kf f+ = x x x x

Teorema: Sea fC3 en Rn y asmase que su hessiana es definida positiva en un mnimo local x*; si el algoritmo comienza suficientemente cerca de x*, los sucesivos puntos generados por el algoritmo convergen a x*. El orden de convergencia es al menos de 2.



Modificaciones aplicables en puntos alejados de la solucin: Aunque el algoritmo tiene propiedades muy interesantes en las proximidades de un mnimo, es necesario realizar una serie de modificaciones antes de poder aplicarlo en puntos alejados de la solucin:

Introduccin de un parmetro de ajuste: El parmetro k se va ajustando para evitar que la funcin objetivo empiece a aumentar debido a trminos no cuadrticos.

Modificacin de la hessiana antes de invertirla: Considere el siguiente algoritmo: donde Mk es una matriz nxn.

La direccin ser descendente si para >0 pequeo, f decrece cuando aumenta. Para valores pequeos de :

Como 0, el segundo trmino de la derecha domina sobre el tercero. Para garantizar un descenso en f para pequeo, se requiere que

( ) ( )121 Tk k k k kf f + = x x x x

( )1 Tk k k k kf+ = x x M x

( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )2 21 1 Tk k k k k k k k k kf f f O f f f O + += + + = +x x x x x x x x x M x( )Tk k kf= d M x

( ) ( ) 0Tk k kf f >x M x Impngase que Mk sea definida positiva


Clculo de para que Mk sea definida positiva: Elija una constante >0 y dado xk, calcule los autovalores de la hessiana en ese punto y elija como la menor constante no negativa para la que la matriz

tenga autovalores mayores o iguales que .


Modificaciones aplicables en puntos alejados de la solucin:

Modificacin de la hessiana antes de invertirla:

( )1 Tk k k k kf+ = x x M x

( ) 12k k kf = + M I x

Si Mk=I se obtiene el mtodo de nxima pendiente.

Si Mk= se obtiene el mtodo de Newton, pero en un punto alejado de la solucin Mk puede que no sea definida positiva o incluso que no exista.

( ) 12 kf x

Muy elevado mtodo de mxima pendiente

mtodo de Newton

k0k =

kk ( )2k kf +I x


Mtodos basados en el gradiente.Mxima pendiente v.s. Newton

Ejemplo: Filtro FIR adaptativo de orden 1

Mtodo de mxima pendiente Mtodo de Newton


Mtodos Quasi-Newton

z Estos mtodos utilizan una aproximacin de la inversa de la matriz hessiana.z Mtodo clsico:

z Clculo aproximado de la inversa de la hessiana. Cmo puede construirse la inversa de la matriz hessiana a partir del gradiente calculado en varios puntos.Sea f una funcin en Rn con segundas derivadas continuas. Si para dos puntos xk, xk+1, definimos

( ) ( )121 0 Tk k k kf f + = x x x x La hessiana que se calcul con el primer punto es la que se emplea en todo el proceso.

( ) ( )1 1 1; ; T Tk k k k k k kf f+ + += = = g x g x p x x entonces ( )21k k k kf+ g g x pSi la hessiana es constante: 21k k k kf+ q g g p

Adems puede determinarse de forma nica a partir de n direcciones p0,,pn-1, linealmente independientes y sus correspondientes q0,qn-1. Si P y Q son matrices cuyas columnas son pk y qk, respectivamente:

2 1f =QP


Mtodos Quasi-Newton

z Clculo aproximado de la inversa de la hessiana.

Llegados a este punto, se propone la construccin de aproximaciones sucesivas de la inversa de la hessiana, Hk, en funcin de datos obtenidos en los primeros k pasos de un proceso descendente, de modo que si la hessiana fuese constante:

Despus de n iteraciones linealmente independientes,

1 0k i i i k+ = H q p

( )-12n f= HPara cualquier k


Mtodos Quasi-Newton

z Correccin de rango 1.

Como y su inversa son matrices simtricas, resulta lgico imponer que Hk, la aproximacin de F-1, tambin

lo sea. Veamos la posibilidad de utilizar una regla de adaptacin del tipo:

define una matriz de (al menos) rango1. ak y zk se eligen para cumplir :

1T

k k k k ka+ = +H H z z

2 f= F

Tk k ka z z 1k k k+ =H q p

1T

k k k k k k k k ka+= = +p H q H q z z q( )( )

( )1 2T

k k k k k kk k T

k k ka+

= + p H q p H qH Hz q

( )2T T Tk k k k k k k ka =q p q H q z q ( )( )( )1T

k k k k k kk k T

k k k k+

= + p H q p H q

H Hq p H q


Mtodos Quasi-Newton

z Correccin de rango 1.

En un proceso de optimizacin se calcular la direccin descendente en la iteracin k-sima como:

A continuacin se minimizar f(xk+kdk) con respecto a k0, para obtener: :

k k k= d H g

1k k k k+ = +x x d

k k k=p d1k+g

( )( )( )1

Tk k k k k k

k k Tk k k k

+ = +

p H q p H qH H

q p H q

La frmula de actualizacin de Hk asegura que el resultado es una matriz definida positiva si el denominador es mayor que cero, condicin que no est garantizada. E incluso cuando es mayor que cero, puede ser demasiado pequeo dando lugar a problemas numricos.


Si Hk es definida positiva, tambin lo ser Hk+1

Mtodos Quasi-Newtonz Mtodo de Davidon-Fletcher-Powell

En cada paso, la inversa de la hessiana se actualiza con la suma de dos matrices simtricas de rango 1. Tambin se

conoce como correccin de rango 2.

Comenzando con cualquier matriz simtrica, definida positiva H0, cualquier punto x0 y k=0:

Paso 1:

Paso 2: Minimizar f(xk+kdk) con respecto a k0, para obtener:Paso 3: :

k k k= d H g1k k k k+ = +x x d k k k=p d 1k+g

1

T Tk k k k k k

k k T Tk k k k k

+ = + p p H q q HH H p q q H q

1k k k+= q g g

programacion no lineal final

Documents