Minimização com Igualdades
Eduardo Camponogara
Universidade Federal de Santa Catarina
Departamento de Automação e Sistemas
1 / 64
Sumário
Sumário
1
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
2
Eliminando as Restrições de Igualdade
3
Usando o Dual
Método de Newton com Restrições de Igualdade
4
Método de Newton com Partida Infactı́vel
2 / 64
Minimização Com Restrições de Igualdade
Sumário
1
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
2
Eliminando as Restrições de Igualdade
3
Usando o Dual
Método de Newton com Restrições de Igualdade
4
Método de Newton com Partida Infactı́vel
3 / 64
Minimização Com Restrições de Igualdade
Problemas de Minimização com Igualdades
Aqui estamos preocupados com problemas da forma:
Minimize f (x)
(1a)
Sujeito a : Ax = b
(1b)
onde f : Rn → R é convexa e duas vezes diferenciável e rank(A) = p < n,
com A ∈ Rp×n .
I
Assumiremos que uma solução ótima x ? existe e p ? denotará o valor
ótimo, p ? = inf{f (x) : Ax = b} = f (x ? ).
I
Das condições de otimalidade, x ? ∈ dom f é ótimo se existe v ? ∈ Rp
tal que
Ax ? = b, ∇f (x ? ) + AT v ? = 0
(2)
4 / 64
Minimização Com Restrições de Igualdade
I
Resolver as equações (2) é equivalente a resolver o problema (1). As
equações (2) são equações KKT:
n + p equações
n + p variáveis
5 / 64
Minimização Com Restrições de Igualdade
I
Resolver as equações (2) é equivalente a resolver o problema (1). As
equações (2) são equações KKT:
n + p equações
n + p variáveis
I
A primeira equação, Ax ? = b, é chamada de
equação de factibilidade primal. Tais equações são lineares.
I
A segunda equação, ∇f (x ? ) + AT v ? = 0, é chamada de
equação de factibilidade dual. Tais equações são tipicamente não
lineares.
6 / 64
Minimização Com Restrições de Igualdade
I
Em alguns casos, podemos resolver as equações analiticamente, como
na situação onde f é uma função quadrática.
7 / 64
Minimização Com Restrições de Igualdade
I
Em alguns casos, podemos resolver as equações analiticamente, como
na situação onde f é uma função quadrática.
I
Qualquer problema com restrições de igualdade pode ser reduzido a
um problema irrestrito visto no capı́tulo 9.
8 / 64
Minimização Com Restrições de Igualdade
I
Em alguns casos, podemos resolver as equações analiticamente, como
na situação onde f é uma função quadrática.
I
Qualquer problema com restrições de igualdade pode ser reduzido a
um problema irrestrito visto no capı́tulo 9.
I
Uma outra estratégia é resolver o problema dual assumindo que a
função dual é duas vezes diferenciável, e depois recuperando a
solução primal de (1) a partir da solução dual.
9 / 64
Minimização Com Restrições de Igualdade
I
Aqui nos concentramos no método de Newton que trata diretamente
das restrições de igualdade. Isto pode ser desejável, pois a eliminação
das igualdades destrói a esparsidade.
I
Métodos que tratam as restrições diretamente podem ser vistos como
métodos que resolvem as condições de otimalidade (razão conceitual
para tais métodos).
10 / 64
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
Minimização Convexa Quadrática com Restrições de
Igualdade
Considere o problema
1 T
x Px + q T x + r
2
s.a : Ax = b
min
n e A ∈ Rp×n . Aqui, as condições de otimalidade são:
onde P ∈ S+
?
Ax = b, Px ? + q + AT v ? = 0, que podem ser escritas como
−q
P AT x ?
=
v?
b
A 0
(3)
(4)
(5)
11 / 64
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
I
Este sistema de n + p equações lineares e n + p variáveis (x ? , v ? ) é
chamado sistema KKT para o problema quadrático com restrição de
igualdade.
I
Quando o sistema KKT (5) é não singular, então existe um par
(x ? , v ? ) primal-dual ótimo e único.
12 / 64
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
I
Se a matriz KKT é singular, mas o sistema é resolvı́vel, então
qualquer solução produz um par (x ? , v ? ) ótimo.
I
Se o sistema KKT não tem solução, então o problema de otimização
quadrática é ilimitado por baixo ou infactı́vel. Neste caso, existe
v ∈ Rn e w ∈ RP tal que
Pv + AT w = 0
Av = 0
−q T v + b T w > 0
13 / 64
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
Seja x̂ qualquer ponto factı́vel. O ponto x = x̂ + tv é factı́vel para todo t e
f (x̂ + tv ) = f (x̂) + t(v T P x̂ + q T v ) + (1/2)t 2 v T Pv
= f (x̂) + t(−x̂ T AT w + q T v ) − (1/2)t 2 w T Av
= f (x̂) + t(−b T w + q T v )
que decresce sem limites com t → ∞
14 / 64
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
Não Singularidade da Matriz KKT
n e rank(A) = p < n. Há varias condições
Temos a hipótese que P ∈ S+
equivalentes para a não singularidade da matriz KKT:
1
Null(P) ∩ Null(A) = {0}, i.e., P e A não tem um ponto não trivial no
espaço nulo.
2
Ax = 0, x 6= 0 =⇒ x T Px > 0, i.e., P é positiva definida no espaço
nulo de A.
3
F T PF 0, onde F ∈ Rn×(n−p) é uma matriz tal que
range(F ) = Null(A).
15 / 64
Eliminando as Restrições de Igualdade
Sumário
1
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
2
Eliminando as Restrições de Igualdade
3
Usando o Dual
Método de Newton com Restrições de Igualdade
4
Método de Newton com Partida Infactı́vel
16 / 64
Eliminando as Restrições de Igualdade
Eliminando as Restrições de Igualdade
I
Um método geral para resolver o problema (1) é a eliminação das
igualdades e redução a um problema irrestrito.
I
Primeiro, encontramos uma matriz F ∈ Rn×(n−p) e um vetor x̂ ∈ Rn
que parametrize o espaço factı́vel (afim)
{x|Ax = b} = {Fz + x̂|z ∈ Rn−p }
Aqui x̂ pode ser escolhido como uma solução qualquer de Ax = b, e
F ∈ Rn×(n−p) é uma matriz que gera o espaço nulo de A.
17 / 64
Eliminando as Restrições de Igualdade
Eliminando as Restrições de Igualdade
I
Então, formamos o problema reduzido
min f˜(z) = f (Fz + x̂)
(6)
que é um problema irrestrito na variável z ∈ R(n−p) .
I
A partir da solução z ? para (6), obtemos a solução x ? = Fz ? + x̂.
I
Podemos ainda encontrar uma solução ótima dual v ? para o problema
com restrições de igualdade
v ? = −(AAT )−1 A∇f (x ? )
18 / 64
Eliminando as Restrições de Igualdade
I
Para mostrar que esta expressão é correta, temos que verificar a
condição de factibilidade dual
∇f (x ? ) + AT v ? = ∇f (x ? ) + AT [−(AAT )−1 A∇f (x ? )] = 0
I
Note que
FT ∇f (x ? ) + AT [−(AAT )−1 A∇f (x ? )] = 0
A
(7)
onde usa-se o fato que:
F T ∇f (x ? ) = ∇f˜(z ? ) = 0
AF = 0
uma vez que a matriz à esquerda é não-singular, verificamos (7).
19 / 64
Eliminando as Restrições de Igualdade
Escolha da Matriz de Eliminação
I
Há diferentes escolhas para a matriz de eliminação F , que pode ser
qualquer matriz em Rn×(n−p) com range(F ) = Null(A).
I
Se F é uma matriz com estas propriedades e T ∈ R(n−p)×(n−p) é não
singular, então F̃ = FT é também uma matriz de eliminação, já que
range(F̃ ) = range(F ) = Null(A)
20 / 64
Eliminando as Restrições de Igualdade
I
Por outro lado, se F e F̃ são duas matrizes de eliminação, então
existe uma matriz não singular T tal que F̃ = FT . Se eliminarmos as
igualdades, então resolvemos o problema
min f (Fz + x̂)
I
Se usarmos F̃ , então resolvemos o problema
min f (F̃ z̃ + x̂) = f (F (T z̃) + x̂)
I
Este problema é equivalente ao anterior, obtido através de uma
mudança de coordenadas z = T z̃
21 / 64
Usando o Dual
Sumário
1
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
2
Eliminando as Restrições de Igualdade
3
Usando o Dual
Método de Newton com Restrições de Igualdade
4
Método de Newton com Partida Infactı́vel
22 / 64
Usando o Dual
Usando o Dual
I
I
Outra estratégia é resolver o problema dual e recuperar a solução
primal x ? .
A função dual de (1) é
g (v ) = inf(f (x) + v T Ax − v T b)
x
= −b T v + inf(f (x) + v T Ax)
x
T
= −b v − sup (−AT v )T x − f (x)
x
?
T
= −b v − f (−AT v )
I
onde f ? é a função conjugada de f .
Logo, o problema dual fica
max g (v ) = max − b T v − f ? (−AT v )
v
v
23 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
Método de Newton com Restrições de Igualdade
I
Assumimos que o ponto inicial é factı́vel: x ∈ dom f e Ax = b.
I
O método de Newton é semelhante ao caso irrestrito, tomando
cuidado no passo para garantir factibilidade.
I
Ou seja, fazemos com que A∆xnt = 0.
24 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
O Passo de Newton
I
Para derivar o passo de Newton de
min f (x)
s.a : Ax = b
I
Considera-se o problema no ponto x. Assim substitui-se a função
objetivo pela aproximação de Taylor de 2a ordem, formando o
problema
1
Minimize fˆ(x + v ) = f (x) + ∇f (x)T v + v T ∇2 f (x)v
2
Sujeito a : A(x + v ) = b
(8a)
(8b)
com variável v .
25 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
I
Este é um problema quadrático convexo com igualdade que pode ser
resolvido analiticamente.
I
Definimos ∆xnt , o passo de Newton no ponto x, como a solução do
problema convexo (8), assumindo que a matriz KKT associada é não
singular.
I
Em outras palavras, o passo de Newton é o que deve ser adicionado a
x para resolver o problema quando a aproximação quadrática de f é
usada.
26 / 64
Usando o Dual
I
Método de Newton com Restrições de Igualdade
Da análise de QP convexo, o passo de Newton deve satisfazer
2
−∇f (x)
∇ f (x) AT ∆xnt
=
w
0
A
0
(9)
onde w é a variável dual ótima associada ao QP (8).
27 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
I
O passo de Newton é definido apenas em pontos onde a matriz KKT
é não singular.
I
Quando f é aproximadamente quadrática, x + ∆xnt deve ser uma boa
aproximação de x ? , e w deve ser uma boa estimativa de v ? .
28 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
Solução das Equações Linearizadas
I
Pode-se interpretar o passo de Newton ∆xnt e o vetor w , como a
solução da aproximação linear das condições de otimalidade,
Ax ? = b
∇f (x ? ) + AT v ? = 0
I
Substituı́mos x + ∆xnt por x ? e w por v ? , e trocamos o gradiente
pela aproximação linear em torno de x, obtendo as equações
A(x + ∆xnt ) = b
∇f (x + ∆xnt ) + AT w ≈ ∇f (x) + ∇2 f (x)∆xnt + AT w = 0
29 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
Usando Ax = b, elas se tornam
A∆xnt = 0
2
∇ f (x)∆xnt + AT w = −∇f (x)
que são precisamente as equações (9) que definem o passo de Newton.
30 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
O Decremento de Newton
I
Define-se o decremento de Newton do problema restrito como
q
T ∇2 f (x)∆x
λ(x) = ∆xnt
nt
(10)
que é exatamente o mesmo do caso irrestrito, com as mesmas
interpretações.
I
Por exemplo, λ(x) é a norma do passo de Newton com a norma
definida pela Hessiana.
I
Seja
1
fˆ(x + v ) = f (x) + ∇f (x)T v + v T ∇2 f (x)v
2
a aproximação de Taylor de 2a ordem de f em torno de x.
31 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
I
A diferença entre f (x) e o mı́nimo da aproximação de 2a ordem
satisfaz
λ(x)2
f (x) − inf{fˆ(x + v )|A(x + v ) = b} =
(11)
2
exatamente como no caso irrestrito.
I
Então, como no caso irrestrito, λ(x)2 /2 nos dá uma estimativa de
f (x) − p ? baseada na aproximação quadrática em torno de x.
I
Logo, λ(x)2 serve de base para uma condição de parada.
32 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
Direção de Descenso Factı́vel
I
Suponha que Ax = b. Dizemos que v ∈ Rn é uma direção factı́vel se
Av = 0. Neste caso, qualquer ponto da forma x + tv é também
factı́vel, i.e., A(x + tv ) = b.
I
Dizemos que v é uma direção de descenso de f em x, se para t > 0
pequeno, f (x + tv ) < f (x).
I
O passo de Newton ∆xnt é sempre uma direção factı́vel.
I
O fato de ∆xnt ser uma direção de descenso segue do seguinte: a
derivada direcional de f na direção ∆xnt é
d
f (x + t∆xnt )|t=0 = ∇f (x)T ∆xnt = −λ(x)2 < 0
dt
33 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
Invariante Afim
I
Seja T ∈ Rn×n uma matriz não singular defina f¯(y ) = f (Ty ). Então,
temos que
∇f¯(y ) = T T ∇f (Ty )
∇2 f¯(y ) = T T ∇2 f (Ty )T
e a igualdade Ax = b se torna ATy = b, pois x = Ty .
I
Agora considere o problema:
min f˜(y )
s.a : ATy = b
34 / 64
Usando o Dual
I
Método de Newton com Restrições de Igualdade
O passo de Newton ∆ynt em y é definido como a solução de
T 2
T ∇ f (Ty )T T T AT ∆ynt
−T T ∇f (Ty )
=
w̄
AT
0
0
35 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
I
O passo de Newton ∆ynt em y é definido como a solução de
T 2
T ∇ f (Ty )T T T AT ∆ynt
−T T ∇f (Ty )
=
w̄
AT
0
0
I
Comparando com o passo de Newton ∆xnt para f em x = Ty , dado
em (9), vemos que:
∆xnt = T ∆ynt
w = w̄
36 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
I
O passo de Newton ∆ynt em y é definido como a solução de
T 2
T ∇ f (Ty )T T T AT ∆ynt
−T T ∇f (Ty )
=
w̄
AT
0
0
I
Comparando com o passo de Newton ∆xnt para f em x = Ty , dado
em (9), vemos que:
∆xnt = T ∆ynt
w = w̄
I
Os passos de Newton em y e x são relacionados pela mesma
mudança de coordenada y = Tx.
37 / 64
Usando o Dual
Método de Newton com Restrições de Igualdade
Algoritmo 1 - Método de Newton
para Minimização com Restrições de Igualdade
Dado um p o n t o i n i c i a l x ∈ dom f com Ax = b ,
t o l e r â n c i a ε > 0
Repita
1 . C a l c u l e o p a s s o de Newton ∆xnt e d e c r e m e n t o
λ(x)
2 . C r i t é r i o de Parada : Pare s e λ2 /2 ≤ ε .
3 . Busca L i n e a r : E s c o l h a um comprimento de
p a s s o t p o r b u s c a l i n e a r com r e t r o c e s s o
4 . A t u a l i z e : x := x + t∆xnt
38 / 64
Método de Newton com Partida Infactı́vel
Sumário
1
Minimização Com Restrições de Igualdade
Minimização Convexa Quadrática
2
Eliminando as Restrições de Igualdade
3
Usando o Dual
Método de Newton com Restrições de Igualdade
4
Método de Newton com Partida Infactı́vel
39 / 64
Método de Newton com Partida Infactı́vel
Método de Newton com Partida Infactı́vel
I
O método de Newton descrito acima é um método de descenso
factı́vel.
I
Aqui desenvolvemos uma generalização do método de Newton que
opera com um ponto inicial infactı́vel, gerando iterandos que não são
necessariamente factı́veis com respeito ao sistema Ax = b.
40 / 64
Método de Newton com Partida Infactı́vel
Passo de Newton em Pontos Infactı́veis
I
As condições de otimalidade KKT aplicadas ao problema de
minimização sujeito a equações lineares são:
Ax ? = b,
∇f (x ? ) + AT ν ? = 0
41 / 64
Método de Newton com Partida Infactı́vel
Passo de Newton em Pontos Infactı́veis
I
As condições de otimalidade KKT aplicadas ao problema de
minimização sujeito a equações lineares são:
Ax ? = b,
I
∇f (x ? ) + AT ν ? = 0
Seja x o ponto corrente, não necessariamente factı́vel porém
assume-se que x ∈ dom f . Desejamos encontrar o passo ∆x de forma
que x + ∆x satisfaça, pelo menos de forma aproximada, as condições
de otimalidade, ou seja, x + ∆x ≈ x ? .
42 / 64
Método de Newton com Partida Infactı́vel
Substituindo x + ∆x para x ? e w para ν ? nas condições de otimilidade,
obtemos a aproximação de primeira ordem para o gradiente de f :
∇f (x + ∆x) ≈ ∇f (x) + ∇2 f (x)∆x
que nos leva a seguinte aproximação das condições de primeira ordem:
A(x + ∆x) = b,
∇f (x) + ∇2 f (x)∆x + AT w = 0
que é um conjunto de equações lineares:
2
∆x
∇f (x)
∇ f (x) AT
=−
w
Ax − b
A
0
(12)
43 / 64
Método de Newton com Partida Infactı́vel
As equações (12) são iguais as equações (9) que definem o passo de
Newton em um ponto factı́vel x, mas com uma diferença:
I
O segundo componente no lado direito contém o termo Ax − b, que é
o vetor de resı́duos para o sistema de equações lineares.
I
Quando x é factı́vel, o vetor de resı́duos desaparece, e as equações
(12) se tornam as equações (9).
I
Logo, se x é factı́vel, o passo ∆x definido por (12) coincide com o
passo ∆x definido por (9).
44 / 64
Método de Newton com Partida Infactı́vel
Interpretação Primal-Dual
I
Uma interpretação das equações (12) surge do método primal-dual
para problemas de minimização sujeitos a restrições de igualdade.
I
Um método primal-dual atualiza a variável primal x e a variável dual
ν, buscando satisfazer de forma aproximada as condições de
otimalidade.
45 / 64
Método de Newton com Partida Infactı́vel
As condições de otimalidade podem ser expressas como r (x ? , ν ? ) = 0,
onde r : R n × R p → R × R p é definida como:
r (x, ν) = (rdual (x, ν), rpri (x, ν)).
onde:
rdual (x, ν) = ∇f (x) + AT ν
rpri (x, ν) = Ax − b
são os resı́duos duais e primais respectivamente.
46 / 64
Método de Newton com Partida Infactı́vel
I
A expansão de Taylor de primeira ordem de r , em torno de uma
estimativa y , é
r (y + z) ≈ r (y ) + ∇r (y )z,
onde ∇r (y ) ∈ R (n+p)×(n+p) é a derivada de r , avaliada no ponto y .
47 / 64
Método de Newton com Partida Infactı́vel
I
A expansão de Taylor de primeira ordem de r , em torno de uma
estimativa y , é
r (y + z) ≈ r (y ) + ∇r (y )z,
onde ∇r (y ) ∈ R (n+p)×(n+p) é a derivada de r , avaliada no ponto y .
I
Define-se o passo de Newton primal-dual ∆ypd como o passo z para o
qual a aproximação de Taylor de r (y + z) é nulificada, ou seja,
∇r (y )∆ypd = −r (y )
(13)
48 / 64
Método de Newton com Partida Infactı́vel
I
A expansão de Taylor de primeira ordem de r , em torno de uma
estimativa y , é
r (y + z) ≈ r (y ) + ∇r (y )z,
onde ∇r (y ) ∈ R (n+p)×(n+p) é a derivada de r , avaliada no ponto y .
I
Define-se o passo de Newton primal-dual ∆ypd como o passo z para o
qual a aproximação de Taylor de r (y + z) é nulificada, ou seja,
∇r (y )∆ypd = −r (y )
I
(13)
Note que consideramos x e ν como variáveis, assim
∆ypd = (∆xpd , ∆νpd ) nos dá o passo primal-dual.
49 / 64
Método de Newton com Partida Infactı́vel
Avaliando a derivada de r , podemos expressar (13) como:
2
rdual
∆xpd
∇ f (x) AT
=−
rpri
∆νpd
A
0
∇f (x) + AT ν
=−
Ax − b
(14)
50 / 64
Método de Newton com Partida Infactı́vel
I
+
Reescrevendo νpd + ∆νpd como νpd
, podemos reescrever (14) como:
∇2 f (x) AT
A
0
∆xpd
+
νpd
=−
∇f (x)
Ax − b
(15)
que tem exatamente as mesmas soluções de (12).
51 / 64
Método de Newton com Partida Infactı́vel
I
+
Reescrevendo νpd + ∆νpd como νpd
, podemos reescrever (14) como:
∇2 f (x) AT
A
0
∆xpd
+
νpd
=−
∇f (x)
Ax − b
(15)
que tem exatamente as mesmas soluções de (12).
I
As soluções de (12) e (15) são portanto relacionadas por:
∆xnt = ∆xpd
+
w = νpd
= νpd + ∆νpd
Isto mostra que o passo de Newton (infactı́vel) coincide com o passo
primal do método primal-dual, e o vetor dual w associado
+
corresponde à variável primal-dual atualizada νpd
= νpd + ∆νpd
52 / 64
Método de Newton com Partida Infactı́vel
As expressões (14) e (15) são equivalentes, mas revelam caracterı́sticas
diferentes do método de Newton:
I
De acordo com (14), o passo de Newton primal e dual são obtidos
resolvendo as equações, com resı́duos primais e duais no lado direito.
I
De acordo com (15), o passo de Newton primal e a variável dual
atualizada são obtidos, mas não necessita da variável dual corrente.
53 / 64
Método de Newton com Partida Infactı́vel
Propriedade de Redução da Norma Residual
A direção de Newton, em um ponto infactı́vel, não é necessariamente uma
direção de descenso para f . A partir de (15), note que:
d
= ∇f (x)T ∆x
f (x + t∆x)
dt
t=0
= −∆x T (∇2 f (x)∆x + AT w )
= −∆x T ∇2 f (x)∆x + (Ax − b)T w
que não é necessariamente negativo, a menos que x seja factı́vel com
Ax = b.
54 / 64
Método de Newton com Partida Infactı́vel
A interpretação primal-dual mostra que a norma dos resı́duos decresce na
direção de Newton, ou seja,
d
2
= 2r (y )T ∇r (y )∆ypd
kr (y + t∆ypd )k2 dt
t=0
= −2r (y )T r (y )
55 / 64
Método de Newton com Partida Infactı́vel
A interpretação primal-dual mostra que a norma dos resı́duos decresce na
direção de Newton, ou seja,
d
2
= 2r (y )T ∇r (y )∆ypd
kr (y + t∆ypd )k2 dt
t=0
= −2r (y )T r (y )
Tomando a derivada da raiz quadrada, obtém-se
d
kr (y + t∆ypd )k2 = −kr (y )k2
dt
t=0
(16)
Isto permite empregar kr k2 como uma medida de progresso do método de
Newton com partida infactı́vel, em particular na busca linear.
56 / 64
Método de Newton com Partida Infactı́vel
Factibilidade do Passo Completo
I
O passo de Newton ∆xnt definido em (12) tem a propriedade (por
construção) que
A(x + ∆xnt ) = b
(17)
Portanto, se um passo de comprimento 1 é utilizado usando o passo
de Newton ∆xnt , então o iterando seguinte será factı́vel.
57 / 64
Método de Newton com Partida Infactı́vel
Factibilidade do Passo Completo
I
O passo de Newton ∆xnt definido em (12) tem a propriedade (por
construção) que
A(x + ∆xnt ) = b
(17)
Portanto, se um passo de comprimento 1 é utilizado usando o passo
de Newton ∆xnt , então o iterando seguinte será factı́vel.
I
Uma vez que x seja factı́vel, o método de Newton se torna um
método de direção factı́vel. Todos os iterandos futuros serão factı́veis,
qualquer que seja o comprimento de passo realizado.
58 / 64
Método de Newton com Partida Infactı́vel
Podemos analisar o efeito do passo amortizado no resı́duo primal. Com um
passo de comprimento t ∈ [0, 1], o próximo iterando será x + = x + t∆xnt ,
logo o resı́duo da restrição dado pelo próximo iterando será:
+
rpri
= A(x + ∆xnt t) − b
= A(x + ∆xnt )t + Ax(1 − t) − b
= bt + Ax(1 − t) − b
= (1 − t)(Ax − b)
= (1 − t)rpri
59 / 64
Método de Newton com Partida Infactı́vel
I
Portanto o passo amortecido, com comprimento t, reduz o resı́duo de
um fator 1 − t.
60 / 64
Método de Newton com Partida Infactı́vel
I
Portanto o passo amortecido, com comprimento t, reduz o resı́duo de
um fator 1 − t.
I
Seja x (i+1) = x (i) + t (i) ∆xnt , para i = 0, . . . , k − 1, onde ∆xnt é o
passo de Newton no ponto x (i) ∈ dom f , e t (i) ∈ [0, 1]. Então,
(i)
r (k) =
k−1
Y
(1 − t (i) )r (0)
i=0
onde r (i) = Ax (i) − b.
61 / 64
Método de Newton com Partida Infactı́vel
I
Portanto o passo amortecido, com comprimento t, reduz o resı́duo de
um fator 1 − t.
I
Seja x (i+1) = x (i) + t (i) ∆xnt , para i = 0, . . . , k − 1, onde ∆xnt é o
passo de Newton no ponto x (i) ∈ dom f , e t (i) ∈ [0, 1]. Então,
(i)
r (k) =
k−1
Y
(1 − t (i) )r (0)
i=0
onde r (i) = Ax (i) − b.
I
Logo, o resı́duo primal é reduzido a cada passo. Isto mostra que uma
vez que o passo de Newton seja completo, todos os iterandos futuros
são factı́veis.
62 / 64
Método de Newton com Partida Infactı́vel
Algoritmo de Newton com Partida Infactı́vel
I
O método de Newton com iterando inicial factı́vel pode ser estendido,
usando o passo de Newton ∆xnt definido por (12), com x (0) ∈ dom f ,
mas não necessariamente satisfazendo Ax (0) = b.
2
∆xnt
−∇f (x)
∇ f (x) AT
=
w
Ax − b
A
0
I
Também usamos a parte dual do passo de Newton: ∆νnt = w − ν da
notação (12).
63 / 64
Método de Newton com Partida Infactı́vel
Método de Newton com Partida Infactı́vel
g i v e n s t a r t i n g p o i n t x ∈ dom f , ν ,
t o l e r a n c e > 0 , α ∈ (0, 1/2) , β ∈ (0, 1) .
repeat
1 . Compute p r i m a l −d u a l Newton s t e p : ∆xnt , ∆νnt .
2 . B a c k t r a c k i n g l i n e s e a r c h on kr k2 .
t := 1.
w h i l e kr (x + t∆xnt , ν + t∆νnt )k2 > (1 − αt)kr (x, ν)k2
t := βt .
3 . Update . x := x + t∆xnt , ν := ν + t∆νnt .
u n t i l Ax = b and kr (x, ν)k2 ≤ .
64 / 64
Método de Newton com Partida Infactı́vel
Encerramento
I
Agradeço Thiago Silva pelo apoio na preparação em LATEX.
I
Obrigado pela presença.
65 / 64