Otimização/Método da lagrangiana aumentada

Origem: Wikilivros, livros abertos por um mundo aberto.

< Otimização

Ir para: navegação, pesquisa

Otimização

O problema a ser resolvido é:

$\left\{\begin{matrix} \min f(x)\\ h_j(x) = 0; j = 1, \ldots, q \end{matrix}\right.$

Sabe-se que se for aplicado o método da lagrangiana, será considerada a função:

$l:\mathbb{R}^n \times \mathbb{R}^q \mapsto \mathbb{R}$ dada por

$l(x,v) = f(x) + \sum_{j=1}^{q} v_j h_j (x)$ .

e também

$\beta:\mathbb{R}^q \mapsto \mathbb{R} \cup \{-\infty\}$ , dada por

$\beta(v) = \inf_{x \in \mathbb{R}^n} l(x,v)$

A grande dificuldade seria saber quando o valor de $β$ é finito. Uma idéia seria modificar um pouco a lagrangiana (aumentando-a, com um termo extra), da seguinte maneira:

$l(x,v) = f(x) + \sum_{j=1}^{q} v_j h_j (x) + r \sum_{j=1}^{q} \left(h_j (x)\right)^2$

Com isso, seria necessário garantir que a idéia de fato resolve o problema. Por este motivo, é preciso desenvolver alguns resultados teóricos. Para fazer a análise deste método, um primeiro resultado importante é o seguinte:

Lema (Finsler-Debreu)

Seja $A_{n\times n}$ uma matriz simétrica e $B_{p\times n}$ . As seguintes afirmações são equivalentes:

Se $B x = 0$ , com $x \not = 0$ , então $\langle Ax, x \rangle > 0$ ;
Existe $r > 0$ tal que a matriz $A + rB^\top B$ é definida positiva;
Existe $s > 0$ tal que a matriz $A + rB^\top B$ é definida positiva para todo $r > s$ .

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 $s > 0$ , tal que a matriz $A + sB^\top B$ é definida positiva. Logo, para concluir a outra implicação, basta notar que para qualquer $x \not = 0$ vale:

$\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}$

Assim, (2) também implica (3).

Agora, será mostrado que de (2) se conclui (1). De fato, se $B x = 0$ , para algum $x \not = 0$ , então:

$\langle A x, x \rangle = \langle A x, x \rangle + r\|Bx\|^2 = \langle (A + rB^\top B)x, x \rangle > 0$

Finalmente, será garantido que se vale (1) então vale (3) (ver também página 25, de 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 $x \not = 0$ tal que $B x = 0$ , tem-se $\langle Ax, x \rangle > 0$ , e que fosse falsa a afirmação (3), existiria para cada $s > 0$ algum $r > s$ e algum $x \not =0$ de modo que

$\langle A x, x \rangle + r\|Bx\|^2 \le 0$

Neste caso, dividindo por $\|x\|^2$ , e denotando $u = \frac{x}{\|x\|}$ , segue que para cada $k \in \mathbb{N}$ , existe algum $r k > k$ e algum $u_k \in \mathbb{R}^n$ , com $\|u_k\| = 1$ , tais que

$\langle A u_k, u_k \rangle + r_k\|Bu_k\|^2 \le 0$

Como todos os $u k$ estão na esfera unitária, que é compacta, a sequência ${u k}$ tem algum ponto de acumulação, por exemplo $\bar{u}$ . Passando o limite em $k$ , e considerando apenas a subsequência de ${u k}$ que converge para $\bar{u}$ , tem-se

$r_k \to +\infty$ (pois $r k > k$ )
$\langle A u_k, u_k \rangle \to \langle A \bar{u}, \bar{u} \rangle$ e
$\|Bu_k\|^2 \to \|B\bar{u}\|^2 \not = 0$

Neste caso,

$\lim_{k \to +\infty} \langle A u_k, u_k \rangle + r_k\|Bu_k\|^2 \le 0$

só é possível se $\|B\bar{u}\|^2 = 0$ , ou seja, se $B\bar{u}=0$ . Logo,

$\langle A \bar{u}, \bar{u} \rangle \le 0$

contradizendo a hipótese (1).

Exercício

Prove a seguinte variante do lema anterior:

Seja $A_{n\times n}$ uma matriz simétrica e semi-definida positiva, e $B_{p\times n}$ . As seguintes afirmações são equivalentes:

Se $B x = 0$ , com $x \not = 0$ , então $\langle Ax, x \rangle > 0$ ;
Existe $r > 0$ tal que a matriz $A + rB^\top B$ é definida positiva;
Para todo $r > 0$ , a matriz $A + rB^\top B$ é definida positiva.

A partir de agora, o problema será:

$\left\{\begin{matrix} \min f(x)\\ h_j(x) = 0; j = 1, \ldots, q \end{matrix}\right.$

onde se supõe que $f,\, h_i : \mathbb{R}^n \mapsto \mathbb{R}$ são funções de classe $\mathcal{C}^2\left( \mathbb{R}^n\right)$ e que para todo $\lambda \in \mathbb{R}$ , o conjunto $\{x \in \mathbb{R}^n; f(x) \le \lambda\}$ é compacto (em inglês costuma-se usar a expressão inf-compact para descrever tais funções).

Sabe-se que a lagrangiana associada ao problema $(P)$ é:

$l:\mathbb{R}^n \times \mathbb{R}^q \mapsto \mathbb{R}$ dada por

$l(x,v) = f(x) + \sum_{j=1}^{q} v_j h_j (x)$ .

e ainda, em uma notação mais sintética, considerando a função $H$ dada por:

$H:\mathbb{R}^n \mapsto \mathbb{R}^q$ definida por

$H(x) = \begin{bmatrix} h_1(x)\\ \vdots \\ h_q(x)\end{bmatrix}$

tem-se a lagrangiana expressa da seguinte maneira:

$l(x,v) = f(x) + H(x)^\top v$

Para o método da lagrangiana aumentada serão assumidas as seguintes hipóteses:

Se $\bar{x}$ é solução, então existe $\bar{u} \in \mathbb{R}^q$ tal que $\nabla_x l(\bar{x}, \bar{u}) = 0$ ;
Para todo $d \not = 0$ , o jacobiano de $H$ satizfaz:

$J_H(x) d = 0 \Rightarrow d^\top H_x^2 l (\bar{x}, \bar{u}) d > 0$

Note que a segunda hipótese tem exatamente a mesma forma de uma das condições que aparece no lema de Finsler-Debreu.

Definição

Dado $ρ > 0$ , se define a lagrangiana aumentada para o problema $(P)$ como:

$l_{\rho}:\mathbb{R}^n \times \mathbb{R}^q \mapsto \mathbb{R}$ dada por

$l_{\rho}(x,v) = f(x) + H(x)^\top v + \frac{\rho}{2}H(x)^\top H(x) = l(x,v) + \frac{\rho}{2}H(x)^\top H(x)$

Observe que é justamente a aparição do termo $\frac{\rho}{2}H(x)^\top H(x)$ sendo somado à lagrangiana que justifica o nome lagrangiana aumentada.

Esse conceito possui algumas interpretações:

Exercício

Verifique que a lagrangiana aumentada $l ρ$ é justamente a lagrangiana do problema $(P)$ penalizado, ou seja, de

$\left\{\begin{matrix} \min f(x) + \frac{\rho}{2}H(x)^\top H(x)\\ H(x) = 0 \end{matrix}\right.$

Demonstração
Basta notar que dentro do conjunto viável as funções objetivos são iguais.

Exercício

Verifique que a função dual $β ρ$ (o ínfimo da lagrangiana aumentada em relação à primeira componente), dada por

$\beta_\rho:\mathbb{R}^q \mapsto \mathbb{R} \cup \{-\infty\}$ , com

$\beta_\rho(v) = \inf_{x \in \mathbb{R}^n} l_\rho(x,v)$

para

0 < ρ < δ

satisfaz

$\beta_\rho (v) \le \beta_\delta (v) \le f(\bar{x})$

onde $\bar{x}$ é solução de

(P)

Demonstração

$\begin{align} \beta_\rho(v) & = \inf_{x \in \mathbb{R}^n} l_\rho(x,v)\\ & = \inf_{x \in \mathbb{R}^n} [f(x)+H(x)^{\top}v+\frac{\rho}{2}H(x)^{\top}H(x)]\\ & \leq \inf_{x \in \mathbb{R}^n} [f(x)+H(x)^{\top}v+\frac{\delta}{2}H(x)^{\top}H(x)]\\ & = \inf_{x \in \mathbb{R}^n} l_\delta (x,v)\\ & = \beta_\delta(v) \end{align}$

E a segunda desigualdade

$\beta_\delta(v)= \inf_{x \in \mathbb{R}^n} l_\delta (x,v)\leq l_\delta (\bar{x},v)=f(\bar{x})$ .

Exercício

Verifique que $\{x \in \mathbb{R}^n; l_\rho(x,v) \le \lambda \}$ é compacto, qualquer que seja $\lambda \in \mathbb{R}$ e $v \in \mathbb{R}^q$ .

Resolução
A resolução deste exercício é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

Proposição

Se $\bar{x}$ é solução de $(P)$ , então existe algum $ρ 0 > 0$ , algum $δ 0 > 0$ e alguma vizinhança $X 0$ de $\bar{x}$ tais que $l_{\rho_0} ( \cdot, \bar{v})$ é fortemente convexa com parâmetro $δ 0$ .

Demonstração

Conforme o lema de Finsler-Debreu, a hipótese (2), segundo a qual para todo $d \not = 0$ , o jacobiano de

H

satizfaz:

$J_H(x) d = 0 \Rightarrow d^\top H_x^2 l (\bar{x}, \bar{u}) d > 0$

equivale a dizer que existe algum $ρ 0 > 0$ tal que $\nabla_x l(\bar{x},\bar{v}) + \rho_0 \left(J_H(x)\right)^\top \left(J_H(x)\right)$ é definida positiva.

Mas a Hessiana de $l_{\rho_0}$ é dada por $\nabla_x^2 l_{\rho_0}(\bar{x},\bar{v}) = \nabla_x^2 l(\bar{x},\bar{v}) + \left(J_H(x)\right)^\top \left(J_H(x)\right)$ . Logo, a hipótese equivale a dizer que $\nabla_x^2 l_{\rho_0} (\bar{x}, \bar{v})$ é definida positiva.

Considere agora a função $\delta: \mathbb{R}^n \times \mathbb{R}^n \mapsto \mathbb{R}$ definida por

$\delta(d,x) = d^\top \nabla_x^2 l_\rho (x,\bar{u}) d$

Logo, para qualquer $d \not = 0$ , tomando $x = \bar{x}$ , tem-se

$\delta(d,x) = \delta(d,\bar{x}) = d^\top \nabla_x^2 l_\rho (\bar{x},\bar{u}) d > 0$

Pela continuidade da função $δ$ , existe uma vizinhança $X 0$ de $\bar{x}$ tal que $δ(d, x) > 0$ para todo ponto $x \in X_0$ , e qualquer que seja $d\not = 0$ . Além disso, tal vizinhança pode ser tomada aberta, convexa e suficientemente pequena para que $\delta(d,x) \ge \epsilon > 0$ .

Assim, tomando o ínfimo, pode-se definir $δ 0$ como

$\delta_0 = \inf_{\begin{smallmatrix}x \in X_0\\\|d\| = 1\end{smallmatrix}} \delta(d,x)$

Então

$\delta\left(\frac{d}{\|d\|}, x\right) = \left(\frac{d}{\|d\|}\right)^\top \nabla_x^2 l_{\rho_0} (x,\bar{u}) \left(\frac{d}{\|d\|}\right) \ge \delta_0$

quaisquer que sejam $d\not=0$ e $x \in X_0$ .

Portanto,

$d^\top \left[\nabla_x^2 l_{\rho_0} (x,\bar{u})\right] d \ge \delta_0 \|d\|^2$

ou seja, os auto-valores de $\nabla_x^2 l_{\rho_0} (x,\bar{u})$ são todos positivos.

Para concluir que $l_{\rho_0}(\cdot, \bar{u})$ é fortemente convexa, basta recordar-se de dois fatos:

Uma função $f$ de classe $\mathcal{C}^2$ é convexa se, e somente se, $\nabla^2 f$ é semidefinida positiva;
Uma função $f$ é fortemente convexa se, e somente se, existe uma constante $α > 0$ tal que $f(x) - \frac{\alpha}{2}\|x\|^2$ é convexa, ou seja, $d^\top \nabla^2 f(x) d - \alpha \|x\|^2 \ge 0$ .

Com isso, $l_{\rho_0}(\cdot, \bar{u})$ é fortemente convexa pois

$d^\top \left[\nabla_x^2 l_{\rho_0} (x,\bar{u})\right] d - \delta_0 \|d\|^2 \ge 0$

Isso significa que há um único mínimo local para tal função, e que consequentemente ele é um mínimo global. Das hipóteses 1 e 2 colocadas no início da discussão sobre a lagrangiana aumentada, segue que $l_{\rho_0}$ é fortemente convexa em $X 0$ .

Com essas condições, mostrou-se que em um ponto que seja solução, a lagrangiana aumentada é fortemente convexa.

Antes de apresentar o algoritmo, será fixada mais uma notação:

$(P_{\rho, u})\left\{\begin{matrix} \min l_{\rho} (x,u)\\ x \in \mathbb{R}^n \end{matrix}\right.$

[editar] Algoritmo da lagrangiana aumentada

Dados $ρ > 0$ e $\epsilon \in (0,\rho)$ .

Início: Tome  e  $k = 0$ .

Iteração: Calcule  $x k$ , solução de .
     Se  $H (x k) = 0$ , pare: .
     Senão, faça
            $u k + 1 = u k + ε H (x k)$ 
            $k = k + 1$

Este é um dos algoritmos mais usados e mais eficientes para problemas de programação não linear. A garantia de convergência segue dos próximos teoremas.

Teorema

Sejam $ρ 0$ , $δ 0$ e $X 0$ como na proposição anterior. Se $U$ é uma vizinhança de $\bar{u}$ , existe algum $ρ U > ρ 0$ tal que:

$X(\rho, u) \subset X_0, \forall u \in U$
$X(\rho, \bar{u}) = \{ \bar{x} \}$ e $\beta_\rho (\bar{u}) = f(\bar{x})$

Observações:

$X (ρ, u)$ denota as soluções do problema;
A igualdade $\beta_\rho (\bar{u}) = f(\bar{x})$ significa que não há salto de dualidade.
Já foi mostrado que a função é fortemente convexa em uma vizinhança. Logo, os minimizadores devem estar em tal vizinhança.
A prova é um pouco técnica, e usa as condições de KKT, mostrando que o cone linearizado é igual ao cone tangente.

Prova
Esta prova é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

O segundo teorema é:

Teorema

Se $ρ$ é suficientemente grande e $δ$ suficientemente pequeno, então:

$x_k \to \bar{x}$
$l_\rho (x_k,u_k) \to f(\bar{x})$
${u k}$ é limitada

Observações:

A propriedade 2 praticamente segue do fato de não haver salto de dualidade.

Justificativa
Fica a cargo do leitor justificar este fato. Sinta-se livre para melhorar a qualidade deste texto, incluindo a justificativa neste módulo.

Com esses resultados, tem-se a garantia de que o algoritmo realmente converge para uma solução, desde que os parâmetros sejam tomados adequadamente. A questão que ainda permanece é como identificar os valores adequados de $ρ$ e de $δ$ para que tal convergência ocorra.

Exercício

Argumente porque as hipóteses 1, 2 e 3 garantem que a iteração do algoritmo da Lagrangiana aumentada para problemas de minimização com restrições de igualdade tem uma única solução, sendo:

Todas as funções são de classe $\mathcal{C}^2$ e a função objetivo tem todos os seus subníveis compactos.
Se $\bar{x}$ é solução do problema, então existe $\bar{u}$ tal que o gradiente da Lagrangiana não aumentada com respeito a variável primal se anula em $(\bar{x},\bar{u})$ .
A hessiana da Lagrangiana não aumentada com respeito a variável primal é definida positiva sob a variedade ortogonal de todos os gradientes no ponto $\bar{x}$ das restrições.

Otimização/Método da lagrangiana aumentada

Origem: Wikilivros, livros abertos por um mundo aberto.

[editar] Algoritmo da lagrangiana aumentada

Acessos

Ferramentas pessoais

Pesquisa

Navegação

Projecto

Imprimir/exportar

Ferramentas