00:00:02
cómo resolver un problema de
00:00:04
optimización sin restricciones
00:00:08
bueno primero veamos en qué consiste
00:00:12
para eso necesitamos una función f que
00:00:16
va de rn en r esa función debe ser
00:00:20
continuamente diferencial
00:00:23
resolver el problema de optimización es
00:00:26
sin restricciones consiste en resolver
00:00:30
el siguiente problema
00:00:33
minimiza fx con x en el rey
00:00:38
como pueden ver x o el lugar en donde
00:00:42
vamos a buscar la solución
00:00:45
debe estar en el dominio de la función
00:00:48
pero no se le somete a ninguna otra
00:00:51
condición no se le imponen otra
00:00:55
restricción por eso se llama sin
00:00:58
restricciones o un problema de
00:01:01
minimización irrestricto
00:01:04
quiere saber cómo se resuelve
00:01:07
bueno ya te lo diré
00:01:10
[Música]
00:01:27
considere este problema en tres
00:01:29
dimensiones
00:01:34
bueno allí vemos una superficie el
00:01:37
dominio es todo r2 que es el piso que
00:01:42
vemos allí
00:01:44
en el piso vemos unas curvas esas son
00:01:48
las curvas de nivel de la superficie que
00:01:51
vemos en la parte superior
00:01:55
claramente el punto blanco en el centro
00:01:58
del dominio o del piso que vemos es la
00:02:03
solución o el minimizador de este
00:02:06
problema
00:02:08
sin embargo en la práctica no sabemos
00:02:11
cuál es el minimizador
00:02:14
así que la idea de este algoritmo es a
00:02:20
partir de un punto inicial
00:02:22
un punto que damos tratar de acercarnos
00:02:27
a la solución
00:02:29
en la gráfica podemos ver un punto
00:02:31
amarillo como a partir de ese punto
00:02:35
buscar el minimizador moviéndonos en el
00:02:40
dominio de la función
00:02:43
de eso se trata el algoritmo de búsqueda
00:02:47
direccional
00:02:48
encontrar una dirección para sumarse al
00:02:52
punto y cambiar de lugar
00:02:56
tratemos de ver esto en el gráfico
00:03:01
allí este negocio el punto y una
00:03:03
dirección eso nos mueve el punto a otro
00:03:06
sitio
00:03:08
este sitio está más cerca del
00:03:10
minimizador que el punto amarillo
00:03:12
anterior
00:03:14
a partir de ese punto encuentro una
00:03:17
dirección
00:03:19
que me acerque más
00:03:22
se lo sumo esa dirección al punto
00:03:25
encontrando un siguiente punto amarillo
00:03:27
y así sucesivamente en cada paso me
00:03:32
acerco más al minimizador y aún
00:03:35
minimizador por si hay más de la función
00:03:40
tratemos la siguiente definición
00:03:43
dirección de descenso
00:03:47
una dirección es un vector pero debe
00:03:51
cumplir las siguientes condiciones
00:03:55
un vector de nn es una dirección de
00:04:00
descenso de f a partir de x
00:04:05
si la derivada dirección al df en la
00:04:10
dirección de x es negativa
00:04:14
es decir
00:04:16
su derivada direccional
00:04:18
como vemos allí en símbolos negativos
00:04:21
para el caso donde la función es
00:04:24
diferenciables podemos establecer esta
00:04:27
dirección de descenso y esta derivada
00:04:30
direccional utilizando el gradiente es
00:04:34
decir si es diferenciable podemos decir
00:04:39
que la dirección de descenso
00:04:42
es una dirección que cumple esta
00:04:45
condición
00:04:47
el gradiente transpuesto por d es
00:04:51
negativo
00:04:54
consideremos una dirección de descenso
00:04:57
como ejemplo
00:04:59
de igual al menos el gradiente
00:05:05
veamos lo siguiente cómo saber si es una
00:05:08
dirección de descenso
00:05:10
pues debemos hacer el producto gradiente
00:05:13
de efe por la dirección
00:05:17
en este caso nos da lo que vemos allí y
00:05:21
esto es menos la norma del gradiente de
00:05:25
f al cuadrado
00:05:27
por supuesto todo esto es negativo
00:05:34
o menor o igual que 0
00:05:36
la mayoría de los casos
00:05:40
por lo tanto
00:05:42
menos gradiente de efe es una dirección
00:05:46
de descenso
00:05:49
esta dirección tiene un nombre especial
00:05:53
y es llamada la dirección de máximo
00:05:58
descenso
00:06:00
- el gradiente de efe es la dirección de
00:06:05
máximo descenso
00:06:07
pero no quiere decir que es la única
00:06:13
como podemos caracterizar una dirección
00:06:16
de descenso
00:06:18
bueno lo primero que sabemos es que el
00:06:22
producto punto o producto interior entre
00:06:26
el gradiente en el punto y la dirección
00:06:29
debe dar negativo este producto punto
00:06:33
producto interior se puede escribir como
00:06:37
el producto de las normas de cada uno de
00:06:40
los vectores por el coseno del ángulo
00:06:42
entre dichos vectores
00:06:45
así que podemos describirlo como vemos
00:06:48
en en la imagen
00:06:51
eso quiere decir que el coseno del
00:06:54
ángulo debe ser negativo
00:06:58
en qué ángulos el coche no da negativo
00:07:01
bueno en el segundo y tercer cuadrante
00:07:05
así que el ángulo que se forma entre el
00:07:10
gradiente y la dirección de descenso
00:07:13
tiene que ser mayor que mi medios o
00:07:17
mayor que 90 y menor que tres y medio o
00:07:21
sea menor que 270 grados
00:07:26
mediante un diagrama quiero ilustrar que
00:07:31
es una dirección de descenso considere
00:07:35
esta curva como si fuera una curva de
00:07:37
nivel y el punto amarillo un punto x en
00:07:42
donde vamos a considerar buscar una
00:07:45
dirección de descenso
00:07:47
trazamos la recta tan cliente
00:07:51
ahora el vector normal a esa recta
00:07:56
tangente y que están es perpendicular o
00:08:01
normal
00:08:03
la curva del nivel es el vector
00:08:05
gradiente
00:08:06
como lo vemos allí para encontrar una
00:08:11
dirección de descenso
00:08:14
se requiere que ese vector forme un
00:08:17
ángulo mayor de 90 grados como el
00:08:21
gradiente para que el producto interior
00:08:25
sea negativo que el vector nos puede
00:08:29
servir
00:08:30
cualquiera de los vectores en estas
00:08:34
direcciones que vemos en movimiento
00:08:36
pueden servir como dirección de descenso
00:08:39
en particular
00:08:41
- es gradiente es una dirección de
00:08:45
descenso pero pueden ver que hay
00:08:47
infinitas direcciones de descenso así
00:08:51
que buscar un método que de una
00:08:54
dirección de descenso sí es muy
00:08:56
importante
00:09:00
en esta proposición veremos como la
00:09:04
dirección del descenso nos ayuda a
00:09:07
encontrar puntos más cercanos al
00:09:11
minimizador
00:09:14
de qué forma veamos consideremos una
00:09:18
función
00:09:20
de rn en r y consideremos que la función
00:09:25
y de clase c1 o sea que tiene es que es
00:09:27
continuamente diferenciable si además
00:09:31
tenemos una dirección de descenso
00:09:34
es decir efe el gradiente df atrás
00:09:38
puesto por d es negativo entonces existe
00:09:43
un valor de holanda positivo tal que fx
00:09:49
más lambda de es menor que fx
00:09:54
qué significa esta proposición que yo
00:09:57
tengo un valor x un punto x y al sumarle
00:10:02
lambda de obtengo otro punto que al
00:10:05
evaluar la función me da más pequeño sí
00:10:09
estoy buscando el minimizador ese es la
00:10:13
dirección correcta el camino correcto
00:10:16
en esta proposición no se dice cómo
00:10:20
escoger a lando aunque la demostración
00:10:23
se dan indicios de cómo puede ser veamos
00:10:28
la demostración
00:10:31
comencemos con la demostración
00:10:35
vamos a suponer
00:10:37
que tenemos una dirección de descenso
00:10:41
esto es existe un de rn tal que el
00:10:45
gradiente de fx traspuesto por ese te
00:10:50
pueda negativo
00:10:53
a partir de allí definamos la función
00:10:56
fui
00:10:59
fidel anda es/efe de x más blanda porte
00:11:09
como esta ecuación la usaremos más
00:11:11
adelante la voy a escribir en la columna
00:11:15
de la derecha
00:11:20
bueno de manera trivial podemos
00:11:23
determinar cuánto da fi de cero
00:11:27
efectivamente es fx
00:11:33
este valor también lo vamos a utilizar
00:11:35
más adelante
00:11:38
volviendo a fides lambda calculemos la
00:11:42
derivada utilizando la regla de la
00:11:44
cadena
00:11:46
mi prima de landa es el gradiente de fx
00:11:50
más blanda de
00:11:53
tras puesto orden
00:11:57
bueno podemos calcular de manera muy
00:12:00
sencilla cuánto da fe de 0
00:12:05
fidel 0 es gradiente de fx propuesto por
00:12:10
d
00:12:11
por la hipótesis que tenemos como de es
00:12:14
una dirección de descenso
00:12:17
este valor es negativo
00:12:19
por lo tanto la derivada de fi en 0 es
00:12:24
negativo
00:12:26
este es otro valor que estaremos
00:12:28
utilizando
00:12:34
usando la definición de derivada con
00:12:38
límites podemos decir lo siguiente
00:12:47
la derivada de fide x es igual al límite
00:12:51
cuando holanda tiende a cero de fidel
00:12:54
anda menos fi de 0 sobre helado
00:12:59
por supuesto aquí irlanda es un valor
00:13:01
pequeño
00:13:04
como el límite existe dado que la
00:13:07
derivada existe los limites laterales
00:13:09
también existen así que puedo trabajar
00:13:12
únicamente con la derivada por la
00:13:16
derecha
00:13:19
es decir esto da lo mismo que límite
00:13:24
cuando holanda tiende a cero por la
00:13:26
derecha o sea cuando holanda es mayor
00:13:29
que cero
00:13:32
si analizamos este consciente tanto el
00:13:35
numerador como el denominador y ya
00:13:38
sabemos que el denominador es positivo
00:13:41
podemos decir lo siguiente
00:13:45
en el límite
00:13:47
si prima de landa tiene el mismo signo
00:13:51
que fidel anda menos puede ser
00:13:57
porque el denominador es positivo
00:14:00
o sea que el signo podemos afirmar lo
00:14:04
siguiente con respecto a él para lambda
00:14:06
pequeño
00:14:13
mi prima demanda y fidel anda menos fi
00:14:16
de 0 son negativos
00:14:19
bueno es el segundo el que va a terminar
00:14:22
la demostración como negativo
00:14:27
decimos lo siguiente
00:14:30
y ahora reemplazando por las ecuaciones
00:14:33
que tenemos a la derecha
00:14:37
tenemos que
00:14:41
lo que queríamos demostrar efe de x más
00:14:45
blanda d es menor que fx
00:14:52
bueno ya tenemos la garantía de que en
00:14:55
una dirección
00:14:58
vamos a descender vamos a encontrar un
00:15:02
punto en donde encontraremos estaremos
00:15:06
más cerca del minimizado
00:15:09
cuál es el algoritmo básico de este
00:15:12
método
00:15:14
vamos a eso el algoritmo básico en la
00:15:17
interacción acá acá va a ir desde cero
00:15:20
no hasta infinito porque las iteraciones
00:15:24
terminarán antes de llegar a el número
00:15:29
máximo de interacciones que nosotros
00:15:31
mismos hemos puesto como restricciones
00:15:34
así que vamos a ver el corazón de este
00:15:38
algoritmo la parte central cómo se
00:15:41
actualizan los puntos
00:15:43
primer paso
00:15:46
dado el punto x k es decir lo tenemos
00:15:50
porque es x 0 y lo dieron cuando empezó
00:15:55
el algoritmo o es el resultado del paso
00:15:58
anterior de la integración anterior
00:16:01
camino sur
00:16:03
paso 2
00:16:05
calculamos la dirección de descenso de
00:16:08
su campo
00:16:09
dependiendo del método que estemos
00:16:11
usando hasta ahora en lo que hemos visto
00:16:14
las de es una dirección de descenso que
00:16:19
después veremos cómo elegirla
00:16:22
paso 3
00:16:25
asignamos x1x k más blanda de acá
00:16:32
para algún blanda que haga aceptable a x
00:16:35
cam azul
00:16:37
es decir no sirve todo el andar
00:16:41
algo nos indicó que tenía que ser un
00:16:44
número pequeño sin embargo
00:16:48
queremos que avance un poco más rápido y
00:16:51
no sea tan lento cuáles son los valores
00:16:54
aceptables de landa es una pregunta que
00:16:58
tenemos que resolver
00:17:01
resolvamos esta pregunta importa la
00:17:04
selección de la dirección de descenso
00:17:10
a continuación vamos a responder esta
00:17:12
pregunta con un ejemplo el ejemplo
00:17:16
parece inicialmente que está bien
00:17:19
planteado porque tiene todas las
00:17:21
condiciones pero no se obtiene la
00:17:24
respuesta deseada
00:17:26
veamos cuáles
00:17:29
vamos a considerar la función de igual a
00:17:32
coseno hiperbólico de x
00:17:34
su derivada es igual a 0 hiperbólico de
00:17:38
x
00:17:40
vamos a utilizar la iteración xk más 1
00:17:44
igual a xk más la cndh acá por b y vamos
00:17:48
a comenzar en el punto inicial igualados
00:17:53
usaremos siempre la misma dirección de
00:17:56
descenso de igual a menos 1 irlanda
00:17:59
igual a 2 a la menos cama azul
00:18:04
observen que en efecto de acá es una
00:18:07
dirección de descenso porque al
00:18:10
multiplicar de por de prima dado que x
00:18:15
es mayor que 0 nos va a dar negativo así
00:18:20
que aquí en el que está haciendo las
00:18:22
funciones de gradiente es la derivada
00:18:24
así que d
00:18:26
es una dirección de descenso
00:18:29
vamos a hacer este esta prueba de forma
00:18:33
gráfica
00:18:35
aquí tenemos la función de igual a
00:18:39
coseno hiperbólico de x y vamos a
00:18:42
comenzar en el punto x igual a 2
00:18:46
en la columna de la derecha podremos
00:18:49
observar que los números van decreciendo
00:18:54
en efecto la dirección de descenso me
00:18:58
permite encontrar valores de la función
00:19:01
que sean cada vez menores
00:19:04
y la solución del problema es x igual a
00:19:08
0 porque es donde se minimiza la función
00:19:11
que estamos analizando
00:19:14
pero algo ocurre con este programa o con
00:19:17
la selección de irlanda que no nos
00:19:20
permite llegar al ser
00:19:22
veamos
00:19:27
1.75
00:19:30
1.62 51.56 25 1.53 12 1.51 56 1.50 78
00:19:45
1.50 39 1.50
00:19:50
02 02 algo falsa y no alcanzamos a
00:19:55
llegar al 0
00:19:57
como ven en la columna de la derecha
00:19:59
siempre está decreciendo pero no nos
00:20:03
permite llegar a la solución
00:20:05
incluso parece que el 1.5 se convirtiera
00:20:10
en una barrera de la cual no podemos
00:20:13
salir
00:20:15
qué pasa por qué está ocurriendo esto
00:20:18
bueno tiene que ver con la elección de
00:20:22
de y del tamaño de paso
00:20:25
eso es lo que veremos a continuación
00:20:28
ilustrar la situación con estas gráficas
00:20:31
aquí vemos una superficie
00:20:36
que queremos minimizar es decir
00:20:38
encontrar el punto en donde se alcanza
00:20:42
el mínimo el punto que llamaremos
00:20:44
minimizado
00:20:46
vemos en el piso vemos en el dominio
00:20:50
que tenemos un punto que vamos a ver
00:20:54
supongamos que tenemos un punto y un
00:20:56
punto que no es minimizado y una
00:20:59
dirección de descenso estamos cerca pero
00:21:02
no hemos llegado al minimizado
00:21:06
es posible llevar este problema a una
00:21:08
sola dimensión como lo harían observen
00:21:14
como estamos variando solamente el
00:21:17
usando la misma dirección pero aún
00:21:20
cambiando el tamaño del paso podemos
00:21:23
hacer lo siguiente cortamos el plano
00:21:27
y ahora la intersección de ese plano con
00:21:30
la superficie nos da una curva
00:21:35
esta es la curva que tenemos que
00:21:37
estudiar en una variable y ver cómo
00:21:40
podemos resolver el problema de
00:21:43
minimizarlo en esta diversión
00:21:47
al proceso de buscar el lambda adecuado
00:21:50
le llamaremos búsqueda lineal
00:21:53
existen dos tipos de maneras de hacerlo
00:21:57
una se conoce como búsqueda lineal
00:22:01
exacta y la otra es inexacto hablemos un
00:22:05
poco de la primera
00:22:08
miremos la curva que obtuvimos hace un
00:22:13
momento
00:22:15
encontrar el anda adecuado para este
00:22:18
caso es encontrar en landa en donde se
00:22:21
obtiene el mínimo pero en la curva
00:22:25
obtenida en la dirección de d
00:22:28
bueno es un problema de una sola
00:22:31
dimensión o de dos variables de una
00:22:33
variable en dos dimensiones como vemos
00:22:35
allí
00:22:37
así que debería ser fácil resolverlo
00:22:41
entonces en qué consiste la búsqueda
00:22:44
lineal exacta y qué ejemplo podemos ver
00:22:49
la búsqueda lineal exacta consiste
00:22:53
básicamente en resolver en cada paso
00:22:57
este problema minimizar fidel anda con
00:23:01
la anda en guerra o sea un problema de
00:23:04
una sola variable
00:23:06
este es un problema parecido a los que
00:23:08
se resuelven en cálculos derivar e
00:23:12
igualar a cero y despejar
00:23:14
pero no siempre es tan sencillo
00:23:18
a ese lambda que se encuentra a veces se
00:23:21
le llama el argumento
00:23:24
así que otra forma de escribir lo mismo
00:23:27
es decir el argumento del mínimo de
00:23:30
minimizar fidel anda con la anda jr
00:23:35
ahora teniendo en cuenta esto tendríamos
00:23:39
que resolver un problema donde la
00:23:41
derivada sea igual a 0 o sea el
00:23:44
gradiente traspuesto de imán landa
00:23:46
detrás puesto por d es igual a cero
00:23:51
en general no es un problema tan fácil
00:23:54
de resolver aunque en teoría de una sola
00:23:58
variable
00:24:00
no se acostumbra a utilizar la búsqueda
00:24:03
lineal exacta porque cada problema o
00:24:06
cada iteración hay que resolver un
00:24:08
problema que muchas veces es en sí mismo
00:24:12
un problema interactivo
00:24:15
pero en algunos casos como el que vamos
00:24:17
a poner ahora que no pudimos resolver en
00:24:21
el ejemplo anterior el problema en
00:24:23
cosenos lo vamos a resolver
00:24:27
usando búsqueda lineal exacto aquí
00:24:30
tenemos la función la dirección de
00:24:33
descenso y el punto inicial al evaluar
00:24:36
los puntos del punto 2 obtenemos lo que
00:24:40
nos da y al multiplicar podemos ver
00:24:43
fácilmente de qué
00:24:46
cumplen las hipótesis
00:24:49
veamos ahora teniendo esto
00:24:56
vamos a reemplazar en la derivada los
00:24:59
valores que tenemos x d
00:25:03
pero la derivada del coseno hiperbólico
00:25:05
es seno y perdón
00:25:08
eso nos lleva a la siguiente ecuación
00:25:18
- seno hiperbólico y esto nos lleva a 2
00:25:22
- landa buenas
00:25:25
la única solución que tiene este
00:25:27
problema slam da igual
00:25:30
con landa igualados hubiésemos resuelto
00:25:33
el problema del coseno en un solo paso
00:25:38
por supuesto esto no siempre ocurre ni
00:25:42
tampoco es el camino más recomendable
00:25:46
el otro camino para resolver este
00:25:48
problema es la búsqueda lineal inexacta
00:25:53
o también llamada algoritmo de
00:25:55
contracción de paso
00:25:58
en qué consiste
00:26:00
queremos resolver el problema en cada
00:26:04
paso de encontrar un lambda adecuado
00:26:08
no nos vamos a esforzar por encontrar el
00:26:12
land a dónde se minimiza la curva en una
00:26:15
dimensión como acabamos de hacer en la
00:26:17
búsqueda lineal exacta sino que nos
00:26:20
conformaremos con encontrar un landa que
00:26:24
de una reducción en la función que sea
00:26:27
aceptable
00:26:29
por eso se llama inexacta dado que al
00:26:32
encontrar esa esa solución o ese
00:26:35
minimizador todavía no es el mismo
00:26:37
iniciador de todo el problema
00:26:42
para ir resolverlo por búsqueda lineal
00:26:45
inexacta empezaremos por lo general con
00:26:49
la anda igual a 1 y en cada vez que no
00:26:52
se encuentre un landó adecuado este se
00:26:55
va a encoger se va a contraer
00:26:58
multiplicando los por un número entre 0
00:27:00
y 1 que aquí le llamamos alfa
00:27:04
el primer paso es asignar a lambda el
00:27:08
valor de
00:27:10
el segundo en este ejemplo estoy
00:27:12
poniendo 0.5 pero puede ser cualquier
00:27:15
número entre 0 y 1
00:27:17
después entramos en un ciclo
00:27:20
de mientras donde hay una condición si
00:27:24
la condición no se cumple entonces se
00:27:28
multiplicará al andar por la constante
00:27:31
en este caso 05 encogiendo el tamaño de
00:27:35
la na
00:27:37
las condiciones que aparecen aquí las
00:27:39
analizaremos a continuación después de
00:27:43
este algoritmo no todas sino las más
00:27:46
importantes y las más utilizadas
00:27:50
pueden ser varias condiciones que se
00:27:52
usen en este mismo algoritmo
00:27:55
ahora después de encontrar después de
00:28:00
asignar esto se repetirá este ciclo
00:28:03
hasta que lo arroje un lambda aceptable
00:28:07
o una lambda que satisface que satisfaga
00:28:10
las condiciones o la condición que
00:28:13
dijese en el número 3
00:28:16
pero es posible que eso llegue a un
00:28:19
ciclo infinito pues no porque en la
00:28:23
proposición anterior encontramos que
00:28:26
existía un landa en donde
00:28:30
hay una reducción aceptable
00:28:34
por eso sabemos que cuando la banda es
00:28:37
muy pequeño
00:28:39
por lo general sale un valor y no entra
00:28:43
un ciclo infinito
00:28:45
bueno veamos cómo se hace ahora voy a
00:28:48
ilustrar cómo funciona este algoritmo de
00:28:52
contracción de paso mediante un
00:28:56
la animación que veremos aquí en dos
00:28:59
dimensiones
00:29:01
a ver consideremos que tenemos un
00:29:04
problema una función a minimizar y estas
00:29:07
curvas que vemos aquí son las curvas de
00:29:10
nivel
00:29:12
desde aparecen solamente tres valores de
00:29:15
las curvas de nivel pero como la función
00:29:18
es continua y es diferenciable
00:29:21
seguramente vamos a encontrar todo tipo
00:29:24
de valores entre esos valores dados
00:29:28
ahora pensemos en lo siguiente tenemos
00:29:31
un punto inicial o un punto de fiscal
00:29:33
bueno esa es la solución a la que
00:29:36
debemos llegar se encuentra en el punto
00:29:38
más bajo más bajo de la superficie
00:29:44
supongamos que tenemos en este punto
00:29:46
inicial y tenemos también una dirección
00:29:49
esa dirección me genera una semi recta
00:29:55
por donde pasa por xk en la dirección de
00:29:59
d
00:30:00
cuando holanda es igual a 1 nos lleva a
00:30:03
al otro punto que vemos allí
00:30:09
es notorio que si ha bajado porque ahora
00:30:12
está en otra curva de nivel
00:30:15
pero paso por mejores sitios y no se
00:30:19
quedó tal vez
00:30:22
hubiese quedado un poco más en el centro
00:30:25
y si hubiese descendido más
00:30:29
si en este caso estoy tomando blanda
00:30:32
igual a 1 como pueden ver arriba en la
00:30:35
ecuación
00:30:36
qué pasa si cambiamos a ese land por
00:30:39
ejemplo que es el anda mal de a 0.1
00:30:44
disminuye la función pero no disminuye
00:30:48
suficiente
00:30:50
qué pasa si la banda es mayor por
00:30:53
ejemplo 0.3
00:30:57
pueden ver que ha disminuido en el valor
00:31:00
de la función
00:31:02
esta hora entre 2 y 3
00:31:06
pero si vale 05
00:31:09
tal vez pueda bajar más veamos
00:31:15
llegó a la curva de nivel z igualados o
00:31:18
menos
00:31:20
por usar el tamaño de paso igual a 07
00:31:25
entonces como pueden ver lo que hacemos
00:31:27
es empezamos en uno sin uno no baja
00:31:30
suficiente lo reducimos a 05 sino a la
00:31:35
mitad de ese 25 y así sucesivamente
00:31:37
hasta que el tamaño de paso sea
00:31:41
aceptable
00:31:42
a continuación voy a describir dos de
00:31:45
las condiciones de la búsqueda lineal
00:31:47
que son más utilizadas
00:31:50
la primera de ellas se llama la
00:31:53
condición de armijo
00:31:56
y también es conocida como la condición
00:31:58
de descenso suficiente representada en
00:32:03
1966 por la real mijo y publicada en
00:32:08
pacific journal of mathematics
00:32:11
así que desde entonces ya hace parte de
00:32:15
la optimización este artículo
00:32:19
en este él presenta una forma de hacer
00:32:22
que cada descenso o cada paso se permita
00:32:28
que bajen más que solamente un descenso
00:32:32
simple
00:32:34
aclaremos esto primero consideremos un
00:32:38
valor de alfa entre 0 y 1
00:32:42
muy pequeño por lo general suele usarse
00:32:45
alfa como 10 al menos 4 un número
00:32:49
pequeño
00:32:51
el descenso simple se refiere a la
00:32:54
siguiente desigualdad
00:32:56
qué quiere decir que el paso siguiente
00:33:00
de una imagen más pequeña que el paso
00:33:05
actual
00:33:07
ahora cuál es el descenso suficiente
00:33:11
bueno
00:33:12
larreal mi hijo le agrego algo más al
00:33:16
término de la derecha
00:33:23
le agrego esta otra parte que incluye el
00:33:27
gradiente traspuesto de d
00:33:31
y veamos en qué le afecta
00:33:34
la primera parte es la imagen de la
00:33:37
iteración actual o la que estamos
00:33:40
buscando porque recuerden que en este
00:33:42
proceso estamos buscando en landa
00:33:44
apropiados
00:33:47
ahora la primera parte del lado derecho
00:33:49
se refiere al descenso simple
00:33:55
que se le agrega
00:33:58
la cantidad que vemos allí es negativa
00:34:01
porque como de es una dirección de
00:34:04
descenso el gradiente traspuesto por d
00:34:07
es negativo
00:34:09
x lambda que es positivo da negativo
00:34:13
x alfa sigue siendo negativo es decir en
00:34:18
esta condición se le está exigiendo a
00:34:21
que el paso siguiente sea no solamente
00:34:24
menor afe fx sino que sea mucho más
00:34:29
pequeño pero al mismo tiempo que sea
00:34:32
proporcional al grado ente de la de la
00:34:34
función en el punto actual de esa manera
00:34:38
siempre será posible encontrar un valor
00:34:42
que satisfaga esta condición
00:34:45
cuál es la interpretación geométrica de
00:34:48
estas condiciones veamos
00:34:51
realicemos con más detalle la condición
00:34:54
de mi hijo
00:34:56
vamos a escribirla en el formato de fit
00:34:59
ya lo hemos usado antes
00:35:02
qué significa esta línea que aparece
00:35:04
aquí en color blanco
00:35:08
fidel anda es una curva
00:35:12
ya la hemos trazado anteriormente
00:35:15
pero lo que está del lado derecho es una
00:35:19
línea recta
00:35:20
donde la única variable es landa
00:35:25
veamos de qué estoy hablando primero
00:35:28
vamos a trazar fidel anda
00:35:32
sí qué es
00:35:34
una curva
00:35:37
ya lo hemos trazado antes aquí va a
00:35:40
fidel anda y por él cuando anda vale 0
00:35:46
es el corte de la curva con el eje z
00:35:50
ese es el interfecto de la recta
00:35:54
ahora solamente unos minutos unos
00:35:57
segunditos ignoremos el valor de alfa
00:36:01
solamente o consideremos que alfa vale 1
00:36:05
para no escribir y analicemos esta
00:36:10
segunda parte fui prima de 0 en la
00:36:13
pendiente de la recta tangente a la
00:36:16
curva azul en el punto blanda igual a 0
00:36:22
así que lo que tenemos del lado derecho
00:36:25
de la desigualdad es la ecuación de la
00:36:28
recta tangente
00:36:31
a la curva azul en el punto blanda igual
00:36:35
a cero
00:36:37
es
00:36:39
que tiene la ecuación fi de 0 + landa
00:36:43
por fin prima de share
00:36:47
llegó el momento de hablar de alfa
00:36:51
cuando multiplicamos la pendiente por
00:36:54
alfa y recuerden que alfa es un número
00:36:57
entre 0 y 1 lo que hace es convertir
00:37:00
esta recta en una recta casi horizontal
00:37:10
al tener en cuenta el valor de alfa nos
00:37:13
queda la siguiente recta
00:37:21
como pueden ver esta es la recta fin de
00:37:26
0 + alfa por landa por fui prima de c
00:37:33
ahora qué es lo que pide la condición de
00:37:36
armijo
00:37:37
pide que los valores aceptables de
00:37:41
lambda satisfagan esa desigualdad
00:37:45
es decir encuentre los valores de landa
00:37:51
donde la recta está por encima de la
00:37:55
curva azul
00:37:59
y eso nos da un conjunto bastante amplio
00:38:03
desde cero hasta donde vemos la línea
00:38:06
amarilla esos son los valores aceptables
00:38:11
la intención de la condición de armijo
00:38:14
principalmente es permitir que valores
00:38:18
de landa grandes lo más grande que se
00:38:21
pueda puedan ser aceptados y así poder
00:38:25
dar pasos mayores y no solamente pasos
00:38:28
pequeñitos cuando es posible
00:38:32
en eso consiste la condición de armijo
00:38:35
esta aparece en todos los problemas de
00:38:39
búsqueda lineal por la importancia que
00:38:41
tiene pero no es la única condición
00:38:44
ahora hablaremos de otra condición que
00:38:48
es muy importante
00:38:51
la otra condición importante es la
00:38:54
condición de coste o condición de
00:38:56
curvatura
00:38:58
esta fue propuesta en 1967 por allan
00:39:04
goldstein
00:39:07
constructive real análisis
00:39:12
después de presentarlo lo que él hace
00:39:17
miren esta desigualdad qué significa
00:39:21
vamos a analizarla un poco en términos
00:39:24
de fe eso nos ayudará más a entender
00:39:29
beta es el nuevo la nueva en nuevos
00:39:33
parámetros que aparece aquí
00:39:36
y es mayor que alfa
00:39:39
y menos
00:39:41
por eso algunas veces es llamada con la
00:39:45
beta condición y la de armijo la alfa
00:39:48
conducción
00:39:50
así que vamos a ver vamos a escribir
00:39:52
esto en términos de las derivadas de
00:39:55
fila
00:39:56
la primera
00:40:00
la primera parte de la desigualdad
00:40:04
beta por la derivada de fi en cero
00:40:10
y la segunda parte de la vez de la
00:40:12
desigualdad es la derivada de ti
00:40:18
son los valores que tenemos ahora
00:40:20
tratemos de entender qué es lo que está
00:40:23
pidiendo esta desigualdad el término
00:40:26
geométrico
00:40:27
entonces vamos a hacer una comparación
00:40:29
primero
00:40:31
mi prima vencer o beta prima de 0
00:40:34
que se esperaría de primaveras
00:40:40
veamos estas tres gracias'
00:40:42
la primera de prima de 0 es la pendiente
00:40:46
de la recta tangente en landa igual a 0
00:40:53
supongamos que seáis
00:40:55
ahora la segunda que está multiplicada
00:40:59
por un número entre 0 y 1
00:41:02
entonces va a quedar un poco más
00:41:04
horizontal
00:41:06
entonces lo que está pidiendo la
00:41:09
desigualdad de costes
00:41:12
se cojan a aquellos largas cuya
00:41:15
pendiente de encima o cuya valor ente y
00:41:21
prima sea mayor que la segunda
00:41:25
que me está por fin prima del ser
00:41:29
la re una cantidad infinita de valores
00:41:32
que se pueden tomar como podemos ver
00:41:35
cualquiera de esos valores irles incluso
00:41:38
podría hasta tener una inclinación
00:41:40
positiva y sirve
00:41:44
eso es lo que dice la condición de golf
00:41:47
pero qué efecto tiene eso ya en la
00:41:50
selección de los blandas en la gráfica
00:41:53
donde ponemos así
00:41:55
veamos
00:41:57
bueno recordemos que la condición de
00:41:59
constant depende de las pendientes si
00:42:02
aquí nos interesa son las pendientes
00:42:05
al escribirla como ya habíamos hecho
00:42:07
antes en función de las de la función
00:42:11
fin nos va a quedar la desigualdad que
00:42:15
aparece aquí en blanco
00:42:16
ahora pongamos aquí la gráfica y la
00:42:20
función fin
00:42:22
y analicemos qué es lo que está pidiendo
00:42:25
a ver la primera
00:42:28
ya vimos en la pendiente de la recta
00:42:31
tangente mi prima en ser
00:42:34
al multiplicar la por beta lo que hace
00:42:37
que queda un poco más horizontal
00:42:45
como vemos aquí en la gráfica
00:42:47
bueno esta línea verde es la que nos
00:42:50
interesa vamos a borrar la otra
00:42:55
y vamos a tener en consideración las
00:42:57
pendientes
00:43:00
qué puntos de landa tienen la pendiente
00:43:04
igual a la curva verde
00:43:08
y cuáles lo tienen tienen una pendiente
00:43:10
mayor
00:43:12
bueno atrás hemos esta recta paralela a
00:43:17
la línea verde que es tangente
00:43:20
esa pendiente es la misma de la
00:43:25
pendiente verde así que a partir de ese
00:43:30
punto en donde se encuentra en la recta
00:43:33
paralela y tangente hacia la derecha
00:43:37
todas tienen una inclinación más grande
00:43:41
que esa que tenemos
00:43:44
por ejemplo en este punto que vemos aquí
00:43:47
vamos a ir marcando varias expendientes
00:43:50
poses mayor mayor
00:43:52
todas esas pendientes son mayores que la
00:43:55
primera así que qué intervalo de landa
00:43:59
no siempre a partir del punto en donde
00:44:02
encontramos ese segmento paralelo y al
00:44:07
mismo tiempo tangente de ahí en adelante
00:44:10
nos servirán los datos
00:44:15
desde donde vemos la línea amarilla
00:44:17
hacia delante
00:44:19
todos esos valores son aceptables
00:44:24
así que qué es lo que hace la condición
00:44:29
de goldstein
00:44:31
está permitiendo que se utilicen valores
00:44:35
de landa mayores a aquellos valores
00:44:39
pequeñitos que se solían usar
00:44:43
nos nos prohíbe esta condición utilizar
00:44:47
valores de lambda muy pequeños
00:44:51
por eso es tan importante esta condición
00:44:54
para exigir que hayan pasos
00:44:57
suficientemente grandes
00:45:00
está en la condición de colista
00:45:04
ahora juntas
00:45:06
esta condición en la anterior nos dan
00:45:10
unos resultados
00:45:13
veamos
00:45:15
esta unión aparece dos años después en
00:45:19
1900
00:45:21
69 como el teorema de word
00:45:27
este fue publicado por philip words en
00:45:32
1969 ninguno de sus artículos
00:45:36
y mostró que se pueden mezclar las dos
00:45:40
condiciones y que se obtienen resultados
00:45:43
importantes
00:45:45
y que las dos condiciones no son
00:45:48
excluyentes
00:45:50
veamos en qué consiste ese teorema
00:46:01
efe una función continuamente
00:46:04
diferenciable de r
00:46:09
y sean xk rm y de suk a una dirección de
00:46:14
descenso
00:46:18
y asumimos que para la banda mayor que 0
00:46:21
en el conjunto de las imágenes
00:46:26
x + landare está acostado inferior mente
00:46:36
si beta se coge mayor que alfa pero
00:46:41
entre 0 y 1 entonces es existe blanda
00:46:46
surge irlanda su a él anda surge
00:46:50
producto de la condición de goldstein en
00:46:53
landa su producto de la condición de
00:46:56
armijo
00:47:04
la condición el alfa de la banda de la
00:47:07
condición g con landa
00:47:10
lo menos que el otro tal que para xk más
00:47:15
uno igual a equis
00:47:17
más blanda por d
00:47:23
satisface la condición de armijo y coste
00:47:28
irlanda está en el intervalo blanda
00:47:31
surge la cndh azul
00:47:35
qué quiere decir eso que siempre va a
00:47:38
haber valores de landa que satisfagan
00:47:42
las dos condiciones importantes la de al
00:47:46
mismo y la de los tres
00:47:49
ese es el significado
00:47:53
pero como siempre queremos una
00:47:55
interpretación geométrica de qué quiere
00:47:57
decir este teorema
00:47:59
consideremos nuevamente film fidel anda
00:48:02
y analicemos la condición de árnica
00:48:05
en ella habíamos encontrado un intervalo
00:48:09
que nos permite tener pasos grandes los
00:48:13
más grandes que se puedan
00:48:16
si nos da un conjunto de valores
00:48:19
aceptables
00:48:22
el punto que vamos a llamar landa sub
00:48:26
la otra condición la condición de corte
00:48:30
nos dice que no vamos a aceptar valores
00:48:34
muy pequeños así que nos da un límite
00:48:37
inferior que es la cndh a surgir
00:48:40
si queremos que se cumplan las dos
00:48:42
condiciones entonces los conjuntos son
00:48:46
la intersección de ellos dos
00:48:49
es decir ahora los valores aceptables
00:48:52
serán aquellos que estén entre landa
00:48:55
surje y las basuras
00:48:58
qué hubiera pasado si hubiéramos
00:48:59
trabajado con
00:49:02
búsqueda lineal exacta hubiésemos
00:49:05
encontrado en la estrella que estaba en
00:49:09
ese ínter
00:49:12
sin embargo con búsqueda lineal inexacta
00:49:15
podemos encontrar cualquiera de los
00:49:17
valores de landa que estén en ese
00:49:19
conjunto y también será muy práctico muy
00:49:23
útil y se necesitará menos operaciones
00:49:28
esa es básicamente la idea de usar las
00:49:31
dos y también se le conoce a estas dos
00:49:34
condiciones juntas como las condiciones
00:49:38
de wolf
00:49:41
tenemos entonces completo el panorama
00:49:45
para presentar el algoritmo completo
00:49:50
ya estamos listos para hablar sobre el
00:49:53
algoritmo completo de búsqueda lineal
00:49:56
vamos a empezar hablando sobre los
00:49:58
parámetros
00:50:01
los parámetros son alfa beta k épsilon y
00:50:06
el el alfa es el correspondiente a la
00:50:10
condición de army o beta el
00:50:13
correspondiente a la condición de
00:50:15
goldstein
00:50:17
es el número de declaraciones actuales
00:50:20
épsilon o tolerancia será un valor que
00:50:24
nos va a decir si es aceptable la
00:50:28
solución o tenemos que seguir avanzando
00:50:30
más y n mayúscula es el número máximo de
00:50:35
iteraciones en este caso de 50 pero si
00:50:40
la dimensión del problema es grande lo
00:50:42
necesario será aumentar este
00:50:47
ahora el segundo paso proporcionar x 10
00:50:51
se necesita un valor inicial
00:50:53
este es el vector inicial
00:50:55
paso 3
00:50:57
hay un ciclo empieza un ciclo de
00:51:00
mientras y las condiciones
00:51:04
son las siguientes la norma del
00:51:07
gradiente en el punto acto en la imagen
00:51:10
del punto actual tiene que ser
00:51:13
mayor o igual que el silo para poder
00:51:17
entrar y también cada menor o igual que
00:51:20
m cuando una de estas dos condiciones
00:51:22
deja de cumplirse se sale del ciclo es
00:51:26
decir o tenemos la solución o hemos
00:51:30
superado el número máximo de iteraciones
00:51:34
vamos a continuar seguimos con la
00:51:37
dirección calculamos la dirección como
00:51:40
se calcula esta dirección hay varios
00:51:43
métodos pero eso lo explicaré en el
00:51:45
siguiente vídeo
00:51:47
después de encontrar a la dirección
00:51:53
vamos al siguiente paso la anda igual a
00:51:56
1 vamos a empezar con ese valor y
00:51:59
probamos si satisface las condiciones
00:52:01
del mismo y de golpe
00:52:04
aquí están las condiciones negadas
00:52:07
cuando no se cumplan entonces es cuando
00:52:11
no se cumpla lo que está allí entonces
00:52:14
vamos a entrar al ciclo y vamos a
00:52:17
multiplicar a landa por 0 5
00:52:20
cuando ya se cumplan las dos condiciones
00:52:22
de armijo y goldstein entonces se sale
00:52:25
del ciclo
00:52:27
con este lambda actualizamos el
00:52:29
siguiente punto x + 1 se le asigna x más
00:52:34
en landa obtenido y la dirección de
00:52:37
descenso actualizamos nuevamente el
00:52:41
valor de acá y repetimos el proceso con
00:52:45
esto al terminar ya tendremos la
00:52:48
solución o un mensaje de error que
00:52:51
indique que no se alcanzó la solución en
00:52:54
el número de iteraciones n
00:52:58
bueno espero que estén atentos al
00:53:01
próximo vídeo que hablara sobre los
00:53:03
métodos que hay de búsqueda direccional
00:53:06
sí
00:53:15
sí
00:53:22
[Música]
