Otimização/Método de gradientes conjugados
Algumas considerações históricas
editar- 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
editarEste 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-
Este é um conjunto convexo, pois todo segmento com extremidades no conjunto está totalmente contido no conjunto.
-
Este é um conjunto côncavo, pois existe um segmento com extremidades no conjunto que não está totalmente contido no conjunto.
- 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:
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
editarSeja 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
editarPrimeiro 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
editarConsidere 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
editarAbaixo é 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 já 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
editarUm 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
Um dos autores deste material sugeriu a adição de uma implementação do algoritmo acima em SciLab. |
Algoritmo de Polak-Ribière
editarUm 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
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
editarPara 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:
Implementar a regra de Armijo e corrigir o esboço acima. |