Aplicação de Métodos Determinísticos (Outubro 2017)

...

O método de Newton Modificado difere do método de Newton pela minimização do "passo" dado a cada iteração, garantindo uma diminuição monotônica da função objetivo. Ou seja, uma variável, que decresce a cada iteração, determina o tamanho do "passo" dado.

Assim como o método Gradiente, caso o ponto inicial não esteja na bacia de atração do ponto x ótimo, o método converge para um mínimo local ou não converge.

- Função teste 1, (n = 2):

[pic 6]

x* = 1 ; f(x*) = 0

[pic 7]

Figura 5 Newton Modificado n=2 Console

[pic 8]

Figura 6 Newton Modificado n=2 Gráfico

A execução do algoritmo Newton Modificado para a Função Teste da questão 1 convergiu como esperado para n=2, o x ótimo seria x* = 1. O valor encontrado foi x* = [0.9999 09997], bem próximo ao esperado. A função neste ponto resultou f (x*)=0 como esperado.

- Função teste 1, (n =4):

[pic 9]

x* = 1 ; f(x*) = 0

[pic 10]

Figura 7 - Newton Modificado n=4 Console

[pic 11]

Figura 8 - Newton Modificado n=4 Gráfico

Já para n=4 o algoritmo não convergiu como esperado. Na função teste, o x ótimo seria x* = 1. No entanto encontramos o valor de x* = [-0.6705 0.4617 0.2206 0.0492]. O algoritmo parou no critério máximo de parada, número de interações igual a 1000. E pela Figura 7, podemos ver que o Algoritmo ficou travado logo na quarta interação.

-

Família de Broyden (Método BFGS)

Os métodos que formam a Família de Broyden são os métodos de Algoritmo quase-newton. O método Broyden-Fletcher-Goldfarb-Schanno (BFGS) é um dos métodos mais eficientes dessa família. Esses métodos utilizam uma regra recursiva para a construção de uma matriz H correspondente ao inverso da Hessiana da função objetivo. Dessa forma, a função objetivo precisa ter apenas derivada primeira não necessita ser duas vezes diferenciável, como o método de Newton e Newton Modificado. Utiliza uma correção de posto própria, a CBFGS e uma correção genérica. Essa correção atualiza a matriz H a cada iteração. O método BFGS converge da mesma forma que o método Gradiente.

- Função teste 1, (n=2):

[pic 12]

x* = 1; f(x*) = 0

[pic 13]

Figura 9 - FBroyden n=2 Console

[pic 14]

Figura 10 - FBroyden n=2 Gráfico

A execução do Algoritmo BFGS para a Função Teste da questão 1 com n=2 convergiu como o esperado. Como dado na função teste, o x ótimo seria x* = 1. Encontramos o valor de x*=[+0.9998 +0.9997], um valor muito próximo ao valor ótimo. A função nesse ponto resultou em f (x*)=0, valor igual ao valor ótimo dado.

- Função teste 1, (n=4):

[pic 15]

x* = 1 ; f(x*) = 0

[pic 16]

Figura 11 - FBroyden FT1 n=4 Console

[pic 17]

Figura 12 - FBroyden FT1 n=4 Gráfico

A execução do Algoritmo BFGS para a Função Teste da questão 1 com n=4 convergiu como o esperado. Como dado na função teste, o x ótimo seria x* = 1. Encontramos o valor de x*=[+0.9999 +0.9998 +0.9996 +0.9991], um valor muito próximo ao valor ótimo. A função nesse ponto resultou em f (x*)=0, valor igual ao valor ótimo dado.

-

Gradientes Conjugados

- Função teste 1, (n=2):

[pic 18]

x* = 1; f(x*) = 0

O método de otimização conhecido como Gradientes Conjugados foi desenvolvido inicialmente na década de 1950 para a solução de sistemas de equações lineares, e ainda é um dos métodos mais utilizados para a solução de sistemas com matrizes esparsas.

Em 1964, Fletcher e Reeves generalizaram o método para resolver problemas de otimização não linear irrestrita com funções não quadráticas.

[pic 19]

Figura 13 - Gradientes Conjugados n=2 Console

[pic 20]

Figura 14 - Gradientes Conjugados n=2 Gráfico

A execução do Algoritmo Gradientes Conjugados para a Função Teste da questão 1 com n=2 convergiu como o esperado. Como dado na função teste, o x ótimo seria x* = 1. Encontramos o valor de x*=[+0.9995 +0.9991], um valor muito próximo ao valor ótimo. A função nesse ponto resultou em f (x*)=0, valor igual ao valor ótimo dado.

- Função teste 1, (n=4):

[pic 21]

x* = 1 ; f(x*) = 0

[pic 22]

Figura 14 - Gradientes Conjugados n=4 Console

[pic 23]

Figura 15 - Gradientes Conjugados n=4 Gráfico

A execução do Algoritmo Gradientes Conjugados para a Função Teste da questão 1 com n=4 convergiu como o esperado. Como dado na função teste, o x ótimo seria x* = 1. Encontramos o valor de x*=[+0.9998 +0.9996 +0.9991 +0.9992], um valor muito próximo ao valor ótimo. A função nesse ponto resultou em f (x*)=0, valor igual ao valor ótimo dado.

Consolidação dos resultados

Gradiente

Newton Modificado

BFGS

Gradiente