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 $\small A$ de dimensão $\small n \times n$ e os vetores $\small b$ e $\small X$ de dimensão n.
Dado o sistema linear $\small A X = b$, deseja-se obter a solução $\small 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 $\small A X = b$ pelo problema de encontrar o minimizador da função quadrática:
$\small 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 $\small f$ para que um ponto $\small X$ seja mı́nimo local desta função?
Introdução
Temos que um ponto mı́nimo de uma função é aquele que satisfaz:
Gradiente $\small \left( {f\left( { X } \right) }\right) = \nabla f\left( { X } \right) = 0$;
Hessiana $\small \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 $\small X^*$ seja o minimizador da função $\small f\left( X \right) = \frac{1}{2} X^T A X - b^T X$?
Introdução
Dada a função $\small f\left( X \right) = \frac{1}{2} X^T A X − b^T X$, note-se que:
\[ \small \nabla f\left( { X } \right) = AX - b\\ \small \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 $\small A$ deve ser simétrica e definida positiva;
Sendo $\small A$ simétrica e definida positiva, encontrar a solução do sistema linear $\small AX = b$ é equivalente a encontrar o ponto $\small X$ que satisfaz $\small \nabla f\left( { X } \right) = AX - b = 0$, ou seja, o mı́nimo da função $\small 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 \small A$ de dimensão $\small \small n \times n$, qualquer vector $\small \small X$ de valores diferentes de zero satisfaz a equação:
\[ \small AX = \lambda X \]
sendo $\small \small \lambda$ um factor de escala, chamado de autovetor e os elementos escalares de $\small \small \lambda$ chamados de autovalores.
Se $\small \small X \neq 0$, então $\small \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 \\ \small {\lambda ^2} - 4\lambda + 3 = 0 $
$\small \left| {\begin{array}{*{20}{c}} {2 - \lambda }&1\\ 1&{2 - \lambda } \end{array}} \right| = 0 \\ \small {\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 $\small 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 $\small X^{(0)}$;
Assim, dados o sistema $\small AX = b$ e um ponto inicial $\small X^{(0)}$, o objetivo é construir uma sequência $\small X^{(k)} $ que convirja para a solução do sistema.
Note-se que, $\small X^{(k)} $ convergir para a solução do sistema é equivalente a $\small r^{(k)}$ convergir para zero, sendo
\[ \small r^{(k)} = b - A X^{(k)} = - \nabla f\left( X^{(k)} \right) \]
o resı́duo no ponto $\small X^{(k)}$.
Direção de Busca
Para que a sequência $\small r^{(k)}$ tenda a zero, toma-se uma direção $\small d^{(k)}$ e se atualiza $\small X^{(k)}$ nesta direção. Assim, tem-se que:
\[ \small X^{(k + 1)} = X^{(k)} + \alpha d^{(k)} \]
de forma que $\small r^{(k + 1)} < r^{(k)}$.
Assim, dados o sistema $\small AX = b$ e um ponto inicial $\small X^{(0)}$, o objetivo é construir uma sequência $\small X^{(k)} $ que convirja para a solução do sistema.
É natural tomarmos a direção $\small d^{(k)}$ como sendo a direção oposta a $\small \nabla f\left( { X } \right)$ devido ao fato que a função $\small f$ cresce na direção do gradiente, ou seja, $\small d^{(k)} = r^{(k)}$.
Tamanho do Passo
Como $\small X^{(k + 1)} = X^{(k)} + \alpha r^{(k)}$ só resta definir $\small \alpha$ de forma que minimize $\small f\left( { X^{(k + 1)} } \right)$ na direção $\small r^{(k)}$. Isso é equivalente a encontrar $\small \alpha$ tal que:
\[ \small \frac{\partial f\left( { X^{(k + 1)} } \right)}{ \partial \alpha} = 0 \]
Note-se que:
\[ \small 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:
\[ \small f \left( { X^{(k + 1)} } \right) = \frac{1}{2} \left( { X^{(k)} } \right)^T A X^{(k)} − b^T \left( { X^{(k)} } \right) + \\ \small \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \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:
\[ \small \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 $\small \alpha$, tem-se:
\[ \small \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 $\small A x = b$ e um ponto inicial $\small x^{(0)}$, o Método do Gradiente para a resolução do sistema é definido com:
\[ \small r^{(k)} = b - A X^{(k)} = - \nabla f\left( X^{(k)} \right) \]
\[ \small \alpha = \frac{\left( { r^{(k)} } \right)^T r^{(k)} }{\left( { r^{(k)} } \right)^T A r^{(k)} } \]
\[ \small X^{(k + 1)} = X^{(k)} + \alpha r^{(k)} \]
Algoritmo
Dados: $\small A$, $\small b$, $\small x^{(0)}$ e a precisão, $\small \epsilon$, desejada. O algoritmo do Método do Gradiente é definido a seguir:
Fazer $\small k \leftarrow 0$.
Fazer $\small r^{(k)} = b - A X^{(k)}$ e $\small \alpha = \frac{\left( { r^{(k)} } \right)^T r^{(k)} }{\left( { r^{(k)} } \right)^T A r^{(k)} }$.
Atualizar $\small X^{(k + 1)} = X^{(k)} + \alpha r^{(k)}$.
Critério de parada: Se $\small \frac{| X^{(k + 1)} - X^{(k)} |}{| X^{(k + 1)} |}$ < $\small \epsilon$ ou se $\small k$ é maior que o máximo número de iterações, então parar $\small \rightarrow$ A solução é $\small X^{(k + 1)}$.
Fazer $\small k \leftarrow k + 1$ e voltar ao passo 2.
Exemplo 3.1.2: Método do Gradiente
Usando o Método do Gradiente para obter uma solução para o sistema linear $\small A X = b$, sendo:
\[ \small 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 $\small {x^{(0)}} = \left[ {\begin{array}{*{20}{c}} 0 \\ 0 \end{array}} \right]$ e com uma precisão $\small \epsilon = 10^{-1}$.
Primeira iteração ($\small k = 0$):
\[ \small {r^{(0)}} = b - A{X^{(0)}} = b = \left[ {\begin{array}{*{20}{c}} 5\\ 4 \end{array}} \right]\]
\[ \small \alpha = \frac{{{{\left( {{r^{(0)}}} \right)}^T}{r^{(0)}}}}{{{{\left( {{r^{(0)}}} \right)}^T}A{r^{(0)}}}} = 0,22\]
\[ \small {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:
\[ \small \frac{{\left\| {{x^{(1)}} - {x^{(0)}}} \right\|}}{{\left\| {{x^{(1)}}} \right\|}} = 1 > {10^{ - 1}}\]
Segunda iteração ($\small k = 1$):
\[ \small {r^{(1)}} = b - A{X^{(1)}} = b = \left[ {\begin{array}{*{20}{c}} -0,23\\ 0,30 \end{array}} \right]\]
\[ \small \alpha = \frac{{{{\left( {{r^{(1)}}} \right)}^T}{r^{(1)}}}}{{{{\left( {{r^{(1)}}} \right)}^T}A{r^{(1)}}}} = 0,41\]
\[ \small {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:
\[ \small \frac{{\left\| {{x^{(2)}} - {x^{(1)}}} \right\|}}{{\left\| {{x^{(2)}}} \right\|}} = 0,12 > {10^{ - 1}}\]
Terceira iteração ($ \small k = 2$):
\[ \small {r^{(2)}} = b - A{X^{(2)}} = b = \left[ {\begin{array}{*{20}{c}} 0,05\\ 0,04 \end{array}} \right]\]
\[ \small \alpha = \frac{{{{\left( {{r^{(1)}}} \right)}^T}{r^{(1)}}}}{{{{\left( {{r^{(1)}}} \right)}^T}A{r^{(1)}}}} = 0,41\]
\[ \small {x^{(3)}} = {x^{(2)}} + \alpha {r^{(2)}} = \left[ {\begin{array}{*{20}{c}} {1}\\ {1} \end{array}} \right]\]
Verificação do critério de parada:
$\small \frac{{\left\| {{x^{(3)}} - {x^{(2)}}} \right\|}}{{\left\| {{x^{(3)}}} \right\|}} = 0,01 < {10^{ - 1}}$ $\small \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 $\small A X = b$, sendo:
\[ \small A = \left[ {\begin{array}{*{20}{c}} \small 10 & 1 & 0\\ \small 1 & 10 & 1\\ \small 0 & 1 & 10 \end{array}} \right]; \ \ b = \left[ {\begin{array}{*{20}{c}} \small 11\\ \small 11\\ \small 1 \end{array}} \right],\]
a partir do ponto $ \small {x^{(0)}} = \left[ {\begin{array}{*{20}{c}} 0 \\ 0 \\ 0 \end{array}} \right]$ e com uma precisão $ \small \epsilon = 10^{-1}$.
Primeira iteração ($\small k = 0$):
\[ \small {r^{(0)}} = b - A{X^{(0)}} = b = \left[ {\begin{array}{*{20}{c}} \small 11\\ \small 11\\ \small 1 \end{array}} \right]\]
\[ \small \alpha = \frac{{{{\left( {{r^{(0)}}} \right)}^T}{r^{(0)}}}}{{{{\left( {{r^{(0)}}} \right)}^T}A{r^{(0)}}}} = 0,0902\]
\[ \small {x^{(1)}} = {x^{(0)}} + \alpha {r^{(0)}} = \left[ {\begin{array}{*{20}{c}} \small {0,9922}\\ \small {0,9922}\\ \small {0,0902} \end{array}} \right]\]
Verificação do critério de parada:
\[ \small \frac{{\left\| {{x^{(1)}} - {x^{(0)}}} \right\|}}{{\left\| {{x^{(1)}}} \right\|}} = 1 > {10^{ - 1}}\]
Segunda iteração ($ \small k = 1$):
\[ \small {r^{(1)}} = b - A{X^{(1)}} = b = \left[ {\begin{array}{*{20}{c}} \small 0,0858\\ \small -0,0044\\ \small -0,8542 \end{array}} \right]\]
\[ \small \alpha = \frac{{{{\left( {{r^{(1)}}} \right)}^T}{r^{(1)}}}}{{{{\left( {{r^{(1)}}} \right)}^T}A{r^{(1)}}}} = 0,0999\]
\[ \small {x^{(2)}} = {x^{(1)}} + \alpha {r^{(1)}} = \left[ {\begin{array}{*{20}{c}} \small {1,0007}\\ \small {0,9917}\\ \small 0,0009 \end{array}} \right]\]
Verificação do critério de parada:
$ \small \frac{{\left\| {{x^{(2)}} - {x^{(1)}}} \right\|}}{{\left\| {{x^{(2)}}} \right\|}} = 0,06 < {10^{ - 1}}$ $\small \rightarrow$ Convergiu!
Exemplo 3.1.4: Método do Gradiente
Usando o Método do Gradiente para obter uma solução para o sistema linear $\small A X = b$, sendo:
\[ \small A = \left[ {\begin{array}{*{20}{c}} \small 5 & 1 & 1\\ \small 3 & 4 & 1\\ \small 3 & 3 & 6 \end{array}} \right]; \ \ b = \left[ {\begin{array}{*{20}{c}} \small 5\\ \small 6\\ \small 0 \end{array}} \right],\]
a partir do ponto $ \small {x^{(0)}} = \left[ {\begin{array}{*{20}{c}} 0 \\ 0 \\ 0 \end{array}} \right]$ e com uma precisão $ \small \epsilon = 10^{-2}$.
Primeira iteração ($\small k = 0$):
\[ \small {r^{(0)}} = b - A{X^{(0)}} = b = \left[ {\begin{array}{*{20}{c}} \small 5\\ \small 6\\ \small 0 \end{array}} \right]\]
\[ \small \alpha = \frac{{{{\left( {{r^{(0)}}} \right)}^T}{r^{(0)}}}}{{{{\left( {{r^{(0)}}} \right)}^T}A{r^{(0)}}}} = 0,1568\]
\[ \small {x^{(1)}} = {x^{(0)}} + \alpha {r^{(0)}} = \left[ {\begin{array}{*{20}{c}} \small {0,7841}\\ \small {0,9409}\\ \small {0} \end{array}} \right]\]
Verificação do critério de parada:
\[ \small \frac{{\left\| {{x^{(1)}} - {x^{(0)}}} \right\|}}{{\left\| {{x^{(1)}}} \right\|}} = 1 > {10^{ - 2}}\]
Segunda iteração ($ \small k = 1$):
\[ \small {r^{(1)}} = b - A{X^{(1)}} = b = \left[ {\begin{array}{*{20}{c}} \small 0,1388\\ \small -0,1157\\ \small -5,1748 \end{array}} \right]\]
\[ \small \alpha = \frac{{{{\left( {{r^{(1)}}} \right)}^T}{r^{(1)}}}}{{{{\left( {{r^{(1)}}} \right)}^T}A{r^{(1)}}}} = 0,1673\]
\[ \small {x^{(2)}} = {x^{(1)}} + \alpha {r^{(1)}} = \left[ {\begin{array}{*{20}{c}} \small 0,8073\\ \small 0,9215\\ \small -0,8656 \end{array}} \right]\]
Verificação do critério de parada:
$ \small \frac{{\left\| {{x^{(2)}} - {x^{(1)}}} \right\|}}{{\left\| {{x^{(2)}}} \right\|}} = 0,8656 > {10^{ - 2}}$
Demais iterações:
$ \scriptsize \begin{array}{||c||c|c|c|c|c|c|c||} \hline \hline k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline r_1^{(k )} & 5 & 0.1388 & 0.9077 & 0.1032 & 0.1635 & 0.0250 & 0.0312 \\ \hline r_2^{(k )} & 6 & -0.1157 & 0.7577 & -0.1162 & 0.0378 & -0.0667 & -0.0187 \\ \hline r_3^{(k )} & 0 & -5.1748 & 0.0074 & -0.7572 & 0.0165 & -0.0952 & 0.0213 \\ \hline \alpha^{(k )} & 0.1568 & 0.1673 & 0.1517 & 0.1688 & 0.1588 & 0.1673 & 0.2302 \\ \hline x_1^{(k+1 )} & 0.7841 & 0.8073 & 0.9450 & 0.9624 & 0.9884 & 0.9926 & 0.9997 \\ \hline x_2^{(k+1 )} & 0.9409 & 0.9215 & 1.0365 & 1.0168 & 1.0228 & 1.0117 & 1.0074 \\ \hline x_3^{(k+1 )} & 0 & -0.8656 & -0.8645 & -0.9924 & -0.9897 & -1.0057 & -1.0008 \\ \hline \small \frac{{\left\| {{x^{(k+1)}} - {x^{(k)}}} \right\|}}{{\left\| {{x^{(k+1)}}} \right\|}} & 1 & 0.5774 & 0.1089 & 0.0761 & 0.0155 & 0.0115 & 0.0056 \\ \hline \end{array} $
Convergência na iteração 7!
Otimização em Sistemas de Energia Elétrica
Departamento de Engenharia Elétrica