Trabalho Otimizacao

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

i 
 
Sumário 
Sumário ................................................................................................................................................ 1 
Capítulo 1 ............................................................................................................................................ 2 
Capítulo 2 ............................................................................................................................................ 3 
Capítulo 3 ....................................................................................................................................... 155 
Capítulo 4 ......................................................................................................................................... 18 
Capítulo 5 ......................................................................................................................................... 20 
 
 
 
 
 
 
2 
 
Capítulo 1 
Introdução 
O Trabalho 3 visa estudar a otimização em problemas não lineares com restrição. 
Em que cada aluno explorará o comportamento de um método. Aqui será trata o método 
elipsoidal e as duas variantes do método, Lagrangea e Atrator. As três variantes do 
método elipsoidal (original, deep-cut Rodney-Takahashi, deep-cut Douglas-Adriano). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3 
 
Capítulo 2 
Estudo de funções de 2 dimensões partindo do mesmo 
ponto inicial 
2.1.1 Função 1: 
Função quadrática com restrições lineares 
Código: fdemonst.m 
 
% Quadract function 
% Objective function 
 fx = (x(1,:)- 1).^2 + (x(2,:)- 1).^2; 
 dfx = [2*(x(1)-1); 2*(x(2)-1)]; 
% Contraints (g1(x) <= 0) 
 gx(1,:) = x(1,:) + x(2,:) - 1; 
 dgx(1,1) = 1; 
 dgx(2,1) = 1; 
% Contraints (g2(x) <= 0) 
 gx(2,:) = x(1,:) - x(2,:) - 1; 
 
 
Figura 1 - Função objetivo e restrições para a Função 1 
 
2.1.2 Função 2: 
Problema de Rosen e Suzuki 
Código: pb_rosensuzuki_convexa.m 
 
 
 
4 
 
 
Figura 2 - Função objetivo e restrições para a Função 2 
2.1.3 Função 3: 
Função quadrática com restrições quadráticas 
Código: fquadx.m 
 
% Objective function 
 fx = (x(1,:)- 2).^2 + (x(2,:)- 2).^2; 
 dfx = [2*(x(1)-2); 2*(x(2)-2)]; 
 % Contraints (g1(x) <= 0) 
gx(1,:) = x(1,:) .^ 2 + 4 * x(2,:) .^ 2 - 1; 
dgx(1,1) = 2*x(1,1); 
 dgx(2,1) = 8*x(2,1); 
 % Contraints (g2(x) <= 0) 
 gx(2,:) = (x(1,:)-2) .^ 2 + 4 * x(2,:) .^ 2 - 1; 
 dgx(1,2) = 2*x(1,1)-2; 
 dgx(2,2) = 8*x(2,1); 
 
 
Figura 3 - Função objetivo e restrições para a Função 3 
 
2.1.4 Função 4: 
Problema de Svanverg 
Código: fsvanb.m 
 
% Funcao objetivo. 
 fobj = x(1,1)*sqrt(1+x(2,1)^2); 
 
 
 
5 
 
% gradiente função objetivo. 
% f = x(1,1)*sqrt(1+x(2,1)^2); 
 dfobj(1,1) = sqrt(1+x(2,1)^2); 
 dfobj(2,1) = x(1,1)*x(2,1)/sqrt(1+x(2,1)^2); 
 
% Funcões de restricao g(x,1) <= 0.0. 
 gsinal(1,1) = -1; 
 gsinal(2,1) = -1; 
 g(1,1) = 0.124*sqrt(1+x(2,1)^2)*(8/x(1,1)+1/(x(1,1)*x(2,1)))-1; 
 g(2,1) = 0.124*sqrt(1+x(2,1)^2)*(8/x(1,1)-1/(x(1,1)*x(2,1)))-1; 
 
% Funcões de restricao g1(x,1) <= 0.0. 
% g1 = 0.124*sqrt(1+x(2,1)^2)*(8/x(1,1)+1/(x(1,1)*x(2,1)))-1; 
 df1(1,1) =-0.124*sqrt(1+x(2,1)^2)*(8/x(1,1)^2+1/(x(2,1)*x(1,1)^2)); 
 df1(2,1) = 0.124*(x(2,1)*(8/x(1,1)+1/(x(1,1)*x(2,1)))/sqrt(1+x(2,1)^2)- ... 
sqrt(1+x(2,1)^2)/(x(1,1)*x(2,1)^2)); 
 
 
Figura 4 - Função objetivo e restrições para a Função 4 
2.1.5 Função 5: 
 
Função objetivo quadrática com restrições elipsoidais 
Código: fflower.m 
 
Figura 5 - Função objetivo e restrições para a Função 5 
 
2.1.6 Função 6: 
 
Norma distorcida e condicionada com restrições 
 
 
6 
 
Código: ftiltednormcond_rosensuzu.m 
Figura 6 - Função objetivo e restrições para a Função 6 
2.2Resultados para ponto inicial fixo 
 
Nesta seção os métodos são comparados pelo número de iterações, valor final da 
função objetivo e fator final de convergência de Powell. Além destes valores, são 
mostrados os gráficos com o traçado das elipses em cada iteração, evolução da função 
objetivo e evolução do fator de convergência de Powell. Para todas as funções e métodos 
de deep-cut foram usados o ponto inicial x0 = (8,8). 
 
2.1.1 Função 1: 
Função quadrática com restrições lineares 
Código: fdemonst.m 
 
Tabela 1 - Resultados para Função 1, 2 dimensões, x_0 fixo 
 
 
 
 
7 
 
 
Figura 7 - Convergência para Função 1, método original 
 
 
Figura 8 - Convergência para Função 1, deep-cut Rodney-Takahashi 
 
 
Figura 9 - Convergência para Função 1, deep-cut Douglas-Adriano. 
 
 
 
8 
 
 
2.1.2 Função 2: 
Problema de Rosen e Suzuki 
Código: pb_rosensuzuki_convexa.m 
 
Tabela 2 - Resultados para Função 2, 2 dimensões, x_0 fixo 
 
 
 
Figura 10 - Convergência para Função 2, método original 
 
 
Figura 11 - Convergência para Função 2, método deep-cut Rodney-Takahashi 
 
 
 
9 
 
 
Figura 12 - Convergência para Função 2, método deep-cut Douglas-Adriano 
 
2.1.3 Função 3: 
Função quadrática com restrições quadráticas 
Código: fquadx.m 
 
Tabela 3 - Resultados para Função 3, 2 dimensões, x_0 fixo 
 
 
 
Figura 13 - Convergência para Função 3, método original 
 
 
 
10 
 
 
Figura 14 - Convergência para Função 3, método deep-cut Rodney-Takahashi 
 
 
Figura 15 - Convergência para Função 3, método deep-cut Douglas-Adriano 
 
2.1.4 Função 4: 
Problema de Svanverg 
Código: fsvanb.m 
 
Tabela 4 - Resultados para Função 4, 2 dimensões, x_0 fixo 
 
 
 
 
11 
 
 
Figura 16 - Convergência para Função 4, método original 
 
 
Figura 17 - Convergência para Função 4, método deep-cut Rodney-Takahashi 
 
 
Figura 18 - Convergência para Função 4, método deep-cut Douglas-Adriano 
 
2.1.5 Função 5: 
 
 
 
12 
 
Função objetivo quadrática com restrições elipsoidais 
Código: fflower.m 
 
Tabela 5 - Resultados para Função 5, 2 dimensões, x_0 fixo 
 
 
 
Figura 19 - Convergência para Função 5, método original 
 
 
Figura 20 - Convergência para Função 5, método deep-cut Rodney-Takahashi 
 
 
 
13 
 
 
Figura 21 - Convergência para Função 5, método deep-cut Douglas-Adriano 
 
 
2.1.6 Função 6: 
 
Norma distorcida e condicionada com restrições 
Código: ftiltednormcond_rosensuzu.m 
Tabela 6 - Resultados para Função 6, 2 dimensões, x_0 fixo 
 
 
 
Figura 22 - Convergência para Função 6, método original 
 
 
 
14 
 
 
Figura 23 - Convergência para Função 6, método deep-cut Rodney-Takahashi 
 
 
Figura 24 - Convergência para Função 5, método deep-cut Douglas-Adriano 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
15 
 
Capítulo 3 
Estudo do parâmetro s do deep-cut 
Nesta seção foi investigado o efeito do parâmetro s para a realização do método 
deep-cut. Para tal usou-se a função 2 (problema de Rosen-Suzuki com restrições) e o 
método de Rodney-Takahashi com ponto inicial x_0 = (8, 8)T. Foram testados dez 
valores de s indo de 0 até 0,3125, avaliando sua influência no número de iterações, valor 
final da função objetivo e valor final do fator de convergência. Foram registrados os 
gráficos de convergência da função objetivo e do fator de convergência para s = 0, s = 
0,1736 e s = 3,125. 
 
Tabela 7 - Resultados da influência do parâmetro s do deep-cut 
 
 
 
16 
 
 
Figura 25 - Efeito de s nas métricas de interesse a) Número de iterações, b) Valor final do fator de 
convergência de Powell e c) valor final da função objetivo. 
 
 
Figura 26 - Gráficos de convergência para a) s=0, b) s=0,1736 e c) s=0,3125. 
 
 
 
17 
 
 Observa-se que o número de iterações diminui com o aumento de s de forma 
aparentemente linear. O valor final da função objetivo e o fator de convergência não 
apresentam dependência aparente de s. A dependência linear do número de iterações com 
o parâmetro s poderia ser testada para problemas com maior dimensão, porém tal teste não 
foi realizado neste trabalho. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
18 
 
Capítulo
4 
Estudo do aumento da dimensão do problema 
 Foi investigado o efeito do aumento da dimensão n do problema. Para tal usou-se a 
função 2 (problema de Rosen-Suzuki com restrições) para o método original, para o 
deep-cut de Rodney-Takahashi e de Douglas-Adriano ambos com s=1/(n+1,1). Foram 
realizadas 10 execuções para cada dimensão, sendo registrado o número de iterações, 
valor final da função objetivo e valor final do fator de convergência, com ponto inicial 
variando a cada execução. 
 
 
Tabela 8 - Resultado para aumento de dimensão. Número de Iterações 
 
 
 
 
Tabela 9 - Resultado para aumento de dimensão. Valor final da função objetivo 
 
 
 
 
 
 
 
 
 
19 
 
 
Tabela 10 - Resultado para aumento de dimensão. Valor final do fator de convergência de Powell 
 
 
 
 
Figura 27 – Gráfico comparativo do número de iterações em função da dimensão para os três métodos. 
 
 A tabela 9 indica que os três métodos chegaram em torno da mesma solução, com 
o deep-cut de Douglas-Adriano chegando à uma solução ligeiramente pior do que os 
outros dois métodos. A tabela 8 assim como o gráfico da figura 27 mostram que há 
grande diferença na complexidade dos métodos. O método original é sem dúvidas o mais 
lento, com crescimento aparentemente exponencial do número de iterações. O método 
de Rodney-Takahashi se mostra significativamente mais rápido que o original. O método 
que melhor escala com a dimensão do problema é o de Douglas-Adriano, sendo então o 
mais indicado no caso de problemas de alta dimensionalidade. 
 
 
 
 
 
 
 
 
 
20 
 
Capítulo 5 
Conclusão 
 Os experimentos realizados no capítulo 2 deste trabalho indicam que o método 
original seja o mais robusto, sendo capaz de otimizar todos os problemas apresentados, 
enquanto a versão de Douglas-Adriano teve problemas ao otimizar a função 2 e o 
método de Rodney-Takahashi teve problemas ao otimizar a função 4. 
 Os experimentos do capítulo 3 indicam que um aumento do parâmetro s de deep-
cut reduz o número de iterações necessário sem influenciar na qualidade da solução. Os 
experimentos da capítulo 4 indicam que a versão com deep-cut de Douglas-Adriano é a 
mais eficiente, reduzindo consideravelmente o crescimento do número de iterações em 
função da dimensão do problema. 
 Globalmente pode-se notar que o método elipsoidal se baseia em delimitar 
regiões que contém a solução, diminuindo gradualmente essa região até que ela se torne 
apenas a solução. Outra característica observável do método é que a solução encontrada 
é aproximada. Os gráficos de convergência (figuras 8 a 24 e figura 26) indicam que a 
região de busca cerca rapidamente a solução, porém a aproximação da solução é 
assintótica, dando a característica hiperbólica dos gráficos.