CAPÍTULO 5

EXPERIMENTOS NUMÉRICOS, CONCLUSÕES E RECOMENDAÇÕES

5.1 EXPERIMENTOS NUMÉRICOS

Para analisar o comportamento do algoritmo foram efetuados vários experimentos numéricos. Os testes foram realizados em uma SUN workstation SPARC IPX da UFSC. Os programas foram implementados em linguagem Fortran 77, utilizando precisão dupla.

As funções testes utilizadas foram obtidas em [28]('Testing Unconstrained Optimization', de Moré-Garbow-Hillstron) e em [5] (Testing a Class of Methods for Minimization Problems with Simple Bounds on the Variables', de Conn-Gould-Toint). Entretanto, os testes efetuados por Conn-Gould-Toint eram para problemas de menor dimensão. O número de variáveis consideradas no trabalho desses autores era, no máximo, igual a 45.

Na implementação do algoritmo, os problemas de minimização sem restrições são considerados como caso particular do problema
min f(x)

s.a l(i)<=x(i)<=u(i) ,

considerando-se os limitantes l(i) adequadamente pequenos e os limitantes u(i) suficientemente grandes, para todo i {1,...n}. Foram considerados l(i) = -10⁴ e u(i) = 10⁴, para quaisquer i {1,...,n}.

Na maioria dos casos cada função teste foi utilizada inicialmente para resolver um problema de minimização irrestrita, com aproximações das Hessianas tridiagonais e pentadiagonais. Posteriormente, foram acrescentadas restrições canalizadas e resolvido um problema com restriçoes canalizadas, sendo também utilizadas aproximacões das Hessianas tridiagonais e pentadiagonais. As restrições canalizadas são as mesmas propostas por Conn-Gould-Toint [5]:

-100.0<=x_i<=100.0 , se i é par, sendo x_* o ponto de ótimo obtido no problema sem restrições.

O ponto inicial para o problema com restrições canalizadas é a projeção do ponto inicial do problema de minimização irrestrita na região viável do problema com restrições canalizadas.

Em todos os testes , a aproximação inicial da matriz Hessiana é a matriz Identidade .

Na implementação do algoritmo 2.1 foram definidos os seguintes parâmetros:

,( ),

₁ =₂ = 0.5, alfa= 10^-4, = 1, D_k = I,

10 e 0.5.

O critério principal de parada do algoritmo é que a norma infinito do gradiente da função objetivo projetado na caixa seja menor que 10^-6. Além disso, o número máximo permitido de iterações da subrotina principal do algoritmo é 600, no caso sem restrições, e 300 no caso com restrições. Outro critério adicional de parada é o seguinte:seja x_c a aproximação da solução x na iteração corrente; o programa pára se o raio da região de confiança se torna menor que 10^-16 (que é a tolerância estabelecida para a região de confiança) e, considerando a direção da projeção de -f(x_c) na região viável da iteração corrente, não foi possível obter o decréscimo da função objetivo f estabelecido pela Condição de Armijo.

Na apresentação dos resultados obtidos se utiliza a seguinte simbologia:

N : número de variáveis independentes.

: norma infinito do gradiente projetado da função objetivo f.

F.O.: valor da função objetivo na solução obtida.

Aval. f: número de avaliações da função objetivo .

Iterações: número de iterações da subrotina principal do algoritmo.

Tempo : tempo de CPU em segundos.

> 600 (na coluna de Iterações):significa que o programa parou por ter atingido o número máximo de iterações permitido no caso sem restrições.

> 300 (na coluna de Iterações):significa que o programa parou por ter atingido o número máximo de iterações permitido no caso com restrições.

# (na coluna do N): significa que o programa parou porque o raio da região de confiança se tornou menor que a tolerância estabelecida e não foi possível obter decréscimo da função na direção da projeção de -f(x_c) na região viável

A seguir são apresentados os resultados dos testes realizados.

1- Função Estendida de Rosenbrock [5 e 28].

f(x) = , onde n é par.

[a]- Minimização sem Restrições:

Valor Ótimo (esperado) da função objetivo: f = 0 em

x_* = (1,...,1).

Aproximação inicial: x = (-1.2,1,-1.2,1,...,-1.2,1).

[a.1]- Resultados obtidos com Aproximações de Banda

Tridiagonais:


Tabela 1

[a.2]- Resultados obtidos com Aproximações de Banda Pentadiagonais:


Tabela 2

[b]- Minimização com Restrições Canalizadas:
[b.1]- Resultados obtidos com Aproximações de Banda Tridiagonais:

Tabela 3

[b.2]- Resultados obtidos com Aproximações de Banda Pentadiagonais:
Observação: Para N =1000, o problema foi resolvido com a aproximação da solução x_* obtida na iteração 600 do problema irrestrito.

Tabela 4

2- Função Singular Estendida de Powell ( [5 e 28]).
f(x)=

sendo n um múltiplo de 4.

[a]- Minimização sem Restrições:

Valor Ótimo da função objetivo: f = 0 em x_* = (0,...,0).

Aproximação Inicial x = (3,-1,0,1,...,3,-1,0,1).

[a.1]- Resultados Obtidos com Aproximações de Banda Tridiagonais:

Tabela 5

[a.2]- Resultados Obtidos com Aproximações de Banda Pentadiagonais:



Tabela 6

[b]- Minimização com Restrições Canalizadas:
[b.1]- Resultados obtidos com Aproximações de Banda Tridiagonais:

Tabela 7

[b.2]- Resultados obtidos com Aproximações de Banda Pentadiagonais:

Como em [a.2], para N = 100, 200 e 1000, o algoritmo não convergiu em 600 iterações, para esses valores de N os problemas com restrições canalizadas foram gerados da seguinte forma: para N = 100 foi retirada a condição de número máximo de iterações, e resolvido novamente o problema para o caso irrestrito com aproximações das Hessianas pentadiagonais; o ponto de ótimo x_* foi obtido na iteração 673, e esse ponto foi utilizado para resolver o problema canalizado. Para N = 200 e N = 1000 o problema com restrições canalizadas foi gerado com a aproximação da solução x_* obtido na iteração 600.

Tabela 8

3- Função Trigonométrica [28]).
f(x) = .

Valor Ótimo da função objetivo: f = 0 em x_* = (0,...,0).

Aproximação Inicial: x = (1/n,1/n,...,1/n).
[a]- Minimização sem Restrições:
[a.1]- Resultados obtidos com Aproximações de Banda Tridiagonais:

Tabela 9

[a.2]- Resultados obtidos com Aproximações de Banda Pentadiagonais:

Tabela 10

[b]-Minimização com Restrições Canalizadas:
Obs:Para N = 1000 será utilizado x_* obtido na iteração 600.

[b.1]- Resultados obtidos com Aproximações de Banda Tridiagonais:

Tabela 11

[b.2]- Resultados obtidos com Aproximações de Banda Pentadiagonais:

Tabela 12

4- Função Associada ao Problema de Contorno Discretizado[28].
f(x) =,

onde h = 1/(n+1), t_i = ih, x₀ = x_n+1 = 0.

Valor Ótimo da função objetivo: f = 0.

Aproximação Inicial: x = (_i) onde _i = t_i(t_i - 1),

i = 1,...,n..

[a.1]- Resultados obtidos com Aproximações de Banda Tridiagonais:

Tabela 13

[a.2]- Resultados obtidos com Aproximações de Banda Pentadiagonais:

Tabela 14

[b]- Minimização com Restrições Canalizadas:
[b.1]- Resultados obtidos com Aproximações de Banda Tridiagonais:(Para N = 100 e 200 foram utilizados os resultados obtidos na iteração 600 em [a.1].

Tabela 15

[b.2]- Resultados obtidos com Aproximações de Banda Pentadiagonais:

Tabela 16

5- Função Linear (posto máximo)[28].

f(x) = .

Valor Ótimo da função objetivo: f = 0 em x_* =(-1,-1,...,-1).

Aproximação Inicial: x = (1,1,...,1,1).

[a.1]- Resultados obtidos com Aproximações de Banda Tridiagonais:

Tabela 17

[a.2]- Resultados Obtidos com Aproximações de Banda Pentadiagonais:

Tabela 18

[b]- Minimização com Restrições Canalizadas:
[b.1]- Resultados obtidos com Aproximações de Banda Tridiagonais para os casos onde houve convergência no caso [a.1]:

Tabela 19

6- f(x) = 2 - (ver[5])

(Uma generalização do problema 45 de Hock e Schittkowski).

Restrições: 0 x_i i, i 1 i n.

Aproximação Inicial: x = (2,2,...,2).

Valor Ótimo da função objetivo: f = 1 em x_* = (1,2,...,n).

Tabela 20

Observação: Para valores maiores de N, o ponto inicial já satisfaz a condição principal de convergência. Seria necessário impor que a norma do gradiente projetado fosse menor do que o utilizado.

7- f(x) = x^TAx , onde x Rⁿ , A R^nxn ,A = diag(1,2,...,n).

n = 5000

Aproximação Inicial: x₀ = (50,50,...,50).

Valor Ótimo da função objetivo: f = 0 em x_* = (0,...,0).

O objetivo deste teste era comparar o resultado com o resultado obtido pelo algoritmo de Friedlander-Martínez-Santos [17]. No caso de minimização de quadráticas , quando se utilizam as matrizes hessianas verdadeiras , o método de Martínez-Friedlander-Santos converge numa única iteração da subrotina Box (subrotina central do algoritmo).

Com as aproximações das hessianas utilizadas nesse trabalho,o algoritmo convergiu em duas iterações da subrotina Box. Os testes foram realizados com aproximações das hessianas diagonais, tridiagonais e pentadiagonais obtendo os mesmos resultados em todos os casos , com exceção do tempo de execução:

x_* = (0,0,...,0,0)

Valor da função objetivo: f = 0

Norma infinito do gradiente projetado :0

Número de avaliações da função objetivo :3

Tempo de execução do Algoritmo:

a) Aproximações de Banda Diagonais:1.69 segundos..

b) Aproximaçoes de Banda Tridiagonais: 2.06 segundos.

c) Aproximações de Banda Pentadiagonais: 2.41 segundos.

5.2 CONCLUSÕES E RECOMENDAÇÕES

O algoritmo se mostrou eficiente para resolver a maioria dos problemas testados. Mesmo em casos em que não houve convergência alguns resultados podem ser considerados bons; por exemplo, a Função Singular Estendida de Powell, com N = 100 e aproximações Hessianas pentadiagonais (caso [a.2]),não convergiu com o número máximo permitido de iterações, mas se for relaxado esse critério de parada se obtém o seguinte resultado: convergência na iteração 673, com =9.13d-7, F.O.= 3.72d-8, Aval. f = 6546 e Tempo = 981.2 segundos. A forma de executar os testes, exigindo que a norma do gradiente projetado seja menor do que 10^-6, foi bastante rigorosa, pois não permitiu que se declarasse convergência mesmo quando o valor da função objetivo estava próximo do valor verdadeiro. Isso foi feito porque em muitos problemas reais não se tem uma estimativa razoável do valor esperado da f e será necessário esse tipo de exigência.

A grande vantagem do método é que não se requer o cálculo das Hessianas verdadeiras, e o armazenamento necessário para as aproximações de banda pode ser muito menor, quando se considera N grande e aproximações tridiagonais ou pentadiagonais.

Não foram feitos testes utilizando um número maior de diagonais, e isso deverá ser feito posteriormente; o número de diagonais não nulas acima da diagonal principal é um parâmetro na implementação do método. Os resultados com aproximações diagonais das Hessianas não foram satisfatórios(com exceção da função quadrática do problema 7),o que já era esperado.

Do ponto de vista do usuário a grande vantagem é que é suficiente calcular o gradiente de cada função a ser utilizada. Além disso, depois de sucessivas análises, a maioria dos parâmetros utilizados no algoritmo de Friedlander-Martínez-Santos tem seus valores definidos ou sugeridos.

A desvantagem apresentada pelo algoritmo é que o trabalho computacional aumenta à medida que N cresce, pois nos testes se verificou, em quase todos os casos, que o número de iterações, e principalmente o número de avaliações de f, aumenta quando N aumenta. Provavelmente isso vai depender da complexidade da função objetivo . Com funções quadráticas, que são muito usuais em problemas práticos, o algoritmo convergiu rapidamente, apesar de N ser grande.

Os testes com o algoritmo devem prosseguir, e espera-se fazer uma análise mais adequada da influência nos resultados do número de diagonais utilizado. Além disso essas aproximações de banda para as Hessianas deverão ser testadas num caso mais geral, em que são utilizadas restrições não lineares. O algoritmo de região de confiança de Friedlander-Martínez-Santos foi estendido para esse caso mais geral, o que permitirá essa análise.