- 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.
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.
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.
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.
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
.

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

Mas
implica que
, logo

e consequentemente

Donde
. Portanto
.
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.
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
.
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
.
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:
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 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
|
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
|
Um dos autores deste material sugeriu a adição de uma implementação do algoritmo acima em SciLab.
|
|
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
|
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.
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:



|
Implementar a regra de Armijo e corrigir o esboço acima.
|