00:00:01
[Música]
00:00:11
en este vídeo vamos a hablar del método
00:00:14
de youtube para minimización
00:00:17
entre los métodos que existen para
00:00:20
minimizar ya vimos el método del
00:00:23
gradiente
00:00:24
o más exactamente menos el gradiente
00:00:28
o también conocido como método de máximo
00:00:31
descenso
00:00:32
pero el método de newton ha resultado
00:00:35
ser el método más exitoso
00:00:39
para minimizar
00:00:42
por supuesto hay variantes que podemos
00:00:44
analizar
00:00:46
y vamos a demostrar en este en esta
00:00:48
clase que vamos a ver que puede
00:00:51
convertir mucho más rápido para algunas
00:00:53
funciones
00:00:55
vamos a interpretar de qué se trata el
00:00:58
método de newton para minimización
00:01:05
supongamos que tenemos el caso ideal de
00:01:07
tener una ecuación una función
00:01:09
cuadrática en varias variables
00:01:13
como esta ya hemos visto que su derivada
00:01:17
o su ingrediente
00:01:18
se calcula
00:01:20
simplemente con una equis
00:01:23
así que su solución en su solución el
00:01:27
gradiente debe dar cero
00:01:30
es decir para resolver un problema
00:01:33
cuadrática
00:01:35
es suficiente con resolver un sistema de
00:01:38
ecuaciones lineales a x igual a b y
00:01:42
encontramos de manera inmediata en un
00:01:44
solo paso la solución
00:01:47
tratando de llevar esta idea
00:01:50
vamos a ver cómo se desarrolló el método
00:01:54
del yute y haciendo aproximaciones
00:01:57
cuadráticas
00:01:58
esto nos lleva a pensar en el polinomio
00:02:01
de taylor
00:02:05
y pensemos en cómo sería una
00:02:06
aproximación cuadrática
00:02:09
bueno para una función dos veces
00:02:11
diferenciables
00:02:13
de rn en r
00:02:16
la aproximación de trino tendría esta
00:02:19
forma
00:02:21
sería hd de igual a fx más el gradiente
00:02:25
df tras puesto porte más un medio desde
00:02:30
atrás puesto por la matriz es jana en x
00:02:33
por d
00:02:36
como es una función cuadrática
00:02:39
el mínimo o mínimis más bien el
00:02:42
minimizador de esta función se puede
00:02:45
localizar
00:02:46
resolviendo un sistema de ecuaciones
00:02:49
lineales
00:02:50
recuerden que el gradiente de h vendría
00:02:53
siendo
00:02:56
la matriz es jana de efe o sea lo que en
00:03:00
el caso que acabamos de ver era la
00:03:02
matriz
00:03:04
por de más el gradiente de que en el
00:03:10
ejemplo anterior era b
00:03:13
para encontrar una solución de este
00:03:16
problema de esta aproximación
00:03:17
tendríamos simplemente que resolver un
00:03:20
sistema de ecuaciones lineales
00:03:23
este sistema de ecuaciones
00:03:26
y es en esta idea que se basa el método
00:03:29
de neutro resolver de manera sucesiva un
00:03:33
número finito de problemas
00:03:38
cuadra ticos
00:03:40
voy a tratar de ilustrarlo con la
00:03:43
siguiente con el siguiente digo vamos a
00:03:46
suponer que queremos minimizar esta
00:03:49
función en una variable
00:03:52
queremos empezar en el 2
00:03:55
entonces a partir de ese punto inicial
00:03:58
vamos a construir una función cuadrática
00:04:02
y como ésta tiene una solución fácil de
00:04:06
calcular ya una fórmula cerrada para el
00:04:09
caso de una cuadrática de la forma
00:04:12
x2 más bx más el minimizador se
00:04:17
encontraría en menos b sobre dos años
00:04:21
en este caso en esta aproximación
00:04:23
podemos encontrar cuál es el minimizado
00:04:26
este sería el segundo punto de la
00:04:29
sucesión repetimos el proceso
00:04:33
encontramos una aproximación que pase
00:04:35
por el punto x suma f x 1 nos da otra
00:04:38
cuadrática encontramos el minimizador
00:04:41
ese sería x2
00:04:44
ahora repetimos el proceso
00:04:47
aproximamos en ese punto con un modelo
00:04:50
cuadrática
00:04:51
resolvemos este problema usando la
00:04:55
fórmula cerrada y así nos vamos
00:04:58
aproximando a la solución de este
00:05:01
problema recuerde el minimizador de el
00:05:06
problema es lo que estamos buscando
00:05:08
teniendo esto claro
00:05:11
vamos a plantear un algoritmo
00:05:14
de newton como sería el algoritmo básico
00:05:18
de vida
00:05:23
lo primero que necesitamos es un punto
00:05:28
inicial
00:05:29
e ingresar un punto inicial
00:05:33
x 0
00:05:38
después determinamos la dirección de
00:05:41
newton resolviendo el problema
00:05:46
es ya la matriz en ciana df por de
00:05:49
dedica igual a menos el gradiente de
00:05:53
observen que este es un sistema
00:05:57
de ecuaciones lineales
00:06:01
como es un sistema de ecuaciones
00:06:02
lineales se puede resolver por eliminar
00:06:05
su obra social
00:06:06
pero también tiene sus inconvenientes
00:06:11
porque como ustedes saben un sistema de
00:06:13
ecuaciones lineales podrían no tener
00:06:15
solución o aunque tuvieran la matriz que
00:06:20
determina el sistema podría estar mal
00:06:23
condicionada y los resultados que noten
00:06:26
pueden ser basura
00:06:30
hay que tenerlo en cuenta en cuenta a la
00:06:33
hora de la programación
00:06:35
el siguiente paso después de tener la
00:06:37
dirección del minuto es actualizar el
00:06:40
literal
00:06:43
sumando landa por de ese land azúcar se
00:06:47
obtiene con búsqueda lineal y exacta
00:06:51
no tenemos un detalle a pesar de que el
00:06:55
método de newton para minimización se
00:06:58
basa en un modelo cuadrática no es
00:07:02
necesario que en cada paso se plantee
00:07:05
quién es la función h
00:07:08
esta función cuadrada no es necesario
00:07:10
solamente nos movemos a través de las
00:07:13
soluciones que dan esos modelos
00:07:16
cuadraditos
00:07:19
bueno después de tener esto como
00:07:23
de tener este método pues queremos saber
00:07:26
cómo implementarlo pero recuerden hay un
00:07:30
asunto a tener en cuenta con un sistema
00:07:36
ahora nos preguntamos la dirección de
00:07:39
newton es una dirección de descenso
00:07:42
claro que sí bajo la hipótesis de que la
00:07:46
matriz decían que siempre debe ser
00:07:49
simétrica
00:07:50
la hipótesis es que esta matriz sea
00:07:53
definida positivo
00:07:56
veamos
00:07:58
supongamos que tenemos que resolver este
00:08:01
sistema de ecuaciones y multiplicamos a
00:08:05
la izquierda por de atrás puesto de sus
00:08:08
caras
00:08:11
si la hipótesis se cumple de que la
00:08:14
matriz diana es definida positiva el
00:08:16
término que está a la izquierda es
00:08:20
positivo
00:08:23
así que si es positivo entonces también
00:08:28
lo es menos de atrás puesto por el
00:08:31
gradiente de f
00:08:33
y eso quiere decir que es una dirección
00:08:37
de descenso
00:08:38
recuerden que el producto interno de
00:08:41
conmutativa y para que una dirección sea
00:08:44
de descenso debe cumplirse que el
00:08:46
gradiente con el producto interno por d
00:08:49
debe dar negativo y eso es lo que está
00:08:52
pasando aquí
00:08:56
tenemos que considerar como mencioné
00:08:58
antes los problemas que puede tener
00:09:01
resolver un sistema de ecuaciones
00:09:02
lineales
00:09:04
para este problema hay dos cosas que
00:09:08
debemos considerar para el problema
00:09:10
relacionado con el método del judo
00:09:15
un problema
00:09:18
que a no sea definida es positiva
00:09:23
en otras condiciones nos interesaría
00:09:25
simplemente que afuera no singular
00:09:30
pero como aquí necesitamos que sea una
00:09:33
dirección de descenso no solamente le
00:09:36
vamos a pedir que sea no singular sino
00:09:38
que sea definida positiva es decir que
00:09:43
no tenga cero como valor propio pero que
00:09:45
sus valores propios sean positivos
00:09:49
y no queremos tener que en cada programa
00:09:53
en el programa tengamos que calcular los
00:09:55
valores propios porque eso sería muy
00:09:58
costoso desde el punto de vista
00:09:59
computacional
00:10:02
si la matriz no es definidas positivas
00:10:04
que podemos hacer
00:10:06
voy a explicar una alternativa que ha
00:10:09
resultado muy práctica
00:10:12
y sumar a la matriz a un múltiplo de la
00:10:17
matriz identidad
00:10:19
esta perturbación
00:10:21
alterará un poco a la matriz pero
00:10:25
podría convertirla en definida positiva
00:10:29
si no lo hace nuevamente le sumamos view
00:10:33
por mí o es un número pequeño así que
00:10:37
estaríamos sumando esa misma cantidad en
00:10:41
los elementos de la diagonal
00:10:43
haciendo así que el espectro de la
00:10:45
matriz se vuelva positivo o esté en un
00:10:48
conjunto positivo
00:10:51
para el caso particular que estamos
00:10:53
tratando a quien deberíamos perturbar
00:10:56
esa la matriz social
00:10:59
sumándole un poli
00:11:01
el otro problema es que la matriz no sea
00:11:05
bien condicionada
00:11:07
si la matriz ya no está bien
00:11:09
condicionada
00:11:11
lamentablemente no podemos hacer nada
00:11:14
no podemos corregirla
00:11:17
el problema cada vez que usemos el
00:11:20
sistema de ecuaciones al no estar bien
00:11:23
condicionada nos va a arrojar basura lo
00:11:26
que arroja los valores que nos dé como
00:11:29
respuesta no son confiables así que dado
00:11:33
que esto puede pasar en medio del
00:11:35
algoritmo
00:11:36
tendríamos que buscar una alternativa y
00:11:40
es cambiar la dirección de minutos por
00:11:43
una dirección que aunque no sea
00:11:48
la de newton sea efectiva como pasa con
00:11:53
el método del gravity
00:11:55
así que en el caso de que eso pase lo
00:11:59
que vamos a hacer es cambiar la
00:12:00
dirección de por menos el gradiente
00:12:03
esa sería la solución
00:12:06
como se programa vamos a hacer un
00:12:08
experimento a ver como se programa esto
00:12:11
en manda
00:12:14
hablemos de la programación del método
00:12:16
de newton
00:12:19
aquí tengo programado no está escrito
00:12:21
como función sino como un script que se
00:12:23
puede ejecutar desde aquí
00:12:26
empecemos hablando de la primera línea
00:12:28
clc para borrar la pantalla cada vez que
00:12:32
se ejecute en el punto x es el punto
00:12:35
inicial
00:12:36
observen que a x no escribo cada
00:12:39
componente sino simplemente escribo x y
00:12:43
aquí como vector columna las componentes
00:12:45
que necesiten
00:12:47
efe x es la función evaluada en x la
00:12:52
función fue escrita en esta parte
00:12:55
aquí tengo varias pero en este momento
00:12:58
estoy hablando de la última más adelante
00:13:01
voy a explicar cuál es el problema de
00:13:03
resultado
00:13:05
el gradiente en gradiente de la función
00:13:07
también he escrito como vector columna
00:13:11
es efe es la función que calcula la
00:13:14
matriz s a
00:13:17
desde el tamaño de paso que inicialmente
00:13:21
es un pica es un contador que nos
00:13:24
indicará el número de operaciones
00:13:27
tipo es una variable alfa numérica que
00:13:30
nos va a indicar si se usa el método de
00:13:33
newton o el método del gradiente o del
00:13:36
máximo descenso que es el que vamos a
00:13:39
usar para comparar
00:13:42
empezamos aquí en un ciclo con la línea
00:13:45
9 del ciclo white se va a detener cuando
00:13:49
la norma del gradiente con la norma
00:13:51
infinito la norma del gradiente sea
00:13:55
menor que 10 a la menos 3 se va a
00:13:59
detener así que en el 'wild va la
00:14:02
negación
00:14:03
aquí lo que dice es haga mientras la
00:14:06
norma infinita del gradiente sea mayor o
00:14:10
igual que díaz a la menos 3
00:14:15
que acá sea menor o igual que equipo es
00:14:18
un número bastante grande pero realmente
00:14:20
no es necesario que sea tan grande es
00:14:22
con 200 estará bien
00:14:26
ahora el fp
00:14:29
mostrará una tabla como se ve aquí en la
00:14:32
columna de la derecha mostrará estos
00:14:35
datos quiero que la primera sea el
00:14:38
contador acá pero escrito como ente por
00:14:41
eso dice aquí
00:14:43
1.0 o sea 0 de simán es 0 cifras
00:14:47
decimales
00:14:48
cuando uno escribe por ciento él sabe
00:14:51
que va a escribir una variable y cuando
00:14:54
pone f que va a ser en punto flotante
00:14:56
así que entre por ciento y f debes decir
00:14:59
cómo va a ser el formato de la variable
00:15:04
el enlace a este comando para dar en la
00:15:09
tabulación
00:15:11
aquí escribir los paréntesis nuevamente
00:15:14
por ciento en el número que voy a
00:15:17
escribir aquí tiene tres cifras
00:15:19
decimales
00:15:21
y es un número en punto flotante lo
00:15:23
mismo pasa con la segunda componente
00:15:25
noten que hay una diferencia acá en la
00:15:29
última boya voy a ocultar esta parte
00:15:33
para poder hablar de esta línea por
00:15:36
completo
00:15:38
aquí está la primera variable que
00:15:40
variable aquí la primera que aparezca en
00:15:43
esta línea
00:15:45
la segunda variable que va aquí después
00:15:48
del paréntesis es x sur
00:15:51
y así sucesivamente
00:15:52
recuerden que la variable tipo no es un
00:15:56
número es una variable alfa numérica
00:15:58
aquí es n y la otra opción es g que uno
00:16:03
dice s que el gradiente ok
00:16:07
entonces él va a escribir en la última
00:16:09
columna para mostrar que es
00:16:11
una variable alfa numérica escribimos
00:16:14
por ciento ese 1% f como pasa con los
00:16:18
números de punto flotante sino por
00:16:21
ciento s
00:16:23
así que aquí va la variable que vamos a
00:16:26
ejecutar
00:16:29
ahora recuerden que la matriz diana es
00:16:32
una matriz simétrica para que el método
00:16:35
de newton converge la matriz es jana
00:16:38
debe ser definida positiva simétrica
00:16:41
obviamente y definida positiva eso no
00:16:45
siempre pasa como hablamos antes hay dos
00:16:48
problemas al resolver un sistema de
00:16:50
ecuaciones que la matriz no sea
00:16:53
invertirle o que sea invertible pero el
00:16:55
número de condición sea muy mal
00:16:58
para resolverlo primero para resolver
00:17:01
que sea que se mejore que la matriz que
00:17:04
es simétrica y definida positiva he
00:17:08
construido un algoritmo que se llama
00:17:10
mejor este algoritmo está aquí descrito
00:17:16
él recibe la matriz y da como salida la
00:17:19
matriz h
00:17:23
pregunta si es definida positiva este
00:17:26
comando de matlab si p es igual a 0 es
00:17:29
definida positiva si no da igual a cero
00:17:32
entonces
00:17:34
quiere decir que no lo es entonces le
00:17:37
sumamos un múltiplo de la identidad y
00:17:40
eso lo hacemos tantas veces hasta que la
00:17:43
matriz se vuelva definida positiva
00:17:47
incluso si la matriz en la matriz nula
00:17:50
esto algún día
00:17:52
se convertirá en una matriz
00:17:55
simétrica y definida positiva por eso no
00:17:58
tiene un contador para evitar un bucle
00:18:01
infinito
00:18:02
pero la idea es que se altere un poquito
00:18:06
la matriz no mucho para que ella sea
00:18:09
definida positiva
00:18:11
bien esto es lo que también se le conoce
00:18:14
en álgebra lineal numérica como una
00:18:15
perturbación
00:18:17
así que la salida es una matriz que
00:18:21
a lo mejor sea una perturbación de la
00:18:25
matriz que entró y si la matriz que
00:18:29
entró ya es definida positiva
00:18:30
simplemente sale igual
00:18:34
volvamos al algoritmo
00:18:36
entonces aquí ya se proporciona una
00:18:38
matriz h que es una matriz mejorada ya
00:18:43
es simétrica y definida positiva
00:18:46
ahora vamos a sortear el otro problema
00:18:48
si el número condición es muy pequeño
00:18:53
este ere como no es el número
00:18:55
condiciones el recibo como se llama
00:18:58
recíproco el número de condición
00:19:01
recíproco entre más cercano sea 0 la
00:19:05
matriz es más inestable es mal
00:19:08
condicional
00:19:10
así que si eso ocurre entonces la
00:19:13
dirección que vamos a usar será la
00:19:14
dirección de menos el gradiente y
00:19:17
marcará
00:19:19
esa esa integración con que para saber
00:19:23
qué uso la dirección del gradiente
00:19:26
en caso contrario resolvemos el sistema
00:19:29
menos h
00:19:32
slash de x esta rayita no es una
00:19:36
división esto resuelve el sistema
00:19:40
h
00:19:42
de igual al menos de equis
00:19:45
si voy a escribirlo aquí
00:19:48
vamos a escribir aquí cómo sería para
00:19:51
entenderlo mejor si yo tengo el problema
00:19:53
a x igual a b entonces uno debería
00:19:58
escribir x igual
00:20:01
x igual a a
00:20:05
islas beck
00:20:08
si no debe entenderse eso ese está
00:20:11
incorporado en matlab usa factorización
00:20:14
iu lv eliminación de oceana y resuelve
00:20:17
ese sistema
00:20:19
en caso de que se use esta dirección
00:20:21
marcará line
00:20:24
después se actualizan los valores steele
00:20:27
que está aquí es búsqueda lineal la
00:20:30
búsqueda lineal
00:20:32
recuerden que lo que hace es encontrar
00:20:35
el tamaño de paso adecuado vamos a ver
00:20:38
como está programado
00:20:43
como dato de entrada el punto ese punto
00:20:46
no está cambiando lo que es también lo
00:20:48
que va a salir aquí es el es solamente
00:20:51
el tamaño del paso entonces ingreso el
00:20:53
punto la dirección obtenida en la el
00:20:59
valor de la función de f y el valor del
00:21:01
gradiente de f
00:21:03
entonces aquí aparece como tamaño de
00:21:06
paso inicial el 1 los valores alfa que
00:21:09
es el de la condición de armijo beta la
00:21:12
condición de coste y aquí aparece en
00:21:15
uruguay la negación de las dos cosas que
00:21:18
deben pasar
00:21:20
y aquí también tiene un c este para
00:21:23
evitar un ciclo infinito
00:21:25
empieza en 1 y termine en siempre si se
00:21:29
cumple la condición del mismo para sale
00:21:32
inmediatamente sino el tamaño de paso se
00:21:36
multiplica por un medio o sea se hace
00:21:38
contracción de paso
00:21:41
lo mismo pasa si está de acá
00:21:44
deja de cumplirse
00:21:48
bueno deben dejar de cumplirse la tos
00:21:50
para que para que pueda
00:21:55
y salir de ahí
00:21:57
volvamos al método
00:22:00
se puede obtener el tamaño del paso
00:22:02
actualizamos el x sumando x le sumamos
00:22:06
el deporte
00:22:08
nuevamente calculamos efe calculamos y
00:22:11
actualizamos acá
00:22:13
el ciclo se repite y nos mostrará nos
00:22:17
dará a esta pregunta de nuevo y lo hará
00:22:20
hasta que encuentre la respuesta o
00:22:22
supere el número de interacciones
00:22:24
hay una tercera opción
00:22:28
en la dires el punto inicial que hayamos
00:22:31
escogido no encuentre una dirección en
00:22:37
un punto estacionaria entonces empieza a
00:22:40
bajar y suponiendo que en esa dirección
00:22:42
la función no tiene ínfimo si podría ser
00:22:46
una función que no tenga el ínfimo sino
00:22:49
que defienda en alguna dirección a
00:22:51
infinito en ese caso el algoritmo se va
00:22:55
a detener porque los números ya no son
00:22:57
los valores ya no son números son
00:23:00
cantidades exageradas el algoritmo se va
00:23:03
a detener o sea que él nunca podemos
00:23:06
garantizar de que si hace pocas
00:23:08
iteraciones significa necesariamente
00:23:11
que el algoritmo o que el punto inicial
00:23:15
es correcto vamos a ver esta afirmación
00:23:18
en práctica aquí empezamos en menos 11 y
00:23:22
hizo estos no uso la dirección del
00:23:25
gradiente siempre la de u2
00:23:27
el tamaño del paso ha ido cambiando el
00:23:29
valor inicial fue 1 después fue 1.25
00:23:33
este número puede subir o bajar
00:23:35
dependiendo de lo que se necesite la
00:23:38
tercera columna es el gradiente y ya en
00:23:42
la última es pues el valor que está
00:23:45
tomando como dijimos que el gradiente
00:23:47
fue en hacia la menos 3 aquí ya se
00:23:49
satisface
00:23:51
el último valor es el valor de la
00:23:54
función
00:23:56
si cambiamos el punto inicial vamos a
00:23:58
cambiarlo
00:24:00
vamos a poner 1 1 1
00:24:04
veamos al ejecutar miren que hace siete
00:24:07
iteraciones pero en la séptima iteración
00:24:11
los números son tan grandes
00:24:14
ya no puede que hacer el cambio nn
00:24:18
quiere decir nada a number no son
00:24:22
números entonces el algoritmo se detiene
00:24:25
y no está no encontró nada esto por qué
00:24:28
ocurre esto
00:24:29
ocurre cada vez que la función en por
00:24:35
alguna razón o por la misma definición
00:24:37
de la función hay una dirección en la
00:24:40
que la función tiende a menos infinito
00:24:43
un lado de la función si tal vez por
00:24:46
ejemplo como pasa en la función cúbica
00:24:49
si viajas a la izquierda y empiezas a
00:24:52
buscar un lado más abajo pues
00:24:55
seguramente siempre vas a encontrar un
00:24:57
punto más abajo y del algoritmo no va a
00:25:00
funcionar
00:25:02
si entonces este es la programación del
00:25:04
método delito
00:25:08
qué le parece si ahora hacemos un
00:25:10
ejemplo
00:25:11
tomemos la función que se implementó
00:25:15
esta función
00:25:17
[Música]
00:25:19
es
00:25:22
x al cuadrado más
00:25:25
x por 3 - x a la 2
00:25:29
como ven no es una función cuadrática
00:25:32
porque la si fuera cuadrática la re
00:25:34
superior
00:25:39
en este caso el gradiente nos da este
00:25:41
vector columna
00:25:46
y la matriz es jana
00:25:49
la siguiente matriz simétrica
00:25:57
vamos a ver cómo queda esta
00:25:59
implementación vamos a ver de verdad
00:26:02
vamos a probar el problema de bien esta
00:26:06
es la función es x 1 x 1 x menos todo
00:26:14
esto al cuadrado más y por abro
00:26:19
paréntesis 3 x x a la 2
00:26:22
este es efe noten que aquí arriba no
00:26:25
peor que escribir x etc
00:26:29
solamente x y entonces al definir lo que
00:26:32
se sabe cuánta variable tiene
00:26:35
el con el gradiente está la función
00:26:37
gradiente este punto de coma en un salto
00:26:40
de línea en el punto y coma que aparece
00:26:42
aquí así que es un vector columna si
00:26:45
también el valor de entrada en x y acá
00:26:48
es que se sabe cuántas variables tienen
00:26:51
la matriz es jana aquí este es el
00:26:54
gradiente la función la matriz diana es
00:26:57
muy cortita
00:26:59
2 - 2 y coma - 2 - 2x es simétrica y acá
00:27:06
queda duros
00:27:08
bueno ahora sí probar al probarlo
00:27:11
le damos a ejecutar
00:27:13
y no sale ocho pasos
00:27:17
como ven todos los pasos que se hicieron
00:27:19
fueron pasos de youtube
00:27:21
la solución es la que aparece aquí al
00:27:24
final
00:27:25
el tamaño del paso no siempre es uno
00:27:29
sino que fue 05 en la mayoría de los
00:27:31
casos y en la tercera columna
00:27:36
y nos muestra la norma del gradiente
00:27:39
la cuarta columna es el valor de la
00:27:41
función
00:27:43
bueno es normal que nos preguntemos
00:27:44
bueno es mejor el método del minuto
00:27:46
momento del gradiente
00:27:48
bueno la respuesta es que en la mayoría
00:27:51
de los casos es mejor el método de
00:27:53
newton
00:27:55
pero hay funciones que es que son deben
00:27:59
de cierta forma que podría ser que
00:28:02
tengan las mismas interacciones en ambos
00:28:05
métodos o incluso que podría ser al
00:28:09
revés
00:28:10
vamos a cambiar aquí un poquito y vamos
00:28:13
a obligar a que siempre use el método
00:28:17
del gradiente entonces vamos a poner
00:28:20
esto aquí y vamos a comentar esto para
00:28:23
que solamente haga el método de newton
00:28:27
le vamos a guardar lo recuerde que hubo
00:28:30
ocho iteraciones y que este es el punto
00:28:34
solución vamos a iniciar en el mismo
00:28:36
punto compilar nos da 12 interacciones
00:28:40
el dobles de declaraciones
00:28:43
y aquí dicen yuto porque acá
00:28:47
y dice n pero ya saben que fue solamente
00:28:49
una prueba
00:28:52
bueno realmente no es el doble todo se
00:28:54
instalaciones se incrementó
00:28:57
en cuatro interacciones más se obtuvo la
00:29:01
misma solución también cambian los
00:29:04
tamaños de paso los tamaños de pasas el
00:29:07
de pasos son específicos para cada
00:29:09
interacción y para cada mes así que
00:29:12
eso no se compara no es comparable
00:29:15
entonces vamos a dejarlo como el cama
00:29:21
y con eso hemos probado que para este
00:29:24
ejemplo el método de newton es más
00:29:28
rápido que el método del gradiente
00:29:33
vamos a ver estos resultados con más
00:29:35
detalles
00:29:37
aquí tenemos la tabla que se obtuvo
00:29:40
en matlab
00:29:43
note que en ocho interacciones empezando
00:29:47
en menos uno menos uno se obtuvo este
00:29:50
punto que es un punto de esta ciudad
00:29:54
bueno aquí en la norma del gradiente de
00:29:57
0.02 es casi cero
00:30:01
seguramente si usamos más decimales y
00:30:04
llegamos a tener un noveno paso vamos a
00:30:06
obtener
00:30:07
más precisión pero ya tenemos un punto
00:30:10
en donde vamos a encontrar un vídeo
00:30:14
también pueden ver que el tamaño de
00:30:17
lambda
00:30:19
puede ser 105 y para cada paso que se
00:30:24
actualiza dependiendo de lo que necesite
00:30:28
bueno ahora porque para algunos casos
00:30:31
porque para algunos valores
00:30:33
y nos dio como esperábamos o sea nos
00:30:36
daba un números demasiado grandes o muy
00:30:40
pequeños muy negativos vamos a ver
00:30:56
miremos esta gráfica
00:30:59
vamos a tratar de ver la superficie
00:31:04
estamos estudiando esta es la función
00:31:07
efe
00:31:08
noten hay tres puntos especiales dos
00:31:11
azules y uno amarillo pero que lo estén
00:31:14
viendo
00:31:16
los azules son o máximos o puntos de
00:31:19
silla
00:31:21
el punto que estamos buscando es el
00:31:23
punto amarillo
00:31:24
observen que si estamos cerca del punto
00:31:28
azul
00:31:29
podemos vernos por un precipicio que es
00:31:32
lo que se ve allí así que si estamos
00:31:34
cerca y buscando una dirección de
00:31:37
descenso nos va a enviar hacia menos
00:31:40
infinito
00:31:43
ese es el peligro de no saber dónde
00:31:46
vamos a escoger el punto inicial
00:31:49
esa es la pregunta una pregunta una
00:31:51
buena pregunta cómo escoger el punto
00:31:53
inicial
00:31:54
realmente eso no se sabe cada caso es
00:31:57
diferente
00:31:59
bueno este es el punto que tenemos que
00:32:01
ubicar
00:32:02
el punto amarillo en donde se encuentra
00:32:04
el mínimo de esta función
00:32:09
después de tener ese punto vamos a
00:32:12
tratar de ubicar los puntos de la
00:32:14
sucesión que hemos ido encontrando
00:32:17
con el algoritmo de newton para ver cómo
00:32:20
se llegó a ese a ese valor veamos desde
00:32:25
el punto inicial - 11 y noten cómo los
00:32:28
puntos rojos van llegando a la solución
00:32:30
del problema
00:32:33
esto es lo que hace el método del
00:32:36
si escogemos un punto inicial adecuado
00:32:43
hay un teorema muy importante que nos
00:32:46
dice los sirvientes
00:32:57
sea el de rn en r
00:33:02
y esta es una función
00:33:04
de ese 2
00:33:14
y
00:33:15
bueno si la matriz es ya la elipsis
00:33:18
continua como funciona miren eso la
00:33:21
matriz la función cristiana como función
00:33:24
elipsis continua
00:33:27
escogemos un punto inicial
00:33:30
si x estrella es un minimizador local de
00:33:34
efe y además en las en la solución la
00:33:38
matriz de cidades definida positiva
00:33:42
y entonces existe un épsilon por lo
00:33:44
tanto existe una vecindad tal que si x0
00:33:48
y equis estrella están suficientemente
00:33:51
cerca
00:33:53
y tomando holanda subcampeona igual que
00:33:56
uno
00:33:57
la sucesión
00:33:58
xk generada por el algoritmo de youtube
00:34:02
satisface los siguientes
00:34:05
primero
00:34:09
la matriz cian a en todos los puntos de
00:34:12
la sucesión son debilidades positivas
00:34:16
claro esa parte nos interesa mucho si
00:34:19
estamos cerca de la solución
00:34:21
entonces no vamos a tener el problema de
00:34:25
necesitar convertir la matriz cristiana
00:34:28
en definida positiva
00:34:31
segundo
00:34:36
la sucesión converge la sucesión
00:34:39
generada por el algoritmo de luto con
00:34:42
vez
00:34:44
y tercero
00:34:49
existe un c positivo tal que el error
00:34:54
aquí hace una comparación entre errores
00:34:57
sucesivos
00:34:59
pero en esencia lo que dice es que si la
00:35:03
matriz es jana es
00:35:07
discontinua el algoritmo de newton
00:35:10
converge de manera cuadrática
00:35:14
claro eso mucho más rápido que la
00:35:16
convergencia que obtuvimos para el
00:35:19
método el gradiente que era solamente
00:35:21
lineal se puede obtener convergencia
00:35:25
cuadrática bajo la hipótesis de que la
00:35:29
matriz es jana sea lipshitz contigo
00:35:33
qué interesante verdad bueno con esto
00:35:36
hemos terminado de hablar sobre el
00:35:39
método de newton
00:35:42
sin embargo
00:35:45
puede que surja una inquietud y está
00:35:48
relacionada con el método de newton para
00:35:51
resolver sistemas de ecuaciones
00:35:55
qué les parece si hacemos una
00:35:57
comparación para ver cuál es la
00:35:59
diferencia entre el método del youtube
00:36:02
para minimización
00:36:07
el método de newton para resolver
00:36:10
sistemas de ecuaciones
00:36:14
primer asunto el problema que se
00:36:16
resuelve es diferente
00:36:18
para minimizar
00:36:19
efe de rn jr y hay que minimizar esa
00:36:24
función
00:36:26
en el sistema de ecuaciones se tiene una
00:36:29
función de rn en rn y lo que vamos a
00:36:33
buscar es en donde esas esa función de
00:36:37
hacer
00:36:41
cada paso de newton para cada problema
00:36:44
se puede ver así para el caso de
00:36:47
minimización
00:36:49
la matriz cian es la que la matriz del
00:36:53
sistema mientras que en el sistema de
00:36:57
ecuaciones el jefe prima conocida como
00:37:01
la matriz hakobyan a de f
00:37:03
también hay que resolver un sistema pero
00:37:06
los problemas a afrontar son un poco
00:37:09
diferentes
00:37:10
en el caso de la matriz diana queremos
00:37:13
que sea
00:37:14
simétrica y definida positiva
00:37:18
en el caso del jacob ya no nos interesa
00:37:21
únicamente que la matriz sea no singular
00:37:25
con eso será suficiente
00:37:29
además
00:37:32
la manera de actualizar el integrante
00:37:35
también un poco diferente
00:37:37
para minimización se encuentra blanda
00:37:43
con búsqueda lineal es decir con la
00:37:46
condición de armijo la condición de
00:37:48
goldstein u otras equivalentes
00:37:51
pero como acá no hay una función
00:37:54
potencial que como efe entonces
00:37:59
no podríamos encontrar un tamaño de paso
00:38:02
a menos que el sistema de ecuaciones se
00:38:06
convierta por medio de una función de
00:38:08
mérito en un problema de minimización
00:38:11
entonces aquí simplemente landa siempre
00:38:14
va a ser
00:38:17
bien espero que estas aclaraciones les
00:38:19
hayan servido y que les haya quedado
00:38:21
claro de cómo funciona el método de
00:38:24
newton para minimización
00:38:28
hasta la próxima clase
00:38:29
[Música]
