programacion no lineal
DESCRIPTION
definiciones y resultados de programacion no linealTRANSCRIPT
-
UNIVERSIDAD CENTROCCIDENTALLISANDRO ALVARADO
Decanato de Ciencias y TecnologaLicenciatura en Ciencias Matemticas
Sobre una nueva bsqueda lineal tipo armijo ysu relacin con el mtodo de region de
confianza
Trabajo Especial de Grado presentado por
Br. Ranghely del C. Hernndez Castaeda
como requisito final
para obtener el ttulo de Licenciado
en Ciencias Matemticas
rea de Conocimiento: Optimizacin.
Tutor: Dr. Rmulo Castillo
Barquisimeto, Venezuela. Julio de 2012
-
Dedicado A mis Padres Carmen y Rafael,
A mis Hermanos, Raidicar, Wilfredo,
Rodolfo, A mis Abuelos, Lucila, Rafael, A
mi novio Miguelangel.
-
AGRADECIMIENTOS
ADIOS primeramente por darme la oportunidad de vivir y regalarme una familia
maravillosa, por que a pesar de los obstculos me llenaste de fuerza y voluntad para
poder culminar mi carrera.
A mis padres, por haberme dado la vida por su apoyo y esfuerzo, por la confianza
depositada en mi, por estar a mi lado en todo momento a quienes debo este triunfo,
por incentivarme a seguir adelante y por todos esos sacrificios que hicieron por mi
para lograr que sea una profesional.
A mi hermano, por sus palabras y consejos que nunca faltaban siempre las tuve
presente, por su espritu luchador y emprendedor eres mi ejemplo a seguir.
A mi hermanos, Raidicar, Wilfredo y Rodolfo, por que no slo son mis hermanos,
son mis mejores amigos siempre aconsejndome para bien, ayudndome siempre en
todo lo que necesite gracias por nunca faltarme su apoyo tanto financiero como
personal y por confiar en mi.
A mis tias (Nelly, Alida), primas (Aliana, Albany) y primos (Keiber, David) por
sus consejos, por el apoyo brindado.
A mis amigos (Maria G., Elena, Beomay, Williams, Orangel, ), por compartir
conmigo buenos y malos momentos, por las enseanzas que me dejaron cada uno de
ellos.
A mis compaeros de clase (Mary Ines, Dayana, Maria E.,), por su disposicin
para ayudarme cuando los necesitaba.
A Miguelangel, por tu apoyo incondicional que me permiti mantenerme cons-
tante y no decaer, por motivarme a luchar por lo que quiero.
A mi tutor Rmulo Castillo por ser un gran Mentor y amigo.
Y a todos aquellos que de una u otra forma colaboraron conmigo.
i
-
Sobre una nueva bsqueda lineal tipo armijo ysu relacin con el mtodo de region de
confianza
RESUMENEl propsito central de este trabajo es relacionar los Mtodo bsqueda lineal
con el Mtodo de Regin de Confianza, los cuales son dos importantes clases de
tcnicas para resolver problemas de optimizacin inrrestrictas y tienen sus ventajas
respectivamente. En este trabajo se utiliza la Regla de Armijo la cual es un Mtodo
de bsqueda lineal inexacto, y se propone una Nueva Bsqueda Lineal de problemas
de optimizacin sin restricciones. Convergencia global y la velocidad de convergencia
del nuevo mtodo se analizan en leves condiciones. Adems, la nueva estrategia tipo
Armijo de bsqueda lneal se muestra como equivalente a una aproximacin de un
mtodo de regin de confianza, entonces tiene tanto ventajas de la estrategia de
bsqueda en lnea y la estrategia de regin de confianza.
ii
-
Introduccin
Al resolver problemas de optimizacin irrestricta nos vemos en la necesidad de
estudiar principalmente dos tipos de metodologas que generan sucesiones, las cuales
se esperan de alguna forma converger a un minimizador de la funcin objetivo. Por
una parte tenemos los mtodos basados en bsquedas lineales, en los cuales, una
vez obtenida una direccin de avance, realizamos una bsqueda lineal en esa direc-
cin; tales bsquedas pueden ser exactas o inexactas. Entre estas ultimas tenemos
las bsquedas de Armijo, Wolfe y Goldstein. Por otra parte los mtodos de region
de confianza constituyen otra metodologa para el mismo fin; en este ultimo caso
primero se preocupa uno del tamao del paso y luego de la direccin resultante por
medio de una aproximacin cuadrtica local de la funcin objetivo en cada iteracin.
En el presente trabajo realizaremos un estudio general de las bsquedas lineales y el
mtodo de region de confianza, pero nos detendremos en el anlisis de una particu-
lar bsqueda tipo Armijo propuesta recientemente que relaciona el iterado obtenido
mediante esta nueva bsqueda con la solucin aproximada del subproblema corres-
pondiente al mtodo de region de confianza.
-
ndice
Agradecimientos i
Resumen ii
1. PRELIMINARES 1
1.0.1. Direccin de Descenso . . . . . . . . . . . . . . . . . . . . . . 6
1.0.2. Direccin de Newton . . . . . . . . . . . . . . . . . . . . . . . 8
1.0.3. Otras Direcciones de Descenso . . . . . . . . . . . . . . . . . . 9
1.0.4. Condicin de Suficiente Descenso para dk . . . . . . . . . . . 10
1.0.5. MTODO DE BSQUEDA LINEAL . . . . . . . . . . . . . . 10
1.0.6. Mtodo de Regin de Confianza . . . . . . . . . . . . . . . . . 15
1.1. Razn de Convergencia . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Referencias 24
2. SOBRE UNA BSQUEDA LINEAL TIPO ARMIJO Y SU RELA-
CIN CON EL MTODO DE REGIN DE CONFIANZA 25
2.1. Un novedoso uso de la regla de Armijo . . . . . . . . . . . . . . . . . 25
2.2. Convergencia Global . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3. Razn de Convergencia . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.1. Convergencia Lineal . . . . . . . . . . . . . . . . . . . . . . . 31
2.4. Convergencia Superlineal . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5. Convergencia Cuadrtica . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6. Relacin con el Mtodo de Regin de Confianza . . . . . . . . . . . . 37
iv
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza v
2.7. Conclusin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Referencias bibliogrficas. 41
-
ndice de figuras
1.1. Grfica de la funcin con corte de planos . . . . . . . . . . . . . . . . 4
1.2. Conjunto de nivel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3. Direccin de Mximo Descenso . . . . . . . . . . . . . . . . . . . . . 7
1.4. La dificultad es que el direccin de mximo descenso es casi ortogonal
a la direccin que conduce al mnimo cuando las superficies de costo
de f son alargada. Con lo que resulta, que el mtodo vaya en zig-zag
sin hacer avance rpido. . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5. Direccin de Descenso . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6. Mtodo de Bsqueda Lineal . . . . . . . . . . . . . . . . . . . . . . . 11
1.7. Grfica de () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.8. Mtodo de Biseccin . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.9. Regla de Armijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.10. Regla de Goldstein: lustra el conjunto de tamaos de paso que son
aceptables en la regla de Goldstein. . . . . . . . . . . . . . . . . . . . 15
1.11. Region de Confianza . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.12. Punto de Cauchy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.13. Punto de Pata de Perro. . . . . . . . . . . . . . . . . . . . . . . . . . 20
vi
-
Captulo1PRELIMINARES
En este captulo se presentan los fundamentos de la optimizacin sin restricciones.
En la optimizacin sin restricciones, se minimiza una funcin objetivo que de-
pende de variables reales, sin restriccin alguna en los valores de estas variables.
Consideremos el problema de minimizacin sin restriccin.
minf(x), xRn. (1.1)
Donde Rn denota un espacio Euclideano n-dimensional y f : Rn R es una funcincontinuamente diferenciable. Para la minimizacin de dicha funcin se procede por
medio de varios mtodos, entre los cuales nos enfocaremos en el Mtodo de Bsqueda
Lineal y el Mtodo de Regin de Confianza.
Definicin 1.0.1. Un punto x se dice que es un punto mnimo relativo o punto
mnimo local de f sobre si existe un > 0 tal que f(x) 6 f(x) para todo x ,dentro de una distancia de x (Esto es, x y |x x| < ). Si f(x) < f(x) paratodo x y |xx| < , x 6= x, entonces x es llamado punto mnimo local estrictode f sobre
Definicin 1.0.2. Un punto x se dice punto mnimo global de f sobre , si
f(x) 6 f(x) para todo x . Si f(x) < f(x) para todo x y x 6= x, entoncesx es un punto mnimo global estricto de f sobre
Definicin 1.0.3. (Funcin Continua)
Sea f : X Rn R es continua si:
> 0, > 0;xX, x a < f(x) f(a) < (1.2)
1
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 2
Donde es la norma euclideana.Definicin 1.0.4. (Funcin Uniformemente Continua)
Una funcin f : Rn R, n > 1 es uniformemente continua en un intervalo A Rnsi para todo > 0 existe algn > 0 tal que para todo x, yA se cumple que si
x y < , entonces f(x) f(y) < Teorema 1.0.5. (Teorema del Valor Medio, de Lagrange)
Sea A un abierto en Rn, sea f : A R diferenciable sobre A. Si A contiene elsegmento de linea con extremos a y a+ h, entonces existe un punto c = a+ h, con
[0, 1], tal que:
f(a+ h) f(a) = g(a+ h)h (1.3)La prueba se encuentra en cualquier libro de anlisis ver
Teorema 1.0.6. (Teorema Fundamental del Clculo) Sea A un abierto en Rn, sea
f : A R. Si f es continua sobre A, entonces ax
f = f(x) f(a) (1.4)
Prueba ver
Definicin 1.0.7. (Lipschitz continua)
Una funcin f : Rn R, se dice que es Lipschitz continua o simplemente Lipschit-ziana, si existe una constante M > 0, tal que:
f(x) f(y) 6Mx y,x, yRn. (1.5)
Donde M es llamada la contaste Lipschitz de la funcin.
Igualmente es Lipschitz continua en un conjunto X Rn si existe una constanteM > 0, tal que:
f(x) f(y) 6Mx y,x, yX. (1.6)Si M es la constante Lipschitz de f, entonces f(x) 6M toda vez que el gradientede la funcin exista. Contrariamente, si f : I Rn R es una funcin diferenciablecon derivada acotada, f(x) 6 L para toda x en I, entonces f es Lipschitz continuacon constante Lipschitz K = L, una consecuencia del teorema del valor medio.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 3
Proposicin 1.1 Sea f : X Rn R Lipschitziana, entonces es continuamenteuniforme
Demostracin.
Sea f Lipschitziana, luego existe un c > 0, tal que f(x)f(y) 6 cxy,x, yX.As para cualquier > 0, basta tomar = /c. Por Lipschitziana tenemos que
x y < f(x) f(y) <
Entonces f es continuamente uniforme
Definicin 1.0.8. (Funcin Convexa)
El trmino onvexo"se puede aplicar tanto a conjuntos como funciones. Un conjunto
S Rn es convexo si el segmento de recta que une dos puntos cualesquiera de S seencuentra totalmente dentro de S. Formalmente, para dos puntos cualesquiera x,y
S, tenemos que
x+ (1 )yS, [0, 1]. (1.7)La funcin f es una funcin convexa si su dominio S es un conjunto convexo y si para
cualquier par de puntos x,y S, se satisface la siguiente propiedad:
f(x+ (1 )y) 6 f(x) + (1 )f(y), [0, 1]. (1.8)
Ejemplos de funciones convexas incluyen la funcin lineal f(x) = cTx + , para
cualquier vector constante c Rn y escalar , y la funcin cuadrtica convexa f(x) =
xHx, donde H es una matriz simtrica semidefinida positiva.
Decimos que f es estrictamente convexa si la desigualdad (1.8) es estricta siempre
que x 6= y y est en el intervalo abierto (0, 1). Una funcin f se dice que es cncavasi f es convexa.
Si la funcin objetivo es convexa en todo su dominio, entonces cualquier solucin
local del problema es, de hecho, una solucin global.
Definicin 1.0.9. (Funcin Pseudoconvexa)
Sea f : S R una funcin diferenciable sobre S, f es pseudoconvexa si para cadax1, x2 S se cumple que,
Sif(x2) < f(x1), entoncef(x1)T (x2 x1) < 0 (1.9)
o de manera equivalente,
Sif(x1)T (x2 x1) > 0, entoncef(x2) > f(x1) (1.10)
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 4
Y tenemos como consecuencia que,
Sif(x) = 0, entonces x es unminimo global. (1.11)
Ya que si f(x) = 0, entonces f(x)T (x2 x) > 0,x2S se cumple f(x2) >f(x)x2 SDefinicin 1.0.10. (Conjunto de Nivel)
Sea H un conjunto y f : H R. El conjunto de nivel Ck para la funcin f es elsubconjunto de puntos x en H para los cuales f(x) = k.
En Simbolo:
Ck = {xH : f(x) = k} (1.12)Si H=R2, los conjuntos de nivel son en general curvas y se las llama curvas denivel.
Si H=R3, los conjuntos de nivel suelen ser superficies y se les llama superficiesde nivel.
Cuando H = R2, f(x) = z con xH, la grfica de dicha funcin correspondeal conjunto gr(f) = {(x1, x2, f(x1, x2)) : (x1, x2)H}. Al ubicar los puntos en elespacio R3, obtenemos una superficie en dicho espacio. Las curvas de nivel se obtienencortando la superficie con planos horizontales situados a distintas alturas. Si cortamos
la grfica con varios planos horizontales obtenemos una serie de curvas situadas sobre
la grfica:
Figura 1.1: Grfica de la funcin con corte de planos
Y si ahora proyectamos esas curvas sobre el plano xy (lo cual equivale a mirar la
grfica, desde arriba, a vista de pajaro) vemos una familia de curvas planas, que son
el conjunto de las curvas de nivel de esta grfica:
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 5
Figura 1.2: Conjunto de nivel
Conjuntos de nivel y gradientes
Si el conjunto H coincide con Rn y el campo escalar es de clase C1 entonces losvectores gradiente del campo escalar son ortogonales a los conjuntos de nivel en el
siguiente sentido: Sea Ck un conjunto de nivel y c : I R C : k una curvadiferenciable. Los vectores gradiente del campo f sobre la curva, son ortogonales a
los vectores velocidad de la curva. En efecto, para todo t en I, f(c(t)) = k. Derivan-
do respecto de t se obtiene (usando la derivada de una composicin de funciones),
f(c(t))c(t) = 0En particular, las curvas integrales asociadas al campo vectorial generado por el
gradiente de f son .ortogonales.a los conjuntos de nivel asociadas a dicha funcin.
Teorema 1.0.11. (Teorema de Taylor)
Supongamos que f.Rn R continuamente diferenciable y p Rn, entonces tenemosque:
f(x+ d) = f(x) +f(x+ td)Td (1.13)Para algn t (0, 1). Adems, si f es dos veces continuamente diferenciable, tenemos:
f(x+ d) = f(x) + 1
0
2f(x+ td)ddt (1.14)
y que,
f(x+ d) = f(x) + dTf(x) + 12dT2f(x+ td)d (1.15)
Para algn t (0, 1).
Condicin necesaria para optimalidad es la derivada para asumir que x es un
mnimo local y entonces probar los hechos sobre f(x) y 2f(x)Teorema 1.0.12. (Condicin necesaria de primer orden)
Si x es un mnimo local de f y f es continuamente diferenciable en un vecindad
abierta de x, entonces f(x) = 0 y 2f(x)es semidefinida positiva.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 6
Teorema 1.0.13. (Condicin necesaria de segundo orden)
Si x es un mnimo local de f y f es dos veces continuamente diferenciable en un
vecindad abierta de x, entonces f(x) = 0.Teorema 1.0.14. (Condicin suficiente de segundo orden)
Supongamos que 2f(x) es continua en una vecindad abierta de x y que f(x) =0 y 2f(x)es definida positiva, entonces x es un mnimo local estricto de f.
1.0.1. Direccin de Descenso
Para deducir las propiedades de la direccin de descenso, hacemos llamativo al
teorema de Taylor (1.0.11) , que nos dice que para cualquier direccin d y tamao
de paso , tenemos que:
f(xk + d) = f(xk) + dTf(xk) + 1
22dT2f(xk + td)d (1.16)
Para algn t (0, ).
Por conveniencia denotaremos f(xk) por fk o en otros casos por gk, f(xk) porfk, 2f(xk) por 2fk o por Gk y f(x) por f ,respectivamente.
El factor reductor de cambio en f a lo largo de la direccin d desde xk es simple-
mente el coeficiente de , a saber, dTf(xk). Por lo tanto, la nica direccin d dems rpido decrecimiento es la solucin del problema.
minddTfk, sujeto a d = 1 (1.17)
Donde dTfk = dfk cos = fk cos , y es el ngulo entre d y fk, esfcil ver que el reductor se alcanza cuando cos = 1, esto ocurre cuando = pi y
d =fkfk (1.18)
Esta direccin es llamada la direccin de mximo descenso, la figura (1.3) ilustra
la direccin ortogonal en el contorno de la funcin.
La direccin de mximo descenso es usada en mtodo de bsqueda lineal que se
mueve a lo largo de dk = fk en cada paso. Se puede elegir la longitud k enuna variedad de formas que se discute mas adelante. Una ventaja de la direccin de
mximo descenso es que requiere el clculo de fk pero no de la segunda derivada.Sin embargo puede ser muy lento en los problemas difciles.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 7
Figura 1.3: Direccin de Mximo Descenso
Figura 1.4: La dificultad es que el direccin de mximo descenso es ca-si ortogonal a la direccin que conduce al mnimo cuando las super-ficies de costo de f son alargada. Con lo que resulta, que el mtodovaya en zig-zag sin hacer avance rpido.
Mtodos de Bsqueda lineal pueden usar una direccin que no sea la direccin de
mximo descenso. En general, como hemos visto que el mximo descenso ocurre en
= pi cualquier direccin que forme un ngulo estrictamente mayor que pi2con fk,
o anlogamente que forme un ngulo estrictamente menor que pi2con fk garantiza
una disminucin en f, siempre que la longitud del paso sea suficiente pequea, ver
figuras (1.5).
Figura 1.5: Direccin de Descenso
Podemos probar esta afirmacin usando el teorema de Taylor
f(xk + dk) = fk + dTfk +O(k) (1.19)
Donde dT es una direccin de descenso, el ngulo k entre pk y fk tiene cos k < 0,
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 8
de modo que
(dk)Tfk = dkfk cos k < 0 (1.20)
Si tomamos en cuenta el ngulo k, como el ngulo entre dk y gk, podemos verlode la siguiente forma
(dk)Tgk = dkgk cos k > 0 (1.21)O lo que es lo mismo
cosgk, dk = (gk)Tdk
gkdk > 0 (1.22)
Y por completitud en R
cosgk, dk = (gk)Tdk
gkdk > , (1.23)
Donde 0 < 6 1.De esto se deduce que f(xk+dk) < f(xk) para todo valor positivo pero suficiente
pequeo de .
1.0.2. Direccin de Newton
Otra importante bsqueda de direccin, tal vez la ms importante de todas es la
direccin de Newton. Esta direccin se deriva de la serie de Taylor de segundo orden
aproximando f(xk + d), que es
f(xk + d) fk + dTfk + 12dT2fkdk = mk(d) (1.24)
Asumamos por el momento que Gk = 2f(xk) es definida positiva, obtenemos ladireccin de Newton por la bsqueda del vector d que minimiza mk(d). Por la simple
igualacin de la derivada de la funcin mk(d) a 0, obtenemos la siguiente frmula
explcita:
gk + dTGk = 0 (dk)N = (Gk)1gk (1.25)
La Direccin de Newton es confiable cuando la diferencia entre la funcin verdadera
f(xk + d) y su modelo cuadrtico mk(d) no es tan grande. Por comparacin (1.16) y
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 9
(1.24), vemos que la nica diferencia entre estas funciones es que la matriz 2f(xk +d) en el tercer termino de la expansin ha sido reemplazado por 2fk. Si 2f essuficientemente suave, esta diferencia introduce una perturbacin de solo Od3 enla expansin, que por que lo que cuando d es pequea la aproximacin f(xk+d) mk(d) es bastante exacta.
La direccin de Newton puede usarse en mtodos de bsqueda lineal cuando 2fkes definida positiva. En este caso sustituyendo (1.25) y multiplicando por f(xk)tenemos
(fk)T (dk)N = (fk)T (2fk)1fk (1.26)y
(fk)T (2fk)1fk 6 kfk (1.27)Para algn k > 0. A menos que el fk (y por lo tanto el paso (dk)N) es igual
a cero, tenemos que (fk)T (dk)N < 0, por lo que la Direccin de Newton es unadireccin de descenso.
Cuando 2fk no es definida positiva, la direccin de Newton ni siquiera se puededefinir, ya que (2fk)1 puede no existir. Incluso cuando se puede definir, puedeque no cumpla con la propiedad de descenso (fk)T (dk)N < 0, en cuyo caso no esadecuada como una direccin de bsqueda.
Los mtodos que utilizan la direccin de Newton tiene una rpida tasa de con-
vergencia local, por lo general cuadrtica. Despus de una vecindad de la solucin
se alcanza, la convergencia con alta precisin a menudo se produce en tan slo unas
pocas iteraciones. El principal inconveniente de la direccin de Newton es el la nece-
sidad de calcular la Hessiana 2f(x). El clculo explcito de esta matriz de segundasderivadas a veces puede ser un proceso engorroso, propenso a errores, y caro.
1.0.3. Otras Direcciones de Descenso
Adems la direccin de descenso a menudo tiene la forma
dk = (Dk)1fk (1.28)
donde Dk es una matriz simtrica y no singular. En el mtodo de la direccin de
mximo descenso, Dk es simplemente la matriz identidad In, mientras que en el
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 10
mtodo de Newton, Dk es la exacta Hessiana 2fk. Tambin podemos mencionar losmtodos Cuasi-Newton, Dk es una aproximacin a la de Hessiana, que se actualiza
en cada iteracin por medio de una frmula de bajo rango.
1.0.4. Condicin de Suficiente Descenso para dkPara asegurar que algn mtodo no se quede pegado se considera las condiciones
tcnicas, que pueden ser fcilmente aplicadas a la mayora de los algoritmos de inte-
rs. Para el caso en que dk = (Dk)1fk, y DK es definida positiva los autovaloresde la matriz simtrica Dk son acotados superiormente y lejos de cero, es decir, para
algunos escalares positivos c1 y c2, tenemos
c1z2 6 zTDkz 6 c2z2 (1.29)
Se puede apreciar entonces que tomando solo la desigualdad izquierda que,
|f(xk)Tdk| = |f(xk)TDkf(xk)| > c1f(xk)2 (1.30)
Luego esto implica que
f(xk)TDkf(xk) > c1f(xk)2of(xk)TDkf(xk) 6 c1f(xk)2 (1.31)
En orden de garantizar la convergencia global, nosotros sometemos el requerimiento
que dk satisfasga
f(xk)Tdk 6 c1f(xk)2 (1.32)Para detalles de la prueba ver referencia
1.0.5. MTODO DE BSQUEDA LINEAL
Cada iteracin de un mtodo de bsqueda lineal, calcula una bsqueda de direc-
cin y luego decide cuan lejos se mover a lo largo de esa direccin. La iteracin esta
dada por
xk+1 = xk + kdk (1.33)
Donde el escalar positivo k es llamado el tamao de paso.El xito de un mtodo de
bsqueda lineal depende de las decisiones eficaces, tanto de la direccin dk como el
tamao de paso k.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 11
La mayora de los algoritmo de bsqueda lineal requieren que dk sea una direc-
cin de descenso, esto es que se cumpla (dk)Tfk < 0, porque esta caractersticagarantiza que la funcin f puede reducirse a lo largo esta direccin, como se discuti
anteriormente.
Una vez que la direccin de descenso dk se determina se debe buscar un tamao de
paso a lo largo la direccin de descenso y completa una iteracin. Ahora consideremos
cuidadosamente la eleccin del tamao de paso, parmetro k.
Figura 1.6: Mtodo de Bsqueda Lineal
Tamao de paso
En el tamao de paso k, se encuentra una disyuntiva. Nos gustara elegir k para
dar una reduccin sustancial de la f, pero al mismo tiempo, no queremos gastar
mucho tiempo de costo en hacer la eleccin. La opcin ideal sera el minimizador
global de la funcin univaluada () definida por
() = f(xk + dk), > 0, (1.34)
Cuando la bsqueda del tamao de paso se realiza resolviendo la minimization
de (1.35), entonces se trata de una "Bsqueda lineal exacta". Entra las cuales men-
cionaremos el Mtodo de Biseccin.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 12
Figura 1.7: Grfica de ()
Mtodo de Biseccin
Consideremos una funcin () = f(xk +dk) Pseudoconvexa sobre un intervalo
[a1, b1]. Supongamos que [ak, bk] es el intervalo de incertidumbre en una iteracin k.
Supongamos que ck = bkak2 [ak, bk] y (ck) existe. Luego pueden suceder uno de
los tres casos,
1. (ck) = 0, entonces ck es un mnimo.
2. (ck) > 0, entonces para c > ck (ck)(c ck) > 0, entonces (c) > (ck),luego
[ak + 1, bk + 1] = [ak, ck]
3. (ck) < 0, entonces para c < ck, (ck)(c ck) > 0, entonces (c) > (ck). As,
[ak + 1, bk + 1] = [ck, bk]
Esto nos da un mtodo que se describe en el siguiente algoritmo
(Algoritmo (1))
Entrada x0 punto inicial, a0,b0 puntos extremos del intervalo de entrada, Tol tole-
rancia k=0; Paso 1: Calcula ck = bkak2 Paso 2: Calcular (ck)
Paso 3: Si (ck) = 0 o bkak2 < Tol Salida (c = ck) PARAR;
Si no; Paso 4: Si
phi(ck) > 0 [ak+1, bk+1] = [ak, ck], y k = k+1; Volver al paso 1 Si no [ak+1, bk+1] =
[ck, bk],k = k + 1; Volver al paso 1
Para ilustrar el mtodo de Biseccin mostramos la siguiente figura.
() = f(xk + dk), > 0, (1.35)
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 13
Figura 1.8: Mtodo de Biseccin
Pero, en general, es demasiado caro identificar el valor mnimo de la funcin ().
Para encontrar incluso un minimizador local de f con una precisin moderada gene-
ralmente requiere demasiadas evaluaciones de la funcin objetivo f, y posiblemente
el gradiente f . Estrategias ms prcticas realizan una bsqueda lineal para identi-ficar a un tamao de paso que logre reducciones que son necesarias en f a un costo
mnimo a lo cual se le llama "Bsqueda lineal inexacta", las ms usadas son la regla
de Armijo, Regla de Goldstein y Regla de Wolfe, .
Regla de Armijo
Un prctico criterio popular para determinar una bsqueda lineal es la regla de
Armijo. La idea esencial es que la regla debe primero garantizar que la seleccin de
no demasiado grande.
En la regla ms simple de este tipo un tamao de paso inicial s se elide, y si el
vector correspondiente xk+sdk no produce una mejora del valor de f, es decir,f(xk+
sdk) > f(xk), el tamao del paso se reduce, quizs varias veces, por un determinadofactor, hasta que el valor de f se mejore.
Aqu, escalares fijos s > 0, , y , con 0 < < 1, y 0 < < 1 se eligen, y
establecemos k = smk , donde mk es el primer entero no negativo tal que
f(xk) f(xk + smdk) > smf(xk)Tdk (1.36)
As el tamao de paso k = sm, con m = 0, 1, ...., se tratan sucesivamente hasta
que la desigualdad anterior se cumpla, En otras palabras, se elide k el mas grande
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 14
en {s, s, s2, ..., } tal que
f(xk) f(xk + dk) > f(xk)Tdk (1.37)
Por lo tanto, el tamao de paso no debe ser slo positivo, sino que debe ser lo
suficientemente pequeo para que se cumpla (1.37). En funcin de ver esta regla
geomtricamente podemos reescribir (1.37) como
f(xk + dk) 6 f(xk) + f(xk)Tdk (1.38)
la figura siguiente ilustra esta regla.
Figura 1.9: Regla de Armijo
La bsqueda lineal por la regla de Armijo. Comenzamos con el estudio del tamao
de paso s y continuar con s, s2, .., .. hasta la primera vez que sm caiga dentro del
conjunto de tamaos de paso que satisface la desigualdad, donde la linea punteada
representa la funcin f(xk) + f(xk)Tdk en la Figura (1.10).Por lo general, se elige cerca del cero, por ejemplo, [105, 101]. El factor
de reduccin se elige generalmente de 1/2 a 1/10 en funcin de la confianza que
tenemos del paso inicial s. Siempre podemos tomar s = 1 y multiplicar la direccin
dk por un factor de escala.
Regla De Goldstein
Otra regla de bsqueda lineal de precisin que es usada frecuentemente es la regla
de Goldstein. Aqu, un escalar fijo (0, 1/2) es seleccionado, y k se elige para
satisfacer
6 f(xk + dk) f(xk)f(xk)dk 6 1 (1.39)
Reescribiendo esta condicin tenemos, que un valor es aceptable si
f(xk)dk + f(xk) 6 f(xk + k) 6 (1 )f(xk)dk + f(xk) (1.40)
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 15
Figura 1.10: Regla de Goldstein: lustra el conjunto de tamaos depaso que son aceptables en la regla de Goldstein.
la figura siguiente ilustra esta regla.
Hay algoritmos muy simples para encontrar el tamao de paso, pero no lo hare-
mos entrar en detalles, ya que en la prctica, la simple regla de Armijo parece ser
universalmente preferida. La regla de Goldstein se incluye aqu debido principalmen-
te a de su importancia histrica: fue la primer regla para generar una bsqueda lineal
que no se basara en la minimizacin exacta de f a lo largo de la direccin de descenso,
y fue la idea fundamental para posteriormente proponer la regla era Armijo.
Regla de Wolfe
Si derivamos de la funcin objetivo, sus valores pueden ser evaluados con relativa
facilidad, entonces la regla de wolfe, que es una variacin de la anterior, es tambin
preferida. En este caso c1 es seleccionado con 0 < c1 < 1/2 y requiere satisfacer
() > (1 c1)(0) (1.41)
Esto se ilustra
1.0.6. Mtodo de Regin de Confianza
Mtodo de Regin de confianza define una regin alrededor de la iteracin actual
en la que se confa que el modelo sea una representacin adecuada de la funcin
objetivo, y luego elegir el paso a ser el reductor aproximado del modelo en esta
regin. As, el mtodo elige la direccin y la longitud del paso de forma simultnea.
La funcin del modelo mk que se utiliza en cada xk iteracin es cuadrtica.
Adems, mk se basa en el desarrollo de la serie de Taylor de f alrededor de xk que es
f(xk + p) = fk + gTk p+
1
2pT2f(xk + tp)p (1.42)
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 16
Donde fk = f(xk), gk = f(xk) y t es cierto escalar en el intervalo (0, 1). Medianteel uso de una aproximacin Bk a la Hessiana 2f(xk) = Gk en el trmino de segundoorden, mk se define como sigue:
mk = fk + gTk p+
1
2pTBkp (1.43)
Donde BK es una matriz simtrica. La diferencia entre f(x+p) y mk es O(p2)que es pequea cuando p es pequeo. Cuando Bk = Gk se dice que el mtodo de
Regin de Confianza es tipo Newton.
Para obtener cada paso, buscamos una solucin del subproblema
minpRnmk = fk + gTk p+
1
2pTBkp s.t.p 6 k (1.44)
Donde k > 0 es el radio de la regin de confianza, el cual determina la longitud
del paso de xk a xk+1. En la mayor parte de nuestras discusiones, se define . paraser la norma eucldea, de modo que la solucin p de (1.11) es el reductor de mk en
la bola del radio k.
Uno de los ingredientes clave en un algoritmo de Regin de Confianza es la
estrategia para la eleccin del radio k en cada iteracin pk se define la relacin de
reduccin
rk =f(xk) f(xk + pk)mk(0)mk(pk) =
actualreduccin
previstareduccin(1.45)
Si la relacin de reduccin es grande por ejemplo k > 3/4, el tamao de la regin
de confianza aumenta en la siguiente iteracin.
Si la relacin de reduccin es pequea, por ejemplo k < 1/4, el tamao de la
regin de confianza es reducido en la siguiente iteracin.
Adems, el paso pk solo se aceptara si le relacin de reduccin no es demasiado
pequea. Lo que nos lleva al siguiente algoritmo
Algoritmo (2)
Dado > 0, o(0, ) y [0, 1/4) Para k = 0, 1, 2, ..., hasta que xk es optimal
Obtener la solucin aproximada para tentativa del paso pk
minpRnmk = fk + gTk p+
1
2pTBkp s.t.p 6 k (1.46)
Calcular la relacin de reduccin
rk =f(xk) f(xk + pk)mk(0)mk(pk)
Para pk Actualizar el punto actual
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 17
xk+1 =
{xk + pk sipk >
xk Enotrocaso
Actualizar el radio de la regin de confianza
k+1 =
14k sirk 34ypk = k
k Enotrocaso.
Figura 1.11: Region de Confianza
A continuacin se describen dos estrategias para encontrar soluciones aproxima-
das del subproblema (1.43)
El Punto de Cauchy
El punto de Cauchy, no es ms que el reductor de mk a lo largo de la direccin
de mximo descensogk. Sujeto a la confianza. Como hemos visto, los mtodos debsqueda lineal pueden ser convergente, incluso cuando la longitud del paso ptimo
no se utiliza en cada iteracin. De hecho, la longitud del paso k slo necesita sa-
tisfacer criterios. Aunque en principio buscamos la solucin ptima del subproblema
(1.43), es suficiente para fines de convergencia global encontrar una solucin aproxi-
mada que se encuentra dentro de la regin la confianza y da una reduccin suficiente
en el modelo. La reduccin suficiente puede ser cuantificado en trminos del punto
de Cauchy , que denotamos por pck y definir en trminos del simple procedimiento
siguiente.
Algoritmo(3) Encontrar el vector psk que resuelva una version lineal de (1.43),
que es,
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 18
psk = argminpRnfk + gTp s.t.p 6 k (1.47)
Calcular k > 0 que minimice mk(psk) sujeto a satisfacer el conjunto de regin
de confianza, esto es,
k = argmin>0mk(psk) s.t.p 6 k (1.48)
Establecer pck = kpskEs fcil deducir que la solucin de (1.47) es simplemente
psk =k.gkgk (1.49)
Esto lo podemos comprobar del mismo modo que lo hicimos para deducir la direccin
de descenso, sabiendo que el coeficiente de cambio en (1.47) es gTk py ver que la
mxima reduccin sucede s.t p = k.Para obtener k explcitamente, consideramos el caso que gTkBkgk 6 0 y gTkBkgk >
0 por separado.
Para el primer caso, la funcin mk(psk) decrece monotonamente con cuando
gk 6= 0, As k = 1 el valor mas grande que se satisface en la regin de confianza.Para el caso gTkBkgk > 0, mk(psk) es cuadriculada convexa en , As k se obtiene
de la minimizacin no restringida de esta cuadrtica, esto es, derivando con respecto
a a mk(psk) e igualando a 0, obtenemos:
pskgk + (psk)TBkp
sk = 0
=pskgk
(psk)TBkp
sk
Sustituyendo psk =kgkgk
=kgkgk
.gk
kgTkgk
Bkkgkgk
=kgk
gk22kgTkBkgk
gk2
= gk3
kgTk Bkgk
As que en el caso que gTkBkgk > 0, = gk3/(kgTkBkgk) o es 1, cualquiera queocurra primero.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 19
En resumen tenemos,
pck = kkgkgK
Donde
k =
1 sigTkBkgk 6 0min( gk3kg
Tk Bkgk
, 1) Enotrocaso
La figura.3 ilustra el Punto de Cauchy para en que Bk es definida positiva
Figura 1.12: Punto de Cauchy.
El Mtodo de Dogled
El enfoque de este mtodo va con el ttulo descriptivo del mtodo de pata de
perro. El cual puede ser usado solo cuando Bk es definida positiva. El subproblema
de la regin de confianza.
minpmk = fk + gTk p+
1
2pTBkp s.t.p 6 k
Es un problema difcil. La solucin no restringida de mk es pB = B1g, cuandoeste punto es factible para (1.46) es min (1.43), es evidente una solucin por lo que
tenemos
p() = pB, cuando > pB (1.50)Cuando es pequeo en relacin a pB, la restriccin p 6 asegura que el trminode segundo grado en m tiene poco efecto en la solucin "4.5. As podemos obtener
la solucin por
p() gg , cuandoespequeo (1.51)
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 20
Figura 1.13: Punto de Pata de Perro.
Para valores intermedios de , la solucin p(), tpicamente sigue una trayectoria
curva como la figura (1.13)
El mtodo de pata de perro aproxima la trayectoria curva de p(), mediante un
ruta de acceso que consta de dos lneas.
Formalmente definimos la trayectoria por p() para [0, 2], como:
k =
{p si0 6 6 1p+ ( 1)(pB pu) si1 6 6 2
El punto pu es el de Cauchy, es decir, el minimizador de m a lo largo de la direccin
de mximo descenso;
pu = gTg
gTBgg (1.52)
El mtodo de pata de perro elige p para minimizar el modelo m a lo largo de este
camino, con sujecin a la regin confianza. El siguiente lema muestra que el mnimo
lo largo de la ruta de acceso pata de perro se pueden encontrar fcilmente.
Lema 1.0.15. Sea B definida positiva. Entonces
p() es una funcin creciente de , y
m(p()) es una funcin decreciente de .
La demostracin de este lema es muy fcil de probar y se encuentra en cualquier
libro de optimizacin ver [?]libro Nocedal). Este lema garantiza que que el camino
p() se cruza con la regin de confianza p = exactamente en un punto si pB >, Y en ninguna otra parte. Como m es decreciente a lo largo del camino, el valor
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 21
elegido de p estar en pB si pB 6 . En este caso, se calcula el valor apropiado de por la solucin de la ecuacin cuadrtica escalar siguiente:
pu + ( 1)(pB pu) = 2 (1.53)
Consideremos ahora el caso en el que B = Gk, cuando Gk es definida positiva,
podemos simplemente tomar el conjunto B = Gk(es decir, pB = G1k gk) y aplicar el
procedimiento anterior para encontrar el paso Newton de pata de perro. El mtodo
de Newton-pata de perro es el ms apropiado cuando la funcin objetivo es convexa
(es decir, Gk es siempre semidefinida positiva).
Definicin 1.0.16. (Notacin o, O) Si g es una funcin de variable real a valores
reales, la notacin g(x) = O(x), significa que g(x) tiende a cero por lo menos tan
rpidamente como lo hace x, esto es, que la hay una k > 0, tal que:
|g(x)||x| 6 k, cuandox 0 (1.54)
La notacin g(x) = o(x), significa que g(x) tiende a cero ms rpido que lo hace
x, es equivalente a que el k anterior es cero.
1.1. Razn de ConvergenciaConsidere una sucesin de numeros reales {xi}i=0 convergente a el lmite x.
Definiremos la nocin de velocidad de convergencia de la sucesin.
Definicin 1.1.1. Sea la sucesin {xi}i=0 convergente a x. El orden de convergenciade {xi} es definido como el nmero supremo no negativo p satisfaciendo
o 6 lmi|xi+1 x||xi x|p
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 22
Valores mas grandes del orden p, implica en sentido de distancia para el lmite
x, ms rpida convergencia. En efecto, si la sucesin tiene orden p, podemos ver
la siguiente comparacin, como {xi}i=0 convergente a x, luego |xi x| < 1 para isuficientemente grande, y vemos que |xi x|p se har mas pequeo mientras p seamas grande, as el siguiente iterado estar a una menor distancia de x, sin ignorar
a con lo que tenemos que a menor radio ms rpida convergencia.
Es decir, que a valores mas grandes de p y valores mas pequeos de tendremos
aun mayor rapidez de convergencia.
El estudio de la velocidad de convergencia adems de estudiar la eficacia relativa
de los algoritmos de los mtodos es un anlisis de aproximacin local el cual a tenido
considerable xito en prediccin de comportamientos de distintos mtodos donde
la funcin de costo puede ser bien aproximada por una cuadrtica. Sin embargo,
el enfoque de anlisis local tambin tiene algunos inconvenientes importantes, el
ms importante de las cuales es que no se tiene en cuenta el ritmo de progreso en
las primeras iteraciones. No obstante, en muchas situaciones prcticas, no es una
omisin grave porque el progreso es rpido en las iteraciones iniciales y con menor
crecimiento slo en el lmite (Las razones de esto parecen difciles de entender, estos
son problemas dependientes). Adems, a menudo en la prctica, los puntos de partida
que estn cerca de una solucin son fcilmente obtenibles por una combinacin de
heurstica y experiencia, en cuyo caso el anlisis local es ms significativo.
El anlisis local no es muy til para problemas que involucran ya sea singula-
ridades o mnimos locales, que son difciles de encontrar en el sentido de que los
principales mtodos le toma muchas iteraciones para llegar cerca de su solucin en
la que se aplica el anlisis local.
Si los mtodos a comparar tienen igual orden de convergencia la comparacin
se basara en los correspondientes radios de convergencia, con menor valor del radio
mayor sera la rapidez de la convergencia.
Definicin 1.1.2. sea la sucesin {xk} convergente a x, si existe un (0, 1) y talque
lmi|xi+1 x||xi x| = (1.57)
La sucesin se dice convergente linealmente a x con radio de convergencia .
Una sucesin convergente linealmente con radio de convergencia , puede decirse
tener una convergencia por lo menos tan rpido como la secuencia geomtrica ck
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 23
para alguna constante c.
En el caso cuando = 0 es denomina convergencia superlineal.
Ahora decimos que la sucesin converge con orden p en x para p > 1, si
lmi|xi+1 x||xi x|p = (1.58)
En particular, convergencia con orden:
2 se denomina convergencia cuadrtica.
3 se denomina convergencia cubica.
etc.
Definicin 1.1.3. (Definicin ampliada)
El inconveniente de las definiciones anteriores es que stas no perciben algunas su-
cesiones que todava convergen razonablemente rpido, pero cuya "velocidad.es va-
riable. Por lo tanto, la definicin de orden de convergencia a veces se extiende como
sigue. Segn la nueva definicin, la sucesin {xk} converge con al menos orden q ax, si existe una sucesin {k} tal que
xk x < qk k (1.59)y la sucesin {k} converge a cero con orden p de acuerdo a la definicin anterior.Para distinguir esta definicin, se le llama convergencia R-lineal, convergencia R-
cuadrtica , etc (Con el q permanente). Es decir, si q = 1 la sucesin converge
R-lineal, as sucesivamente.
Definicin 1.1.4. Una sucesin {xn}, se llama uniformemente acotada, si existe unaconstante L > 0, tal que xn 6 L n. El numero L se llama cota uniforme de {xn}.Definicin 1.1.5. (Convergencia Global)
Un mtodo interactivo se dice que converge globalmente cuando la sucesin de puntos
producidos por los iterados del mtodo converge a la solucin donde el punto inicial
es arbitrario.
-
Referencias
24
-
Captulo2SOBRE UNA BSQUEDA LINEAL
TIPO ARMIJO Y SU RELACIN CON
EL MTODO DE REGIN DE
CONFIANZA
En este captulo presentamos un uso novedoso de la regla de Armijo y desarrolla-
mos un mtodo de bsqueda de lnea. En las secciones 2 y 3 se analiza la convergencia
global y la tasa de convergencia, respectivamente del nuevo mtodo. En la Seccin 4
se pone de manifiesto algunas relaciones entre el nuevo mtodo de bsqueda lineal y
el Mtodo de Regin Confianza. Conclusin declaraciones se dan en la seccin 5.
2.1. Un novedoso uso de la regla de ArmijoPrimero asumamos que:
(H1). La funcin objetivo f(x) es continuamente diferenciable y es acotada inferior-
mente en Rn.
(H2). El gradiente g(x) de f(x) es continuo uniformemente en un conjunto convexo
abierto B que contiene el conjunto de nivel L0 = {xRn|f(x) 6 f(x0)}, donde x0 esdado.
(H2). El gradiente g(x) de f(x) es Lipschitz continua en un conjunto convexo abierto
25
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 26
B que contiene el conjunto de nivel L0, es decir, existe M tal que
g(x) g(y) 6M x y, x, y B.Es evidente que (H2)mplica (H2) ver preliminares.
Definimos un nuevo uso de la Regla de Armijo o simplemente lo llamamos una
Nueva Bsqueda de Armijo.
Nueva Bsqueda de Armijo Dado (0, 12) y (0, 1), Bk es una aproximacin
de Gk = 2f(xk) y Bk es definida de la siguiente procuracin: tomar i el entero maspequeo tal que dTkBkdk+ idk2 > 0. Establecer sk = g
Tk dk
dTk Bkdky k es el mas grande
en {sk, sk, sk2, ..., } tal quefk f(xk + dk) > [gTk dk +
1
2dTkBkdk]
Algoritmo (A)
Paso 0. Elegir x0Rn y establecer k := 0.
Paso 1. Si gk = 0 entonces parar; si no ir al paso 2;Paso 2. Establecer xk+1 = xk + kdk, donde dk es una direccin de descenso de f(x)
en xk y k es seleccionado por la Nueva Bsqueda de Armijo;
Paso 3. Establecer k := k + 1.
Lema 2.1.1. Si (H1) se tiene y gTk < 0, entonces la Nueva Bsqueda de Armijo esta
bien definida.
Demostracin.
Por (H1), tenemos
lm0+[f(xk+kdk)fk 122dTkBkdk
] = lm0+[
f(xk+kdk)fk
] 12
lm0+[dTkBkdk]
= gkTdk 0,< gTk dk.
Por lo tanto, existe un k < 0, tal que
f(xk + kdk) fk 122dTkBkdk
6 gTk dk, [0, k].Luego,
f(xk + kdk) fk 6 gTk dk +1
22dTkBkdk, [0, k].
Entonces
fk f(xk + kdk) > [gTk dk +1
2dTkBkdk], [0, k].
Lo que implica que la Nueva Bsqueda de Armijo esta bien definida.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 27
2.2. Convergencia GlobalTeorema 2.2.1. Si (H1) y (H2) se cumplen, dk satisface (??)Y k es definida por la
Nueva Bsqueda de Armijo. Algoritmo (A) genera una secuencia infinita {xk}, conuna secuencia acotada {Bk}, esto es, hay un tal que Bk 6 ,k. Entonces
lmk
(gTk dkdk ) = 0 (2.1)
Demostracin.
Por contradiccin, Supongamos que existe un subconjunto infinitoK {0, 1, 2, 3, ....}y un > 0, tal que
gTk dkdk > , kK (2.2)
Entonces
gkTdk > dk, kK (2.3)Por la Nueva Bsqueda de Armijo, en el caso de dTkBkdk 6 0 (kK), tenemos:
fk fk+1 > k[gTk dk + 12kdTkBkdk]> kgTk dk (Y a que dTkBkdk 6 0)> kdk (Por (2.3));
Y en el caso de dTkBkdk > 0 (kK), tenemos:
fk fk+1 > k[gTk dk + 12kdTkBkdk]> k[gTk dk + 12skdTkBkdk] (Desde que k 6 sk)= 1
2kg
Tk dk (Sustituyendo sk y restando)
> 2kdk,kK (Por (2.3)).
De aqu vemos que en ambos casos llegamos a que fk fk+1 > 0, ya que k, , , sonescalares positivos, as fk > fk+1,kK, luego la funcin es montona decreciente yacotada inferiormente por (H1), con lo que tenemos que
lmk
fk fk+1 = 0, k K.
Esto, implica que
kdk 6 fk fk+1 0, (kK, k ) (2.4)En el paper se encuentra un pequeo error debido a que hacen la siguiente compa-
racin de un vector con un escalar; kdk 6 kdk
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 28
Tambin por la Nueva Bsqueda de Armijo, Bk 6 implica que
Bk 6 2 + 1, k. (2.5)
Sea K1 = {kK|k = sk}, K2 = {kK : k < sk},Podemos probar que K1 es un subconjunto finito. En efecto, si K1 es un subcon-
junto infinito, vemos que:
kdk = gTk dk
dkTBkdkdk (Sustituyendok) (2.6)
Por (2.5) tenemos
dTk Bkdk 6 (2 + 1)dk2 1
dTk Bkdk> 1
(2 + 1)dk2
As en ((2.6)) , tendramos
gTk dkdk
(2 + 1)dk2 6 gTk dk
dTk Bkdkdk = kdk 0(k K1, k ), (Por (2.5))
Que contradice (2.2). En consecuencia K2 debe ser un subconjunto infinito y k/ 6sk, kK2. Adems, tenemos que k es el mas grande tal que la desigualdad de laNueva Bsqueda de Armijo se cumple, con lo que = k/ har que la desigualdad
en la Nueva Bsqueda de Armijo falle, es decir,
fk f(xk + (/)dk) < (k/)[gTk dk +1
2dTkBkdk]
Por lo tanto
f(xk + (/)dk) fk > (k/)[gTk dk + 12(k/)dTkBkdk]> (k/)[gTk dk 12(k/)dTk Bkdk]> (k/)[gTk dk 12skdTk Bkdk] (k/ 6 sk)= 3
2(k/)g
Tk dk, kK2. (Sustituyendo sk = g
Tk dk
dTk Bkdk)
Usando el Teorema del valor medio en el lado izquierdo de la desigualdad anterior,
existe k[0, 1], tal que
f(xk + (/)dk) fk = (k/)g(xk + k(k/)dk)Tdk,
Luego
(k/)g(xk + k(k/)dk)Tdk >
3
2(k/)g
Tk dk, kK2.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 29
De aqu,
g(xk + k(k/)dk)Tdk >
3
2gTk dk, kK2. (2.7)
Restando a ambos lados gTk dkdk y acomodando tenemos:
(1 32)
gTk dkdk 6
[g(xk+k(k/)dk)gk]T dkdk
6 g(xk+k(k/)dk)gkdkdk (Por la desigualdad deCauchy Schwartz)= g(xk + k(k/)dk) gk 0(kK2, k ) (Por (2.4) y por (H2))
Lo que contradice (2.2) y por tanto, la conclusin es vlida.
Teorema 2.2.2. Si (H1) y (H2)se cumplen, dk satisface (??) y k es definida por la
Nueva Bsqueda de Armijo. Algoritmo (A) genera una secuencia infinita {xk} y Bkes uniformemente acotada, esto es, existe un > 0 tal que Bk 6 , k. Entonces
k=0
(gTk dkdk
2
) k[gTk dk + 12kdTkBkdk]> k[gTk dk + 12kdTk Bkdk] (dTk Bkdk > dTkBkdk)= 1
2kg
Tk dk (Evaluando=sk en el segundo termino)
= 2.(gTk dk)
2
dTk Bkdk(Sustituyendok por sk)
> 2(2+1)
(gTk dkdk2
), kK1. (Por(2.5))
As
fk fk+1 > 2(2 + 1)
(gTk dkdk
2
), k K1. (2.9)
En el caso de kK2 tenemos que k 6 sk, podemos probar similar a (2.7) que
g(xk + k(k/)dk)Tdk >
3
2gTk dk, kK2, (2.10)
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 30
Y por la desigualdad de Cauchy Schwartz, (2.5), (2.4) y restando a ambos lados porgTk dkdk , obtuvimos:
(1 32)gTk dkdk 6 g(xk + k(k/)dk) gk, kK2
Por lo que (H2)mplica que existe un M tal que:
(1 32)
gTk dkdk 6 g(xk + k(k/)dk) gk
6 M k/dk, (M = kM)(kK2)Y que despejando a k, obtenemos:
k >(1 3
2)
M gTk dkdk2 , kK2. (2.11)
Por consiguiente,
fk fk+1 > k[gTk dk + 12kdTkBkdk]> k[gTk dk + 12skdTk Bkdk] (kdTkBkdk 6 skdTk Bkdk)= k[gTk dk 12gTk dk] (Sustituyendo sk)= 1
2kg
Tk dk
> (132)
2M (gTk dkdk )
2, kK2. (Por (2.10))
Por la inecuacin (2.9) y tomando
=
2min(
1
2 + 1,(1 3
2)
M ),
Se tiene que:
ff fk+1 > (gTk dkdk )
2, k. (2.12)
Por (H1) f es continuamente diferenciable y acotada por debajo y adems la funcin
es decreciente, as
k=0
(gTk dkdk )
2 6k=0
(fk f > k + 1) < +.
Esta desigualdad implica que (2.8) se cumple.
Corolario 2.2.3. Si (H1) y (H2) se cumplen, dk satiface (??) y k es definida por
la Nueva Bsqueda de Armijo. Algoritmo (A) genera una secuencia infinita {xk} yBk 6 , k. Entonces
lmkgk = 0 (2.13)
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 31
Demostracin.
Por Teorema (2.2.1), se tiene:
gk 6 gTk dk
gkdk= gTk dkdk 0, (k ).
La prueba termina.
2.3. Razn de ConvergenciaEn orden de analizar la razn de convergencia, adems asumimos que:
(H3). xk x cuando k , 2f)x0 y f(x) es dos veces continuamente dife-renciable en N(x, 0) = {x|x x < 0}.Lema 2.3.1. Asumamos que (H3) se cumple. Entonces existe 0 < m 6 M y 6 0tal que:
my2 6 yT2f(x)y 6M y2,x, y N(x, ); (2.14)1
2mx x2 6 f(x) f(x) 6 1
2M x x2,x N(x, ); (2.15)
M x y2 > (g(x) g(y))T (x y) > mx y2, x, y N(x, ); (2.16)Y as,
M x x2 > g(x)T (x x) > mx x2,x N(x, ); (2.17)Por (2.17) y (2.16) podemos obtener, de la desigualdad de Cauchy Schwartz, que
M x x2 > g(x) > mx x2, x N(x, ); (2.18)
Y
g(x) g(y) 6M x y2,x, y N(x, ); (2.19)La prueba se puede encontrar en la literatura de
2.3.1. Convergencia Lineal
Teorema 2.3.2. Asumir que (H3) se cumple, dk satisface (??) y k es definida por
la Nueva Bsqueda de Armijo y que Bk 6 ,k. Si el Algoritmo (A) genera unsecuencia infinita {xk}, entonces {xk} converge a x por lo menos R-lineal.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 32
Demostracin.
Si (H3) se cumple entonces existe un ktal que xk in N(x, 0), k > k y (H1) y(H2)se cumplen si x0 in N(x, 0). Por Teorema (2.2.2) y (??) tenemos:
ffk+1 > (gTk dkdk )
2
> 2gk, k > k (Por(??))
Por la desigualdad anterior y lema ??, Haciendo = 2, se obtiene
ffk+1 > gk> m2xk x2 (Por(2.18))> 2m2
M (fk f ). (Por(2.15))Sea
= m
2
M > 0
Probemos que < 1. En efecto, por la definicin de y en la prueba del Teorema
(2.2.2), se obtiene:
2 = 2m2
M =2m22
M
6 2m22M
(1 32)
2M (Por )
6 2(1 32). (0 < m 6M )
6 (1 32). (0 < 6 1)
< 1. (0 < 6 1/2)(0 < < 1)
Definamos
0 < w =
1 2 < 1Retomando la desigualdad de arriba que
fk fk+1 6 2(fk f ) fk f fk+1 + f 6 2(fk f ) fk+1 f > (fk f ) 2(fk f )
Luego,fk+1 f > (1 2)(fk f )
= w2(kk+1)(fk f )6 w2(k(k1)+1)(fk1 f )
...
6 w2(k(k+1)+1)(fk+1 f )= w2(kk
)(fk+1 f ).
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 33
Esto y por (2.15)de el Lema (2.3.1) se tiene
xk+1 x2 6 2m (fk+1 f )6 w2(kk) 2(fk+1f
)m
As
xk+1 x 6 wkk
2(fk+1 f )m
Es decir, que si cambiamos el subndice k por k 1, tenemos
xk x 6 wk1k
2(fk+1f)m
= wk
wk+1
2(fk+1f)
m
= wk
2(fk+1f)mw2(k+1) .
Notemos que
2(fk+1f)mw2(k+1) es una constante, y aplicando la raz k-esima y limite a
ambos lados, tenemos finalmente que:
R1{xk} = lmkxk x 1/k 6 lm
kw(
2(fk+1 f )mw2(k+1)
)1/2k = w < 1
Que muestra que {xk} converge a x al menos R-Lineal.
2.4. Convergencia SuperlinealSupongamos adems que,
(H4). {BBk} es una secuencia de matrices definida positiva y Bk 6 , k. Algo-ritmo (A) con dk = B1k gk satisface la siguiente condicin
lmk
[Bk 2f(x)]dkdk = 0 (2.20)
Lema 2.4.1. Si (H3) y (H4) se cumplen. Algoritmo (A) genera una secuencia infinita
{xk}. Entonces existe ktal que
k = 1,k > k. (2.21)
Demostracin.
Por corolario (2.2.3) y (H4)
lmkgk = 0 lm
k B1k gk = 0
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 34
Esto y por (H3), implica que
lmk
xk = x, lm
kdk = 0, (2.22)
Y as
lmk
(xk + tdk x) = 0, (2.23)Donde t [0, 1]. Adems, (H4) implica que
0 6 lmk dTk [Bk2f(x)]dk
dk2
6 lmk dk[Bk2f(x)]dk
dk2
= lmk[Bk2f(x)]dk
dk2
Luego
dTk [Bk 2f(x)]dk = o(dk2). (2.24)En el paper presenta un detalle al declarar que es el teorema del valor medio, pero
la validez de la siguiente igualdad es por el teorema fundamental de calculo:
f(xk + dk) fk = gTk dk + 1
0
(1 t)dTk2f(xk + tdk)dkdtEn efecto,
gTk dk + 1
0(1 t)dTk2f(xk + tdk)dkdt = gTk dk +
10dTk2f(xk + tdk)dkdt
10tdTk2f(xk + tdk)dkdt
= gTk dk +f(xk + dk)Tdk gTk dk 1
0tdTk2f(xk + tdk)dkdt
= f(xk + dk)Tdk 1
0tdTk2f(xk + tdk)dkdt,
Integrando por parte, con u = t ydv = dTk2f(xk + tdk)dkdt,gTk dk +
10
(1 t)dTk2f(xk + tdk)dkdt = f(xk + dk)Tdk f(xk + dk)Tdk+ 1
0f(xk + tdk)dkdt
= 1
0f(xk + tdk)dkdt
= f(xk + dk) fksi para un k suficiente grande, tenemos:
f(xk + dk) fk = gTk dk + 1
0(1 t)dTk2f(xk + tdk)dkdt
= [gTk dk +12dTkBkdk] +
10
(1 t)dTk [2f(xk + tdk)2f(x)]dkdt+ 1
2dTk [2f(x)Bk]dk
= [gTk dk +12dTkBkdk] + o(dk2). (Por (2.23)) y (2.24))
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 35
Donde dk = B1k gk, sustituimos en la desigualdad derecha anterior vemos que,
gTk dk +12dTkBkdk = g
Tk dk 12gTk dk. (Porque gTk dk R).
= 12gTk dk
< 0. (Por(??))
Por esto y (2.22), se tiene en la igualdad de arriba que:
f(xk + dk) fk = [gTk dk +1
2dTkBkdk] + o(dk2) 6 [gTk dk +
1
2dTkBkdk]
Lo que implica que existe un kpara que el (2.21) es valida.
Teorema 2.4.2. Si (H3) y (H4) se cumplen. Algoritmo (A) genera una sucesin infinita
{xk}. Entonces {xk} converge a x superlinealmente.Demostracin.
Por Corolario (2.2.3) y Lema (2.3.1) sabemos que {xk} x. Por Lema (2.4.1),existe ktal que (2.21)) se cumple y tenemos:
xk+1 = xk + dk, k > k (2.25)
Donde dk = B1k gk. Por el teorema fundamental del calculo se sigue que:
gk+1 gk = 1
02f(xk + t(xk+1 xk))(xk+1 xk)dt
= 1
02f(xk + tdk)dkdt. (Por (2.25))
= 2f(x)dk + 1
0[2f(xk + tdk)2f(x)]dkdt
Veamos que:
lmk
2f(xk + tdk)2f(x)]dkdk 6 lmk
2f(xk + tdk)2f(x)]dkdk = 0
Asi 1
0[2f(xk + tdk)2f(x)]dkdt = o(dk) y en la igualdad de arriba obtendra-
mos:gk+1 = gk +2f(x)dk + o(dk)
= Bkdk +2f(x)dk + o(dk)= [Bk 2f(x)]dk + o(dk)= o(dk). (Por (2.20))
Entonces
lmk
gk+1dk = 0 (2.26)
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 36
De (2.18) y (2.26) se deduce que:
gk+1dk >
mxk+1xdk
= mxk+1xxk+1xk (Por (2.25))
> mxk+1xxk+1x+xkx= m
xk+1xxkx
1+xk+1xxkx
Y as
lmk
xk+1 xxk x = 0
Lo que implica que {xk} converge a x Superlinealmente.
2.5. Convergencia CuadrticaSi tomamos Bk = 2f(xk) en el Algoritmo (A), entonces (H4) se cumple. y
tenemos el siguiente resultado.
Teorema 2.5.1. Si (H3) se cumple, Bk = 2f(xk) para k suficiente grande. Algo-ritmo (A) genera una sucesin infinita {xk}. Entonces {xk} converge a x al menosSuperlinealmente.
Demostracin.
En este caso, (H4) se cumple automticamente, en consecuencia el resultado del
Teorema (2.4.2) se cumple.
Teorema 2.5.2. Si (H3) se cumple, Bk = 2f(xk) para k suficiente grande. Adems,existe una epsilon vecindad N(x, ) = {x Rn|x x < } de x con < 0 talque 2f(x) es Lipschitz continua en N(x, ), es decir, existe L() tal que
2f(x)2f(y) 6 L()x y, x, y N(x) (2.27)
Algoritmo (A) genera una secuencia infinita {xk}. Entonces {xk} converge a xCuadrticamente.
Demostracin.
Por Corolario (2.2.3), Lema (2.3.1) y (2.4.1), se sigue que {xk} converge a x y existektal que para todo k > k, xk N(x, ), Bk = 2f(xk), y k = 1. Sea k = xkx.Por teorema fundamental del calculo tenemos:
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 37
k+1 = xk+1 x= xk x + dk (Por (2.25))= k 2f(xk)1gk= k 2f(xk)1(gk g)= k 2f(xk)1
102f(x + tk)kdt
= 2f(xk)1[2f(xk) 1
02f(x + tk)kdt]
= 2f(xk)1 1
0[2f(xk)2f(x + tk)]kdt
Esto y (2.27) implica que:
k+1 = 2f(xk)1 1
0[2f(xk)2f(x + tk)]kdt
6 2f(xk)1 1
02f(xk)2f(x + tk)dtk
6 |2f(xk)1L() 1
0xk + tk xkdtk
= |2f(xk)1L()k2 1
0tdt
= 122f(xk)1L()k2.
Por lo tanto,
lmk
k+1k
Con lo que {xk} converge a x Cuadrticamente.
2.6. Relacin con el Mtodo de Regin de ConfianzaLa relacin entre el mtodo de lnea nueva bsqueda y el mtodo de regin de
confianza se dar a conocer en esta seccin.
Ya vimos en el Captulo 1 El Mtodo de Regin de Confianza, el cual se basa en
buscar una solucin al subproblema
minpRnmk(p) = fk + gTk p+1
2pTBkp, s.t.p 6 k, (2.28)
Dnde k es de un radio de la Regin de Confianza. Definimos por la normaeuclidiana, de modo que la solucin pk de (2.28) es el reductor de mk(p) en la bolade radio k. Por lo tanto, el Mtodo de Regin de Confianza nos obliga a resolver
una secuencia del subproblemas (2.28) en el que la funcin objetivo y restricciones (
Que se puede escribir como pTp 6 2k) son ambos cuadrticos.El primer problema que surge en la definicin del Mtodo de Regin de Confian-
za es la estrategia para la eleccin del radio de la regin la confianza k en cada
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 38
iteracin. Con base a esta eleccin en la relacin entre el modelo mk y la funcin
objetivo f en la anterior iteraciones, se define la relacin de reduccin
rk =fk f(xk + pk)mk(0)mk(pk) , (2.29)
Y la influencia de esta relacin de reduccin en la eleccin de dicho radio k la vimos
en el Algoritmo(2) del Captulo 1.
La convergencia global del Mtodo de Regin de Confianza depende de las reduc-
ciones obtenidas en la solucin del modelo cuadrtico mk. Pero, no requiere resolver
el subproblema (2.28) del Mtodo de la Regin de confianza con exactitud, podemos
encontrar un pk que satisfaga:
mk(0)mk(pk) > c1gkmin(k, gkBk), (2.30)
Y
pk 6 k, (2.31)Para > 1 y c1 (0, 1]. Lo cual garantiza la convergencia del mtodo.
En efecto, la solucin exacta P k de (2.28) satisface (2.30) y (2.31) ([3]). Basta
ver que mk(0)m(pk) > mk(0)mk(pk),pk y k.Lema 2.6.1. Sea = 0 en el Algoritmo(2). Supongamos que Bk 6 para algunaconstante , que f es Lipschitz continua diferenciable y acotada inferiormente en el
conjunto de nivel
L0 = {x R|f(x) 6 f(x0)},Y que la aproximacin de la solucin de (2.28) satisface (2.30) y (2.31) para cons-
tantes positivas c1 y . Entonces se tiene
lmkgk = 0 (2.32)
Lema 2.6.2. Sea (0, 14) en el Algoritmo(2). Supongamos que Bk 6 para
alguna constante , que f es Lipschitz continua diferenciable y acotada inferiormente
en el conjunto de nivel L0, Y que la aproximacin de la solucin de (2.28) satisface
(2.30) y (2.31) para constantes positivas c1 y . Entonces se tiene
lmkgk = 0 (2.33)
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 39
En la Nueva Bsqueda de Armijo, si el conjunto p=kdk entonces
fk f(xk + pk) > [gTk pk 1
2pTkBkpk]
Y xk+1 = xk + pk es solo una aceptable reduccin en el Mtodo Regin de Confianza
y sabemos que mk(0)mk(pk) = fk fk gtkpk 12pTkBkpk = gTk pk 12pTkBkpk > 0,tenemos
rk =fk fk+1
mk(0)mk(pk) > , (2.34)
Es obvio que (2.34) coincide con la condicin de aceptacin en (??).
Este rk es justamente la relacin de la reduccin actual y la reduccin predicha.
Si la relacin anterior se cumple entonces el nuevo punto xk = xk + pk es aceptado
tanto por la Nuevo Mtodo de Bsqueda lineal como por el Mtodo de Regin de
Confianza. De lo contrario, debemos ajustar el tamao de paso en el Nuevo Mtodo
de Bsqueda lineal o ajustar el radio de la regin de confianza en el Mtodo de Regin
de Confianza. De hecho, si el nuevo punto xk = xk+pk es rechazado, debemos reducir
el tamao del paso en el Nuevo Mtodo de Bsqueda lineal o reducir el radio de la
regin de confianza en el Mtodo de Regin de Confianza. Desde este punto de vista,
el Mtodo de Regin de Confianza y el Mtodo de Bsqueda Lineal se pueden unificar
en una forma general.
-
Sobre una nueva bsqueda lineal tipo armijo y su relacin con elmtodo de region de confianza 40
2.7. ConclusinEn esta Investigacin se utiliza La Bsqueda Lineal Tipo Armijo en una forma
novedosa y proponen un Nuevo Mtodo de Bsqueda Lineal para problemas de
optimizacin sin restricciones. La convergencia global y razn de convergencia del
Nuevo Mtodo se analizan en leves condiciones. Adems, cada iteracin generada por
La Nueva Bsqueda Lineal tipo Armijo se demuestra que es una solucin aproximada
del subproblema de correspondiente al Mtodo de Regin de Confianza, lo que revela
la relacin entre el Mtodo Bsqueda lineal y el Mtodo de Regin de Confianza,
en cierto sentido. Para ponerlo en detalle, si tomamos pk = kdk en el propuesto
Mtodo de Bsqueda Lineal entonces, se tiene la condicin de aceptacin
rk = fk fk+1gTk dk +
12pTkBkpk
>
Que es exactamente la condicin de avance en el Mtodo de Regin de Confianza.
Por otra parte, cabe destacar que el paper presenta algunos errores, que fueron
arreglados en la desarrollo de la Investigacin, y que se mencionan a continuacin:
La ecuacin (2.4), era originalmente kdk 6 kdk, pero esta fue cambiadadebido a que no cabe comparar un vector con un nmero real.
En el Lema (2.6.1), falta la premisa de que la funcin f sea Lipschitz Continua,
ya que es una hiptesis fundamental para la demostracin del Lema (ver [1]).
Adems, la definicin de L0 (2.6.1) en el mismo Lema, f(x0) en el paper es
f(x1) lo cual no concuerda con la definicin de conjunto de nivel.
En el Lema (2.6.2) el paper menciona el Algoritmo (2.1), el cual adems de
no encontrarse en el paper es una referencia equivocada, realmente se quera
referir al Algoritmo (2).
-
Referencias bibliogrficas.
[1] P.-A. Absil, C. G. Baker, and K. A. Gallivan,Trust-region methods on
Riemannian manifold with applications in numerical linear algebra, Pro-
ceedings of the 16th International Symposium on Mathematical Theory of
Networks and Systems (MTNS2004), Leuven, Belgium, 5-9 July 2004, 2004.
[2] Zhen-Jun Shi y Xiang-Sun Zhang. From Line Search Method to Trust Re-
gion Method. Operations Research and Its Applications, Lecture Notes
in Operations Research, vol.5, pp.156-170,World Publishing Corporation,
2005.
[3] J. Nocedal and J. S. Wright, Numerical Optimization, Springer-Verlag New
York, Inc.(1999).
[4] Bertsekas D. Nonlinear Programming,Athena Scientic, 2000.
41
AgradecimientosResumenPRELIMINARESDireccin de DescensoDireccin de NewtonOtras Direcciones de DescensoCondicin de Suficiente Descenso para dk MTODO DE BSQUEDA LINEALMtodo de Regin de Confianza
Razn de Convergencia
ReferenciasSOBRE UNA BSQUEDA LINEAL TIPO ARMIJO Y SU RELACIN CON EL MTODO DE REGIN DE CONFIANZAUn novedoso uso de la regla de ArmijoConvergencia GlobalRazn de ConvergenciaConvergencia Lineal
Convergencia SuperlinealConvergencia CuadrticaRelacin con el Mtodo de Regin de ConfianzaConclusin
Referencias bibliogrficas.