Otimização/Método da lagrangiana aumentada: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Introdução ao método da lagrangiana aumentada [ aula de 11/11 ] |
incluindo demonstração do Lema de Debreu [finalizando aula de 11/11] |
||
Linha 19:
{{Teorema
|;Lema (de
Seja <math>A_{n\times n}</math> uma matriz simétrica e <math>B_{p\times n}</math>. As seguintes afirmações são equivalentes:
# Se <math>Bx = 0</math>, com <math>x \not = 0</math>, então <math>\langle Ax, x \rangle > 0</math>;
Linha 25:
# Existe <math>s>0</math> tal que a matriz <math>A + rB^\top B</math> é definida positiva para todo <math>r>s</math>.
}}
{{Demonstração
|Primeiramente, será mostrado que a afirmação (2) é equivalente à afirmação (3).
Obviamente, (3) implica em (2).
Por outro lado, supondo que se tem (2), existe algum <math>s > 0</math>, tal que a matriz <math>A + sB^\top B</math> é definida positiva. Logo, para concluir a outra implicação, basta notar que para qualquer <math>x \not = 0</math> vale:
:<math>\begin{align} \langle (A + rB^\top B)x, x \rangle
& = \langle A x, x \rangle + r\langle B^\top B x, x \rangle\\
& = \langle A x, x \rangle + r\langle B x, Bx \rangle\\
& = \langle A x, x \rangle + r\|Bx\|^2\\
& > \langle A x, x \rangle + s\|Bx\|^2,\, \forall r > s\\
& = \langle (A + sB^\top B)x, x \rangle\\
& > 0
\end{align}</math>
Assim, (2) também implica (3).
Agora, será mostrado que de (2) se conclui (1). De fato, se <math>Bx = 0</math>, para algum <math>x \not = 0</math>, então:
:<math>\langle A x, x \rangle = \langle A x, x \rangle + r\|Bx\|^2 = \langle (A + rB^\top B)x, x \rangle > 0</math>
Finalmente, será garantido que se vale (1) então vale (3) (ver também página 25, de [[Otimização/Bibliografia#Izmailov & Solodov (2007)|Izmailov & Solodov (2007)]]). Isso será mostrado por contradição, ou seja, supondo que vale (1) e que mesmo assim, não seja válido (3). Se disso seguir uma contradição, a implicação desejada é verdadeira.
Supondo que para todo <math>x \not = 0</math> tal que <math>Bx = 0</math>, tem-se <math>\langle Ax, x \rangle > 0</math>, e que fosse falsa a afirmação (3), existiria para cada <math>s>0</math> algum <math>r>s</math> e algum <math>x \not =0</math> de modo que
:<math>\langle A x, x \rangle + r\|Bx\|^2 \le 0</math>
Neste caso, dividindo por <math>\|x\|^2</math>, e denotando <math>u = \frac{x}{\|x\|}</math>, segue que para cada <math>k \in \mathbb{N}</math>, existe algum <math>r_k > k</math> e algum <math>u_k \in \mathbb{R}^n</math>, com <math>\|u_k\| = 1</math>, tais que
:<math>\langle A u_k, u_k \rangle + r_k\|Bu_k\|^2 \le 0</math>
Como todos os <math>u_k</math> estão na esfera unitária, que é compacta, a sequência <math>\{u_k\}</math> tem algum ponto de acumulação, por exemplo <math>\bar{u}</math>. Passando o limite em <math>k</math>, e considerando apenas a subsequência de <math>\{u_k\}</math> que converge para <math>\bar{u}</math>, tem-se
* <math>r_k \to +\infty</math> (pois <math>r_k > k</math>)
* <math>\langle A u_k, u_k \rangle \to \langle A \bar{u}, \bar{u} \rangle</math> e
* <math>\|Bu_k\|^2 \to \|B\bar{u}\|^2 \not = 0</math>
Neste caso,
:<math>\lim_{k \to +\infty} \langle A u_k, u_k \rangle + r_k\|Bu_k\|^2 \le 0</math>
só é possível se <math>\|B\bar{u}\|^2 = 0</math>, ou seja, se <math>B\bar{u}=0</math>. Logo,
:<math>\langle A \bar{u}, \bar{u} \rangle \le 0</math>
contradizendo a hipótese (1).
}}
{{Exercício
| |||