Otimização em Sistemas de Energia Elétrica
Departamento de Engenharia Elétrica
Unidade 3
Resolução de Problemas de Otimização Usando Metodologias Clássicas
3.1. Método do Gradiente
Introdução
Considere-se a matriz $A$ de dimensão $n \times n$ e os vetores $b$ e $X$ de dimensão n.
Dado o sistema linear $A X = b$, deseja-se obter a solução $X$ deste sistema;
O Método do Gradiente pode ser utilizado para a resolução deste sistema.
A ideia básica do método é trocar o problema de encontrar a solução do sistema $A X = b$ pelo problema de encontrar o minimizador da função quadrática:
$ f\left( X \right) = \frac{1}{2} X^T A X − b^T X$
Introdução
Quais condições são necessárias sobre uma função $f$ para que um ponto $X$ seja mı́nimo local desta função?
Introdução
Temos que um ponto mı́nimo de uma função é aquele que satisfaz:
Gradiente $\left( {f\left( { X } \right) }\right) = \nabla f\left( { X } \right) = 0$;
Hessiana $\left( {f\left( { X } \right) }\right) = \nabla^2 f\left( { X } \right) \rightarrow $ Definida positiva.
A primeira condição garante que o ponto seja estacionário, e a segunda garante que este seja um mı́nimo local.
Introdução
Então, quais condições são necessárias para que o ponto $X^*$ seja o minimizador da função $ f\left( X \right) = \frac{1}{2} X^T A X - b^T X$?
Introdução
Dada a função $ f\left( X \right) = \frac{1}{2} X^T A X − b^T X$, note-se que:
\[ \nabla f\left( { X } \right) = AX - b\\ \nabla^2 f\left( { X } \right) = A \]
Assim, para poder aplicar o Método do Gradiente e encontrar o mı́nimo da função, a matriz $A$ deve ser simétrica e definida positiva;
Sendo $A$ simétrica e definida positiva, encontrar a solução do sistema linear $AX = b$ é equivalente a encontrar o ponto $X$ que satisfaz $\nabla f\left( { X } \right) = AX - b = 0$, ou seja, o mı́nimo da função $f$.
Matriz Definida Positiva
A condição para que uma matriz seja definida positiva exige que todos os autovalores desta matriz, avaliados em determinado ponto crítico, sejam positivos.
Dada uma matriz $\small A$ de dimensão $\small n \times n$, qualquer vector $\small X$ de valores diferentes de zero satisfaz a equação:
\[ \small AX = \lambda X \]
sendo $\small \lambda$ um factor de escala, chamado de autovetor e os elementos escalares de $\small \lambda$ chamados de autovalores.
Se $\small X \neq 0$, então $\small \lambda$ fornece as raízes da equação característica:
\[ \small \left| {A - \lambda I} \right| = 0 \]
Exemplo 3.1.1: Matriz Definida Positiva
Calcular os autovalores e os autovectores da matriz:
$\small A = \left[ {\begin{array}{*{20}{c}} 2&1\\ 1&2 \end{array}} \right]$
Os autovalores do problema são definidos como:
$\small \left[ {\begin{array}{*{20}{c}} 2&1\\ 1&2 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}} \end{array}} \right] = \lambda \left[ {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}} \end{array}} \right] $
A característica polinomial é dada por:
$\small \left| {A - \lambda I} \right| = 0 $
Ou:
$\small \left| {\begin{array}{*{20}{c}} {2 - \lambda }&1\\ 1&{2 - \lambda } \end{array}} \right| = 0 \\ {\lambda ^2} - 4\lambda + 3 = 0 $
$\small \left| {\begin{array}{*{20}{c}} {2 - \lambda }&1\\ 1&{2 - \lambda } \end{array}} \right| = 0 \\ {\lambda ^2} - 4\lambda + 3 = 0 $
As raízes do polinómio $\small {\lambda ^2} - 4\lambda + 3 = 0$ são: $\small \lambda_1 = 3$ e $\small \lambda_2 = 1$. Então, os autovalores de $\small A$ são 3 e 1.
Como os autovalores da matriz $A$ são positivos, então a matriz A é definida positiva.
Filosofia do Método
O Método do Gradiente é um método iterativo. Portanto, é necessário partir de um ponto inicial $X^{(0)}$;
Assim, dados o sistema $AX = b$ e um ponto inicial $X^{(0)}$, o objetivo é construir uma sequência $X^{(k)} $ que convirja para a solução do sistema.
Note-se que, $X^{(k)} $ convergir para a solução do sistema é equivalente a $r^{(k)}$ convergir para zero, sendo
\[ r^{(k)} = b - A X^{(k)} = - \nabla f\left( X^{(k)} \right) \]
o resı́duo no ponto $X^{(k)}$.
Direção de Busca
Para que a sequência $r^{(k)}$ tenda a zero, toma-se uma direção $d^{(k)}$ e se atualiza $X^{(k)}$ nesta direção. Assim, tem-se que:
\[ X^{(k + 1)} = X^{(k)} + \alpha d^{(k)} \]
de forma que $r^{(k + 1)} < r^{(k)}$.
Assim, dados o sistema $AX = b$ e um ponto inicial $X^{(0)}$, o objetivo é construir uma sequência $X^{(k)} $ que convirja para a solução do sistema.
É natural tomarmos a direção $d^{(k)}$ como sendo a direção oposta a $\nabla f\left( { X } \right)$ devido ao fato que a função $f$ cresce na direção do gradiente, ou seja, $d^{(k)} = r^{(k)}$.
Tamanho do Passo
Como $X^{(k + 1)} = X^{(k)} + \alpha r^{(k)}$ só resta definir $\alpha$ de forma que minimize $f\left( { X^{(k + 1)} } \right)$ na direção $r^{(k)}$. Isso é equivalente a encontrar $\alpha$ tal que:
\[ \frac{\partial f\left( { X^{(k + 1)} } \right)}{ \partial \alpha} = 0 \]
Note-se que:
\[ f\left( { X^{(k + 1)} } \right) = \frac{1}{2} \left( { X^{(k)} + \alpha r^{(k)} } \right)^T A \left( { X^{(k)} + \alpha r^{(k)} } \right) − b^T \left( { X^{(k)} + \alpha r^{(k)} } \right) \]
Tamanho do Passo
Com algumas manipulações algébricas temos:
\[ f \left( { X^{(k + 1)} } \right) = \frac{1}{2} \left( { X^{(k)} } \right)^T A X^{(k)} − b^T \left( { X^{(k)} } \right) + \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \alpha \left( { r^{(k)} } \right)^T A X^{(k)} + \frac{\alpha^2}{2} \left( { r^{(k)} } \right)^T A r^{(k)} -\alpha b^T r^{(k)} \]
Assim:
\[ \frac{\partial f \left( { X^{(k + 1)} } \right)}{\partial \alpha} = \left( { r^{(k)} } \right)^T A X^{(k)} + \alpha \left( { r^{(k)} } \right)^T A r^{(k)} - b^T r^{(k)} = 0 \]
Tamanho do Passo
Isolando $\alpha$, tem-se:
\[ \alpha = \frac{\left( { r^{(k)} } \right)^T r^{(k)} }{\left( { r^{(k)} } \right)^T A r^{(k)} } \]
que é o melhor passo que pode ser dado nesta direção.
Resumo
Dado o sistema linear $A x = b$ e um ponto inicial $x^{(0)}$, o Método do Gradiente para a resolução do sistema é definido com:
\[ r^{(k)} = b - A X^{(k)} = - \nabla f\left( X^{(k)} \right) \]
\[ \alpha = \frac{\left( { r^{(k)} } \right)^T r^{(k)} }{\left( { r^{(k)} } \right)^T A r^{(k)} } \]
\[ X^{(k + 1)} = X^{(k)} + \alpha r^{(k)} \]
Algoritmo
Dados: $A$, $b$, $x^{(0)}$ e a precisão, $\epsilon$, desejada. O algoritmo do Método do Gradiente é definido a seguir:
Fazer $k \leftarrow 0$.
Fazer $r^{(k)} = b - A X^{(k)}$ e $\alpha = \frac{\left( { r^{(k)} } \right)^T r^{(k)} }{\left( { r^{(k)} } \right)^T A r^{(k)} }$.
Atualizar $X^{(k + 1)} = X^{(k)} + \alpha r^{(k)}$.
Critério de parada: Se $\frac{| X^{(k + 1)} - X^{(k)} |}{| X^{(k + 1)} |}$ < $\epsilon$ ou se $ k$ é maior que o máximo número de iterações, então parar $\rightarrow$ A solução é $X^{(k + 1)}$.
Fazer $k \leftarrow k + 1$ e voltar ao passo 2.
Exemplo 3.1.2: Método do Gradiente
Usando o Método dos Gradientes para obter uma solução para o sistema linear $A X = b$, sendo:
\[A = \left[ {\begin{array}{*{20}{c}} 4 & 1\\ 1 & 3 \end{array}} \right]; \ \ b = \left[ {\begin{array}{*{20}{c}} 5\\ 4 \end{array}} \right],\]
a partir do ponto ${x^{(0)}} = \left[ {\begin{array}{*{20}{c}} 0 \\ 0 \end{array}} \right]$ e com uma precisão $\epsilon = 10^{-1}$.
Primeira iteração ($k = 0$):
\[{r^{(0)}} = b - A{X^{(0)}} = b = \left[ {\begin{array}{*{20}{c}} 5\\ 4 \end{array}} \right]\]
\[ \alpha = \frac{{{{\left( {{r^{(0)}}} \right)}^T}{r^{(0)}}}}{{{{\left( {{r^{(0)}}} \right)}^T}A{r^{(0)}}}} = 0,22\]
\[{x^{(1)}} = {x^{(0)}} + \alpha {r^{(0)}} = \left[ {\begin{array}{*{20}{c}} {1,09}\\ {0,87} \end{array}} \right]\]
Verificação do critério de parada:
\[\frac{{\left\| {{x^{(1)}} - {x^{(0)}}} \right\|}}{{\left\| {{x^{(1)}}} \right\|}} = 1 > {10^{ - 1}}\]
Segunda iteração ($k = 1$):
\[{r^{(1)}} = b - A{X^{(1)}} = b = \left[ {\begin{array}{*{20}{c}} -0,23\\ 0,30 \end{array}} \right]\]
\[ \alpha = \frac{{{{\left( {{r^{(1)}}} \right)}^T}{r^{(1)}}}}{{{{\left( {{r^{(1)}}} \right)}^T}A{r^{(1)}}}} = 0,41\]
\[{x^{(2)}} = {x^{(1)}} + \alpha {r^{(1)}} = \left[ {\begin{array}{*{20}{c}} {0,99}\\ {0,99} \end{array}} \right]\]
Verificação do critério de parada:
\[\frac{{\left\| {{x^{(2)}} - {x^{(1)}}} \right\|}}{{\left\| {{x^{(2)}}} \right\|}} = 0,12 > {10^{ - 1}}\]
Terceira iteração ($k = 2$):
\[{r^{(2)}} = b - A{X^{(2)}} = b = \left[ {\begin{array}{*{20}{c}} 0,05\\ 0,04 \end{array}} \right]\]
\[ \alpha = \frac{{{{\left( {{r^{(1)}}} \right)}^T}{r^{(1)}}}}{{{{\left( {{r^{(1)}}} \right)}^T}A{r^{(1)}}}} = 0,41\]
\[{x^{(3)}} = {x^{(2)}} + \alpha {r^{(2)}} = \left[ {\begin{array}{*{20}{c}} {1}\\ {1} \end{array}} \right]\]
Verificação do critério de parada:
$\frac{{\left\| {{x^{(3)}} - {x^{(2)}}} \right\|}}{{\left\| {{x^{(3)}}} \right\|}} = 0,01 > {10^{ - 1}}$ $\rightarrow$ Convergiu!
Exemplo 3.1.3: Método do Gradiente
Usando o Método do Gradiente para obter uma solução para o sistema linear $A X = b$, sendo:
\[ \scriptsize A = \left[ {\begin{array}{*{20}{c}} \scriptsize 10 & 1 & 0\\ \scriptsize 1 & 10 & 1\\ \scriptsize 0 & 1 & 10 \end{array}} \right]; \ \ b = \left[ {\begin{array}{*{20}{c}} \scriptsize 11\\ \scriptsize 11\\ \scriptsize 1 \end{array}} \right],\]
a partir do ponto $ \scriptsize {x^{(0)}} = \left[ {\begin{array}{*{20}{c}} 0 \\ 0 \\ 0 \end{array}} \right]$ e com uma precisão $ \scriptsize \epsilon = 10^{-1}$.
Primeira iteração ($k = 0$):
\[ \scriptsize {r^{(0)}} = b - A{X^{(0)}} = b = \left[ {\begin{array}{*{20}{c}} \scriptsize 11\\ \scriptsize 11\\ \scriptsize 1 \end{array}} \right]\]
\[ \scriptsize \alpha = \frac{{{{\left( {{r^{(0)}}} \right)}^T}{r^{(0)}}}}{{{{\left( {{r^{(0)}}} \right)}^T}A{r^{(0)}}}} = 0,0902\]
\[ \scriptsize {x^{(1)}} = {x^{(0)}} + \alpha {r^{(0)}} = \left[ {\begin{array}{*{20}{c}} \scriptsize {0,9922}\\ \scriptsize {0,9922}\\ \scriptsize {0,0902} \end{array}} \right]\]
Verificação do critério de parada:
\[ \scriptsize \frac{{\left\| {{x^{(1)}} - {x^{(0)}}} \right\|}}{{\left\| {{x^{(1)}}} \right\|}} = 1 > {10^{ - 1}}\]
Segunda iteração ($k = 1$):
\[ \scriptsize {r^{(1)}} = b - A{X^{(1)}} = b = \left[ {\begin{array}{*{20}{c}} \scriptsize 0,0858\\ \scriptsize -0,0044\\ \scriptsize -0,8542 \end{array}} \right]\]
\[ \scriptsize \alpha = \frac{{{{\left( {{r^{(1)}}} \right)}^T}{r^{(1)}}}}{{{{\left( {{r^{(1)}}} \right)}^T}A{r^{(1)}}}} = 0,0999\]
\[ \scriptsize {x^{(2)}} = {x^{(1)}} + \alpha {r^{(1)}} = \left[ {\begin{array}{*{20}{c}} \scriptsize {1,0007}\\ \scriptsize {0,9917}\\ \scriptsize 0,0009 \end{array}} \right]\]
Verificação do critério de parada:
$ \scriptsize \frac{{\left\| {{x^{(2)}} - {x^{(1)}}} \right\|}}{{\left\| {{x^{(2)}}} \right\|}} = 0,06 > {10^{ - 1}}$ $\scriptsize \rightarrow$ Convergiu!
Otimização em Sistemas de Energia Elétrica
Departamento de Engenharia Elétrica