Estudo do desempenho de métodos para
minimização irrestrita com controle de passo∗
Sandra A. Santos,
Larissa O. Xavier†,
Depto de Matemática Aplicada, IMECC, UNICAMP,
13083-970, Campinas, SP
E-mail: [email protected],
Neste trabalho apresentamos um estudo teóricoprático de métodos locais para minimização
irrestrita com controle de passo. A liberdade
inerente a estes métodos é explorada por meio das
escolhas para a direção de descida e o tamanho
do passo. As direções são tomadas com base no
método do gradiente e em uma nova proposta
de direção. Para o tamanho do passo, além dos
métodos puros (passo completo) e do passo ótimo
no caso do gradiente em problemas quadráticos,
analisamos o desempenho do passo espectral de
Barzilai e Borwein [1] para o método do gradiente
e de passos aleatórios uniformemente gerados [5].
O ponto de partida é a compreensão dos métodos
e das diferentes possibilidades para o tamanho do
passo em problemas quadráticos.
Apresentamos também um conjunto extensivo de
testes com problemas de quadrados mı́nimos não
lineares [4]. Para estes testes, além do método do
gradiente com bissecção e com os passos propostos
por Barzilai e Borwein, utilizamos o método de
Gauss-Newton com passo puro e com bissecção [2].
Propomos também uma modificação a partir dos
passos propostos por Barzilai e Borwein, originando
duas novas escolhas para o tamanho de passo.
Para os testes computacionais o ambiente de
programação é o Matlab. A análise de desempenho
é feita via performance profile, conforme o trabalho
de Dolan e Moré [3]. Apresentamos ainda os resultados da submissão eletrônica de alguns problemas
ao NEOS-server, com a implementação das funções
objetivo em Fortran.
Referências
[1] J. Barzilai & J. Borwein, Two-point step size
gradient methods, IMA Journal of Numerical
Analysis, 8 (1988) 141-148.
∗ Apoios
† bolsista
FAPESP 02/13486-4 e CNPq 300206/96-8.
de Iniciação Cientı́fica FAPESP
[email protected],
[2] J. E. Dennis & R. B. Schnabel, Numerical
Methods for Unconstrained Optimization and
Nonlinear Equations, Prentice-Hall, 1983.
[3] E. D. Dolan & J. J. Moré, Benchmarking
optimization software with performance profiles, Mathematical Programming, 91 (2002) 201213.
[4] J. J. Moré, B. S. Garbow & K. E. Hillstrom,
Testing Unconstrained Optimization Software,
ACM Trans. Math. Software, 7 (1981) 17-41.
[5] M. Raydan & B. F. Svaiter, Relaxed Steepest Descent and Cauchy-Barzilai-Borwein
Method, Computational Optimization and Applications, 21 (2002) 155-167.