Universidad Nacional de Ingenierı́a

Facultad de Ciendias
Escuela Profesional de Matemática Ciclo 2020-II

[Cod: CM-454-A] [Curso: Programación no Lineal]

[Profesor: Jesús Cernades Gómez]

Sexta Práctica Dirigida de

Programación no lineal

1. Considere el esquema iterativo dado por xk+1 = xk + αk dk , k = 1, 2, , · · · , donde

c1 kf 0 (xk )kp1 ≤ −hf 0 (xk ), dk i, kdk k ≤ c2 kf 0 (xk )kp2

c1 , c2 > 0, p1 , p2 ≥ 0, y el comprimento de paso αk es calculado por la regla de Armijo.

2. El método del gradiente no depende del valor α, es decir, a partir de un mismo xk

siempre se obtiene (para cualquier α > 0) el mismo xk+1 usando la búsqueda lineal.
Se puede tomar entonces dk = −∇f (xk ) o dk = −k∇f (xk )k−1 ∇f (xk ).

3. Demuestre que la segunda elección corresponde a la solución óptima del problema

mı́n[h∇f (xk ), di | kdk ≤ 1].

d

de donde el nombre de método de la máxima pendiente.

4. Pruebe que si 0 < c2 < c1 < 1, puede que no haya longitudes de paso satisfaciendo la
condición de Wolfe.

5. Pruebe que kBxk ≥ kxk/kB −1 k para cualquier matriz no singular B.

6. Pruebe
(∇fkT ∇fk )2
 
kxk+1 − x∗ k2Q = 1− kxk − x∗ k2Q
(∇fk Q∇fk )(∇fkT Q−1 ∇fk )
T

siguiendo los siguientes pasos,

∇fkT ∇fk
 
a) Use xk+1 = xk − ∇fk para mostrar
∇fkT Q∇fk
kxk − x∗ k2Q − kxk+1 − x∗ k2Q = 2αk ∇fkT Q(Xk − x∗ ) − αk2 ∇fkT Q∇fk ,

donde, k · k2Q = xT Qx.

b) Use el hecho que ∇fk = Q(xk − x∗ ) para obtener
2(∇fkT ∇fk )2 2(∇fkT ∇fk )2
kxk − x∗ k − kxk+1 − x∗ k = −
(∇fkT Q∇fk ) (∇fkT Q∇fk )
y
kxk − x∗ k2Q = ∇fkT Q−1 ∇fk .
Dirigida de Programación no Lineal 2 Programación no Lineal 2020

7. Sea Q una matriz simétrica definida positiva. Pruebe que para cualquier vector x,
tenemos
(xT x)2 4λn λ1
T T −1
≥ ,
(x Qx)(x Q x) (λn + λ1 )2
donde λn y λ1 son respectivamente, el mayor y menor valor propio de Q.

8. Programe el algoritmo BFGS usando el algoritmo de búsqueda de lineal. Haga

que el código y verifique que y T ksk es siempre positivo. Resolver el problema de
minimización con f (x) = 100(x2 − x21 )2 + (1 − x1 )2 , con punto inicial x0 = (1,2, 1,2) y
x0 = (−1,2, 1).

9. Programe algoritmo de descenso y Newton usando búsqueda lineal en retroceso.

Use esto para minimizar la función f (x) = 100(x2 − x21 )2 + (1 − x1 )2 . Pruebe como
punto inicial x0 = (1,2, 1,2) y x0 = (−1,2, 1)

10. Programe el método de región de confianza. Escoja Bk la Hessiana exacta, y use

esto para minimizar la función
n
X
min f (x) = [(1 − x2i−1 )2 + 10(x2i − x22i−1 )2 ]
i=1

con n = 10. Experimente con un punto inicial y un test de parada.

11. Pruebe que la secuencia (kgk k) generada por el algoritmo de la región de confianza
tiene un punto de acumulación a cero. Pruebe que si la iteración x pertenecen a un
conjunto acotado B, entonces existe un punto lı́mte x∞ de la secuencia {xk } tal que
g(x∞ ) = 0.

12. Pruebe que τk definido por


 1 si gkT Bk gk ≤ 0
τk =
 mı́n(kgk k2 /(4k g T Bk gk ), 1) otro caso.
k

de hecho identifica el minimizador de mk (p) = fk + gkT p + 21 pT Bk p, a lo largo de la

dirección −gk = ∇f (xk ). en el algoritmo de región de confianza.

13. Tomando x0 = (−2, 1), hacer dos iteraciones del método de máximo descenso para la
función
f : R2 → R, f (x) = x21 + x1 x2 + 2x22 + x1 .

14. tomando x0 = (1, −1), hacer una iteración del método del gradiente para la función

f : R2 → R, f (x) = 2x21 + x1 x2 + 3x22 ,

utilizando la regla de Armijo, con parámetros α̂ = 1 y δ =∴= 21 .

Dirigida de Programación no Lineal 3 Programación no Lineal 2020

15. Sea {xk } una secuencia generada por xk+1 = xk + αk dk , k = 1, 2, · · · , donde

c1 kf 0 (xk )k2 ≤ −hf 0 (xk ), dk i, kdk k ≤ c2 kf 0 (xk )k,

c1 , c2 > 0, y la secuencia αk ⊆ R+ satisface

∞
X
lı́m αk = 0, αk = +∞.
k→∞
k=0

Sea f acotada inferiormente y sea la derivada de f Lipschitz-continua en Rn . Pruebe

que la secuencia {f (xk )} convere y que lı́m ı́nf kf 0 (xk )k = 0. Más aun si los conjuntos
k→∞
de nivel {x ∈ Rn | f (x) ≤ c} sin acotados para todo c ∈ R, entonces la secuencia {xk }
es acotada y todo punto de acumulación de {xk } es punto estacionario del problema
mı́n f (x).

16. Sea {xk } una secuencia generada por xk+1 = xk + αk dk , k = 0, 1, · · · , donde αk

es calculada por la regla de Armijo, dk = −(0, · · · , 0, fx0 i (xk ), 0, · · · , 0), y ı́ndice i ∈
{1, · · · , n} satisface |fx0 i (xk )| = máxj=1,··· ,n |fx0 j (xk )|,. Supongamos que la función f es
continuamente diferenciable, pruebe que todo punto de acumulación de {xk } es
punto estacionario de problema de mı́n f (x).

17. Sea f una función continuamente diferenciable. Suponiendo que, dado un punto
xk ∈ Rn , la dirección dk ∈ Rn sea escogida de manera que garantice que cuando
una subsecuencia {xki } converge a un punto no estadcionario para el problema
mı́n f (x), entonces lı́m ı́nfhf 0 (xki ), dki i < 0. Sea {xk } una secuencia generada por
i→∞
xk+1 = xk + αk dk , k = 0, 1, · · · , donde αk es calculado por la regla de Armijo. Pruebe
que todo punto de acumulación de {xk } es punto estacionario del problema mı́n f (x).

18. Sea {xk } una secuencia generada por xk+1 = xk + αk dk , k = 0, 1, · · · , donde dk =

−f (xk ) + k , kk k ≤ δ, ∀k. Supongamos que la secuencia {xk } sea acotada. Pruebe que
para todo c > δ, existe c2 ≥ c1 > 0 tales que si αk ∈ [c1 , c2 ], entonces la secuencia {xk }
posee un punto de acumulación que pertenece al conjunto {x ∈ Rn | kf 0 (xk )k ≤ c}.

19. A partir del punto x0 = 1, hacer dos iteraciones del método de Newton para la
ecuación xp = 0, donde p ≥ 2 es un parámetro entero. Abalizar la tasa de convergencia
y explicar el fenómeno observado. Modificar el método de Newton introduciendo la
longitud de paso igual a p es analizar tasa de convergencia de nuevo.

20. Sea la función Φ : R → R diferenciable p veces en el punto x̄ ∈ R, p ≥ 2, donde x̄ es

una raı́z de orden p de la ecuación Φ(x) = 0,, es decir,

Φ(x̄) = Φ0 (x̄) = · · · = Φ(p−1) (x̄) = 0, Φ(p) (x̄) =6= 0.

Entonces el método de Newton converge localmente a x̄ con tasa lineal, y si

introducirnos la longitud de paso igual a p, la tasa de convergencia se torna
superlineal.
Dirigida de Programación no Lineal 4 Programación no Lineal 2020

21. Pruebe el método de Newton es invariante en relaci

on a las transformaciones lineales de variables, en el sentido siguiente. Sea x = Ay una
transformación de variables, dad por una matriz no singular A ∈ R(n, n). Entonces si
el método de Newton en varibles y genera una secuncia {y k } y en variables x genera
una secuencia {xk }, se tiene que y k = A−1 xk .

22. Hacer dos iteracines del método de Newton a partir del punto x0 = (1, 1) para el
problema de minimización irrestrita de la función

x2
f : R2 → R, f (x) = x2+e
1
2

Analisar la tasa de convergencia. Muestre que, en este caso el método de Newton

posee convergencia global.

23. Considere el método de Newton para minimizar la función

f : R → R, f (x) = x2 + cos x.

Pruebe que f es dos veces diferenciables en una vecindad de x = 0, con segunda

derivada contı́nua en ese punto y que x0 = 2πi donde i ∈ {1, 2, · · · }, la secuencia
generada por el método de Newton no converge.

24. Aplicar el método de Newton para minimizar la función

f : Rn → R, f (x) = kxk3 .

Analizar la tasa de convergencia y explicar lo observado.

25. Pruebe que los métodos DFP y BFGS tiene una relación de dualidad en sentido
siguiente: Para una matriz simétrica difinida positiva Qk ∈ R(n, n), definimos
Hk = Q−1
k . Sea la matriz Qk+1 generada por BFGS, y la matriz Hk+1 generada por

sk (sk )T (Hk rk )(Hk rk )T

Hk+1 = Hk + −
hrk , sk i hHk rk , rk i

suponiendo que Hk+1 sea no singular. Entonces la matriz Qk+1 es no singular y se

tiene que Hk+1 = Q−1
k+1

26. Sea f : Rn → R una función dos veces continuamente diferenciable. Considerar el

siguiente algoritmo. Sea σ ∈ (0, 1/2) θ ∈ (0, 1) parámetros escogidos. Si f 00 (xk ) es no
singular, tomar dk = −(f 00 (xk ))−1 f 0 (xk ), si no, tomar dk = 0. Tomar hk = −f 0 (xk ).
Calcular
xk+1 = xk + αk ((1 − αk )hk + αk dk ),

donde αk es el mayor entre todos los números de la forma θs , s ∈ N, satisfaciendo

f (xk + θs ((1 − θs )hk + θs dk )) ≤ f (xk ) − δθs hf 0 (xk ), (1 − θs )hk + θs dk i.

Dirigida de Programación no Lineal 5 Programación no Lineal 2020

a) Pruebe que el método está bien definido.

b) Pruebe que todo punto de acumulación de una secuencia {xk } ası́ generada, es
un punto estacionario del problema mı́n f (x)

c) Pruebe que si {xk } converge a un punto estacionario x̄ donde f 00 (x̄) es definida

positiva, entonces la tasa de convergencia de {xk } a x̄ es superlineal.

27. Supongamos que para los puntos xk ∈ Rn y xk+1 ∈ Rn y los puntos dk−1 ∈ Rn y d ∈ Rn ,
generado por el métdo de los gradientes conjugados para algún k ≥ 1, se tiene que
hf 0 (xk ), dk−1 i = 0 y hf 0 (xk+1 ), dk h= 0. Pruebe que la dirección dk , calculada de acuerdo
con d0 = −f 0 (x0 ), dk = −f 0 (xk ) + βk−1 dk−1 , y

hf 0 (xk ), f 0 (xk ) − f 0 (xk−1 )i

βk−1 =
kf 0 (xk−1 )k2

puede ser representada por dk+1 = −Qk+1 f 0 (xk+1 ), donde Qk+1 es dada por el método
BFGS con Qk = E n matriz unitaria.

28. Utilizando el método de los gradientes conjugados, con punto inicial x0 = (1, 1),
encontrar el minimizador irrestricto de la función

f : Rn → R, f (x) = x21 + 2x22 .

m
X
29. Sea Q ∈ R(n, n) dada por Q = A+ y i (y i )T , donde A ∈ R(n, n) es una matroz simétrica
i=1
definida positiva y y i ∈ Rn , i = 1, · · · , m, son vectores arbitrarios. Pruebe que el
iterando xk+1 generado por el métdo del gradiente conjugado satisface la relación
 
k+1 cn − c1
f (x ) ≤ f (x0 ),
cn + c1

donde cn y c1 son el mayor y el menos valor propio de la matriz A, respectivamente.

30. Para el método del gradiente conjugado aplicado a a función f (x) = hQx, xi + hq, xi,
donde Q ∈ R(n, n) es una matriz simétrica definda positiva, pruebe que la iteración
xk minimiza a f en el conjunto x0 + span{f 0 (x0 ), Qf 0 (x0 ), · · · , Qk−1 f 0 (x0 )}.

UNI, 11 de enero del 2021*

*
Hecho en LATEX