Aplicação de Métodos Determinísticos (Outubro 2017)
Por: israeloliveira91 • 18/10/2017 • Trabalho acadêmico • 3.375 Palavras (14 Páginas) • 272 Visualizações
Trabalho Computacional – Aplicação de Métodos Determinísticos (Outubro 2017)
Arthur Canabrava , Israel Oliveira, Marcelo Mota - Universidade Federal de Minas Gerais
Resumo – O ramo da otimização busca encontrar as melhores configurações possíveis para funções problema de todo e qualquer tipo de interesse. A partir de algoritmos e modelos computacionais, consegue-se minimizar funções problema. Os métodos determinísticos são aqueles em se conhece todos os passos a serem dados a partir de uma solução inicial. Em oposição a esse método tem se os métodos aleatórios, em que cada execução do código resulta em uma nova sequência de "passos".
Nesse trabalho analisaremos a execução de métodos determinísticos e aleatórios, para a resolução de funções objetivo previamente conhecidas.
Palavras-chave – Otimização, Métodos Aleatórios, Métodos Determinísticos, Minimização Função Objetivo.
INTRODUÇÃO
Otimização é uma forma a se determinar qual a melhor configuração, melhor solução para um problema, uma função objetivo, em todos os possíveis ramos de interesse na vida de uma pessoa. Para alcançar essa configuração ótima, utiliza-se de métodos computacionais diversos, cada um com uma característica diferenciada.
Esses métodos podem ser divididos em Determinísticos e Aleatórios. Os primeiros sempre levam a mesma resposta a partir de um mesmo ponto inicial. Os segundos geram caminhos aleatórios em cada execução do código, podendo resultar em resultados diferentes.
Serão apresentados nesse trabalho os métodos Gradiente, Newton Modificado, Família Broyden, Hooke-Jeeves, Nelder-Mead Simplex, Amostragem Aleatória e Direções Aleatórias.
Os métodos Gradiente, Newton Modificado e Família Broyden utilizam estratégias baseadas em derivadas. Por esse motivo, para empregar esses métodos a função objetivo precisa ser diferenciável.
Já os Hooke-Jeeves, Nelder-Mead Simplex, Amostragem Aleatória e Direções Aleatórias são métodos independentes de derivadas, não obrigando suas funções objetivo a serem diferenciavéis.
Somente os dois últimos métodos citados são aleatórios. Os métodos restantes são determinísticos.
Também serão apresentados os métodos Penalidade Exterior e Lagrangeano Aumentado. Esses métodos consistem em atualizar a função objetivo para algumas restrições (de igualdade e de desigualdade) que ela possa ter.
Todos os métodos serão mais detalhadamente apresentados e discutidos no decorrer deste trabalho.
implementação em matlab
Todas os métodos foram implementados no programa computacional MATLAB e testados nas funções testes disponíveis.
Questão 1 - Estratégias baseadas em derivadas
Método do Gradiente
O método Gradiente é um método baseado em uma direção de busca. Nele cada novo ponto é obtido a partir de uma busca unidimensional na direção inversa ao gradiente da função objetivo no ponto inicial, essa é a direção na qual a função objetivo decresce mais rapidamente. Como a direção utilizada é o inverso do gradiente, a função objetivo deve ser diferençável. Computacionalmente, o gradiente é calculado a partir de aproximações baseadas em diferenças finitas.
A convergência do método Gradiente depende do ponto inicial. Caso ele não esteja localizado na bacia de atração do ponto x ótimo, o algoritmo converge para um mínimo local ou não converge.
- Função teste 1, (n = 2):
[pic 1]
x* = 1 ; f(x*) = 0
[pic 2]
Figura 1 – Gradiente FT1 n=2 Console
[pic 3]
Figura 2 – Gradiente FT1 n=2 Gráfico
A execução do Algoritmo Gradiente para a Função Teste com n=2 convergiu como o esperado. Como dado na função teste, o x ótimo seria x* = 1. No entanto encontramos o valor de x* = [0.9919 0.9839].
- Função teste 1, (n=4):
[pic 4]
x* = 1 ; f(x*) = 0
Figura 3 – Gradiente FT1 n=4 Console
[pic 5]
Figura 4 - Gradiente FT1 n=4 Gráfico
A execução do Algoritmo Gradiente para a Função Teste 1 com n=4 não convergiu como o esperado. Como dado na função teste, o x ótimo seria x* = 1. No entanto encontramos o valor de x* = . O algoritmo parou no critério máximo de parada, número de interações igual a cinco mil (5000). E pela Figura 4, podemos ver que o Algoritmo ficou travado.
Método do Newton Modificado
O método de Newton Modificado como o próprio nome diz é originado do método de Newton. Esse método considera aproximações quadráticas usando séries de Taylor para definir a direção a ser seguida pelo método, que assim como o método do Gradiente, é um método de Direção de Busca. A direção de busca é baseada no inverso da Hessiana da função objetivo. Logo a função também deve ser diferenciavel.
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.
...