Otimização/Método de gradientes conjugados

Origem: Wikilivros, livros abertos por um mundo aberto.
Saltar para a navegação Saltar para a pesquisa


Wikipedia
A Wikipédia tem mais sobre este assunto:
Método do gradiente conjugado

Algumas considerações históricas[editar | editar código-fonte]

  • Este método foi originalmente proposto por Hestenes e Stiefel, em 1952.
  • Seu objetivo inicial foi a resolução de problemas quadráticos sem restrições, mas logo o mesmo foi estendido para casos mais gerais.

O método[editar | editar código-fonte]

Este método pode ser considerado sob dois pontos de vista:

  • Como um método de descida, com busca linear exata;
  • Como um método de resolução de sistema linear, baseado em um processo de ortogonalização.
Definição

Um conjunto não vazio é dito convexo quando e vale

Exemplos de conjuntos convexos e côncavos[editar | editar código-fonte]


Definição

Uma função é dita convexa quando é convexo e e vale

Definição

Dado um conjunto convexo , uma função é dita fortemente convexa quando existe uma constante tal que é convexa.

Exercício

Verifique que uma função quadrática é fortemente convexa se existe uma matriz simétrica definida positiva , um vetor e um escalar de modo que .

Resolução
Sendo uma função quadrática, tem-se . A matriz pode ser suposta simétrica, pois caso não seja, toma-se (simétrica), e segue (verifique).

Além disso, se é uma função fortemente convexa, então é estritamente convexa. Como é duas vezes diferenciável (por ser uma função quadrática), a convexidade estrita implica que é definida positiva.


Nota: Uma matriz é definida positiva se, e somente se, todos os seus autovalores são positivos.

Tem-se:

Sendo , segue em particular que e , onde é uma matriz diagonal cujos elementos da diagonal são os autovalores de e é uma matriz onde as colunas são os autovetores correspondentes aos autovalores.

Note que é uma matriz simétrica, pois é a matriz Hessiana de uma função com segundas derivadas parciais contínuas, e consequentemente vale .

Para introduzir o método de direções conjugadas, serão consideradas somente funções quadráticas.

Uma condição necessária de primeira ordem para que seja um ponto de mínimo para a função é que . Para o presente caso, a função é convexa, então, a condição necessária também é suficiente.

Exercício

Prove que se é uma matriz simétrica definida positiva, então dada por possui um único ponto de mínimo.

Resolução
Uma vez que é simétrica definida positiva, a função é fortemente convexa. Mas toda função fortemente convexa, definida em um conjunto fechado não vazio possui um único minimizador, pois:
  • Os conjuntos de nível de uma função fortemente convexa são compactos;
  • Toda função contínua definida em um compacto tem algum minimizador (pelo teorema de Weierstrass);
  • Os minimizadores de uma função convexa são globais;
  • Funções fortemente convexas não podem ter mais de um minimizador.

Em particular, possui um único ponto de mínimo.

No caso de uma função quadrática, tem-se , ou seja, é solução do sistema linear .

A resolução de um sistema linear nem sempre pode ser feita numericamente de forma eficiente. Por exemplo, se a matriz do sistema é:

A solução do sistema linear corresponde à interseção entre duas retas quase paralelas, e os erros de truncamento podem causar imprecisão na solução obtida computacionalmente.

Analiticamente, o sistema tem como solução. Então alguém poderia se perguntar: qual o problema em resolver esse sistema linear, se basta calcular a inversa da matriz e multiplicar pelo vetor ? A resposta é que o calculo da inversa de uma matriz em geral é impraticável computacionalmente, por ter custo muito alto. Por isso, nas situações práticas, onde as matrizes tem ordem bem maior do que 2 (digamos 1000), o cálculo de matrizes inversas não é uma opção.

Assim, com o intuito de desenvolver um método computacional para o cálculo de minimizadores, é preciso utilizar outras técnicas. Considere o seguinte:

Em um método de descida tem-se sempre uma sequencia , com e é um minimizador de

e

Logo, e multiplicando por obtem-se . Consequentemente, o valor de é dado por

Deste modo, o método consistirá de escolher em cada etapa uma direção , e calcular o coeficiente pela fórmula anterior, para gerar o próximo ponto . Mas como escolher a direção ?

Dado e escolhido , defina como , ou seja, é a restrição da função à reta que passa pelo ponto e que tem direção . Logo, derivando a expressão de em relação a , obtem-se

Então, no ponto de mínimo, , tem-se

Ou seja, a direção a ser seguida a partir do ponto é ortogonal ao gradiente da função , no ponto .

Esquema do método de descida[editar | editar código-fonte]

Seja o minimizador da função . Tem-se

Mas implica que , logo

e consequentemente

Donde . Portanto .

Exercício

Provar que se é uma matriz simétrica, definida positiva, então existe uma matriz simétrica , de modo que

Resolução
Sendo uma matriz simétrica, tem-se , com unitária e

Logo

Usando o resultado desse exercício, tem-se ainda que

Fazendo , o método do gradiente conjugado escolhe as direções de descida tais que . Mas quando , tem-se na expressão apresentada anteriormente apenas

Finalmente, tem-se o algoritmo para este método.

Algoritmo de Hestenes-Stiefel[editar | editar código-fonte]

Uma comparação da convergência do método de descida do gradiente com tamanho de passo ótimo (em verde) e o método do gradiente conjugado (em vermelho) para a minimização da forma quadrática com um sistema linear dado. O gradiente conjugado, assumindo aritmética exata, converge em no máximo n passos onde n é o tamanho da matriz do sistema (no exemplo, n=2).
Primeiro passo: Escolha 
  Se , então pare: 
  Senão: 
  Calcular 
  


Passo iterativo : Dado 
  Se , então pare: 
  Senão: 
  
  

Pode-se verificar facilmente que . De fato, como , tem-se . Logo, .

Exercício

Provar que se então .

Resolução
Tem-se

Multiplicando ambos os membros por , e trocando de lugar com resulta:

,

ou seja,

,

somando em ambos os lados, segue que

,

Então

Sendo a última igualdade devida ao fato de para .



Exemplos[editar | editar código-fonte]

Considere definida por . Em outros termos, tomando , tem-se , onde .

Pode-se aplicar o método de direções conjugadas ao seguinte problema

Note, desde já, que o conjunto solução é .

Inicio
  • Toma-se arbitrário, por exemplo, .
  • Avalia-se o gradiente da função neste ponto inicial:
Iteração 1

A seguir, verifica-se se o gradiente se anula no novo ponto :

Como o gradiente já é nulo, não é preciso fazer a segunda iteração, e o ponto é o (único) minimizador global de .


Em um caso mais geral, considerando definida por , tem-se cálculos muito parecidos em cada passo.

O conjunto solução continua sendo .

Inicio
  • Considere como no primeiro exemplo, ou seja, .
  • Avalia-se o gradiente da função neste ponto inicial:
Iteração 1

A seguir, verifica-se se o gradiente se anula no novo ponto :

Novamente, o gradiente se anula já na primeira iteração, de modo que é o minimizador global de .


Exercício

Seja uma matriz simétrica definida positiva, cujos autovalores são todos iguais. Então começando de qualquer ponto , o método fornece como solução.

Um terceiro exemplo pode ser dado tomando e definida por . Observe que tal matriz é simétrica e definida positiva:

Logo, os autovalores de são e . Isso também implica que a função é fortemente convexa.

Aplicando o método:

Início
  • Toma-se um ponto arbitrário no plano, por exemplo ;
  • Verifica-se se tal ponto é o minimizador global, avaliando nele o gradiente da função:
.
  • Já que o gradiente não se anulou no chute inicial, é preciso escolher uma direção e um comprimento de passo para determinar a próxima aproximação:
Iteração 1

Feitos esses cálculos, o próximo ponto é dado por

Para saber se será necessária uma nova iteração, ou se o minimizador foi encontrado, calcula-se o gradiente da função no ponto:

.

Novamente, será preciso calcular uma nova direção e um novo comprimento de passo:

Iteração 2

onde , no algoritmo de Hestenes é dado por:

Portanto

Além disso, o tamanho do passo é dado por

Portanto

Obviamente, este é o minimizador procurado (pois o método tem a propriedade de convergência quadrática, ou seja utiliza no máximo iterações para chegar a solução quando aplicado a funções quadráticas definidas em )

Exercício

Implementar o algoritmo de Hestenes-Stiefel em alguma linguagem de programação, por exemplo em Scilab, ou Matlab.

Exercício

Seja um função quadrática fortemente convexa. Verifique as seguintes igualdades:

Implementação em Scilab[editar | editar código-fonte]

Abaixo é apresentada uma implementação deste algoritmo na linguagem de programação utilizada pelo Scilab.

A = [2 1; 1 2];

function [x] = min_gradiente_conjugado(xk)
  //Entrada: xk em R^n, qualquer "chute inicial"
  //  Saída: x, o ponto em que f assume o valor mínimo
  
  k        = 0        //Indica quantos loops  foram feitos
  epsilon  = 0.01
  n        = size(xk,1)
  g        = df(xk)
  seq      = zeros(n,n+1)
  seq(:,1) = xk
  while (norm(g) > epsilon) & (k <= n)
    if (k == 0)
      d = -g
    else
      d = Hestenes(g,d,A)
    end
    t  = busca_linear(g,d,A)
    xk = xk + t*d
    k  = k+1
    seq(:,k+1) = xk
    g  = df(xk)
  end
  plot(seq(1,:),seq(2,:))
  x = xk  
endfunction


function [fu] = f(u)
  fu=(1/2)*(u'*A*u)
endfunction


function [grf] = df(u)
  grf = A*u
endfunction


function [d] = Hestenes(g,d,A)
  d=-g + ((g'*A*d)/(d'*A*d))*d
endfunction


function [t] = busca_linear(g,d,A)
  t=(g'*g)/(d'*A*d)
endfunction

Para facilitar a compreensão do método, pode ser útil exibir as curvas de nível da função. Uma forma de implementar uma função com esse propósito é a seguinte:

function plotar_curvas
  qtd=101
  tam=max(seq)
  x=linspace(-tam,tam,qtd)
  y=x
  z=zeros(qtd,qtd)
  for i=1:qtd
    for j=1:qtd
      z(i,j)=f([x(i);y(j)])
    end
  end
  contour2d(x,y,z,10)
  a=gca();
  a.x_location = "middle"; 
  a.y_location = "middle"; 
endfunction

Algoritmo de Fletcher-Reeves[editar | editar código-fonte]

Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem para ilustrar o método de Fletcher-Reeves.


Esta versão é na verdade uma extensão do algoritmo anterior, permitindo a aplicação no caso de funções que não são quadráticas.

Primeiro passo: Escolha 
 Se , então pare: 
 Senão:  (como em todo método de descida)
 Calcular , através de uma busca linear
 
Passo iterativo:
 Se , então pare: 
 Senão: 
 Calcular , através de uma busca linear
 
 


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma implementação do algoritmo acima em SciLab.

Algoritmo de Polak-Ribière[editar | editar código-fonte]

Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem para ilustrar o método de Fletcher-Reeves.

Uma outra versão é a seguinte:

Primeiro passo: Tomar 
 Se , então pare: 
 Senão:  (como em todo método de descida)
 Calcular , através de uma busca linear
 
 
Passo iterativo:
 Se , então pare: 
 Senão: 
 Calcular , através de uma busca linear
 
 


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma implementação do algoritmo acima em SciLab.
Exercício

Verificar que, no caso de uma função quadrática e fortemente convexa, os algoritmos de Hestenes-Stiefel, de Fletcher-Reeves e de Polak-Ribière são os mesmos.

Exercício

Seja . Implemente o método de gradientes conjugados, e utilize o algoritmo para determinar o ponto de mínimo da função . Note que o espaço é unidimensional, então o método de gradientes conjugados reduz-se ao método dos gradientes, com primeira direção . Observe ainda que é uma função coerciva fortemente convexa.

Algoritmo auxiliar[editar | editar código-fonte]

Para o caso de funções não quadráticas, é preciso usar algum método de busca linear para a implementação do método dos gradientes conjugados, seja a versão de Fletcher-Reeves ou a de Polak-Ribière. Uma possibilidade é a busca de linear de Armijo (ver Izmailov & Solodov (2007), vol 2, pag. 65), cujo algoritmo é esboçado a seguir:

function busca_linear_Armijo (f, theta, alpha, delta, t0)
  while (alpha * pred > ared)
    t = d * t
  end
endfunction

com:


Crystal Clear app kaddressbook.png Implementar a regra de Armijo e corrigir o esboço acima.