Algoritmo de Gradiente

1

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

T3-13/05/2015: .

Introdução

No caso de um problema de otimização irrestrito, ele é um critério que engloba de maneira mais geral um cálculo matemático de otimização, o objetivo deste trabalho é justamente avaliar o desempenho de dois métodos básicos, o método de busca de direções aleatórias e o método de gradiente, na busca do mínimo local de uma função dentro da bacia de atração da análise.

Metodologia

O algoritmo de otimização desenhado foi feito na plataforma “MATLAB”, sendo a função objetivo para o problema proposto na página 13 da unidade 5 das notas de aula, como expressa a equação (1).

f ( x )=2 x12+x2

2+2 x1 x2+x1−2 x2+3 eq. [1]

Deve-se obter o valor das variáveis {x} rsub {1 } e {x} rsub {2 } para que a expressão da equação [1] seja o mínimo, sem ter restrições para o valor das variáveis, sendo o ponto inicial em [-1 1].

O processo seguido para programação dos algoritmos de busca de direções e de gradiente foram feitos com base nos passos descritos para cada um deles nas notas de aula mencionados.

a. Algoritmo de busca de direções

A partir do desenho especificado para este algoritmo o qual descreve-se no fluxograma 1, deu-se o início para o desenho das rutinas e sub-rotinas propícias para o casso.

Para obter uma ordem e organização no processo de programação, o caminho seguido foi através do desenho de funções, as quais podem

Maio de 2015

2


ser requeridas como uma sub-rotina por qualquer um dos algoritmos em caso de ser precisados.

Fluxograma 1

Critério de parada: Para a definição do critério de parada, existem três opções as quais se descrevem nas notas de aula no capitulo cinco, sendo considerado para o caso particular o método de aproximação do valor da função objetivo, considerando sempre que as últimas seis iterações não variam mais do 0,0001 respeito da diferença do máximo e mínimo ocorrido durante todo o algoritmo, sendo deste modo executado no critério de fim do anel fechado.

Direção de busca: Para estabelecer o critério de direção de busca, considere-se um vetor de n componentes aleatórios com uma distribuição gaussiana entre zero e um, como dita a norma do algoritmo, sendo para o casso específico um vetor dk=[2,1], já que a

Maio de 2015

[Capte la atención de los lectores mediante una

Xk+1=xk + α·dk

Arg. mínimo de α

α = argmin(f(xk) + α·dk)

Direção de busca dk

Definição da função e dados inicias

Critério de parada

3


função objetivo tem duas variáveis, é importante compreender que para cada um dos ciclos de cálculo gerado é preciso a avalição do novo vetor de direção “dk”.

Constante alpha (α): Um valor que requere um trabalho mais profundo é o escalar “α”, já que junto com a direção “dk”, vão estabelecer o estimativo de crescimento da variável x para cada iteração.O processo de obtenção de “α”, é feito através da função “secaurea()”, a qual vai ser descrita independentemente no Anexo 1, considerando que também vai ser útil no algoritmo de gradiente.

Cálculo do vetor das variáveis: É compreendido que para cada ciclo de execução do anel condicional “while” o vetor das variáveis “xk” vai ter um novo valor otimizado respeito ao seu predecessor, sendo por isso importante armazenar todos os valores gerados, os quais só podemos obter no passo final do algoritmo sendo matematicamente obtido por a equação (2).

xk+1=xk+α ∙ dk eq. [2]

Como se observa na expressão (2), o valor de xk+1 depende diretamente dos valores prévios calculados xk yα ∙d k, o que faz obvio que tem que ser a linha final dentro do algoritmo e a qual var armazenar o valor de x¿.

A função gerada para o algoritmo de busca de direções está expressa em (3).

[xstar,iter]=minbusqueda(f,x,a,b) [3]

Onde cada um dos termos expressos na função é descrito do seguinte modo.

xstar: Vetor que contém a variável para qual a função vai dar o mínimo valor dela.

iter: Escalar que faz o conta do número de repetições requeridas pela função “minbusqueda” foram necessárias para que o algoritmo converge-se ao mínimo local, com o mínimo erro expressado no critério de parada.

Maio de 2015

4


Função f: Função objetivo a qual é o tema de nosso analise. x: Ponto inicial pertencente aos números reais que fica dentro da

bacia de atração condição de existência do algoritmo. a e b: São os limites para o condição “α” que é responsável por gerar

o novo vetor xk.b. Algoritmo do gradiente: O segundo método desenhado para a

determinação do mínimo local da função dentro da bacia de atração em estudo foi o algoritmo do gradiente, o qual difere do algoritmo de busca, só na maneira em que define o valor do vetor “dk” que, neste casso vai ser o vetor gradiente da função objetivo, o qual é calculado por a expressão “gradiente( )” que é uma sub-rotina exclusivamente desenhada para avaliar iterativamente a derivada parcial da função objeto do analises, o algoritmo do gradiente é descrito no Anexo 1.

No processo de fluxo de programação para o algoritmo de gradiente tem que seguir uma sequência similar ao algoritmo de busca de direções aleatória, no fluxograma 2, tem um detalhe onde pode-se apreciar a diferença no ponto de cálculo da direção “dk”.

Fluxograma 2

Maio de 2015

Xk+1=xk + α·dk

Arg. mínimo de α

α = argmin(f(xk) + α·dk)

dk= - gradiente gk(f(·),xk)

Definição da função e dados inicias

Critério de parada

5


Sendo “dk” o negativo do valor do gradiente, calculado por meio da função “gradiente ()”, a qual expressa a direção de decrescimento da função objetivo que neste casso é de ordem dois.

Mantendo a similitude com o algoritmo de busca, procedesse com a determinação do novo “xk”, que vai depender diretamente do seu valor “k-1” somado uma constante “α·dk”.

Finalmente precisa-se determinar a função objetivo para cada uma das iterações, lembrando que seu valor vai ser o critério de parada para a expressão “while” até obter o mínimo erro estabelecido como limite do cálculo.

A função desenhada para o método do gradiente expressasse em (4).

[xstar,iter]=mingrad(f,x,a,b) [4]

Onde:

xstar: Vetor que contém a variável para qual a função f(x), expressa seu mínimo valor.

iter: Escalar que faz o conta do número de repetições requeridas pela função “mingrad” foram necessárias para que o algoritmo convergirá ao mínimo local, dentro do mínimo erro expressado no critério de parada.

Função f: Função objetivo o qual é o tema de analises. x: Ponto inicial pertencente aos números reais que fica dentro da

bacia de atração condição de existência do algoritmo. a e b: São os limites para o condição “α” que é responsável por gerar

o novo vetor xk.

Resultados

i) Algoritmo de busca de direções aleatórias: Executada a função com os dados requeridos que são os expressados na tabela 1. E após o tempo que preciso o computador para convergir a uma resposta satisfatória se obtiveram os valores expressados na tabela 2. Para otimizar a função expressa na equação (1) por meio do da função “minbusqueda(f,x,a,b)”.

Maio de 2015

6


Valores iniciais da função “minbusqueda(f,x,a,b)”x1 x2 a b-2 2 0 10

Tabela 1Valores iniciais algoritmo de busca aleatória

Valores resposta da função “minbusqueda(f,x,a,b)”xsatar iterações

-1.4817 2.4720 334760

Tabela 1Valores finares algoritmo de busca aleatória

ii) Algoritmo de gradiente: Executada a função com os dados requeridos que são os expressados na tabela 3. E após de o tempo que preciso o computador para convergir a uma resposta satisfatória se obtiveram os valores expressados na tabela 4. Para otimizar a função expressa na equação (1) por meio do da função “mingrad(f,x,a,b)”.

iii)

Valores iniciais da função “mingrad(f,x,a,b)”x1 x2 a b-2 2 0 10

Tabela 3Valores iniciais algoritmo de gradiente

Valores resposta da função “mingrad(f,x,a,b)”xsatar iterações

-1.4779 2.3874 11224

Tabela 4Valores finares algoritmo de gradiente

Maio de 2015

7


Maio de 2015

8


Análises dos resultados

Uma vez culminada a execução dos algoritmos, obtiveram-se os gráficos de convergência de cada um deles (anexo 2), sendo as respostas obtidas motivo de análise.

Chama à atenção que o algoritmo de busca de direções consume um maior custo computacional, sendo o mesmo valor de limite de erro para os dois estabelecido em 0.00001.

O algoritmo de gradiente converge muito mais rápido que o algoritmo de busca de direções, mas a precisão do método de busca foi mais confiável já que, pôr o método analítico sabe-se que o mínimo da função está no ponto xal=[-1.5 2.5].

Avaliando um erro relativo para cada um dos algoritmos aplicando a equação [5], obteve-se o expressado na tabela 3.

Er=xal−xstar

xal× 100 [5]

ERRO RELATIVOAlgoritmo de busca Algoritmo de gradiente

Er=[1.22 %1.12 % ] Er=[1.47 % 4.5 % ]

Tabela 3Erro relativo dos algoritmos

Se além disso consideramos que uma relação entre o número de iterações requerido por os algoritmos, pode ser descrito percentualmente por um 2900% maior o para o algoritmo de busca de direções, em outras palavras, a execução do algoritmo de busca de direções precisa 2900% mais iterações que o algoritmo de gradiente, o que claramente é um custo computacional muito maior.

Maio de 2015

9


Dos gráficos de convergência dos algoritmos pode-se observar que o gradiente tem uma naturaliza de estabilidade e, a busca de direções tem uma naturaliza que tende à instabilidade.

Conclusões

Analisando os dados obtidos, é possível concluir que, o algoritmo de gradiente pode se considerar com maior eficiência, já que não só deve-se analisar o erro de convergência, além disso é importante observar o tempo e custo computacional, que não justifica pois para uma diferencia muito considerável de iterações, não entrega uma resposta de erro dentro do mesmo contexto.

Se o critério do otimizador é procurar o menor erro possível, teria que tomar como solução o algoritmo de busca aleatória conseguindo seu objetivo com o sacrifico de tempo e trabalho.

Pode-se compreender que a decisão sobre o melhor algoritmo é subjetiva, e só quando o otimizador defina globalmente os requerimentos do problema poderá tomar a decisão mais acertada.

Considerando que nem sempre o maior número de iterações chega na melhor resposta já que pode cair no casso que o ponto flutuante do computador gere um erro adicional, pode-se estabelecer que na maioria dos casos o algoritmo de gradiente será mais confiável.

Maio de 2015

10


Anexo 1

Função gradiente

function [ gk ] = gradiente( f,X)

delta=0.0001;[row,~]=size(argnames(f));e=eye(row);

for i=1:row-1 for j=1:rowgk(j,i)=(f(X(i)+delta*e(i,j),X(i+1)+delta*e(i+1,j))-f(X(i),X(i+1)))/delta; endendend

Função seção áurea

function [alpha,a1,b1] = secaurea( f,a1,b1,GK,X )i=0;alphaa=b1-0.618*(b1-a1);alphab=a1+0.618*(b1-a1);fa=f(X(1)+alphaa*GK(1),X(2)+alphaa*GK(2));fb=f(X(1)+alphab*GK(1),X(2)+alphab*GK(2));while (b1-a1)>0.0001 if fa<fb b1=alphab; alphab=alphaa; alphaa=b1-0.618*(b1-a1); fb=fa; fa=f(X(1)+alphaa*GK(1),X(2)+alphaa*GK(2)); else a1=alphaa; alphaa=alphab; alphab=a1+0.618*(b1-a1); fa=fb; fb=f(X(1)+alphab*GK(1),X(2)+alphab*GK(2)); endi=i+1; endalpha=(a1+b1)/2;end

Maio de 2015

11


Anexo 2

0 2000 4000 6000 8000 10000 12000-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

iterações

f(x)

Gráfico 1Convergência do algoritmo do gradiente

0 0.5 1 1.5 2 2.5 3 3.5

x 105

-0.5

0

0.5

1

1.5

2

2.5

3

3.5

4x 10

11

iterações

f(x)

Gráfico 2Convergência do algoritmo de busca de seção aleatória

Maio de 2015

12


Anexo 3

Algoritmo de busca de direções aleatórias

function [ xstar,iter ] = minbusqueda( f,x,a,b )parada=0;k=1;X=x(k,:)F(k)=f(X(1),X(2));a1=a;b1=b;[row,~]=size(argnames(f)); while parada==0; dk=rand(row,1); [alpha,a1,b1]=secaurea(f,a1,b1,dk,X); k=k+1; x(k,:)=x(k-1,:)'+alpha*dk; X=x(k,:); F(k)=f(X(1),X(2)); Fxmax=max(F); [Fxmin,xstar]=min(F); deltaF=Fxmax-Fxmin; if k>5 F5=[F(k);F(k-1);F(k-2);F(k-3);F(k-4);F(k-5)]; EF1=max(F5)-min(F5); if EF1<0.00001*deltaF' parada=1; end end end[fila,coluna]=size(x)x(xstar,:)plot(F);iter=k; end

Maio de 2015

13


Algoritmo de busca de gradiente

function [ xstar,iter ] = mingrad( f,x,a,b ) parada=0;k=1;X=x(k,:)F(k)=f(X(1),X(2));a1=a;b1=b; while parada==0; gk(:,k)=gradiente(f,X); GK=gk(:,k); dk=-GK; [alpha,a1,b1]=secaurea(f,a1,b1,GK,X); k=k+1; x(k,:)=x(k-1,:)'+alpha*dk; X=x(k,:); F(k)=f(X(1),X(2)); Fxmax=max(F); [Fxmin,xstar]=min(F); deltaF=Fxmax-Fxmin; if k>5 F5=[F(k);F(k-1);F(k-2);F(k-3);F(k-4);F(k-5)]; EF1=max(F5)-min(F5); if EF1<0.000001*deltaF' parada=1; end end end x(xstar,:)plot(F);iter=k; end

Maio de 2015

Documents

Algoritmo de Gradiente