Ejercicios_Pep1_resueltos (1)

Vista previa del material en texto

Ejercicios - OPTI II
Profesor Francisco Jara
Año 2019 - 1er Semestre
1. Sea desea colocar una ampolleta en el centro de una pieza de base circular
de radio r. La intensidad con que llega la luz de la ampolleta a algún punto
del suelo es proporcional al seno del ángulo α formado entre el haz de luz
y el suelo, e inversamente proporcional a la distancia d entre ese punto
y la ampolleta. Calcule la altura óptima h∗ en que debe ir la ampolleta
de manera que la intensidad en el borde de la pieza (i.e. en los puntos a
distancia r del centro) sea máxima.
h
r
d
α
Solucion: Tenemos que la intensidad I es proporcional a sinα y a 1d .
Notemos que sinα = hd y d
2 = r2 + h2. Por lo tanto,
I(h) = κ
sinα
d
= κ
h
d2
= κ
h
r2 + h2
,
donde κ es una constante de proporcionalidad. Derivando I(h) e igualando
1
a cero, obtenemos
0 = I ′(h)
=
r2 + h2 − 2h2
(r2 + h2)2
=
r2 − h2
(r2 + h2)2
,
lo que implica h∗ = r. Notemos que
I ′′(h∗) = I ′′(r)
=
−2r(r2 + r2)2 − 4r(r2 − r2)(r2 + r2)
(r2 + r2)4
=
−4r5
2r8
= −2 1
r3
< 0.
Por lo tanto, h∗ es un máximo.
2. Sea f una función convexa y considere el problema de minimizar f sobre
un intervalo [a, b]. Es decir,
mı́n
x∈[a,b]
f(x) (1)
Sea x∗ un mı́nimo global (sin restricción) de f . Es decir, x∗ es solución de
mı́n
x∈R
f(x) (2)
(a) Muestre que si x∗ < a entonces a es una solución del problema (1).
Solución: Como x∗ es solución del problema irrestricto, entonces
para todo z ∈ R, se tiene que f(x∗) ≤ f(z). Tomemos entonces un
z ∈ (a, b]. Como se tiene x∗ < a < z, entonces existe λ ∈ (0, 1) tal que
a = λx∗+(1−λ)z (En efecto, considerar λ = z−az−x∗ la cual claramente
está entre 0 y 1). Como f es convexa se tiene que
f(a) = f(λx∗ + (1− λ)z)
≤ λf(x∗) + (1− λ)f(z)
≤ λf(z) + (1− λ)f(z)
= f(z).
Es decir, f(a) ≤ f(z). Como z se eligió en (a, b] de manera arbitraria,
se tiene que f(a) ≤ f(z), para todo z ∈ (a, b] lo que demuestra el
resultado.
2
(b) Muestre que la función ln(x)x es estrictamente decreciente en el inter-
valo [e,∞).
Solución: Basta con evaluar la derivada de f(x) = ln(x)x .
• f ′(z) =
x
x−ln(x)
x2 =
1−ln(x)
x2
Si x ≥ e, entonces 1− ln(x) ≤ 0, siendo desigualdad estricta si x > e.
Como f ′(x) < 0, entonces f es estrictamente decreciente.
(c) Usa la parte (b) para mostrar que si e ≤ a < b, entonces ab > ba.
Solución: Como f es estrictamente decreciente en [e,∞), tenemos
que ln(a)a >
ln(b)
b , lo que implica ln(a)b > ln(b)a, que a su vez implica
(usando la exponencial en cada lado de la desigualdad) que ab =
eln(a)b > eln(b)a = ba.
(d) Concluya que eπ > πe.
Solución: Tomar a = e y b = π, y se tiene el resultado.
3. Una empresa de art́ıculos de campamento desea rediseñar su ĺınea de car-
pas. Parte del proceso de renovación es definir las dimensiones de cada
carpa, dada una cantidad fija de lona, de manera que el volumen sea lo
más grande posible. Si la superficie disponible para hacer una carpa es de
40 cm2, encuentre las dimensiones que maximicen el volumen. Justifique
su respuesta. Para simplificar, puede suponer que la carpa tiene forma de
prisma de base triangular equilátera.
b2a
2a2a
Solución: La fórmula par el volumen de la carpa es
V (a, b) = 4a2
√
3
2
b
. La superficie está dada por
S(a, b) = 4a2
√
3 + 6ab.
3
Como está la condición S(a, b) = 40, podemos despejar b en función de a.
Entonces, b = 40−4a
2
√
3
6a . Reemplazando en V (a, b), obtenemos
V (a, b) = V (a) = 4a2
√
3
2
(
40− 4a2
√
3
6a
)
=
40a
√
3
3
− 4a3.
Derivando e igualando a cero se tiene la ecuación
V ′(a) =
40√
3
− 12a2 = 0,
lo que implica a∗ =
√
10
3
√
3
. Notemos que
V ′′(a) = −24a =< 0,
por lo tanto, V (a) es cóncava cuando a es positiva. Es decir, a∗ es efecti-
vamente un máximo. Por último tenemos b =
40− 403
6
√
10
3
√
3
= 80√
30√
3
.
4. Dos empresas deben fijar el precio de un producto cuya demanda es K. Si
los precios fijados son p1 y p2, la utilidad de la empresa 1 es U1(p1, p2) =
ln(p1) + ln(K − p1 − p2) y la de la empresa 2 es U2(p1, p2) = ln(p2) +
ln(K − p1 − p2).
(a) Encuentre los valores p̄1 y p̄2 que maximizan la utilidad total (i.e. la
suma de la utilidad de ambas empresas).
Solución: La utilidad total UT se escribe como
UT (p1, p2) = U1(p1, p2) + U2(p1, p2)
= ln(p1) + ln(p2) + 2 ln(K − p1 − p2),
la cual es una función cóncava (por ser suma de funciones cóncavas).
Si derivamos e igualamos a cero obtenemos
∇UT (p1, p2) =
( 1
p1
− 2K−p1−p2
1
p2
− 2K−p1−p2
)
=
(
0
0
)
.
Resolviendo el sistema obtenemos que p̄1 = p̄2 =
K
4 , lo que da una
utilidad total UT (p̄1, p̄2) = ln
(
K4
64
)
. Las utilidades de cada empresa
quedan Ui(p̄1, p̄2) = ln
(
K2
8
)
.
(b) Muestre que si la empresa 2 deja p̄2 fijo, entonces la empresa 1 puede
mejorar su propia utilidad cambiando p1, encuentre el p
′
1 óptimo,
4
dado p̄2 fijo encontrado en la parte (a). Diremos que p
′
1 es la mejor
reacción de la empresa 1, dada la decisión p̄2 de la empresa 2.
Solución: La empresa 1 debe maximizar su utilidad dado p̄2 =
K
4 .
La derivada de U1 con respecto a p1 es:
∂U1
∂p1
(p1, p̄2) =
1
p1
− 1
K − p1 − p̄2
=
1
p1
− 1
K − p1 − K4
.
Igualando a cero y despejando p1 se obtiene p
′
1 =
3K
8 . Notemos que
ahora la utilidad de la empresa 1 es
U1(p
′
1, p̄2) = ln
(
9
8
K2
8
)
> ln
(
K2
8
)
.
Es decir, efectivamente la empresa 1 mejoró su utilidad.
Notemos que la utilidad de la empresa 2 quedó en
U2(p
′
1, p̄2) = ln
(
3
4
K2
8
)
< ln
(
K2
8
)
.
Es decir, la empresa 2 empeoró.
(c) Generalice el resultado anterior. Es decir, encuentre p1(p2), en fun-
ción de p2, donde p1(p2) es la mejor reacción de la empresa 1, dada
la decisión p2 de la empresa 2. Haga lo mismo con p2(p1).
Solución: Para encontrar las mejores reacciones de las empresas,
debemos derivar sus utilidades con respecto a sus precios e igualarlos
a cero:
0 =
∂U1
∂p1
(p1, p2) =
1
p1
− 1
K − p1 − p2
=⇒ p1(p2) =
K − p2
2
.
Por simetŕıa, p2(p1) =
K−p1
2 .
(d) Encuentre un par (p∗1, p
∗
2) de manera que p
∗
1 = p1(p
∗
2) y p
∗
2 = p2(p
∗
1).
Este par se denomina “equilibrio”.
Solución: Reemplazando la expresión de p2(p1) en p1(p2) se obtiene:
p1 =
K − p2
2
=
K − K−p12
2
=
K + p1
4
Lo cual implica p∗1 =
K
3 . De nuevo, por simetŕıa se tiene p
∗
2 =
K
3 .
Notemos que U1(p
∗
1, p
∗
2) = U2(p
∗
1, p
∗
2) = ln(
K2
9 ) < Ui(p̄1, p̄2). Es decir,
5
ambos disminuyen su utilidad con respecto a la parte (a). Sin em-
bargo, ninguna de las dos empresas tiene incentivos para modificar
su decisión de manera unilateral (pues su utilidad disminuiŕıa aún
más).
5. Sea f : Rn → R una función convexa. Muestre que el conjunto de solucio-
nes X∗ := {x ∈ Rn|x minimiza f(x)} es convexo.
Solución: Sean x, y ∈ X∗. Como f es convexa, tanto x como y son solu-
ciones globales. Por lo tanto, f(x) = f(y). Sea λ ∈ (0, 1). Entonces,
f(λx+ (1− λ)y ≤ λf(x) + (1− λ)f(y)
= λf(x) + (1− λ)f(x)
= f(x).
Adicionalmente, como x es mı́nimo global, se tiene la desigualdad contra-
ria, f(λx + (1 − λ)y ≥ f(x). Es decir, todo elemento en el segmento que
une x e y tienen la misma evaluación en f y son iguales a f(x) que era un
mı́nimo global. Por lo tanto, todo el segmento también está en X∗.
6. Considere la función f(x1, x2) = (x1 + x
2
2)
2. En el punto x = (1, 0) se
considera la dirección p = (−1, 1). Muestre que p es una dirección de
descenso y encuentre todos los minimizadores del problema
mı́n
α≥0
f(x+ αp).
Solución: Visto en clases.
7. Supongamos que cierta función f : R→ R no tiene forma anaĺıtica y que
sólo se puede evaluar a través de una caja negra. Es decir, uno entrega un
argumento x a la caja negra y ésta devuelve f(x). Se generan n evaluacio-
nes de esta función en los puntos x1, x2, . . . , xn, con lo que se obtiene el
conjunto {(x1, f(x1)), (x2, f(x2)), . . . , (xn, f(xn))} de tuplas de la forma
(x, f(x)).
Es sabido que existe, a lo más, un único polinomio p(x) = a0 + a1x +
. . . + an−1x
n−1, de grado n − 1 tal que p(xi) = f(xi), para todo i, y
queexisten infinitos polinomios de grado mayor a n− 1 que cumplen esta
misma propiedad. Sin embargo, podŕıa no existir tal polinomio si pedimos
que el grado sea menor a n − 1. Sea q(x) un polinomio de grado k, con
k < n − 1, es decir, q(x) =
∑k
i=0 bix
i. Encuentre una expresión para el
vector b = (b0, b1, . . . , bk) ∈ Rk que minimice el error cuadrático medio
entre q(x) y f(x), es decir, que resuelva:
mı́n
b
1
n
n∑
i=1
(q(xi)− f(xi))2 .
6
Como siempre, argumente su respuesta.
Hint: Le puede ser útil definir la siguiente matriz
X =

1 x1 x
2
1 . . . x
k
1
1 x2 x
2
2 . . . x
k
2
...
...
...
...
...
1 xn x
2
n . . . x
k
n

y el vector
y =

f(x1)
f(x2)
...
f(xn)
 .
Puede suponer que la matriz X es de rango completo, i.e., todas sus co-
lumnas son linealmente independientes.
Solución: Consideremos el vector
q̄ :=

q(x1)
q(x2)
...
q(xn)
 =

∑k
i=0 bix
i
1∑k
i=0 bix
i
2
...∑k
i=0 bix
i
n
 = Xb.
Notemos que
1
n
n∑
i=1
(q(xi)− f(xi))2 =
1
n
‖q̄ − y‖22 =
1
n
‖Xb− y‖22.
Derivando con respecto a b e igualando a cero, obtenemos
2
n
XT (Xb− y) = 0,
lo que implica que b∗ = (XTX)−1XT y.
Observaciones:
- XTX es invertible, pues asumimos que X es de rango completo.
- Claramente ‖Xb− y‖22 es una función convexa por ser la composición de
una función lineal afin (Xb − y) con una función convexa (‖·‖22). Por lo
tanto, b∗ es mı́nimo global.
8. Considere el problema de minimizar 5x2 + 5y2 − xy − 11x+ 11y + 11
7
(a) Encuentre un punto que satisfaga las condiciones necesarias de primer
orden.
Solución: Basta derivar e igualar a cero. Notemos que la función se
puede escribir como
f(x, y) =
1
2
(
x
y
)T (
10 −1
−1 10
)(
x
y
)
+
(
−11
11
)T (
x
y
)
+ 11.
Por lo tanto, igualar el gradiente a cero es equivalente a resolver el
sistema de ecuaciones:(
10 −1
−1 10
)(
x
y
)
=
(
11
−11
)
.
Como la matriz es invertible, este sistema tiene una única solución
(x, y) = (1,−1).
(b) Muestre que este punto es un mı́nimo global.
Solución: Analicemos los valores propios de la matriz que define la
función cuadrática.∣∣∣∣( 10− λ −1−1 10− λ
)∣∣∣∣ = (10−λ)2−1 = λ2−20λ+99 = (λ−9)(λ−11).
Por lo tanto, los valores propios son λ1 = 9 y λ2 = 11, ambos positivos
por lo que la matriz es definida positiva, y por consiguiente, la función
es estrictamente convexa. Es decir, el punto encontrado en (a) es
efectivamente un mı́nimo global.
(c) Sabemos que la tasa de convergencia del método del gradiente con
paso exacto es lineal. Calcule la tasa r de decrecimiento.
Solución: La forma de r está dada por r = λn−λ1λn+λ1 , donde λ1 y λn
son el menor y mayor valor propio, respectivamente. Por lo tanto
r =
λn − λ1
λn + λ1
=
11− 9
11 + 9
=
1
10
.
(d) Partiendo en x = y = 0, ¿Cuántas iteraciones del método del gra-
diente con paso exacto se requieren (a lo más) para alcanzar una
precisión de 10−11 en el valor de la función?
Solución: Sabemos que la progresión de las iteraciones en una fun-
ción cuadrática sigue la desigualdad
f(xk+1)− f(x∗) ≤ r2
(
f(xk)− f(x∗)
)
, ∀k ≥ 0.
Esto implica que
f(xk+1)− f(x∗) ≤ (r2)k+1
(
f(x0)− f(x∗)
)
.
8
Forzando el lado derecho a ser menor o igual a 10−11 y despejando k
podemos obtener el número de iteraciones. Notemos que f(x∗) = 0.
También podemos calcular f(0, 0) = 11. Por lo tanto, necesitamos
imponer que (
1
100
)k+1
(11− 0) ≤ 10−11.
Despejando k obtenemos k ≥ 11+log(11)2 ≈ 6, 02. Por lo tanto, en la
séptima iteración se logra una presición de a lo más 10−11.
9. Considere el proceso iterativo
xk+1 =
1
2
(
xk +
a
xk
)
,
donde a > 0. Asumiendo que el proceso converge, ¿Cuál es el ĺımite? ¿Cuál
es la tasa de convergencia?
Solución: Visto en clases.
10. Dado el punto x̄ = (3,−2, 0), encuentre el punto más cercano a x̄ del plano
definido por 2x + y + z = 2. Este punto se conoce como la proyección
ortogonal de x̄ al plano antes definido.
Solución: El problema a resolver es
mı́n ‖x̄− (x, y, z)‖2
s.a. 2x+ y + z = 2
(3)
Notar que podemos resolver para la norma al cuadrado, por la segunda
propiedad de formulaciones equivalentes (composición con función estric-
tamente creciente, como lo es g(x) = x2 con x ≥ 0).
El problema tiene una restricción de igualdad. Para deshacernos de ella,
escribimos z en función de x e y, es decir, z = 2− 2x− y, y reemplazar en
la función objectivo:
mı́n ‖(3,−2, 0)− (x, y, 2− 2x− y))‖2 (4)
Como la norma es una función convexa (y al cuadrado sigue siendo con-
vexa, por ser la norma no-negativa), basta con derivar e igualar a cero.
∇‖(3,−2, 0)− (x, y, 2− 2x− y))‖2 = ∇
{
(3− x)2 + (−y − 2)2 + (2− 2x− y)2
}
=
(
−2(3− x)− 4(2− 2x− y)
2(y + 2)− 2(2− 2x− y)
)
=
(
10x+ 4y − 14
4y + 4x
)
.
9
Por lo tanto, debemos resolver el sistema
10x + 4y = 14
4x + 4y = 0
.
Resolviendo el sistema se obtiene x = 73 e y = −
7
3 . Reemplazando en
z(x, y) obtenemos z = − 13 .
Observación: Este problema también se puede resolver usando álgebra
lineal. En efecto, el vector ortogonal al plano del problema es v = (2, 1, 1),
por lo que el problema se reduce a encontrar λ tal que el vector x̄ + λv
satisfaga la ecuación del plano. El resultado obtenido es el mismo.
11. Muestre que la función f(x) = 8x1 + 12x2 +x
2
1−2x22 tiene un único punto
estacionario, y que no es ni mı́nimo ni máximo. Dibuje las curvas de nivel
de f .
Solución: Necesitamos resolver ∇f(x) = 0 primero. Es decir, resolver el
sistema
8 + 2x1 = 0
12− 4x2 = 0,
con lo que obtenemos x1 = −4 y x2 = 3, como única solución. Para
verificar si es mı́nimo o máximo, calculamos el Hessiano en (−4, 3).
∇2f(x) =
(
2 0
0 −4
)
,
por lo tanto sabemos, por ser ∇2f(x) una matriz diagonal, que sus valores
propios son 2 y −4, es decir, no es ni semidefinida positiva ni semidefinida
negativa. Por lo tanto, (−4, 3) no puede ser mı́nimo ni máximo. Las curvas
de nivel están en la figura 1.
12. Muestre que la secuencia xk =
1
k NO es linealmente convergente, aunque
śı converge a cero. (Esto es llamado convergencia sublineal).
Solución: Claramente la convergencia a cero se tienen automáticamente.
Además, la sucesión xk+1xk =
k
k+1 converge a 1. Es decir, para todo ε > 0,
existe un k̄ tal que
∣∣∣xk+1xk − 1∣∣∣ ≤ ε, para todo k ≥ k̄. Sin embargo, con-
vergencia lineal implica que
∣∣∣xk+1xk ∣∣∣ ≤ r, para algún r ∈ (0, 1) y para todo
k mayor que cierto k′. Tomando ambas desigualdades, y k̂ = máx{k̄, k′},
obtenemos
1− ε ≤
∣∣∣∣xk+1xk
∣∣∣∣ ≤ r.
Como la elección de ε es arbitraria, podemos tomarlo suficientemente pe-
queño como para que la doble desigualdad no tenga solución.
10
Figura 1: Curvas de nivel de f
13. Sea Q � 0. Se define la función ‖·‖Q : Rn → R como ‖x‖2Q := 12x
TQx.
Supongamos que se quiere minimizar la función cuadrática
f(x) =
1
2
xTQx− bTx
con el método del gradiente usando el paso exacto. Sea x∗ la única solución
del problema. Usando la notación gk = ∇f(xk), muestre que:
(a) ‖xk − x∗‖2Q − ‖xk+1 − x∗‖2Q = αk(gk)TQ(xk − x∗)− 12α
2
k(g
k)TQgk
Solución: Desarrollemos ‖xk+1 − x∗‖2Q primero.
‖xk+1 − x∗‖2Q =
1
2
(xk+1 − x∗)TQ(xk+1 − x∗)
=
1
2
(xk − αkgk − x∗)TQ(xk − αkgk − x∗)
=
1
2
(xk − x∗ − αkgk)TQ(xk − x∗ − αkgk)
=
1
2
(xk − x∗)TQ(xk − x∗)− αk(xk − x∗)TQgk +
1
2
α2k(g
k)T gk
= ‖xk − x∗‖2Q − αk(xk − x∗)TQgk +
1
2
α2k(g
k)T gk,
lo que demuestra la igualdad requerida.
11
(b) Usando el hecho que gk = Q(xk − x∗), se tiene que
‖xk − x∗‖2Q − ‖xk+1 − x∗‖2Q =
1
2
((gk)T gk)2
(gk)TQgk
y
‖xk − x∗‖2Q =
1
2
(gk)TQ−1gk.
Solución: En ayudant́ıa vimos que
αk =
(gk)T gk
((gk)TQgk)
.
Reemplazando en el resultado de la parte (a), se tiene
αk(g
k)TQ(xk − x∗) = (g
k)T gk
((gk)TQgk)
(gk)TQ(xk − x∗)
=
((gk)T gk)2
((gk)TQgk)
y
1
2
α2k(g
k)TQgk =
1
2
(
(gk)T gk
(gk)TQgk
)2
(gk)TQgk
=
1
2
((gk)T gk)2
((gk)TQgk)
.
Luego,
‖xk − x∗‖2Q − ‖xk+1 − x∗‖2Q = αk(gk)TQ(xk − x∗)−
1
2
α2k(g
k)TQgk
=
((gk)T gk)2
((gk)TQgk)
− 1
2
((gk)T gk)2
((gk)TQgk)
=
1
2
((gk)T gk)2
((gk)TQgk)
.
Además, notandoque Q−1gk = x0 − x∗, se tiene
‖xk − x∗‖2Q =
1
2
(xk − x∗)TQ(xk − x∗)
=
1
2
(gk)TQ−TQQ−1gk
=
1
2
(gk)TQ−1gk
12
(c) Use ambos resultados de (b) para concluir que
‖xk+1 − x∗‖2Q =
(
1− ((g
k)T gk)2
((gk)TQgk)((gk)TQ−1gk)
)
‖xk − x∗‖2Q
Pista 0: Note que gk = Q(xk − x∗) ⇐⇒ Q−1gk = xk − x∗.
Solución: Juntando ambos resultados de la parte (b) tenemos
‖xk+1 − x∗‖2Q = ‖xk − x∗‖2Q −
1
2
((gk)T gk)2
((gk)TQgk)
= ‖xk − x∗‖2Q −
((gk)T gk)2‖xk − x∗‖2Q
((gk)TQgk)((gk)TQ−1gk)
=
{
1− ((g
k)T gk)2
((gk)TQgk)((gk)TQ−1gk)
}
‖xk − x∗‖2Q
(d) Concluya que si se elige x0 tal que x0 − x∗ es paralelo a un vector
propio de Q, entonces el método converge en una sola iteración.
Pista 1: dos vectores a y b en Rn son paralelos si es que existe un
escalar γ ∈ R tal que a = γb.
Pista 2: Use de manera apropiada el hecho que Q(x0− x∗) = λ(x0−
x∗), donde λ es el valor propio asociado al vector propio paralelo a
(x0 − x∗).
Solución: Notemos que g0 = Q(x0−x∗) = λ(x0−x∗). Por lo tanto,
el numerador de la fracción de la parte (c) es
((g0)T g0)2 = λ4((x0 − x∗)T (x0 − x∗))2,
y el denominador es
((g0)TQg0)((g0)TQ−1g0) = λ2(x0 − x∗)TQ(x0 − x∗)λ2(x0 − x∗)TQ−1(x0 − x∗)
= λ3(x0 − x∗)T (x0 − x∗)λ2(x0 − x∗)T 1
λ
(x0 − x∗)
= λ4((x0 − x∗)T (x0 − x∗))2.
Por lo tanto, ((g
0)T g0)2
((g0)TQg0)((g0)TQ−1g0)
= 1. Reemplazando en (c)
‖x1 − x∗‖2Q =
(
1− ((g
0)T g0)2
((g0)TQg0)((g0)TQ−1g0)
)
‖x0 − x∗‖2Q
= (1− 1) ‖x0 − x∗‖2Q
= 0.
Y por lo tanto, x1 = x∗.
13
14. En clases mecionamos que si Hk � 0 y se cumple la condición de curvatura
yTk sk > 0, entonces Hk+1 � 0. Demuestre tal aseveración. Adicionalmente,
demuestre que si el paso αk cumple la condición de Wolfe, entonces se
puede garantizar la condición de curvatura.
Pista 1: Evalúe vTHk+1v asumiendo Hk � 0 y ρk = ytksk > 0.
Pista 2: Escriba la condición de Wolfe directamente y utilice el hecho que
pk es de descenso, que xk+1 − xk = αkpk y que c2 < 1.
Solución: Sea v ∈ Rn arbitrario. Entonces,
vTHk+1v = v
T (I − ρkskyTk )Hk(I − ρkyksTk )v + ρkvT skskT v
= vT (I − ρkyksTk )THk(I − ρkyksTk )v + ρk(skT v)2
=
(
(I − ρkyksTk )v
)T
Hk(I − ρkyksTk )v + ρk(skT v)2.
El primer término de la suma, definiendo w = (I − ρkyksTk )v, se puede
reescribir como wTHkw el cual es positivo, pues Hk � 0. El segundo
término es el producto de ρk (que se asume positivo) y de (s
T
k v)
2, el cual
es no-negativo (por ser un cuadrado). Por lo tanto, el termino completo
es la suma de un valor positivo y uno no-negativo, es decir, la suma es
positiva, lo que concluye el resultado.
Para demostrar la condición de curvatura, recordemos que Wolfe implica
∇f(xk + αkpk)T pk ≥ c2∇f(xk)T pk.
Por supuesto, αk > 0. Identificando algunos términos observamos que
xk+1 = xk + αkp
k, que c2∇f(xk)T pk > ∇f(xk)T pk (pues c2 < 1 y
∇f(xk)T pk < 0), y que pk = (x
k+1−xk)
αk
= skαk . Por lo tanto, Wolfe im-
plica
∇f(xk+1)T sk
αk
> ∇f(xk)T sk
αk
,
lo cual a su vez implica(
∇f(xk+1)−∇f(xk)
)T sk
αk
> 0.
Identificando yk = ∇f(xk+1)−∇f(xk), se concluye el resultado.
14