exerciciosAna

Prévia do material em texto

Exercícios da disciplina MAP5747
Otimização não linear
Pedro Faria
18 de janeiro de 2016
Sumário
1 Exercícios do livro Elementos de Programação Não-linear 2
1.1 Capítulo 1 - Revisão de Álgebra Linear e Cálculo . . . . . . . 2
1.2 Capítulo 2 - Condições de otimalidade para minimização sem
restrições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3 Capítulo 3 - Convexidade . . . . . . . . . . . . . . . . . . . . . 39
1.4 Capítulo 4 - Modelo de algoritmo com buscas direcionais . . . 42
1.5 Capítulo 5 - Ordem de convergência . . . . . . . . . . . . . . . 57
1.6 Capítulo 6 - Métodos clássicos de descida . . . . . . . . . . . . 58
1.7 Capítulo 7 - Minimização com restrições lineares de igualdade 97
1.8 Capítulo 8 - Algoritmos para restrições lineares de igualdade . 116
1.9 Capítulo 9 - Minimização com restrições lineares de desigualdade139
1.10 Capítulo 10 - Método de restrições ativas . . . . . . . . . . . . 162
1.11 Capítulo 11 - Minimização com restrições lineares de igualdade
e desigualdade . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
1.12 Capítulo 12 - Minimização com restrições não-lineares de igual-
dade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
1.13 Capítulo 13 - Minimização com restrições não-lineares de igual-
dade e desigualdade . . . . . . . . . . . . . . . . . . . . . . . . 201
1.14 Capítulo 14 - Algoritmos para restrições não-lineares . . . . . 230
2 Exercícios dados em aula 260
2.1 Convexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
1
1 Exercícios do livro Elementos de Programa-
ção Não-linear
1.1 Capítulo 1 - Revisão de Álgebra Linear e Cálculo
1.1 Sejam A ∈ Rn×n e x ∈ Rn. Quais das seguintes afirmações são verda-
deiras? Prove ou dê um contraexemplo:
(a) Existe x∗ 6= 0 tal que Ax∗ = 0 se det(A) = 0.
A afirmação é verdadeira. Suponhamos que det(A) = 0. Logo,
A é equivalente a uma matriz A′ (A ∼ A′) que possui uma linha
de zeros (A pode ser transformada em A′ por uma sequência de
operações elementares sobre as linhas de A). Como operações ele-
mentares sobre um sistema não alteram seu conjunto de soluções,
temos que A′x = 0. Como uma das linhas de A′ é nula, então o
sistema A′x = 0 (cujas soluções são as mesmas de Ax = 0) tem
menos equações que variáveis, o que significa que existe pelo me-
nos uma variável xi livre (isto é, que pode assumir qualquer valor
real - em particular, um valor não nulo). Logo, existe x∗ 6= 0 tal
que A′x∗ = 0 e, portanto, Ax∗ = 0.
(b) Existe x∗ 6= 0 tal que Ax∗ = 0 somente se det(A) = 0.
A afirmação é verdadeira; provemos a contrapositiva. Suponha-
mos det(A) 6= 0. Logo, A é inversível e de Ax∗ = 0 segue
A−1A︸ ︷︷ ︸
I
x∗ = A−10 e portanto x∗ = 0.
(c) Existe x∗ 6= 0 tal que Ax∗ = 0 se e somente se det(A) = 0.
A afirmação é verdadeira, pois os itens (a) e (b) são verdadeiros
(e o item (c) é apenas a conjunção das afirmações de (a) e (b)).
1.2 Seja A ∈ Rm×n, m ≥ n e posto(A)= n. Prove que AtA é não singular.
Pelo exercício 1.1, temos que AtA é não singular se e somente x = 0
for a única solução de AtAx = 0.Temos que
AtAx = 0
xtAtAx = xt0
(Ax)tAx = 0
‖Ax‖22 = 0
2
Como ‖x‖2 = 0 ⇐⇒ x = 0, segue que Ax = 0. Como Ax pode ser
vista como uma combinação linear das n colunas de A em que cada
coeficiente é um componente de x, segue que x = 0 (pois as n colunas
de A são linearmente independentes, já que m ≥ n e posto(A)= n).
Logo, AtA é não singular.
1.3 Seja A ∈ Rm×n, m ≤ n e posto(A)= k. Definimos os subespaços
Nu(A) = {x ∈ Rn | Ax = 0} e Im(A) = {y ∈ Rm | ∃x ∈ Rn | y =
Ax}. Prove que:
(a) Nu(A) ⊥ Im(At).
Sejam u ∈ Nu(A), y ∈ Im(At). Como y ∈ Im(At),∃x ∈ Rm tal
que y = Atx. Temos que uty = utAtx = (Au)tx =︸︷︷︸
u∈Nu(a)
0tx = 0.
Logo, u e y são ortogonais e, portanto, Nu(A) ⊥ Im(At).
(b) dim(Nu(A)) = n− k.
Seja R uma matriz escalonada tal que R ∼ A (R pode ser obtida a
partir de A via operações elementares sobre as linhas de A). Como
operações elementares sobre as linhas de A não alteram seu espaço
linha, temos que o posto de A (dimensão do espaço linha de A) é
igual ao número de linhas não nulas de R (logo, R tem k linhas
não nulas). Ainda, como dim(Nu(A)) é o número de variáveis
livres de Ax = 0 (que, por sua vez, é o número de linhas nulas
de R, pois operações elementares também não alteram o espaço
nulo Nu(A)), temos que dim(Nu(A)) = n − k (número de total
de variáveis menos o número de linhas não nulas de R).
(c) Rn = Nu(A)⊕ Im(At).
Primeiramente, seja v ∈ Nu(A) ∩ Im(At). Provemos que v = 0
(i.e., provemos que a soma Nu(A) + Im(At) é direta). Pelo item
(a), temos que vtv = 0 = ‖v‖22. Como ‖v‖2 = 0 ⇐⇒ v = 0,
segue que v = 0.
O espaço Im(At) é gerado pelas colunas de At, que são as linhas
de A. Logo, dim(Im(At)) = posto(A) = k.
Como Nu(A)∩Im(At) = {0}, segue que dim(Nu(A)+Im(At)) =
dim(Nu(A))+dim(Im(At)) = (n−k)+k = n = dim(Rn). Ainda,
como Nu(A), Im(At) ∈ Rn, então o espaço Nu(A) + Im(At) está
contido em Rn. Logo, Rn = Nu(A)⊕ Im(At).
1.4 Considere Ax = b com A ∈ R(n−1)×n, b ∈ Rn−1 e x ∈ Rn, correspon-
dendo a n− 1 hiperplanos �linearmente independentes�. A intersecção
3
desses hiperplanos determina uma reta em Rn. Podemos representar
essa reta na forma y = x + λd, com λ ∈ R e x, d ∈ Rn. Discuta como
escolher x e d.
Como o número de equações do sistema Ax = b é n − 1 e o número
de incógnitas é n, então existe uma variável de x que é livre (e que
pode assumir qualquer valore real). Fixando então um valor para essa
variável livre (pode ser descoberta via escalonamento do sistema), po-
demos resolver o sistema (n− 1)× (n− 1) restante para encontrar uma
solução x0. Fazendo o mesmo procedimento para um outro valor da
variável livre, podemos encontrar uma solução x1. Esses dois pontos
já são suficientes para encontrar a reta desejada, que é definida por
y = x0 + λ(x1 − x0) (isto é escolhemos x = x0 e d = x1 − x0).
1.5 Encontre os autovalores e autovetores da matriz A = uut, onde u ∈ Rn.
Como cada linha de A = uut é um múltiplo de ut, segue que posto(A)
= 1. Logo (pelo exercício 1.3)b)), dim(Nu(A)) = n−posto(A) = n−1.
Como Nu(A) = {x ∈ Rn | Ax = 0}, então a multiplicidade de λ = 0
como autovalor (i.e., a multiplicidade de λ = 0 como raiz do polinômio
característico p(λ) = det(A−λI)) é n−1 (cujos autovetores associados
v são as soluções não nulas de Av = 0 ).
Como o traço de uma matriz é soma de seus autovalores, temos que o
último autovalor restante é λ = tr(A) = tr(uut) = utu. Resolvendo a
equação
Av = λv
u( utv︸︷︷︸
∈R
) = ( utu︸︷︷︸
∈R
)v
utvu = utuv
, temos que v = u. Logo, u é autovetor com autovalor associado utu.
1.6 Prove que os autovetores de uma matriz associados a autovalores dis-
tintos são linearmente independentes e que se a matriz é simétrica eles
são ortogonais.
Sejam λ1, . . . , λr r autovalores distintos de uma matriz A, associados
respectivamente aos autovetores v1, . . . , vr (i.e., Avk = λkvk para k =
1, . . . , r). A prova segue por indução em r.
4
Caso base: para r = 1, como v1 6= 0 (por ser autovetor) temos que
c1v1 = 0 ⇒ c1 = 0. Logo, {v1} é um conjunto de autovetores linear-
mente independentes.
Hipótese de indução: {v1, . . . , vr−1} é um conjunto de autovetores line-
armente independentes.
Passo de indução: seja r ≥ 2. Consideremos a combinação linear
c1v1 + . . . + crvr = 0. Multiplicando os dois lados da combinação por
A à esquerda, como Avi = λivi obtemos:
c1λ1v1 + . . .+ crλrvr = 0
Multiplicando os dois lados da combinação por λr, obtemos:
c1λrv1 + . . .+ crλrvr = 0
Subtraindo a última equação da antepenúltima, obtemos:
c1(λ1 − λr)v1 + . . .+ cr−1(λr−1 − λr)vr−1 = 0
Pela hipótese de indução, como {v1, . . . , vr−1} são linearmente indepen-
dentes então ci(λi − λr) = 0 para i = 1, . . . , r − 1. Como (λi − λr) 6= 0
(autovalores são diferentes), segue c1 = . . . =cr−1 = 0. Logo, da pri-
meira combinação linear temos então que crvr = 0 e, como vr 6= 0
(por ser autovetor), temos cr = 0. Logo, {v1, . . . , vr} é um conjunto
linearmente independente.
Suponhamos agora que A seja simétrica. Temos que:
vt1(Av2) = v
t
1(λ2v2) = λ2(v
t
1v2)
Ainda,
(vt1A)v2 = (v
t
1A
t)v2 = (Av1)
tv2 = (λ1v1)
tv2 = λ1(v
t
1v2)
Das duas últimas equações, segue que:
λ1(v
t
1v2) = λ2(v
t
1v2)
(λ1 − λ2)(vt1v2) = 0
(vt1v2) = 0 pois λ1 6= λ2
5
Logo, os autovetores são ortogonais.
1.7 Prove que os autovalores de uma matriz simétrica são positivos se e
somente se a matriz é definida positiva.
⇒ Seja A uma matriz simétrica com autovalores positivos λ1, . . . , λn.
Logo A admite a decomposição A = QΛQt, onde Q é uma matriz
ortogonal (i.e.,QQt = I) e Λ é uma matriz diagonal com os autovalores
de A. Definamos
√
Λ a matriz diagonal que contém as raízes quadradas
dos autovalores de A (tal que Λ =
√
Λ
√
Λ )
Seja x 6= 0. Temos então que xtAx = xtQΛQtx = (√ΛQtx)t(√ΛQtx) =∥∥∥√ΛQtx∥∥∥2
2
. Como x 6= 0 e √ΛQt é não singular (sua inversa é Q√Λ−1,
onde
√
Λ
−1
é a matriz diagonal com os inversos das raízes quadradas
dos autovalores de A), temos que
√
ΛQtx 6= 0. Ainda, como ‖.‖2 é uma
norma temos então que xtAx =
∥∥∥√ΛQtx∥∥∥2
2
> 0. Logo, A é definida
positiva.
⇐ Seja A uma matriz simétrica definida positiva. Seja v 6= 0 um
autovetor de A, com autovalor associado λ. Temos que:
Av = λv
vtAv = vtλv (multiplicando à esquerda por vt)
vtAv︸︷︷︸
>0
= vtv︸︷︷︸
>0
λ
Como vtAv > 0 (pois v 6= 0 e A é positiva definida) e vtv > 0 (pois
v 6= 0 e vtv = ‖v‖22), segue que λ > 0. Logo, todos os autovalores de A
são positivos.
1.8 Prove que se λ é um autovalor de uma matriz A não-singular, então
1/λ é um autovalor de A−1.
Seja λ um autovalor de uma matriz A não-singular, com autovetor
associado v. Temos que:
6
Av = λv
v = A−1λv (multiplicando à esquerda por A−1)
v = (A−1v)λ
v
1
λ
= A−1v
Logo, 1/λ é um autovalor de A−1, com autovetor associado v.
1.9 Prove que A ∈ Rn×n é singular se e somente se 0 é um autovalor.
⇒ Seja A ∈ Rn×n singular. Logo, existe v 6= 0 tal que Av = 0 = 0v.
Logo, λ = 0 é um autovalor de A, com autovetor associado v.
⇐ Seja 0 um autovalor de A, com autovetor associado v. Logo, Av = 0
. Como v 6= 0 (pois v é autovetor de A), Nu(A) é não trivial. Logo, A
é singular.
1.10 Suponha que limk→∞ xk = α. Prove que se α > β, então existe M > 0
tal que para qualquer k ≥M se verifica que xk > β.
Como limk→∞ xk = α, então para todo � > 0 existe um natural k0 tal
que k > k0 ⇒ α− � < xk < α + �. Para k ≥ k0, temos então que
α− � < xk < α + �
β − � < α− � < xk < α + � (pois α > β)
β < α < xk + �
Como a última inequação vale para todo � > 0, temos então que, esco-
lhendo M = k0 + 1, para k ≥M temos xk ≥ α > β ⇒ xk > β.
1.11 Prove que se limk→∞ xk = α e para todo k ≥ 0, xk ≥ β então α ≥ β.
Trocando o sinal de ≥ por >, a afirmação continua válida? Prove ou
dê um contraexemplo.
Por contradição, suponhamos α < β. Como limk→∞ xk = α, então para
todo � > 0 existe um natural k0 tal que k > k0 ⇒ α− � < xk < α + �.
Para k ≥ k0, temos então que
7
α− � < xk < α + �
xk < α + � < β + � (pois α < β)
xk − � < α < β
Como a última inequação vale para todo � > 0, temos então que, para
k > k0 temos x
k ≤ α < β ⇒ xk < β. Isso é uma contradição com o
fato de que, para todo k ≥ 0, xk ≥ β. Logo, α ≥ β.
Trocando agora o sinal de≥ por>, tentemos provar que, se limk→∞ xk =
α e para todo k > 0, xk > β então α > β. Novamente por contradição,
suponhamos α ≤ β. Como limk→∞ xk = α, então para todo � > 0
existe um natural k0 tal que k > k0 ⇒ α−� < xk < α+�. Para k ≥ k0,
temos então que
α− � < xk < α + �
xk < α + � ≤ β + � (pois α ≤ β)
xk − � < α ≤ β
Como a última inequação vale para todo � > 0, temos então que, para
k > k0 temos x
k ≤ α ≤ β ⇒ xk ≤ β. Isso é uma contradição com o
fato de que, para todo k ≥ 0, xk > β. Logo, α > β (e, portanto, a
afirmação continua válida se trocarmos ≥ por >).
1.12 Se {xk} é uma sequência convergente, então essa sequência é limitada?
A recíproca é verdadeira?
Sim (para a primeira pergunta). Seja xk uma sequência convergente,
com limk→∞ xk = L. Logo, para todo � > 0 existe um natural k0 tal
que k > k0 ⇒ L− � < xk < L+ �. Em particular, para � = 1 e k > k0
temos que:
∣∣xk − L∣∣ < 1∣∣xk∣∣− |L| < ∣∣xk − L∣∣ < 1 (pela desig. triang |u| − |v| ≤ |u− v|)∣∣xk∣∣ < 1 + |L|
8
Seja M = max{|x1| , . . . , ∣∣xk0∣∣ , 1 + |L|}. Da definição de M e da ine-
quação anterior segue que
∣∣xk∣∣ ≤ M para todo k natural, e portanto
{xk} é limitada.
A recíproca não é verdadeira, pois para xk = (−1)k, temos que {xk}
é limitada (pois
∣∣xk∣∣ ≤ 1 para todo k natural) mas não é convergente
(pois para todo k ≥ 1 natural temos ∣∣xk − xk−1∣∣ = 2).
1.13 É possível ter uma sequência convergente tal que x2k > 0 e x2k+1 < 0
para todo k ?
Sim. Considerando a sequência xk = (−1)k 1
k
, temos que x2k = 1
k
> 0 e
x2k+1 = − 1
k
< 0 para todo k > 0 e limk→∞ xk = 0 (para k ∈ Z, basta
considerar a sequência xk = (−1)|k| 1|k|).
1.14 Prove que as funções abaixo são normas:
(a) ‖.‖∞ : Rn → R, ‖x‖∞ = max1≤i≤n |xi| .
Sejam x, y ∈ Rn e α ∈ R.
Temos que :
‖x‖∞ = 0 ⇐⇒
max
1≤i≤n
|xi| = 0 ⇐⇒
|xi| ≤ 0 ∀i ⇐⇒︸ ︷︷ ︸
|xi|≥0
xi = 0 ∀i ⇐⇒
x = 0
Ainda, ‖αx‖∞ = max1≤i≤n |αxi| = |α|max1≤i≤n |xi| = |α| ‖x‖∞.
Por fim,
‖x+ z‖∞ = max1≤i≤n |xi + zi|
≤ max
1≤i≤n
|xi|+ max
1≤i≤n
|zi| (desig. triang)
= ‖x‖∞ + ‖z‖∞
Logo, ‖.‖∞ é uma norma.
9
(b) ‖.‖1 : C(a, b)→ R, ‖f‖1 =
∫ b
a
|f(x)| dx. (C(a, b) é o conjunto das
funções contínuas [a, b]→ R) .
Sejam f, g ∈ C(a, b) e α ∈ R.
Temos que :
‖f‖1 = 0 ⇐⇒∫ b
a
|f(x)| dx = 0 ⇐⇒
|f | = 0 ⇐⇒ (pois |f(x)| ≥ 0)
f = 0 (pois |.| é uma norma em R)
Ainda, ‖αf‖1 =
∫ b
a
|αf(x)| dx = |α| ∫ b
a
|f(x)| dx = |α| ‖f‖1.
Por fim,
‖f + g‖1 =
∫ b
a
|f(x) + g(x)| dx
≤
∫ b
a
|f(x)| dx+
∫ b
a
|g(x)| dx (desig. triang.)
= ‖f‖1 + ‖g‖1
Logo, ‖.‖1 é uma norma.
1.15 Considere as funções f : Rm → Rp e g : Rn → Rm com jacobianos
Jf ∈ Rp×m e Jg ∈ Rm×n , respectivamente. Encontre o jacobiano da
função composta h : Rn → Rp, dada por h(x) = f(g(x)).
Sejam Jfij e Jgij os elementos das posições i, j dos jacobianos de f e g,
respectivamente. Pela definição de jacobiano de h e definindo y = g(x),
temos que:
10
Jhij(x) =
∂hi
∂xj
(x)
=
∂fi
∂xj
(g(x))
=
m∑
k=1
∂fi
∂yk
(g(x))
∂yk
∂xj
(x) (pela regra da cadeia)
=
m∑
k=1
Jfik(g(x))Jgkj(x)
Logo, Jh(x) = Jf (g(x))Jg(x).
1.16 Calcule o gradiente e o hessiano das funções f : Rn → R abaixo:
Temos que o vetor gradiente (∇f) e a matriz hessiana (H(f) ou ∇2f)
são definidos por:
∇f(x) =
(
∂f
∂x1
(x), . . . ,
∂f
∂xn
(x)
)t
Hi,j(f(x)) =
∂2f(x)
∂xi∂xj
(a) f(x) = atx =
∑n
i=1 aixi.
∂f
∂xi
= ai ⇒ ∇f = a
Hi,j(f(x)) =
∂2f(x)
∂xi∂xj
= 0⇒ H(f) = 0
(b) f(x) = 1
2
xtAx + btx + c = 1
2
∑n
i=1
∑n
j=1Aijxixj +
∑n
i=1 bixi + c,
onde A ∈ Rn×n, b ∈ Rn, c ∈ R.
11
∂f
∂xk
=
∂
∂xk
[
1
2
n∑
i=1
n∑
j=1
Aijxixj +
n∑
i=1
bixi + c
]
= bk +
1
2
∂
∂xk
[∑
i 6=k
∑
j 6=k
Aijxixj +
∑
i 6=k
Aikxixk +
∑
j 6=k
Akjxkxj + Akkx
2
k
]
= bk +
1
2
∑
i 6=k
Aikxi +
1
2
∑
j 6=k
Akjxj + Akkxk
= bk +
1
2
n∑
i=1
Aikxi +
1
2
n∑
j=1
Akjxj
Logo, ∇f = 1
2
(A+ At)x+ b.
Ainda,
Hk,l(f(x)) =
∂2f(x)
∂xk∂xl
=
∂
∂xk
[
∂f(x)
∂xl
]
=
∂
∂xk
[
bl +
1
2
n∑
i=1
Ailxi +
1
2
n∑
j=1
Aljxj
]
=
1
2
(Akl + Alk)
Logo, H(f) = 1
2
(A+ At) .
(c) f(x) = gt(x)g(x) = ‖g(x)‖22 =
∑m
i=1 gi(x)
2
, onde g : Rn → Rm
∂f
∂xj
=
m∑
i=1
∂
∂xj
gi(x)
2
=
m∑
i=1
2gi(x)
∂
∂xj
gi(x)Logo, ∇f = 2∑mi=1 gi(x)∇gi(x)
12
Ainda,
Hj,k(f(x)) =
∂2f(x)
∂xj∂xk
=
∂
∂xj
[
∂f(x)
∂xk
]
=
∂
∂xj
[
m∑
i=1
2gi(x)
∂
∂xk
gi(x)
]
=
m∑
i=1
2
∂
∂xj
[
gi(x)
∂
∂xk
gi(x)
]
=
m∑
i=1
2
[
gi(x)
∂
∂xj∂xk
gi(x) +
∂
∂xj
gi(x)
∂
∂xk
gi(x)
]
Logo, H(f) = 2
∑m
i=1 giH(gi) + 2
∑m
i=1∇gi∇gti .
1.17 Sejam A ∈ Rm×n, b ∈ Rm. Para x ∈ Rn, definimos q(x) = f(Ax + b)
com f : Rm → R. Calcule o gradiente e o hessiano da função q.
Temos que q(x) = f(y), onde y = Ax + b e yi = bi +
∑n
j=1Aijxi.
Portanto,
∂q
∂xk
=
m∑
i=1
∂f
∂yi
∂yi
∂xk
=
m∑
i=1
∂f
∂yi
∂
∂xk
[
bi +
n∑
j=1
Aijxi
]
=
∂f
∂yk
n∑
j=1
Akj
Logo, (∇q)k = ∂f∂yk
∑n
j=1Akj ⇒ ∇q = (∇f)t(A× 1), onde 1 ∈ {1}n×1
13
Ainda,
Hi,k(q(x)) =
∂2q(x)
∂xi∂xk
=
∂
∂xi
[
∂q(x)
∂xk
]
=
∂
∂xi
[
∂f
∂yk
n∑
j=1
Akj
]
= 0
Logo, H(q) = 0 .
1.18 Desenhe as curvas de nível das seguintes quadráticas:
(a) f(x, y) = x2 − y2 − x+ y − 1. Como
x2 − y2 − x+ y − 1 = z(
x− 1
2
)2
−
(
y − 1
2
)2
= z + 1
Temos que cada curva de nível é uma hipérbole de centro (1
2
, 1
2
)
(f é um paraboloide hiperbólico).
Figura 1: Curvas de nível geradas com o WolframAlpha . Regiões mais claras
indicam valores maiores da função.
14
(b) f(x, y) = x2 + y2 + 2xy.
Como
x2 + y2 + 2xy = z
(x+ y)2 = z (logo, z ≥ 0)
x+ y = ±√z
y = −x±√z
Temos que cada valor de z determina duas curvas de nível que são
retas de coeficiente angular igual a -1 (f é um cilindro parabólico).
Figura 2: Curvas de nível geradas com o WolframAlpha . Regiões mais claras
indicam valores maiores da função.
(c) f(x, y) = x2 + y2 − xy.
Como
x2 + y2 − xy = z(
x− y
2
)2
+
y2
4
3
= z
Temos que cada curva de nível é uma elipse de centro (y
2
, 0) (f é
um paraboloide elíptico).
15
Figura 3: Curvas de nível geradas com o WolframAlpha . Regiões mais claras
indicam valores maiores da função.
(d) f(x, y) = xy.
Considerando a equação Ax2 +Bxy+Cy2 +Dx+Ey+F = 0 que
define as quádricas, temos que a curva de nível xy − z = 0 é uma
hipérbole pois B2 = 12 > 0 = 4∗0∗0 = 4AC (f é um paraboloide
hiperbólico).
Figura 4: Curvas de nível geradas com o WolframAlpha . Regiões mais claras
indicam valores maiores da função.
1.19 Escreva a expansão em série de Taylor em torno do ponto x0 = 0 para
as seguintes funções:
Para uma função f : R→ R ∈ C∞, sua série de Taylor em torno de x0
é dada por:
16
f(x) =
∞∑
n=0
f (n)(x0)
n!
(x−x0)n = f(x0)+f
′(x0)
1!
(x−x0)+f
′′(x0)
2!
(x−x0)2+· · ·
(a) f(x) = cos(x).
Para n ∈ N, temos que:
cos(n)(0) =

cos(0) = 1 se n ≡ 0 (mod 4)
− sin(0) = 0 se n ≡ 1 (mod 4)
− cos(0) = −1 se n ≡ 2 (mod 4)
sin(0) = 0 se n ≡ 3 (mod 4)
Logo, apenas os termos de potências pares são não nulos, e por-
tanto a série de Taylor de cos(x) em torno de x0 = 0 é dada por:
cos(x) =
∞∑
k=0
(−1)kx2k
(2k)!
(b) f(x) = ln(x+ 1).
Para n = 0, f (n)(0) = ln(0 + 1) = 0.
Para n ∈ N∗, temos que:
f (n)(x) = (−1)n−1(n− 1)!(x+ 1)−n = (−1)
n−1(n− 1)!
(x+ 1)n
Aplicando em x = 0, obtemos:
f (n)(0) = (−1)n−1(n− 1)!
Logo, a série de Taylor de ln(x + 1) em torno de x0 = 0 é dada
por:
ln(x+ 1) =
∞∑
n=1
(−1)n−1(n− 1)!
n!
xn
=
∞∑
n=1
(−1)n−1
n
xn
17
(c) f(x) = exp(x).
Para n ∈ N, temos que:
exp(n)(0) = exp(0) = 1
Logo, a série de Taylor de exp(x) em torno de x0 = 0 é dada por:
exp(x) =
∞∑
n=0
xn
n!
1.20 Discuta a geometria das curvas de nível de uma função quadrática
f(x) = 1
2
xtAx + btx + c, onde A ∈ R2×2 simétrica, b ∈ R2, c ∈ R, nos
seguintes casos.
Sejam A =
[
a1 a2
a2 a1
]
e
b =
[
b1
b2
]
.
Logo f pode ser reescrita como
f(x1, x2) =
1
2
(a1x
2
1 + 2a2x1x2 + a1x
2
2︸ ︷︷ ︸
xtAx
) + b1x1 + b2x2︸ ︷︷ ︸
btx
+c
, com x1, x2 ∈ R.
Usemos também o fato de que, para uma dada matriz A ∈ Rn×n, o
traço de A é a soma dos seus autovalores (contando multiplicidades),
e o determinante de A é o produto de seus autovalores. Para a matriz
A ∈ R2×2 em questão (com autovalores λ1, λ2 ∈ R), temos então que:{
2a1 = λ1 + λ2
a21 − a22 = λ1λ2
(a) A > 0 (i.e., A é definida positiva: xtAx > 0 para todo x 6= 0).
Seja z = 1
2
(a1x
2
1 + 2a2x1x2 + a1x
2
2) + b1x1 + b2x2 + c uma curva de
nível de f . Comparando-a com a equação que define as quádricas
Ax21 +Bx1x2 +Cx
2
2 +Dx1 +Ex2 + F = 0, ela será uma elipse se
B2 < 4AC, isto é, se
18
a22 < 4(
a1
2
)(
a1
2
)
a22 < a
2
1
Como uma matriz simétrica é positiva definida ⇐⇒ todos os
seus autovalores são positivos, temos então que:{
2a1 = λ1 + λ2 > 0
a21 − a22 = λ1λ2 > 0⇒ a22 < a21
Logo, como a22 < a
2
1, as curvas de nível de f são elipses.
(b) A ≥ 0 (i.e., A é semidefinida positiva: xtAx ≥ 0 para todo x ∈ Rn
) e existe x tal que Ax+ b = 0.
não resolvido
(c) A ≥ 0 e não existe x tal que Ax+ b = 0.
não resolvido
(d) A indefinida (i.e., existem x, y ∈ Rn não nulos tais que xtAx >
0 > ytAy ) e não singular (i.e., det(A) 6= 0).
Seja z = 1
2
(a1x
2
1 + 2a2x1x2 + a1x
2
2) + b1x1 + b2x2 + c uma curva de
nível de f . Comparando-a com a equação que define as quádricas
Ax21 +Bx1x2 +Cx
2
2 +Dx1 +Ex2 +F = 0, ela será uma hipérbole
se B2 > 4AC, isto é, se
a22 > 4(
a1
2
)(
a1
2
)
a22 > a
2
1
Como uma matriz simétrica é indefinida ⇐⇒ tem autovalores
positivos e negativos, temos então que:
a21 − a22 = λ1λ2 < 0⇒ a22 > a21
Logo, como a22 > a
2
1, as curvas de nível de f são hipérboles.
19
1.21 Considere a função f(x, y) = x cos(y) + y sin(x). Determine a aproxi-
mação linear de f em torno do ponto (0, 0). Determine um limitante
para o erro na região [−1, 1]× [−1, 1].
Sendo f de classe C2, temos que o polinômio de Taylor de ordem 1 de
f(x, y) em torno de (x0, y0) é dado por:
P1(x, y) = f(x0, y0) +
∂f
∂x
(x0, y0)(x− x0) + ∂f
∂y
(x0, y0)(y − y0)
, sendo o erro (resto) de Lagrange dado por:
E1(x, y) =
1
2
[
∂2f
∂x2
(x¯, y¯)(x− x0)2 + 2 ∂
2f
∂x∂y
(x¯, y¯)(x− x0)(y − y0) + ∂
2f
∂y2
(x¯, y¯)(y − y0)2
]
para algum (x¯, y¯) interno ao segmento de extremidades (x0, y0) e (x, y).
Logo, para a função em questão segue que:
P1(x, y) = f(x0, y0) +
∂f
∂x
(x0, y0)(x− x0) + ∂f
∂y
(x0, y0)(y − y0)
= 0 + (cos(0) + 0 cos(0))(x− 0) + (−0 sin(0) + sin(0))(y − 0)
= x
e, para algum (x¯, y¯) interno ao segmento de extremidades (0, 0) e (x, y),
temos que o erro é dado por:
E1(x, y) =
1
2
[
∂2f
∂x2
(x¯, y¯)(x− x0)2 + 2 ∂
2f
∂x∂y
(x¯, y¯)(x− x0)(y − y0) + ∂
2f
∂y2
(x¯, y¯)(y − y0)2
]
=
1
2
[
(−y¯ sin(x¯))(x− 0)2 + 2(cos(x¯)− sin(y¯))(x− 0)(y − 0) + (−x¯ cos(y¯))(y − 0)2]
=
1
2
[−x2y¯ sin(x¯) + 2xy(cos(x¯)− sin(y¯))− yx¯ cos(y¯)]
Para (x, y), (x¯, y¯) ∈ [−1, 1]× [−1, 1], temos que :
− sin(1) ≤ −x2y¯ sin(x¯) ≤ sin(1)
2(cos(1)− sin(1)) ≤ 2xy(cos(x¯)− sin(y¯)) ≤ 2(1 + sin(1))
−1 ≤ −yx¯ cos(y¯) ≤ − cos(1)
20
Somando as três inequações acima, obtemos que em [−1, 1]× [−1, 1] o
erro é limitado por:
2 cos(1)− 3 sin(1)− 1 ≤ 2E1(x, y) ≤ 2 + 2 sin(1)− cos(1)
|2E1(x, y)| ≤ 2 + 2 sin(1)− cos(1)
|E1(x, y)| ≤ 1 + 1 sin(1)− cos(1)
2
1.2 Capítulo 2 - Condições de otimalidade para mini-
mização sem restrições
2.1 Sejam g : R → R uma função estritamente crescente e f : Rn → R.
Prove que minimizar f(x) é equivalente a minimizar g(f(x)).
Como g é estritamente crescente, temos que x1 < x2 ⇐⇒ g(x1) <
g(x2) para todo (x1, x2) ∈ R2.
⇒ Sendo x∗ minimizador global de f , temos f(x∗) < f(x) para todo
x ∈ R. Como g é estritamente crescente, segue g(f(x∗)) < g(f(x))
para todo x ∈ R. Logo, x∗ minimiza g(f(x)).
⇐ Sendo x∗ minimizador global deg(f(x)), temos g(f(x∗)) < g(f(x))
para todo x ∈ R. Como g é estritamente crescente, g é injetora e por-
tanto admite uma inversa g−1. Logo, g−1(g(f(x∗))) < g−1(g(f(x)))⇒
f(x∗) < f(x) para todo x ∈ R. Logo, x∗ minimiza f(x).
2.2 Resolva o problema de minimizar ‖Ax− b‖, onde A ∈ Rm×n e b ∈ Rm.
Considere todos os casos possíveis e interprete geometricamente.
Como ‖.‖ ≥ 0, minimizar ‖Ax− b‖ equivale a minimizar ‖Ax− b‖2.
Logo,
‖Ax− b‖2 = (Ax− b)t(Ax− b)
= xtAtAx− 2btAx+ btb
Derivando em relação a x e igualando a 0, obtemos:
2AtAx− 2Atb = 0
AtAx = Atb
21
Se as colunas de A forem independentes (i.e., se A tiver posto n), então
AtA ∈ Rn×n será invertível e a solução é dada por x = (AtA)−1Atb.
Geometricamente, queremos escrever b como combinação linear das co-
lunas de A tal que ‖Ax− b‖ seja o menor possível, i.e., que queremos
que Ax∗ seja a projeção de b no espaço coluna de A. Equivalentemente,
queremos que Ax−b esteja no espaço ortogonal ao espaço coluna de A,
isto é, queremos que At(Ax− b) = 0⇒ AtAx = Atb (que é exatamente
a condição de otimalidade acima).
Se posto(A) = r < n, então existem matrizes Aˆ, Q e R tais que Aˆ
é obtida de A via permutação de colunas, Q ∈ Rm×m é ortogonal,
R =
[
R11 R12
0 0
]
∈ Rm×n , R11 ∈ Rr×r é não singular e triangular
superior, e Aˆ = QR.
Dado x ∈ Rn, seja xˆ o vetor obtido de x usando a mesma sequência
de permutações usada para transformar A em Aˆ. Logo, Aˆxˆ = Ax, e
portanto minimizar ‖Ax− b‖ equivale a minimizar
∥∥∥Aˆxˆ− b∥∥∥. Dái vem
que :
Aˆxˆ = b
QRxˆ = b
QtQRxˆ = Qtb
Rxˆ = Qtb (pois Q é ortogonal)[
R11 R12
0 0
] [
xˆ1
xˆ2
]
=
[
cˆ
d
]
O resíduo do sistema acima é dado por s =
[
cˆ−R11xˆ1 −R12xˆ2
d
]
e,
portanto, para minimizar ‖s‖, basta escolher xˆ2 ∈ Rn−r qualquer e
resolver o sistema R11xˆ1 = cˆ−R12xˆ2 ⇒ xˆ1 = R−111 (cˆ−R12xˆ2) (possível
pois R11 é não singular).
2.3 Considere os números reais a1 ≤ a2 ≤ · · · ≤ an. Encontre a solução
dos seguintes problemas:
(a) Minimizar
n∑
i=1
|x− ai|.
22
É imediato que a solução ótima x∗ está em [a1, an], já que a função
objetivo f apenas aumenta se x > an ou se x < a1. Logo, para
ak ≤ x ≤ x+ d ≤ ak + 1, temos:
f(x+ d) =
k∑
i=1
(x+ d− ai) +
n∑
i=k+1
(ai − (x+ d))
= dk +
k∑
i=1
(x− ai)− d(n− k) +
n∑
i=k+1
(ai − x)
= d(2k − n) +
k∑
i=1
(x− ai) +
n∑
i=k+1
(ai − x)
= d(2k − n) + f(x)
Logo, temos a �derivada� f(x+d)−f(x) = d(2k−n) =

< 0 se k < n/2
0 se k = n/2
> 0 se k > n/2
Portanto, para minimizar f(x) escolhemos k = n/2, isto é, f(x) é
minimizado pela mediana de a1, . . . , an.
(b) Minimizar max
i=1,...,n
|x− ai| .
parcialmente resolvido
Temos que o problema é equivalente ao problema linear :
minimizar f(x, y) = y
s.a. y ≥ x− ai ∀i = 1, . . . , n
y ≥ −x+ ai ∀i = 1, . . . , n
Essa formulação garante que y ≥ max
i=1,...,n
|x− ai| (para todo y viá-
vel), e a minimização de y fará com que a solução ótima y∗ seja
tal que y∗ = max
i=1,...,n
|x− ai|. Logo, se todos os ai forem diferentes,
apenas duas restrições estarão ativas na solução ótima.
Reescrevendo as restrições, temos:
23
minimizar f(x, y) = y
s.a. x− y ≤ ai ∀i = 1, . . . , n
−x− y ≤ −ai ∀i = 1, . . . , n
Logo, o problema é tal que:
minimizar f(x, y) = y
s.a. Ax ≤ b
Nesse caso, temos A =

1 −1
1 −1
.
.
.
.
.
.
−1 −1
−1 −1
 e b =

a1
.
.
.
an
−a1
.
.
.
−an

.
Pela observação anterior, sendo (x∗, y∗) a solução ótima, seja ai
tal que x∗ − y∗ = ai e −x∗ − y∗ = −ai. Portanto, a matriz
de coeficientes das restrições ativas é AI =
[
1 −1
−1 −1
]
. Pela
condição de otimalidade de primeira ordem (teorema 9.1 da p. 69
do livro da Ana), então existe λ∗ ∈ R2− tal que:
∇f(x∗, y∗) = AtI(λ∗1, λ∗2)t
(0, 1)t =
[
1 −1
−1 −1
]
(λ∗1, λ
∗
2)
t
(0, 1)t = (λ∗1 − λ∗2,−λ∗1 − λ∗2)t
λ∗1 = λ
∗
2 = −
1
2
(c) Minimizar
n∑
i=1
|x− ai|2.
Temos que:
24
f ′(x) =
n∑
i=1
2(x− ai)
= 2
n∑
i=1
(x− ai)
= 2
n∑
i=1
x− 2
n∑
i=1
ai
= 2nx− 2
n∑
i=1
ai
Logo, os pontos estacionários x∗ são dados por:
f ′(x∗) = 0
2
n∑
i=1
(x∗ − ai) = 0
n∑
i=1
(x∗ − ai) = 0
nx∗ −
n∑
i=1
ai = 0
x∗ =
n∑
i=1
ai
n
Ainda, como
f ′′(x) = 2n
> 0 (para n > 0)
Temos então que x∗ =
n∑
i=1
ai
n
é o minimizador de f .
25
(d) Maximizar
n∏
i=1
|x− ai|.
Como lim
‖x‖→∞
f(x) = +∞, f não tem um maximizador global.
Porém, como f(x) ≥ 0 e f(ai) = 0 ∀i = 1, . . . , n, todo ai (i =
1, . . . , n) é minimizador global de f .
2.4 Obtenha expressões para as derivadas primeiras e segundas da função
de Rosenbrock f(x) = 100(x2−x21)2+(1−x1)2. Verifique que x¯ = (1, 1)t
é um minimizador local. Prove que ∇2f(x¯) é singular se e somente se
x2 − x21 = 0.005.
As derivadas parciais são dadas por:
∂f
∂x1
= −400x1(x2 − x21)− 2(1− x1)
∂2f
∂x21
= −400x2 + 1200x21 + 2
∂f
∂x2
= 200(x2 − x21)
∂2f
∂x22
= 200
∂2f
∂x1∂x2
= −400x1
Logo,∇f(x) = (−400x1(x2−x21)−2(1−x1), 200(x2−x21))t e ∇2f(x) =[ −400x2 + 1200x21 + 2 −400x1
−400x1 200
]
.
Sendo x¯ = (1, 1)t, temos ∇f(x¯) = (0, 0)t e ∇2f(x¯) =
[
802 −400
−400 200
]
.
Utilizemos o fato de que uma matriz é definida positiva ⇐⇒ todos os
seus menores principais são positivos. Os menores principais de ∇2f(x¯)
(determinantes das submatrizes principais de ∇2f(x¯)) são ∆1 = 802 >
0, ∆1 = 200 > 0 e ∆2 = 802× 200− (−400×−400) = 400 > 0. Como
são todos positivos, ∇2f(x¯) é definida positiva.
Portanto, como ∇f(x¯) = (0, 0)t e ∇2f(x¯) é definida positiva, x¯ é um
minimizador local de f .
26
Além disso, temos que
det(∇2f(x)) = (−400x2 + 1200x21 + 2)× (200)− (−400x1)× (−400x1)
= 80000(x21 − x2) + 400
Portanto, ∇2f(x) é singular ⇐⇒ det(∇2f(x)) = 0 ⇐⇒ x21 − x2 =
−400/80000 = −0.005 ⇐⇒ x2 − x21 = 0.005
2.5 Encontre os pontos estacionários de f(x) = 2x31−3x21−6x1x2(x1−x2−
1). Quais desses pontos são minimizadores ou maximizadores, locais
ou globais?
As derivadas parciais são dadas por:
∂f
∂x1
= 6x21 − 6x1 − 12x1x2 + 6x22 + 6x2
∂2f
∂x21
= 12x1 − 6− 12x2
∂f
∂x2
= −6x21 + 12x1x2 + 6x1
∂2f
∂x22
= 12x1
∂2f
∂x1∂x2
= −12x1 + 12x2 + 6
Logo,∇f(x) = (6x21 − 6x1 − 12x1x2 + 6x22 + 6x2,−6x21 + 12x1x2 + 6x1)t
e ∇2f(x) =
[
12x1 − 6− 12x2 −12x1 + 12x2 + 6
−12x1 + 12x2 + 6 12x1
]
.
Os pontos estacionários são dados pelo sistema:{
6x21 − 6x1 − 12x1x2 + 6x22 + 6x2 = 0
−6x21 + 12x1x2 + 6x1 = 0
, e são x0 = (−1,−1), x1 = (0,−1), x2 = (0, 0) e x3 = (1, 0), com
f(x0) = 1, f(x1) = 0, f(x2) = 0, f(x3) = −1.
Temos então que
27
∇2f(x0) =
[ −6 6
6 −12
]
⇒ det(∇2f(x0)) = 36 > 0 e ∂
2f
∂x21
(x0) = −6 < 0
∇2f(x1) =
[
6 −6
−6 0
]
⇒ det(∇2f(x1)) = −36 < 0
∇2f(x2) =
[ −6 6
6 0
]
⇒ det(∇2f(x2)) = −36 < 0
∇2f(x3) =
[
6 −6
−6 12
]
⇒ det(∇2f(x3)) = 36 > 0 e ∂
2f
∂x21
(x3) = 6 > 0
Logo, pelo teste da derivada segunda, x0 = (−1,−1) é máximo local
(não global, pois f(0.5,−1.5) = 4 > 1 = f(x0)), x1 = (0,−1) e x2 =
(0, 0) são pontos de sela e x3 = (1, 0) é mínimo local (não global, pois
f(−1.5, 0.5) = −27 < −1 = f(x3)).
2.6 Seja f(x) = (x1 − x22)(x1 − 12x22). Verifique que x¯ = (0, 0)t é um mi-
nimizador local de φ(λ) ≡ f(x¯ + λd) para todo d ∈ R2, mas x¯ não é
minimizador local de f .
As derivadas parciais de f são dadas por:
∂f
∂x1
= 2x1 − 3
2
x22
∂2f
∂x21
= 2
∂f
∂x2
= −3x1x2 + 2x32
∂2f
∂x22
= −3x1 + 6x22
∂2f
∂x1∂x2
= −3x2
Logo,∇f(x) = (2x1−32x22,−3x1x2+2x32)t e∇2f(x) =
[
2 −3x2
−3x2 −3x1 + 6x22
]
.
Temos então que
28
∇f(x¯) = (2× 0− 3
2
02,−3× 0× 0 + 2× 03)t = (0, 0)t
∇2f(x¯) =
[
2 0
0 0
]
⇒ ∆1 = 2 ≥ 0,∆1 = 0 ≥ 0,∆2 = 2× 0− (0× 0) = 0 ≥ 0
⇒ ∇2f(x¯) é semidefinidapositiva
Logo, como ∇f(x¯) = 0 e ∇2f(x¯) é semidefinida positiva, estão satis-
feitas as condições necessárias para que x¯ seja minimizador local de
f . Porém, x¯ não é minimizador local de f , pois para x1 =
2
3
x22 (com
x2 6= 0) temos f(x1, x2) = (−13x22)(16x22) < 0 = f(x¯) e (23x22, x2)
x2→0−−−→ x¯.
Ainda, temos que
φ(λ) = f(x¯+ λd)
= f((0, 0)t + λ(d1, d2)
t)
= f((λd1, λd2)
t)
= (λd1 − (λd2)2)(λd1 − 1
2
(λd2)
2)
=
1
2
λ4d42 −
3
2
λ3d1d
2
2 + λ
2d21
Dái vem que as derivadas de φ são dadas por:
dφ
dλ
= 2λ3d42 −
9
2
λ2d1d
2
2 + 2λd
2
1 ⇒
dφ
dλ
(0) = 0
d2φ
dλ2
= 6λ2d42 − 9λd1d22 + 2d21 ⇒
d2φ
dλ2
(0) = 2d21 > 0 se d1 6= 0
Logo, λ = 0 é um minimizador local de φ(λ) se d1 6= 0.
2.7 Prove que a função f(x) = (x2 − x21)2 + x51 tem um único ponto estaci-
onário que não é minimizador nem maximizador local.
As derivadas parciais de f são dadas por:
29
∂f
∂x1
= −4x1x2 + 4x31 + 5x41
∂2f
∂x21
= −4x2 + 12x21 + 20x31
∂f
∂x2
= 2x2 − 2x21
∂2f
∂x22
= 2
∂2f
∂x1∂x2
= −4x1
Logo,∇f(x) = (−4x1x2 + 4x31 + 5x41, 2x2 − 2x21)t e
∇2f(x) =
[ −4x2 + 12x21 + 20x31 −4x1
−4x1 2
]
.
Os pontos estacionários são dados pelo sistema:{
−4x1x2 + 4x31 + 5x41 = 0
2x2 − 2x21 = 0
⇒
{
x1(5x
3
1 + 4x
2
1 − 4x2) = 0
−2(x21 − x2) = 0
, cuja única solução é x0 = (0, 0)
t
.
Temos que x0 não é minimizador local de f , pois para x2 = x
2
1 (com
x1 < 0) temos f(x1, x2) = x
5
1 < 0 = f(x0) e (x1, x
2
1)
x1→0−−−−−→ x0.
Analogamente, temos que x0 não é maximizador local de f , pois para
x2 = x
2
1 (com x1 > 0) temos f(x1, x2) = x
5
1 > 0 = f(x0) e (x1, x
2
1)
x1→0+−−−−→
x0.
Logo, f tem um único ponto estacionário x0 = (0, 0)
t
que não é mini-
mizador nem maximizador local de f .
2.8 Encontre funções f : Rn → R, n ≥ 2, tais que ∇(x¯) = 0 e x¯ é:
(a) maximizador local, não global;
Como já visto no exercício 2.5 para a função f(x) = 2x31 − 3x21 −
6x1x2(x1− x2− 1), temos que x0 = (−1,−1) é máximo local (não
global, pois f(0.5,−1.5) = 4 > 1 = f(x0)), pois ∇f(x0) = 0,
det(∇2f(x0)) = 36 > 0 e ∂2f∂x21 (x0) = −6 < 0 .
30
(b) ponto de sela;
Como já visto no exercício 2.5 para a função f(x) = 2x31 − 3x21 −
6x1x2(x1 − x2 − 1), temos que x1 = (0,−1) e x2 = (0, 0) são
pontos de sela pois ∇f(x1) = ∇f(x2) = 0 e det(∇2f(x1)) =
det(∇2f(x2)) = −36 < 0.
(c) minimizador global.
Seja f(x, y) = 3x4 + 2y4. Temos que ∇f(x) = (12x3, 8y3)t,
∇f((0, 0)t) = (0, 0)t e (0, 0)t é minimizador global de f pois
f(x, y) ≥ 0 para todo (x, y) ∈ R2
2.9 Para aproximar uma função g no intervalo [0, 1] por um polinômio de
grau ≤ n, minimizamos a função critério: f(a) = ∫ 1
0
[g(x) − p(x)]2 dx,
onde p(x) = a0 + a1x + · · · + anxn. Encontre as equações a serem
satisfeitas pelos coeficientes ótimos.
Temos que f(a) aumenta quando ‖a‖ aumenta e, como f é limitada
inferiormente por 0, f deve ter um mínimo. Como f é diferenciável
em função de a, então esse mínimo deve ocorrer quando ∇f(a) = 0.
Temos que:
∂f
∂ak
=
∂
∂ak
[∫ 1
0
[g(x)− p(x)]2 dx
]
=
∂
∂ak
[∫ 1
0
[g(x)− (a0 + · · ·+ ak−1xk−1 + akxk + ak+1xk+1 + · · ·+ anxn)]2 dx
]
= −2
∫ 1
0
[g(x)− (a0 + · · ·+ ak−1xk−1 + akxk + ak+1xk+1 + · · ·+ anxn)]xk dx
= −2
∫ 1
0
g(x)xk dx+ 2
n∑
i=0
ai
∫ 1
0
xk+i dx
= −2
∫ 1
0
g(x)xk dx+ 2
n∑
i=0
ai
[
xk+i+1
k + i+ 1
] ∣∣∣1
0
= −2
∫ 1
0
g(x)xk dx+ 2
n∑
i=0
ai
k + i+ 1
Logo, para cada k = 0, 1, . . . , n, as equações a serem satisfeitas pelos
coeficientes ótimos são descritas pelo seguinte sistema:
31
∂f
∂ak
= 0
−2
∫ 1
0
g(x)xk dx+ 2
n∑
i=0
ai
k + i+ 1
= 0
∫ 1
0
g(x)xk dx =
n∑
i=0
ai
k + i+ 1
2.10 Considere o problema irrestrito minimizar f(x) = x21 − x1x2 + 2x22 −
2x1 + exp(x1 + x2).
(a) Escreva as condições necessárias de primeira ordem. São suficien-
tes? Por quê?
As condições de primeira ordem são dadas por:
∂f
∂x1
= 2x1 − x2 − 2 + exp(x1 + x2) = 0
∂f
∂x2
= −x1 + 4x2 + exp(x1 + x2) = 0
Nesse caso, as condições de primeira ordem são suficientes, pois
f(x, y) é convexa (por ser soma de funções convexas).
∂2f
∂x21
= 2 + exp(x1 + x2)
∂2f
∂x22
= 4 + exp(x1 + x2)
∂2f
∂x1∂x2
= −1 + exp(x1 + x2)
Logo, ∇2f(x) =
[
2 + exp(x1 + x2) −1 + exp(x1 + x2)
−1 + exp(x1 + x2) 4 + exp(x1 + x2)
]
.
Os menores principais de ∇2f(x) (determinantes das submatrizes
principais de ∇2f(x¯)) são ∆1 = 2 + exp(x1 + x2) ≥ 0, ∆1 =
32
4 + exp(x1 + x2) ≥ 0 e ∆2 = (2 + exp(x1 + x2)) × (4 + exp(x1 +
x2))− [(−1 + exp(x1 +x2))× (−1 + exp(x1 +x2))] ≥ (2 + exp(x1 +
x2))
2 − (−1 + exp(x1 + x2))2 ≥ 0. Como são todos não negativos,
∇2f(x¯) é semidefinida positiva.
Nesse caso, as condições de primeira ordem são suficientes, pois
∇2f(x) é semidefinida positiva ∀x ∈ R2 (e portanto f é convexa,
o que faz a condição necessária de primeira ordem ser também
suficiente pois R2 é convexo ).
(b) O ponto x¯ = (0, 0)t é ótimo?
Não, pois
∂f
∂x1
(x¯) = −1 6= 0
∂f
∂x2
(x¯) = 1 6= 0
(c) Ache uma direção d ∈ R2 tal que ∇f(x¯)td < 0 .
Tomando d = (1,−1)t, temos ∇f(x¯)td = −1 × 1 + 1 × (−1) =
−2 < 0
(d) Minimize a função a partir de x¯ na direção obtida em (c).
Para λ = 0.25, temos que f(x¯ + λd) = f(0.25,−0.25) ≈ 0.75 <
1 = f(x¯)
2.11 Seja F : Rn → Rn com derivadas contínuas. Seja f : Rn → R dada
por f(x) = ‖F (x)‖2. Seja x¯ minimizador local de f tal que JF (x¯) é
não-singular. Prove que x¯ é solução do sistema F (x) = 0.
Seja F (x) = (F1(x), . . . , Fn(x))
t
, com Fi : R
n → R. Temos então que
f(x) = ‖F (x)‖22 =
n∑
i=1
Fi(x)
2
. Daí segue que:
(∇f(x))k = ∂f
∂xk
=
∂
∂xk
[
n∑
i=1
Fi(x)
2
]
= 2
n∑
i=1
Fi(x)
∂Fi
∂xk
(x)
= 2
n∑
i=1
Fi(x)(JF (x))ik
33
Logo, ∇tf(x) = 2F (x)tJF (x) ⇒ ∇f(x) = 2J tF (x)F (x). Se x∗ é mini-
mizador local de f temos ∇f(x∗) = 0 e portanto
2J tF (x
∗)F (x∗) = ∇f(x∗)
2J tF (x
∗)F (x∗) = 0
J tF (x
∗)F (x∗) = 0
Como JF (x
∗) é não-singular, então o sistema homogêneo J tF (x
∗)F (x∗) =
0 apenas admite a solução trivial F (x∗) = 0. Logo, x∗ é solução do sis-
tema F (x) = 0.
2.12 Considere f : R2 → R, f(x) = (x31 + x2)2 + 2(x2 − x1 − 4)4. Dado
um ponto x ∈ R2 e uma direção 0 6= d ∈ R2, construímos a função
g(λ) = f(x+ λd).
(a) Obtenha uma expressão explícita para g(λ)
g(λ) = f(x+ λd)
= f((x1, x2)
t + λ(d1, d2)
t)
= f((x1 + λd1, x2 + λd2)
t)
= ((x1 + λd1)
3 + (x2 + λd2))
2 + 2((x2 + λd2)− (x1 + λd1)− 4)4
(b) Para x = (0, 0)t e d = (1, 1)t, encontre o minimizador de g
Nesse caso, temos:
g(λ) = ((0 + λ)3 + (0 + λ))2 + 2((0 + λ)− (0 + λ)− 4)4
= (λ3 + λ)2 + 512
Dái vem que as derivadas de g são dadas por:
dg
dλ
= 2(1 + 3λ2)(λ+ λ3) = 0⇒ λ = 0
d2g
dλ2
= 2 + 24λ2 + 30λ4 ⇒ d
2g
dλ2
(0) = 2 > 0
Logo, λ = 0 é um minimizador local de g(λ). Esse minimizador
também é global pois, g(λ) = (λ3 + λ)2 + 512 ≥ 512 = g(0).
34
2.13 Considere a função f(x) = (x1 − 1)2x2. Considere os pontos de R2 da
forma xˆ = (1, x2)
t
.
(a) Analise as condições de otimalidade de primeira e segunda ordem
para esses pontos;
As derivadas parciais de f são dadas por:
∂f
∂x1
= 2x2(x1 − 1)
∂2f
∂x21
= 2x2
∂f
∂x2
= (x1 − 1)2
∂2f
∂x22
= 0
∂2f
∂x1∂x2
= 2(x1 − 1)
Logo,∇f(x) = (2x2(x1−1), (x1−1)2)t e∇2f(x) =
[
2x2 2(x1 − 1)
2(x1 − 1) 0
]
.
Assim, ∇f(xˆ) = (0, 0)t e∇2f(xˆ) =
[
2x2 0
0 0
]
, que é semidefinida
positiva ⇐⇒ x2 ≥ 0.
(b) O que se pode afirmar sobre xˆ utilizando essas informações?
Logo, todos os pontos xˆ são estacionários, mas apenas os com x2 ≥
0 satisfazem a condição necessária para serem mínimos locais.
(c) Use a expressão da função para obter afirmações mais conclusivas
sobre as características de xˆ.Temos que
f(xˆ) = (1− 1)2x2
= 0
Logo, os pontos xˆ estão na curva de nível f(x) = 0.
2.14 Sejam f(x) = 1
2
xtQx − btx, Q ∈ Rn×n simétrica definida positiva e
b ∈ Rn. Sejam x0, x1, . . . , xn ∈ Rn e definimos δj = xj − x0, γj =
35
∇f(xj) − ∇f(x0), j = 0, 1, . . . , n.Prove que se os vetores {δj}nj=1 são
linearmente independentes, então
x˜ = xn − [δ1 . . . δn].[γ1 . . . γn]−1.∇f(xn)
é minimizador global de f .
Pelo exercício 1.16)b), sabemos que ∇f(x) = Qx − b e ∇2f(x) = Q.
Como δj = xj − x0, então xj = δj + x0. Para todo j = 1, . . . , n, temos
que:
γj = ∇f(xj)−∇f(x0)
= Q(δj + x0)− b− [Qx0 − b]
= Qδj +���
��
Qx0 − b−�����[Qx0 − b]
= Qδj
Pela observação da página 39 do livro da Ana, como {δj}nj=1 são linear-
mente independentes então as n diferenças γj = ∇f(δj + x0)−∇f(x0)
(j = 1, . . . , n) determinam completamente Q e Q−1. Nesse caso, temos
então que:
([δ1 . . . δn].[γ1 . . . γn])−1 = ([δ1 . . . δn].[Qδ1 . . . Qδn])−1
= Q−1 (Q é invertível pois é simétrica definida positiva)
Daí vem que
x˜ = xn − [δ1 . . . δn].[γ1 . . . γn]−1.∇f(xn)
= xn −Q−1∇f(xn)
= xn −∇2f(xn)−1∇f(xn)
Portanto, x˜ é obtido a partir de xn via uma iteração do método de
Newton. Logo, x˜ é o minimizador global de f , pois o método de Newton
para funções quadráticas com hessiana definida positiva converge em
um passo para o minimizador global de f (pela proposição 6.1 da p. 35
do livro da Ana).
36
2.15 Definimos a norma de Frobenius de uma matriz A ∈ Rm×n como
‖A‖F =
(
m∑
i=1
n∑
j=1
a2ij
)1/2
. Dada uma matriz A ∈ Rn×n, encontre a matriz simétrica mais pró-
xima de A na norma de Frobenius, isto é, encontre a matriz B ∈ Rn×n,
simétrica tal que ‖A−B‖F é mínima.
Sejam A ∈ Rn×n, B ∈ Rn×n simétrica com elementos (variáveis) bij
(como B é simétrica, bij = bji). Definimos f(B) = f(b11, . . . , bnn) =
‖A−B‖F =
(
n∑
i=1
n∑
j=1
(aij − bij)2
)1/2
.
Temos que f(B) aumenta quando ‖B‖F aumenta e, como f é limitada
inferiormente por 0 (basta escolher B = A), f deve ter um mínimo.
Como f é diferenciável em função de B, então esse mínimo deve ocorrer
quando ∇f(B) = 0. Temos que:
∂f
∂bkl
=
∂
∂bkl
( n∑
i=1
n∑
j=1
(aij − bij)2
)1/2
=
1
2
(
n∑
i=1
n∑
j=1
(aij − bij)2
)−1/2
(−2(akl − bkl)− 2(alk − blk))
Se A for simétrica, temos que B = A minimiza f . Se A não for simé-
trica, temos ‖A−B‖F > 0 e portanto ∇f apenas será nulo quando o
seguinte sistema for satisfeito (definamos xkl = bkl = blk):{
−2(akl − bkl)− 2(alk − blk) = 0 ⇒
{
xkl = (akl + alk)/2
Logo, a matriz B simétrica que minimiza f é dada por B = 1
2
(A+At)
2.16 Seja f : R → R e suponha f (j)(a) = 0, j = 0, . . . , n − 1 e f (n)(a) 6= 0.
Sobre que condições o ponto x = a poderá ser um minimizador de f?
Baseado em sua resposta: f(x) = x13 tem um mínimo em x = 0 ? E
f(x) = x16 ?
O teste da derivada de ordem superior (https://en.wikipedia.org/
wiki/Higher-order_derivative_test) diz que:
Seja f : R → R função de classe Cn+1 no intervalo I ⊂ R, c ∈ I ,
n ≥ 1. Se f ′(c) = · · · = f (n)(c) = 0 e f (n+1)(c) 6= 0, então:
37
• se n é ímpar temos um extremante local em c, isto é:
1. f (n+1)(c) < 0⇒ c é um máximo local
2. f (n+1)(c) > 0⇒ c é um mínimo local
• se n é par temos um ponto de sela (local) em c, isto é:
1. f (n+1)(c) < 0 ⇒ c é um ponto de inflexão estritamente de-
crescente
2. f (n+1)(c) > 0 ⇒ c é um ponto de inflexão estritamente cres-
cente
Para f(x) = x13, temos f ′(0) = · · · = f (12)(0) = 0 e f (12+1)(0) =
13! > 0. Logo, como 12 é par e f (12+1)(0) > 0, segue que c = 0 é um
ponto de inflexão estritamente crescente.
Para f(x) = x16, temos f ′(0) = · · · = f (15)(0) = 0 e f (15+1)(0) =
15! > 0. Logo, como 15 é ímpar e f (15+1)(0) > 0, segue que c = 0 é um
ponto de mínimo local.
2.17 Se for possível determine a e b de modo que f(x) = x3 +ax2 + bx tenha
um máximo local em x = 0 e um mínimo local em x = 1.
Dái vem que as derivadas de f são dadas por:
f ′(x) = 3x2 + 2ax+ b
f ′′(x) = 6x+ 2a
Supondo que 0 e 1 sejam extremantes locais, temos o sistema:{
f ′(0) = 0
f ′(1) = 0
⇒
{
b = 0
a = −3/2
Como x = 0 é máximo local e x = 1 é mínimo local, também devemos
ter:{
f ′′(0) < 0
f ′′(1) > 0
⇒
{
2(−3/2) = −3 < 0
6 + 2(−3/2) = 3 > 0
Logo, para que x = 0 seja máximo local e x = 1 seja mínimo local, é
suficiente que a = −3/2 e b = 0.
38
1.3 Capítulo 3 - Convexidade
3.1 Prove que a intersecção de conjuntos convexos é convexa.
Sejam S, T ⊂ Rn convexos, e sejam x, y ∈ S ∩ T . Como S é convexo,
∀λ ∈ [0, 1] segue que λx + (1 − λ)y ∈ S. Analogamente, como T é
convexo, ∀λ ∈ [0, 1] segue que λx + (1 − λ)y ∈ T . Logo, todas as
combinações convexas de elementos de S ∩ T estão tanto em S quanto
em T , isto é, estão em S ∩ T . Portanto, S ∩ T é convexo.
3.2 Prove que S = {x ∈ Rn | ‖x‖ ≤ c, c > 0}, onde ‖.‖ é uma norma
qualquer em Rn, é um conjunto convexo.
Sejam x, y ∈ S e λ ∈ [0, 1]. Temos que:
‖λx+ (1− λ)y‖ ≤ ‖λx‖+ ‖(1− λ)y‖ (desig. triang)
= λ ‖x‖+ (1− λ) ‖y‖ (‖.‖ é norma e λ, 1− λ ∈ R+)
≤ λc+ (1− λ)c (x, y ∈ S)
= c
Logo, ‖λx+ (1− λ)y‖ ≤ c e portanto λx+ (1− λ)y ∈ S. Como x, y, λ
foram escolhidos arbitrariamente, segue que S é convexo.
3.3 Verifique se as funções abaixo são convexas:
(a) f(x) = max{g(x), h(x)}, onde g e h são funções convexas;
Sejam x, y ∈ S (conjunto convexo que é o domínio de g e h) e
λ ∈ [0, 1]. Temos que:
f(λx+ (1− λ)y) = max{g(λx+ (1− λ)y), h(λx+ (1− λ)y)}
≤ max{λg(x) + (1− λ)g(y), λh(x) + (1− λ)h(y)}
(g, h são convexas)
≤ max{λg(x), λh(x)}+ max{(1− λ)g(y), (1− λ)h(y)}
= λmax{g(x), h(x)}+ (1− λ) max{g(y), h(y)}
= λf(x) + (1− λ)f(y)
Como x, y, λ foram escolhidos arbitrariamente, segue que f é con-
vexa.
39
(b) t(x) =
∑n
i=1 x
2
i = ‖x‖22
Primeiramente, provemos que g(x) = ‖x‖2 é convexa. Sejam
x, y ∈ S (conjunto convexo que é o domínio de g) e λ ∈ [0, 1].
Temos que:
g(λx+ (1− λ)y) = ‖λx+ (1− λ)y‖2
≤ ‖λx‖2 + ‖(1− λ)y‖2 (desig. triang)
= λ ‖x‖2 + (1− λ) ‖y‖2 (‖.‖2 é norma e λ, 1− λ ∈ R+)
= λg(x) + (1− λ)g(y)
Como x, y, λ foram escolhidos arbitrariamente, segue que g é con-
vexa.
Além disso, notemos que f(x) = x2 é convexa (pois f ′′(x) = 2 ≥ 0)
e também é não decrescente para x ≤ 0. Daí segue que, para
x, y ∈ S (conjunto convexo que é o domínio de g) e λ ∈ [0, 1]:
t(λx+ (1− λ)y) = f(g(λx+ (1− λ)y))
≤ f(λg(x) + (1− λ)g(y))
(f é não decrescente para x ≥ 0 e g é convexa
com contradomínio R+)
≤ λf(g(x)) + (1− λ)f(g(y)) (f é convexa)
= λt(x) + (1− λ)t(y)
Como x, y, λ foram escolhidos arbitrariamente, segue que t é con-
vexa (mais geralmente, se f é convexa não decrescente e g é con-
vexa, segue que a composta f ◦ g é convexa).
(c) s(x) = exp(f(x)), f : Rn → R.
Suponhamos que f seja convexa. Temos também que exp(x) é
convexa (pois exp′′(x) = exp(x) > 0) e não decrescente. Logo,
como s = exp ◦f , exp é convexa não decrescente e f é convexa,
segue pelo exercício anterior (3.3)b)) que s é convexa.
3.4 Desenhe as curvas de nível de uma função convexa. Justifique!
40
Seja f uma função convexa definida num convexo S. Seja também
nivα(f) = {x ∈ S | f(x) ≤ α} o conjunto de nível de f correspondente
à constante α ∈ R.
Provemos que nivα(f) é um conjunto convexo. Para x, y ∈ nivα(f) e
λ ∈ [0, 1], temos que:
f(λx+ (1− λ)y) ≤ λf(x) + (1− λ)f(y) (f é convexa)
≤ λα + (1− λ)α (x, y ∈ nivα(f))
= α
Logo, λx+ (1− λ)y ∈ nivα(f). Como x, y, λ são arbitrários, segue que
nivα(f) é um conjunto convexo.
Como a curva de nível correspondente a α é a fronteira do conjunto
nivα(f), isso significa que cada curva de nível de f é a fronteira de um
conjunto convexo (que é nivα(f) ). Em outras palavras, cada curva de
nível de f é uma curva convexa. Por exemplo, as curvas de nível de
f(x, y) = x2 + y2 estão a seguir:
Figura 5: Curvas de nível geradas com o WolframAlpha . Regiões mais claras
indicam valores maiores dafunção.
3.5 Seja f um conjunto convexo não vazio em Rn. Seja f : Rn → R a
função definida por f(y) = min{‖y − x‖ | x ∈ S}. Esta função é
convexa. Prove esta afirmação quando S = {x ∈ R2 | ax1 + bx2 = c} .
Interprete geometricamente.
S é conjunto dos pontos (x1, x2) ∈ R2 que pertencem à reta definida
por ax1 + bx2− c = 0. Como f(y) = min{‖y − x‖ | x ∈ S}, temos que
41
f(y) é a distância de y à reta definida por ax1 + bx2− c = 0 (em outras
palavras, f(y) é a norma da projeção de y em S), e portanto
f(y) =
|ay1 + by2 − c|√
a2 + b2
.
Para x, y ∈ S e λ ∈ [0, 1], temos:
f(λx+ (1− λ)y) = |a(λx1 + (1− λ)y1) + b(λx2 + (1− λ)y2)− c|√
a2 + b2
=
|λ(ax1 + bx2) + (1− λ)(ay1 + by2)− (λ+ (1− λ))c|√
a2 + b2
=
|λ(ax1 + bx2 − c) + (1− λ)(ay1 + by2 − c)|√
a2 + b2
≤ λ |ax1 + bx2 − c|√
a2 + b2
+ (1− λ) |ay1 + by2 − c|√
a2 + b2
(desig. triang.)
= λf(x) + (1− λ)f(y)
Logo, como x, y, λ foram escolhidos arbitrariamente, f é convexa.
1.4 Capítulo 4 - Modelo de algoritmo com buscas dire-
cionais
4.1 Considere a função quadrática f(x) = 1
2
xtAx + btx + c = 1
2
< x,Ax >
+ < b, x > +c, onde A ∈ Rn×n é simétrica, b ∈ Rn e c ∈ R. Seja x˜
minimizador local de f . Prove que x˜ é minimizador global.
Como calculado no exercício 1.16 b), temos que ∇f(x) = Ax + b e
∇2f(x) = A. Como x˜ é minimizador local de f , temos que ∇f(x˜) =
Ax˜+ b = 0⇒ b = −Ax˜. Portanto, f pode ser reescrita como:
42
f(x) =
1
2
< x,Ax > + < b, x > +c
=< x,
1
2
Ax > + < −Ax˜, x > +c
=< x,
1
2
Ax− Ax˜ > +c
=< x,A(
1
2
x− x˜) > +c
Logo, para x ∈ Rn:
f(x)− f(x˜) = 1
2
< x,Ax > + < b, x > +�c−
1
2
< x˜,Ax˜ > − < b, x˜ > −�c
=< x,
1
2
Ax > + < b, x > + < x˜,−1
2
Ax˜ > + < −b, x˜ >
=< x,
1
2
Ax > + < b, x > + < −x˜, 1
2
Ax˜ > + < b,−x˜ >
=< x,
1
2
Ax > + < −Ax˜, x > + < −x˜, 1
2
Ax˜ > + < −Ax˜,−x˜ >
=< x,
1
2
Ax > + < −Ax˜, x > + < −x˜, 1
2
Ax˜− Ax˜ >
=< x,
1
2
Ax > + < −Ax˜, x > + < −x˜,−1
2
Ax˜ >
=< x,
1
2
Ax > +
1
2
< −Ax˜, x > +1
2
< −Ax˜, x > + < −x˜,−1
2
Ax˜ >
=< x,
1
2
Ax > + < x,−1
2
Ax˜ > + < −x, 1
2
Ax˜ > + < −x˜,−1
2
Ax˜ >
(< −x, 1
2
Ax˜ >= −1
2
n∑
i=1
n∑
j=1
aijxix˜j =< −x˜, 1
2
Ax > pois A é simétrica)
=< x,
1
2
Ax > + < x,−1
2
Ax˜ > + < −x˜, 1
2
Ax > + < −x˜,−1
2
Ax˜ >
=< x− x˜, 1
2
Ax− 1
2
Ax˜ >
=
1
2
< x− x˜, A(x− x˜) >
Ainda, como x˜ é minimizador local de f , para todo x ∈ Rn existe ε > 0
tal que:
43
0 ≤ f(x˜+ ε(x− x˜))− f(x˜)
=< x˜+ ε(x− x˜), A(1
2
[x˜+ ε(x− x˜)]− x˜) > +�c− < x˜,A(
1
2
x˜− x˜) > −�c
=< x˜+ εx− εx˜,−1
2
Ax˜+
1
2
εAx− 1
2
εAx˜ > − < x˜,−1
2
Ax˜ >
=< x˜+ ε(x− x˜),−1
2
Ax˜+
1
2
εA(x− x˜) > − < x˜,−1
2
Ax˜ >
=���
���
��
< x˜,−1
2
Ax˜ >+ < x˜,
1
2
εA(x− x˜) > + < ε(x− x˜),−1
2
Ax˜ > + < ε(x− x˜), 1
2
εA(x− x˜) >
−�����
���
< x˜,−1
2
Ax˜ >
=
1
2
ε < x˜, A(x− x˜) > −1
2
ε < x− x˜, Ax˜ > +ε
2
2
< x− x˜, A(x− x˜) >
=���
���
��1
2
ε < x˜, Ax >−XXXXXXXX
1
2
ε < x˜, Ax˜ >−�����
���1
2
ε < x,Ax˜ >+
XXXXXXXX
1
2
ε < x˜, Ax˜ >
+
ε2
2
< x− x˜, A(x− x˜) >
=
ε2
2
< x− x˜, A(x− x˜) >
Daí segue que < x − x˜, A(x − x˜) >≥ 0. Como f(x) − f(x˜) = 1
2
<
x − x˜, A(x − x˜) >, temos também que f(x) − f(x˜) ≥ 0 para todo
x ∈ Rn. Portanto, x˜ é minimizador global de f .
4.2 Através de um desenho mostre que se d é uma direção tal que∇tf(x)d =
0 então d pode ser de descida, subida ou nenhuma das duas coisas.
No desenho a seguir, temos ∇tf(x)d1 = 0 e ∇tf(x)d2 = 0 (pois são
duas direções ortogonais a ∇f(x)), mas d1 é direção de descida (pois
vai na direção de curvas de nível de valor mais baixo de f) e d2 é direção
de subida (pois vai na direção de curvas de nível de valor mais alto de
f)
44
Um caso em que d não é direção de descida e nem de subida ocorre
quando as curvas de nível de f são paralelas. Quando isso ocorre, as
direções perpendiculares a ∇f(x) levam apenas a pontos da mesma
curva de nível de x, e.g., quando f(x, y) = x+ y:
4.3 Considere o sistema não linear
fi(x) = 0, fi : R
n → R, i = 1, . . . ,m.
Como resolveria o sistema com técnicas de minimização irrestrita?
Seja F : Rm → R tal que, para todo i = 1, . . . ,m, temos que ∂F
∂xi
= fi
(ou seja, ∇F (x1, . . . , xm) = (f1, . . . , fm)). Logo, utilizando técnicas de
minimização irrestrita podemos tentar encontrar um ponto xk ∈ Rm
tal que ∇F (xk) = 0. Temos três casos:
• se m = n, então xk ∈ Rn. Como ∇F = (f1, . . . , fm), então segue
que fi(x
k) = 0 para todo i = 1, . . . ,m;
• se m < n (há mais variáveis que equações), então seria necessá-
rio descobrir as n − m variáveis livres do sistema, escrevendo-as
45
em função das variáveis presentes em xk. Dessa forma, podemos
estender xk para um xk
′ ∈ Rn, de tal forma que fi(xk′) = 0 para
todo i = 1, . . . ,m;
• se m > n (há mais equações que variáveis), então podemos res-
tringir xk para um xk
′ ∈ Rn (eliminando as variáveis de xk que
não aparecem no sistema), de tal forma que fi(x
k′) = 0 para todo
i = 1, . . . ,m;
4.4 Seja f(x) = 1
2
‖F (x)‖2, onde F : Rn → Rn, F ∈ C1. Considere o
método iterativo definido por
xk+1 = xk − λk(JF (xk))−1F (xk).
Suponha que JF (x) é não singular para todo x. Prove que se na con-
dição de Armijo usamos α = 0.5, resulta
f(xk+1)
f(xk)
≤ 1− λk
.
Seja F (x) = (F1(x), . . . , Fn(x))
t
, com Fi : R
n → R. Temos então que
f(x) = 1
2
‖F (x)‖22 = 12
n∑
i=1
Fi(x)
2
. Daí segue que:
(∇f(x))k = ∂f
∂xk
=
∂
∂xk
[
1
2
n∑
i=1
Fi(x)
2
]
=
n∑
i=1
Fi(x)
∂Fi
∂xk
(x)
=
n∑
i=1
Fi(x)(JF (x))ik
Logo, ∇tf(x) = F (x)tJF (x)⇒ ∇f(x) = J tF (x)F (x).
Pela definição do método iterativo, temos dk = −(JF (xk))−1F (xk) (ou
seja, dk é a direção de Newton). Nesse caso, como f(x) =
1
2
‖F (x)‖2 ≥ 0
para todo x ∈ Rn, a condição de Armijo fica:
46
f(xk + λkdk) ≤ f(xk) + α∇tf(xk)λkdk
f(xk+1) ≤ f(xk) + 1
2
F (xk)tJF (x
k)λk[−(JF (xk))−1F (xk)]
f(xk+1) ≤ f(xk)− λk
2
F (xk)t JF (x
k)(JF (x
k))−1︸ ︷︷ ︸
=I
F (xk)
f(xk+1) ≤ f(xk)− λk
2
F (xk)tF (xk)︸ ︷︷ ︸
=‖F (xk)‖2
2
f(xk+1)
f(xk)
≤ 1− λk
∥∥F (xk)∥∥2
2
2f(xk)︸ ︷︷ ︸
=1 pois 2f(xk)=‖F (x)‖22
f(xk+1)
f(xk)
≤ 1− λk
4.5 Seja f : R→ R, f ∈ C2, f ′(0) < 0 e f ′′(x) < 0 para todo x ∈ R. Seja
α ∈ (0, 1). Prove que, para todo x > 0,
f(x) ≤ f(0) + αxf ′(0).
Como f ∈ C2, para x > 0, pela fórmula de Taylor com resto de La-
grange existe pelo menos um x¯ ∈ (0, x) tal que:
f(x) = f(0) + xf ′(0) +
f ′′(x¯)
2︸ ︷︷ ︸
<0
x2︸︷︷︸
>0
≤ f(0) + x︸︷︷︸
>0
f ′(0)︸ ︷︷ ︸
<0
(pois
f ′′(x¯)
2
x2 < 0)
≤ f(0) + αxf ′(0) (pois α ∈ (0, 1) e xf ′(0) < 0)
4.6 Se um método de direções de descida com busca linear exata é utilizado
para minimizar uma função quadrática q : Rn → R, mostre que o passo
ótimo é dado por
λ = − d
t∇q(x)
dt∇2q(x)d,
47
onde d é a direção utilizada a partir do ponto x.
Consideremos a função quadrática q(x) = 1
2
xtAx + btx + c = 1
2
<
x,Ax > + < b, x > +c, onde A ∈ Rn×n simétrica, b ∈ Rn e c ∈ R.
Pelo exercício 1.16)b), sabemos que ∇q(x) = Ax+ b e ∇2q(x) = A .
Seja x o ponto atual, e seja d uma direção de descida (i.e.,∇tq(x)d < 0).
Definamos φ(λ) := q(x+ λd). Temos que:
φ(λ) = q(x+ λd)
=
1
2
< x+ λd,A(x+ λd) > + < b, x+ λd > +c
=
1
2
[< x,Ax > + < x,Aλd > + < λd,Ax > + < λd,Aλd >]+ < b, x > + < b, λd > +c
=
1
2
[< x,Ax > +λ < x,Ad > +λ < d,Ax > +λ2 < d,Ad >]+ < b, x > +λ < b, d > +c
A busca linear exata escolhe o tamanho do passo λ que minimiza φ(λ).
Os pontos estacionários de φ(λ) são dados por:
48
0 = φ′(λ)
0 =
1
2
[< x,Ad > + < d,Ax > +2λ < d,Ad >]+ < b, d >
−2 < b, d > =< x,Ad > + < d,Ax> +2λ < d,Ad >
2λ < d,Ad > = −[2 < b, d > + < x,Ad > + < d,Ax >]
λ < d,Ad > = −[< b, d > +1
2
< x,Ad > +
1
2
< d,Ax >]
λ < d,Ad > = −[< b, d > +1
2
< x,Ad > + < d,
1
2
Ax >]
λ < d,Ad > = −[< x, 1
2
Ad > + < d,
1
2
Ax+ b >]
(< x,
1
2
Ad > =< d,
1
2
Ax > pois A é simétrica)
λ < d,Ad > = −[< d, 1
2
Ax > + < d,
1
2
Ax+ b >]
λ < d,Ad > = −[< d,Ax+ b >]
λ = −< d,Ax+ b >
< d,Ad >
λ = −d
t(Ax+ b)
dtAd
λ = − d
t∇q(x)
dt∇2q(x)d
Seja λ∗ = − dt∇q(x)
dt∇2q(x)d . Calculando a derivada segunda de φ em λ
∗
,
obtemos:
φ′′(λ∗) =< d,Ad >
= dtAd (> 0 se A for definida positiva)
Logo, para A simétrica definida positiva (nesse caso, λ∗ é o mínimo de
φ(λ)), o passo ótimo é dado por λ∗ = − dt∇q(x)
dt∇2q(x)d .
4.7 O critério de decréscimo suficiente (condição de Armijo) exige λ ∈ R
tal que
ϕ(λ) = f(x+ λd) < f(x) + αλ∇tf(x)d = ϕ(0) + αλϕ′(0), (∗)
49
com α ∈ (0, 1). Se f é uma função quadrática, então ϕ é uma pará-
bola. Prove que se o minimizador λ˜ dessa parábola é admissível em (∗)
devemos ter α ∈ (0, 1
2
).
Consideremos a função quadrática f(x) = 1
2
xtAx + btx + c = 1
2
<
x,Ax > + < b, x > +c, onde A ∈ Rn×n simétrica definida positiva,
b ∈ Rn e c ∈ R.
Pelo exercício 1.16)b), sabemos que ∇f(x) = Ax+ b e ∇2f(x) = A .
Seja x o ponto atual, e seja d uma direção de descida (i.e., ∇tf(x)d <
0). Definindo ϕ(λ) := f(x + λd), pelo exercício 4.6 sabemos que o
minimizador de ϕ(λ) é λ˜ = −<d,Ax+b>
<d,Ad>
.
Também pelo exercício 4.6, sabemos que
50
ϕ(λ) =
1
2
[< x,Ax > +λ < x,Ad > +λ < d,Ax > +λ2 < d,Ad >]
+ < b, x > +λ < b, d > +c
= λ2
a′︷ ︸︸ ︷
[
1
2
< d,Ad >] +λ
b′︷ ︸︸ ︷
[
1
2
(< x,Ad > + < d,Ax >)+ < b, d >]
+
c′︷ ︸︸ ︷
1
2
< x,Ax > + < b, x > +c
⇒
ϕ(0) =
1
2
< x,Ax > + < b, x > +c
e
ϕ(λ˜) =
−∆
4a′
=
−(b′2 − 4a′c′)
4a′
=
4a′c′ − b′2
4a′
= c′ − b
′2
4a′
=
1
2
< x,Ax > + < b, x > +c− [
1
2
(< x,Ad > + < d,Ax >)+ < b, d >]2
4(1
2
< d,Ad >)
(< x,Ad >=< d,Ax > pois A é simétrica)
=
1
2
< x,Ax > + < b, x > +c− [< d,Ax > + < b, d >]
2
2 < d,Ad >
=
1
2
< x,Ax > + < b, x > +c− < d,Ax+ b >
2
2 < d,Ad >
e que
51
ϕ′(λ) =
1
2
[< x,Ad > + < d,Ax > +2λ < d,Ad >]+ < b, d >
⇒
ϕ′(0) =
1
2
[< x,Ad > + < d,Ax >]+ < b, d >
(< x,Ad >=< d,Ax > pois A é simétrica)
=< d,Ax > + < b, d >
=< d,Ax+ b >
Se λ˜ satisfaz a condição de Armijo, temos que:
ϕ(λ˜) < ϕ(0) + αλ˜ϕ′(0)
((((
((((
((((
((1
2
< x,Ax > + < b, x > +c− < d,Ax+ b >
2
2 < d,Ad >
<
((((
((((
((((
((1
2
< x,Ax > + < b, x > +c+ α(−< d,Ax+ b >
< d,Ad >
) < d,Ax+ b >
((((
((((< d,Ax+ b >2
2
XXXXX< d,Ad >
> α(
((((
(((
< d,Ax+ b >2
XXXXX< d,Ad >
1
2
> α
Pela proposição 4.1 (p.21 do livro da Ana) sabemos que α > 0, e pela
inequação anterior se λ˜ satisfaz a condição de Armijo então α < 1
2
.
Logo, se λ˜ satisfaz a condição de Armijo, então α ∈ (0, 1
2
).
4.8 Sejam f : Rn → R, x, d ∈ Rn e λ > 0 tal que x+λd satisfaz a condição
de Armijo. Seja 0 < µ < λ. µ satisfaz a condição de Armijo? Prove ou
dê um contraexemplo.
Como a condição de Armijo é satisfeita para x+ λd, temos:
f(x+ λd)︸ ︷︷ ︸
φ(λ):=
< f(x) + αλ∇tf(x)d︸ ︷︷ ︸
s(λ):=
= φ(0) + αλφ′(0)
Supondo que d seja direção de descida, temos também que:
52
αλ∇tf(x)d < 0
µ satisfaz a condição de Armijo apenas se:
f(x+ µd) < f(x) + αµ∇tf(x)d
φ(µ) < φ(0) + αµφ′(0)
φ(µ) < φ(0) + αφ′(0)(µ− 0) (∗)
Logo, em particular, se φ(λ) for uma função convexa no intervalo [0, µ]
e se φ′(0) > 0, teremos que:
φ(µ) ≥ φ(0) + φ′(0)(µ− 0)
(como φ′(0)(µ− 0) > 0 e α ∈ (0, 1), temos)
φ(µ) ≥ φ(0) + αφ′(0)(µ− 0)
Nesse caso, temos então que a inequação (∗) não é satisfeita, e portanto
µ não satisfaz a condição de Armijo.
Uma ilustração de um contraexemplo aparece a seguir. Nesse exemplo,
temos que λ = t é admissível (satisfaz a condição de Armijo), mas
λ = βs não é (e temos que 0 < βs < t):
53
4.9 Sejam f : Rn → R, f ∈ C2 e x¯ ∈ Rn tal que ∇f(x¯) = 0 e ∇2f(x¯) não
é semidefinida positiva. Prove que existe uma direção de descida d em
x¯.
Como ∇2f(x¯) não é semidefinida positiva, então existe d ∈ Rn tal que
dt∇2f(x¯)d < 0.
Como dt∇2f(x¯)d < 0, então escolhamos d′ pequeno o suficiente tal que
d′t∇2f(x¯ + εd′)d′ < 0 para todo ε ∈ (0, 1). Pela fórmula de Taylor de
segunda ordem, temos que existe ε ∈ (0, 1) tal que
f(x¯+ d′) = f(x¯) +∇tf(x¯)d′ + 1
2
d′t∇2f(x¯+ εd′)d′
f(x¯+ d′)− f(x¯) =������:
0∇tf(x¯)d′ + 1
2
d′t∇2f(x¯+ εd′)d′
=
1
2
<0︷ ︸︸ ︷
d′t∇2f(x¯+ εd′)d′
< 0
Logo, como f(x¯ + d′) − f(x¯) < 0, d′ é uma direção de descida para f
em x¯.
4.10 No processo de minimizar uma função f : Rn → R, f ∈ C1, a iteração
xk foi obtida fazendo uma busca linear ao longo da direção dk−1. De-
termine uma direção dk ortogonal a dk−1, de descida a partir de xk e
que seja uma combinação linear de dk−1 e ∇f(xk).
Como xk foi obtida fazendo uma busca linear ao longo da direção dk−1,
então existe λk−1 > 0 tal que xk = xk−1 + λk−1dk−1.
Como dk é uma combinação linear de dk−1 e ∇f(xk), então existem
a, b ∈ R tal que dk = adk−1 + b∇f(xk).
Como dk é ortogonal a dk−1, temos:
54
(dk)tdk−1 = 0
(adk−1 + b∇f(xk))tdk−1 = 0
(a(dk−1)t + b∇tf(xk))dk−1 = 0
a(dk−1)tdk−1 + b∇tf(xk)dk−1 = 0
a
∥∥dk−1∥∥2
2
+ b∇tf(xk)dk−1 = 0
a = −b∇
tf(xk)dk−1
‖dk−1‖22
Observemos que, pela desigualdade de Cauchy-Schwarz, para quaisquer
u, v ∈ Rn temos :
(utv)2 ≤ ‖u‖22 ‖v‖22
(para u = ∇f(xk) e v = dk−1)
(∇tf(xk)dk−1)2 ≤ ∥∥∇f(xk)∥∥2
2
∥∥dk−1∥∥2
2
(∇tf(xk)dk−1)2
‖dk−1‖22
− ∥∥∇f(xk)∥∥2
2
≤ 0
∥∥∇f(xk)∥∥2
2
− (∇
tf(xk)dk−1)2
‖dk−1‖22
≥ 0 (> 0 se ∇f(xk) e dk−1 forem L.I.)
55
Além disso, como dk é direção de descida para f a partir de xk, temos:
∇tf(xk)dk < 0
∇tf(xk)(adk−1 + b∇f(xk)) < 0
a∇tf(xk)dk−1 + b∇tf(xk)∇f(xk) < 0
−b∇
tf(xk)dk−1
‖dk−1‖22
∇tf(xk)dk−1 + b ∥∥∇f(xk)∥∥2
2
< 0
−b(∇
tf(xk)dk−1)2
‖dk−1‖22
+ b
∥∥∇f(xk)∥∥2
2
< 0
b

≥0 por Cauchy-Schwarz︷ ︸︸ ︷∥∥∇f(xk)∥∥2
2
− (∇
tf(xk)dk−1)2
‖dk−1‖22
 < 0
(se ∇f(xk) e dk−1 forem L.I.)
b < 0
Portanto, temos que a direção dk desejada é dada por
dk = −b∇
tf(xk)dk−1
‖dk−1‖22
dk−1 + b∇f(xk)
, sendo b algum número real negativo (supondo que ∇f(xk) e dk−1 são
L.I.).
4.11 Sejam f : Rn → R, x¯ ∈ Rn com ∇f(x¯) 6= 0. Seja M ∈ Rn×n definida
positiva. Prove que d = −M∇f(x¯) é uma direção de descida em x¯.
Como M é definida positiva, temos d′tMd′ > 0 para todo 0 6= d′ ∈ Rn.
Em particular, para d′ = ∇f(x¯) 6= 0, segue que:
d′tMd′ > 0
∇tf(x¯)M∇f(x¯) > 0
∇tf(x¯)[−M∇f(x¯)] < 0
∇tf(x¯)d < 0
Logo, d = −M∇f(x¯) é uma direção de descida para f em x¯.
56
1.5 Capítulo 5 - Ordem de convergência
5.1 Prove que convergência superlinear implica linear.
Suponhamos que {xk} ⊆ Rn seja uma sequência que converge superli-
nearmente a x∗, isto é:
lim
k→∞
ek+1
ek
= lim
k→∞
∥∥xk+1 − x∗∥∥
‖xk − x∗‖ = 0
Da definição de limite de sequência, para todo ε > 0 (em particular
para ε ∈ (0, 1)) existe um natural k0 tal que se k > k0 então:
∥∥∥∥ek+1ek − 0
∥∥∥∥ < ε∥∥∥∥∥
∥∥xk+1 − x∗∥∥
‖xk − x∗‖
∥∥∥∥∥ < ε∥∥xk+1 − x∗∥∥
‖xk − x∗‖ < ε∥∥xk+1 − x∗∥∥ < ε∥∥xk − x∗∥∥
ek+1 < εek
Logo, como podemos escolher ε ∈ (0, 1), segue que {xk} converge line-
armente a x∗.
5.2 Prove que convergência quadrática implica superlinear.
Suponhamos que {xk} ⊆ Rn seja uma sequência que converge quadra-
ticamente a x∗, isto é: existem a, k0 > 0 tais que, para k > k0:
57
ek+1 ≤ a(ek)2∥∥xk+1 − x∗∥∥ ≤ a ∥∥xk − x∗∥∥2∥∥xk+1 − x∗∥∥
‖xk − x∗‖ ≤ a
∥∥xk − x∗∥∥
lim
k→∞
∥∥xk+1 − x∗∥∥
‖xk − x∗‖ ≤ limk→∞ a
∥∥xk − x∗∥∥
= a lim
k→∞
∥∥xk − x∗∥∥
= 0
Logo, lim
k→∞
‖xk+1−x∗‖
‖xk−x∗‖ = limk→∞
ek+1
ek
= 0 e, portanto,{xk} converge super-
linearmente a x∗.
5.3 Mostre que uma sequência pode convergir linearmente com uma norma
mas não com outra. No entanto, a convergência superlinear é indepe-
dente da norma.
não resolvido
1.6 Capítulo 6 - Métodos clássicos de descida
6.1 Seja f : Rn → R, diferenciável em x¯ e sejam d1, . . . , dn ∈ Rn vetores
linearmente independentes. Suponha que o mínimo de f(x¯+ λdj) com
λ ∈ R ocorra em λ = 0 para j = 1, . . . , n. Prove que ∇f(x¯) = 0. Isso
implica que f tem um mínimo local em x¯ ?
Definamos φj(λ) := f(x¯ + λd
j). Pela regra da cadeia, temos φ′j(λ) =
∇tf(x¯ + λdj)dj. Como o mínimo de φj(λ) ocorre em λ = 0 para
j = 1, . . . , n, então para todo j = 1, . . . , n segue que:
φ′j(0) = 0
∇tf(x¯+ 0dj)dj = 0
∇tf(x¯)dj = 0
Ou seja, ∇f(x¯) é ortogonal a cada vetor dj (para todo j = 1, . . . , n).
Ainda, como {d1, . . . , dn} são n vetores L.I. em Rn, então eles formam
58
uma base de Rn. Portanto, existem k1, . . . , kn ∈ R tal que ∇f(x¯) =
n∑
i=1
kid
i
. Daí vem que:
‖∇f(x¯)‖22 =< ∇f(x¯),∇f(x¯) >
=<
n∑
i=1
kid
i,∇f(x¯) >
=
n∑
i=1
ki< d
i,∇f(x¯) >︸ ︷︷ ︸
=0
= 0
Logo, ‖∇f(x¯)‖2 = 0 ⇒ ∇f(x¯) = 0. Logo, x¯ é um ponto crítico de f ,
mas não necessariamente um mínimo local. Seria possível que existisse
alguma direção d 6∈ {d1, . . . , dn} que fosse uma direção de descida para
f em x¯, e nesse caso x¯ seria um ponto de sela de f .
6.2 Seja f(x) = 1
2
xtAx + btx + c, onde A ∈ Rn×n é simétrica e definida
positiva, b ∈ Rn e c ∈ R. Sejam L1 e L2 duas retas diferentes e
paralelas em Rn, cujo vetor diretor é d. Sejam x1 e x2 minimizadores
de f em L1 e L2, respectivamente. Prove que (x
2 − x1)tAd = 0.
Pelo exercício 1.16)b), temos que ∇f(x) = Ax + b. Como x1 e x2
minimizadores de f em L1 = x1+λd e L2 = x2+λd (respectivamente),
temos que as funções f(x1 + λd) e f(x2 + λd) são ambas minimizadas
para λ = 0. Logo,
∂f(x1 + λd)
∂λ
∣∣∣∣
λ=0
= 0
∇tf(x1 + λd)d|λ=0 = 0
∇tf(x1)d = 0
∂f(x2 + λd)
∂λ
∣∣∣∣
λ=0
= 0
∇tf(x2 + λd)d|λ=0 = 0
∇tf(x2)d = 0
59
Daí vem que
(x2 − x1)tAd =< x2 − x1, Ad >
=< A(x2 − x1), d > (pois A é simétrica)
=< Ax2 − Ax1, d >
=< Ax2 + b− Ax1 − b, d >
=< ∇f(x2)−∇f(x1), d >
=< ∇f(x2), d > − < ∇f(x1), d >
= ∇tf(x2)d−∇tf(x1)d
= 0− 0
= 0
6.3 Seja f : Rn → R, f ∈ C1. Para k = 0, 1, 2, . . ., definimos xk+1 =
xk − λk∇f(xk) onde λk ≥ λ¯ > 0 para todo k ≥ 0. Suponha que
{xk}∞k=0 converge para x¯. Prove que ∇f(x¯) = 0.
O enunciado do exercício não menciona isso, mas suponhamos que λk
seja escolhido de forma a minimizar f(xk−λk∇f(xk)) , restrito a λk ≥ 0
(ou seja, o algoritmo em questão é o método do gradiente descrito no
algoritmo 6.1 da p.33 do livro da Ana). Em outras palavras, o tamanho
do passo é escolhido pela �regra de minimização� (eq 1.10 do Bertsekas,
p. 29).
Portanto, este é um caso particular da proposição 1.2.1 do Bertse-
kas (estacionariedade de pontos limite para métodos do gradiente).
Logo, todo ponto limite de {xk} é um ponto estacionário (e, portanto
∇f(x¯) = 0).
Alternativamente, suponhamos que ∇tf(xk)∇f(xk+1) = 0 (resultado
do exercício 6.4, que será provado logo em seguida). Como f ∈ C1 e
{xk} converge a x¯, temos que {f(xk)} converge a f(x¯). Logo,
‖∇f(x¯)‖22 = lim
k→∞
< ∇f(xk),∇f(xk+1) >
= lim
k→∞
∇tf(xk)∇f(xk+1)
= lim
k→∞
0 (pelo exercício 6.4)
= 0
60
Portanto, ‖∇f(x¯)‖22 = 0⇒ ∇f(x¯) = 0.
6.4 Prove que no método do gradiente com busca linear exata temos que
∇tf(xk)∇f(xk+1) = 0.
Definamos φk(λ) := f(x
k − λ∇f(xk)). Como λk minimiza φk(λ), pela
regra da cadeia temos:
φ′k(λk) = 0
∇tf(xk − λk∇f(xk))[−∇f(xk)] = 0
∇tf(xk+1)[−∇f(xk)] = 0
∇tf(xk+1)∇f(xk) = 0
6.5 Seja f : Rn → R, f ∈ C1. Seja y o resultado de aplicarmos uma
iteração do método do gradiente com busca linear exata a partir de x.
Seja z o resultado de aplicarmos uma iteração do método do gradiente
a partir de y. Prove que z − x é uma direção de descida a partir de x.
Das definições de z e y, temos:
y = x− λx∇f(x) (λx ≥ 0 que minimiza φx(λ) = f(x− λ∇f(x)))
z = y − λy∇f(y) (λy ≥ 0 que minimiza φy(λ) = f(y − λ∇f(y)))
Do exercício 6.4, como (x, y) e (y, z) são pares de pontos consecutivos
do método do gradiente com busca linear exata, sabemos que:
∇tf(x)∇f(y) = 0
∇tf(y)∇f(z) = 0
Temos que:
61
∇tf(x)(z − x) = ∇tf(x)z −∇tf(x)x
= ∇tf(x)[y − λy∇f(y)]−∇tf(x)[y + λx∇f(x)]
=���
��∇tf(x)y − λy∇tf(x)∇f(y)−�����∇tf(x)y − λx∇tf(x)∇f(x)
= −λy�����
���:0∇tf(x)∇f(y)− λx∇tf(x)∇f(x)
= −λx ‖∇f(x)‖22
(supondo x não estacionario, temos λx > 0 e ‖∇f(x)‖22 > 0)
< 0 (para x não estacionario)
Logo, como ∇tf(x)(z − x) < 0, z − x é uma direção de descida para f
a partir de x.
6.6 Desenhe as curvas de nível da função f(x) = x21 + 4x
2
2 − 4x1 − 8x2.
Encontre o ponto x¯ que minimiza f . Prove que o método do gradiente,
aplicado a partir de x0 = (0, 0)t não pode convergir para x¯ em um
número finito de passos, se usarmos busca linear exata. Há algum ponto
x0 para o qual o método converge em um número finito de passos?
parcialmente resolvido
Figura 6: Curvas de nível geradas com o WolframAlpha . Regiões mais claras
indicam valores maiores da função.
Temos que f(x) = 1
2
xtAx + btx, onde A =
[
2 0
0 8
]
e b =
[ −4
−8
]
.
Como A é simétrica definida positiva, pelo exercício 1.16)b) temos
∇f(x) = Ax + b. Ainda, pelo exercício 4.1, todo minimizador local
62
de f é um minimizador global. Portanto, é suficiente a condição de
primeira ordem:
∇f(x¯) = 0
Ax¯+ b = 0[
2x1 − 4
8x2 − 8
]
=
[
0
0
]
x¯ =
[
2
1
]
Definamos φ(λ) = f(x + λd), sendo d = −∇f(x) = −Ax − b =[ −2x1 + 4
−8x2 + 8
]
. Pelo exercício 4.6 sabemos que:
φ(λ) = f(x+ λd)
= λ2[
1
2
< d,Ad >] + λ[< d,Ax > + < b, d >] +
1
2
< x,Ax > + < b, x >
= λ2[(4− 2x1)2 + 4(8− 8x2)2]
+ λ[2x1(4− 2x1)− 4(4− 2x1)− 8(8− 8x2) + 8(8− 8x2)x2]
+ (x1 − 4)x1 + x2(4x2 − 8)
Logo, pelo método do gradiente, cada novo ponto é da forma x + λd,
onde λ é o minimizador de φ(λ) (restrito a λ ≥ 0) .
Para x0 = (0, 0)t, φ(λ) é dada por φ(λ) = 272λ2−80λ, cujo minimizador
é λ0 =
−(−80)
2×272 =
5
34
. Logo, x1 = x0 + λ0d0 = (
10
20
, 20
17
)t.
Para x1 = (10
20
, 20
17
)t, φ(λ) é dada por φ(λ) = 4905
289
λ2 − 3177
289
λ− 6503
1156
, cujo
minimizador é λ1 =
353
1090
. Logo, x2 = x1 + λ1d1 = (
802
545
, 392
545
)t.
Para x2 = (802
545
, 392
545
)t, φ(λ) é dada por φ(λ) = 1264896
59405
λ2− 1829952
297025
λ− 4036
545
,
cujo minimizador é λ2 =
353
2440
. Logo, x3 = x2 + λ2d2 = (
270026
166225
, 173569
166225
)t.
.
.
.
6.7 Considere o método do gradiente aplicado à minimização de uma função
quadrática q(x) com hessiana definida positiva G. Seja x¯ a solução e
63
suponha que x0 possa ser escrito como x0 = x¯ + µv, onde v é um
autovetor de G associado ao autovalor λ e µ é um número real. Prove
que ∇q(x0) = µλv e que se for feita uma busca linear exata a partir
de x0 haverá convergência em uma iteração. A partir daí, mostre que
o método do gradiente converge em uma iteração para qualquer x0
sempre que G for da forma αI, com α ∈ R.
Como q(x) é quadrática, q(x) = 1
2
xtGx+btx+c. Pelo exercício 1.16)b),
temos que ∇q(x) = Gx + b e ∇2q(x) = G. Pelo exercício 4.1, todo
minimizador local de f é um minimizador global e, portanto, ∇q(x¯) =
Gx¯ + b = 0 ⇒ Gx¯ = −b. Como v é um autovetor de G associado ao
autovalor λ, então Gv = λv Temos que:
∇q(x0) = Gx0 + b
= G(x¯+ µv) + b
= Gx¯+ µGv + b
= −��b+ µλv + ��b
= µλv
Definamos φ(λ) = q(x0 + λd0), sendo d0 = −∇q(x0) = −Gx0 − b =
−µλv. Pelo exercício 4.6 sabemos que:
φ(λ) = f(x0 + λd0)
= λ2[
1
2
< d0, Gd0 >] + λ[< d0, Gx
0 > + < b, d0 >] +
1
2
< x0, Gx0 > + < b, x0 >
Pelo exercício 4.6, sabemos que o mínimo de φ(λ) é atingido em λ = λ0,
onde
64
λ0 =− d
t
0∇q(x0)
dt0∇2q(x0)d0
= − (−Gx
0 − b)t(Gx0 + b)
(−Gx0 − b)tG(−Gx0 − b)
=
(µλv)t(µλv)
(µλv)tG(µλv)
=
(µλv)t(µλv)
(µλv)tµλ(Gv)
= (
((((
((
(µλv)t(µλv)
λ((((
((((µλv)t(µλv)
=
1
λ
Logo, o próximo ponto x1 é dado por:
x1 = x0 + λ0d0
= x0 +
1
SSλ
(−µSSλv)
= x0 − µv
= x0 − (x0 − x¯)
=��x
0 −��x0 + x¯
= x¯
Portanto, se for feita uma busca linear exata a partir de x0, haverá
convergência em uma iteração.
Consideremos agora o caso G = αI, com α ∈ R, com x0 ∈ Rn .
Definamos φ(λ) = q(x0 + λd0), sendo d0 = −∇q(x0) = −Gx0 − b =
−αx0− b. Pelo exercício 4.6, sabemos que o mínimo de φ(λ) é atingido
em λ = λ0, onde
65
λ0 = − d
t
0∇q(x0)
dt0∇2q(x0)d0
= − (−αx
0 − b)t(αx0 + b)
(−αx0 − b)tαI(−αx0 − b)
= ((
((((
((((((αx0 + b)t(αx0 + b)
α((((
((((
(((
(αx0 + b)t(αx0 + b)
=
1
α
Logo, o próximo ponto x1 é dado por:
x1 = x0 + λ0d0
= x0 +
1
α
(−αx0 − b)
=��x
0 −��x0 − b
α
= − b
α
Como temos que
∇q(x1) = Gx1 + b
=�αI(− b
�α
) + b
= −b+ b
= 0
então x1 é o minimizador de q(x) (a condição necessária de primeira
ordem é também suficiente, pois G = αI é definida positiva) e, portanto
haverá convergência em uma iteração.
6.8 Seja f uma função quadrática com hessiana definida positiva. Prove
que se ao aplicarmos o método do gradiente a partir de um certo x0,
66
∇f(x0) 6= 0, encontramos a solução em uma iteração, então d = x1−x0
é um autovetor da hessiana.
Como f(x) é quadrática, f(x) = 1
2
xtGx+btx+c. Pelo exercício 1.16)b),
temos que ∇f(x) = Gx+ b e ∇2f(x) = G.
Definamos φ(λ) = f(x0 + λd0), sendo d0 = −∇f(x0) = −Gx0 − b 6= 0.
Pelo exercício 4.6, sabemos que o mínimo de φ(λ) é atingido em λ = λ0,
onde
λ0 = − d
t
0∇q(x0)
dt0∇2q(x0)d0
= − (−Gx
0 − b)t(Gx0 + b)
(−Gx0 − b)tG(−Gx0 − b)
=
(Gx0 + b)t(Gx0 + b)
(Gx0 + b)tG(Gx0 + b)
Logo, o próximo ponto x1 é dado por:
x1 = x0 + λ0d0
= x0 +
(Gx0 + b)t(Gx0 + b)
(Gx0 + b)tG(Gx0 + b)
(−Gx0 − b)
= x0 − (Gx
0 + b)t(Gx0 + b)
(Gx0 + b)tG(Gx0 + b)
(Gx0 + b)
Como encontramos a solução em uma iteração, então x1 é a solução e,
portanto, ∇f(x1) = Gx1 + b = 0⇒ Gx1 = −b. Daí segue que:
67
Gd = G(x1 − x0)
= Gx1 −Gx0
= −b−Gx0
= −∇f(x0)
= d0
=
1
λ0
(x1 − x0)
=
1
λ0
d
Logo, d = x1 − x0 é um autovetor de G (que é a hessiana de f) com
autovalor associado
1
λ0
.
6.9 Seja f(x) = 1
2
(x21 − x2)2 + 12(1 − x1)2. Qual é o minimizador de f?
Faça uma iteração do método de Newton para minimizar f a partir de
x0 = (2, 2)t. É um bom passo? Antes de decidir, calcule f(x0) e f(x1).
Como cada parcela de f(x) é sempre não negativa, temos que f(x) ≥
0 para todo x ∈ R2. Como f((1, 1)t) = 0, então x∗ = (1, 1)t é o
minimizador de f .
Calculando as derivadas parciais de f , temos:
∂f
∂x1
= 2x1(x
2
1 − x2) + x1 − 1
∂2f
∂x21
= 2(x21 − x2) + 4x21 + 1
= 6x21 − 2x2 + 1
∂f
∂x2
= −(x21 − x2)
= x2 + x
2
1
∂2f
∂x22
= 1
∂2f
∂x1∂x2
= −2x1
68
Logo,∇f(x) = (2x1(x21−x2)+x1−1, x2+x21)t e∇2f(x) =
[
6x21 − 2x2 + 1 −2x1
−2x1 1
]
.
Para x0 = (2, 2)t, ∇f(x0) = (9, 6)t e ∇2f(x0) =
[
21 −4
−4 1
]
.
Para encontrarmos d0, basta resolver o sistema:
∇2f(x0)d0 = −∇f(x0)[
21 −4
−4 1
]
d0 =
[ −9
−6
]
Logo, d0 = (−335 ,−1625 )t. Seja agora φ(λ) = f(x0 + λd0), e efetuemos a
busca linear com backtracking para a escolha de λ (conforme indicado
no passo 2 do algoritmo 6.2 da p.37 do livro da Ana, e descrito no passo
2 do algoritmo 4.2 da p.27 do livro da Ana).
Como o exercício não indicou qual deve ser o valor de α usado na busca
linear (verificação da condição de Armijo), escolhamos α = 1
2
. Como
f(x0) = 5
2
, as iterações são dadas por:
1.i λ← 1
1.ii f(x0 + λd0) = 1344.9 ≥ −124.4 = f(x0) + αλ∇tf(x0)d0
1.iii λ← λ/2 = 0.5
2.ii f(x0 + λd0) = 128.891 ≥ −60.95 = f(x0) + αλ∇tf(x0)d0
2.iii λ← λ/2 = 0.25
3.ii f(x0 + λd0) = 19.571 ≥ −29.225 = f(x0) + αλ∇tf(x0)d0
3.iii λ← λ/2 = 0.125
4.ii f(x0 + λd0) = 5.89991 ≥ −13.3625 = f(x0) + αλ∇tf(x0)d0
4.iii λ← λ/2 = 0.0625
5.ii f(x0 + λd0) = 3.41149 ≥ −5.43125 = f(x0) + αλ∇tf(x0)d0
5.iii λ← λ/2 = 0.03125
6.ii f(x0 + λd0) = 2.80156 ≥ −1.465625 = f(x0) + αλ∇tf(x0)d0
6.iii λ← λ/2 = 0.015625
69
7.ii f(x0 + λd0) = 2.61641 ≥ 0.5171 = f(x0) + αλ∇tf(x0)d0
7.iii λ← λ/2 = 0.0078125
8.ii f(x0 + λd0) = 2.55 ≥ 1.50 = f(x0) + αλ∇tf(x0)d0
8.iii λ← λ/2 = 0.00390625
9.ii f(x0 + λd0) = 2.52 ≥ 2.00 = f(x0) + αλ∇tf(x0)d0
9.iii λ← λ/2 = 0.001953125
10.ii f(x0 + λd0) = 2.51 ≥ 2.25 = f(x0) + αλ∇tf(x0)d0
10.iii λ← λ/2 = 0.000976563
11.ii f(x0 + λd0) = 2.505 ≥ 2.37 = f(x0) + αλ∇tf(x0)d0
11.iii λ← λ/2 = 0.000488281
12.ii f(x0 + λd0) = 2.502 ≥ 2.43 = f(x0) + αλ∇tf(x0)d0
12.iii λ← λ/2 = 0.000488281
.
.
.
18.ii f(x0 + λd0) = 2.50004 ≥ 2.49903 = f(x0) + αλ∇tf(x0)d0
18.iii λ← λ/2 = 2−18
.
.
.
Numericamente podemos perceber que o algoritmo não converge num
número finito de passos (já que a condição de Armijo simplesmente não
é satisfeita), mas suponhamos que o tamanho do passo escolhido seja
λ0 = 2
−17
(esse é o tamanho do passo usado na iteração 18).
Temos então que x1 = x0 + λ0d0 = (
1310687
655360
, 655279
327680
)t. Daí vem que
f(x1) ≈ 2.50004, sendo que f(x0) = 2.5. Logo, esse não é um bom
tamanho de passo, já que está muito longe do minimizador (além de x1
ter praticamente o mesmo valor da função objetivo em x0).
6.10 Considere o método de Newton aplicado para achar o minimizador de
f(x) = sin(x) a partir de x0 ∈ [−pi, pi]. A resposta desejada é x¯ = −pi2 .
Seja ε > 0 suficientemente pequeno. Prove que se x0 = −ε então
x1 ' −1ε . Analogamente, o que acontece se x0 = ε, mas f ′′(x0) é
substituída por um número positivo pequeno?
70
Pelas expansões em série de Taylor em torno de x = 0, temos que
f ′(x) = cos(x) = 1− x
2
2!
+
x4
4!
− x
6
6!
+ . . .
f ′′(x) = − sin(x) = −x+ x
3
3!
− x
5
5!
+
x7
7!
− . . .
Para x0 = −ε, f ′(x0) ≈ 1 e f ′′(x0) ≈ −x0 = ε.
Para encontrarmos d0, basta resolver o sistema:
f ′′(x0)d0 = −f ′(x0)
εd0 ≈ −1
d0 ≈ −1
ε
Para algum valor de λ0 (obtido via busca linear), temos então que:
x1 = x0 + λ0d0
≈ −ε+ λ0(−1
ε
)
(para ε > 0 suficientemente pequeno)
≈ −1
ε
Se x0 = ε, mas f
′′(x0) é substituída por um número positivo pequeno
(digamos, ε′ > 0), a direção é dada por:
f ′′(x0)d0 = −f ′(x0)
ε′d0 ≈ −1
d0 ≈ − 1
ε′
Para algum valor de λ0 (obtido via busca linear), temos então que:
71
x1 = x0 + λ0d0
≈ ε+ λ0(− 1
ε′
)
(para ε, ε′ > 0 suficientemente pequenos)
≈ − 1
ε′
Portanto, assim como no caso anterior, obtemos x1 ≈ − 1
ε′ .
Isso mostra que o método de Newton teria problemas nesses casos, já
que sairíamos de un número pequeno |x0| = ε ≈ 0 para um número
negativo grande −1
ε
(o que não é desejável, já que o minimizador x¯ =
−pi
2
é o ponto médio do intervalo [−pi, 0] ).
6.11 O método de Newton pode convergir para um maximizador local! Para
verificar esta afirmação, use o método de Newton para minimizar a
função f(x) = −x4
4
+ x
3
3
+ x2 a partir de x0 = 1 e tomando λ0 = 1. O
que acontece com o método de Newton quando aplicado à minimização
de f(x) = x
3
3
+ x (equivalente a calcular os zeros de f ′(x) = x2 + 1) ?
As primeira e segunda derivadas de f são dadas por:
f ′(x) = −x3 + x2 + 2x
f ′′(x) = −3x2 + 2x+ 2
Os pontos estacionários são dados por:
f ′(x) = 0
−x3 + x2 + 2x = 0
x(−x2 + x+ 2) = 0
x ∈ {−1, 0, 2}
Cada um dos pontos estacionários é tal que:
72
f ′′(−1) = −3 < 0⇒ x = −1 é máximo local
f ′′(0) = 2 > 0⇒ x = 0 é mínimo local
f ′′(2) = −6 < 0⇒ x = 2 é máximo local
Para encontrarmos d0 (do método de Newton), basta resolver o sistema:
f ′′(x0)d0 = −f ′(x0)
f ′′(1)d0 = −f ′(1)
d0 = −2
Para λ0 = 1, temos então que:
x1 = x0 +