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.2. Método de Newton

Introdução

• O método mais amplamente usado para resolver equações algébricas lineares e não-lineares simultâneas é o Método de Newton-Raphson.

• Este método consiste em processo sucessivo de aproximações baseadas em uma estimativa inicial e o uso da expansão em séries de Taylor.

Dedução das Expressões do Método de Newton

• Considere a solução da equação unidimensional dada por:

  $\small f(x) = c$

• Se $\small x^{(k)}$ é a aproximação da solução, na iteração $\small k$, e $\small \Delta x^{(k)}$ é um pequeno desvio dessa solução, então, a solução, na iteração $\small k + 1$, será:

  $\small f(x^{(k + 1)}) = f(x^{(k)} + \Delta x^{(k)})$

• Expandindo o lado direito da anterior expressão em séries de Taylor em torno de $\small x^{(k)}$:

  $\small f(x^{(k + 1)}) = f(x^{(k)}) + \left({\frac{df}{dx}}\right) ^{(k)}\Delta x^{(k)} + \frac{1}{2!}\left({\frac{d^2f}{dx^2}}\right)^{(k)}\Delta (x^{(k)})^2 + \cdots $

Dedução das Expressões do Método de Newton

$\small f(x^{(k + 1)}) = f(x^{(k)}) + \left({\frac{df}{dx}}\right) ^{(k)}\Delta x^{(k)} + \frac{1}{2!}\left({\frac{d^2f}{dx^2}}\right)^{(k)}\Delta (x^{(k)})^2 + \cdots $

• Assumindo que o erro $\small \Delta (x^{(k)})^2$ seja muito pequeno, os termos de ordem superior a um podem ser desprezados, o que resulta em:

  $\small f(x^{(k + 1)}) = f(x^{(k)}) + \left({\frac{df}{dx}}\right) ^{(k)}\Delta x^{(k)} $

  ou

  $\small f(x^{(k + 1)}) = f(x^{(k)}) + \left({\frac{df}{dx}}\right) ^{(k)} ( x^{(k + 1)} - x^{(k)} ) $

  sendo $ \Delta x^{(k)} = x^{(k + 1)} - x^{(k)}$

Dedução das Expressões do Método de Newton

$\small f(x^{(k + 1)}) = f(x^{(k)}) + \left({\frac{df}{dx}}\right) ^{(k)} ( x^{(k + 1)} - x^{(k)} ) $

• A anterior expressão corresponde à linearização da função no ponto $\small x^{(k + 1)}$. Se a linha reta associada à linearização da função no ponto $\small x^{(k + 1)}$ fosse extendida até a interseção com eixo horizontal, então $\small f(x^{(k + 1)})$ assumiria o valor de zero. Assim, substituindo $\small f(x^{(k + 1)}) = 0$ na anterior expressão, obtem-se que:

  $\small x^{(k + 1)} = x^{(k)} - \frac{ f(x^{(k)}) }{ \left({\frac{df}{dx}}\right)^{(k)} } $

Dedução das Expressões do Método de Newton

• Considere agora o seguinte conjunto $\small n$ dimensional de equações:

  $\scriptsize \begin{array}{*{20}{c}} {{{\left( {{f_1}} \right)}^{(k)}} + {{\left( {\frac{{\partial {f_1}}}{{\partial {x_1}}}} \right)}^{(k)}}\Delta x_1^{(k)} + {{\left( {\frac{{\partial {f_1}}}{{\partial {x_2}}}} \right)}^{(k)}}\Delta x_2^{(k)} + \cdots + {{\left( {\frac{{\partial {f_1}}}{{\partial {x_n}}}} \right)}^{(k)}}\Delta x_n^{(k)} = {c_1}}\\ {{{\left( {{f_2}} \right)}^{(k)}} + {{\left( {\frac{{\partial {f_2}}}{{\partial {x_1}}}} \right)}^{(k)}}\Delta x_1^{(k)} + {{\left( {\frac{{\partial {f_2}}}{{\partial {x_2}}}} \right)}^{(k)}}\Delta x_2^{(k)} + \cdots + {{\left( {\frac{{\partial {f_2}}}{{\partial {x_n}}}} \right)}^{(k)}}\Delta x_n^{(k)} = {c_2}}\\ \vdots \\ {{{\left( {{f_n}} \right)}^{(k)}} + {{\left( {\frac{{\partial {f_n}}}{{\partial {x_1}}}} \right)}^{(k)}}\Delta x_1^{(k)} + {{\left( {\frac{{\partial {f_n}}}{{\partial {x_2}}}} \right)}^{(k)}}\Delta x_2^{(k)} + \cdots + {{\left( {\frac{{\partial {f_n}}}{{\partial {x_n}}}} \right)}^{(k)}}\Delta x_n^{(k)} = {c_n}} \end{array}$

• Aplicando o mesmo procedimento do caso de uma só variável, mostrado anteriormente, obtém-se:

  $\small X^{(k + 1)} = X^{(k)} - \frac{ F^{(k)} }{ \left({\frac{dF}{dX}}\right)^{(k)} } $

Dedução das Expressões do Método de Newton

$\small X^{(k + 1)} = X^{(k)} - \left({ \left({\frac{dF}{dX}}\right)^{(k)} } \right)^{-1} {F} ^{(k)} = X^{(k)} - \left({ \nabla F ^{(k)} } \right)^{-1} \left({ F }\right) ^{(k)} $

sendo:

$\tiny \Delta {X^{(k + 1)}} = \left[ {\begin{array}{*{20}{c}} {\Delta x_1^{(k + 1)}}\\ {\Delta x_2^{(k + 1)}}\\ \vdots \\ {\Delta x_n^{(k + 1)}} \end{array}} \right]; \ \ \Delta {X^{(k)}} = \left[ {\begin{array}{*{20}{c}} {\Delta x_1^{(k)}}\\ {\Delta x_2^{(k)}}\\ \vdots \\ {\Delta x_n^{(k)}} \end{array}} \right]; \ \ F^{(k)} = \left[ {\begin{array}{*{20}{c}} {{{ {{{ {f_1}}}{{ {}}}} }^{(k)}}}\\ {{{ {{{ {f_2}}}{{ {}}}}}^{(k)}}}\\ \vdots \\ {{{ {{{ {f_n}}}{{ {}}}} }^{(k)}}} \end{array}} \right]; \ \ \nabla F^{(k)} = \left[ {\begin{array}{*{20}{c}} {{{\left( {\frac{{\partial {f_1}}}{{\partial {x_1}}}} \right)}^{(k)}}}&{{{\left( {\frac{{\partial {f_1}}}{{\partial {x_{2}}}}} \right)}^{(k)}}}& \cdots &{{{\left( {\frac{{\partial {f_1}}}{{\partial {x_n}}}} \right)}^{(k)}}}\\ {{{\left( {\frac{{\partial {f_2}}}{{\partial {x_1}}}} \right)}^{(k)}}}&{{{\left( {\frac{{\partial {f_2}}}{{\partial {x_{2}}}}} \right)}^{(k)}}}& \cdots &{{{\left( {\frac{{\partial {f_2}}}{{\partial {x_n}}}} \right)}^{(k)}}}\\ \vdots & \vdots & \ddots & \vdots \\ {{{\left( {\frac{{\partial {f_n}}}{{\partial {x_1}}}} \right)}^{(k)}}}&{{{\left( {\frac{{\partial {f_n}}}{{\partial {x_{2}}}}} \right)}^{(k)}}}& \cdots &{{{\left( {\frac{{\partial {f_n}}}{{\partial {x_n}}}} \right)}^{(k)}}} \end{array}} \right]$

Algoritmo do Método de Newton

1. Fazer o contador de iterações $k$ igual a zero. Definir a tolerância $\epsilon$. Assumir valores iniciais das variáveis $X^{(k=0)}$.

2. Avaliar $\small { F }^{(k)}$ e $\small { \nabla F }^{(k)}$. Calcular $\small X^{(k + 1)}$ da seguinte forma:

   $\small X^{(k + 1)} = X^{(k)} - \left({ { \nabla F }^{(k)} } \right)^{-1} { F } ^{(k)}$

3. 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)}$. Caso contrário, fazer $\small k \rightarrow k + 1$, ir para o Passo 2.

Otimização em Sistemas de Energia Elétrica

Departamento de Engenharia Elétrica