Métodos de regiões de confiança para resolução do problema de quadrados mínimos: implementação e testes numéricos

Authors

  • J. L. C. Gardenghi Universidade de São Paulo
  • S. A. Santos Universidade Estadual de Campinas

DOI:

https://doi.org/10.5540/tema.2013.014.01.0069

Abstract

O problema de quadrados mínimos possui várias aplicações no campo de otimização. No presente trabalho, abordamos duas estratégias para sua resolução: Levenberg-Marquardt e Gradientes Conjugados. Cada uma explora características próprias do problema, e ambas usam regiões de confiança para a globalização. Nossa contribuição está na implementação de ambos os métodos no CAS Maxima e na análise comparativa do desempenho desses métodos na resolução de uma família de problemas de quadrados mínimos da literatura.

References

L.N. Andrade, Maxima: um completo programa de computação algébrica, Revista do Professor de Matemática, n. 77, 2012.

A.R. Conn, N.I.L. Gould, Ph.L. Toint, "Trust-region Methods"'. SIAM, Philadelphia, 2000.

E.D. Dolan, J.J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, v. 91, pp. 201-213, 2002.

J.L.C. Gardenghi, S.A. Santos, "Sistemas não-lineares via região de confiança: o algoritmo de Levenberg-Marquardt". Relatório de Pesquisa, 2011. Disponível em http://www.ime.unicamp.br/sites/default/files/rel_pesq/rp03-11.pdf. Acesso em 05 mar. 2013.

J.L.C. Gardenghi, S.A. Santos, "Minimização irrestrita usando gradientes conjugados e regiões de confiança". Relatório de Pesquisa, 2012. Disponível em http://www.ime.unicamp.br/sites/default/files/rel_pesq/rp04-12.pdf. Acesso em 05 mar. 2013.

K. Levenberg, A method for the solution of certain non-linear problems in least squares, The Quarterly of Applied Mathematics 2, pp. 164-168, 1944.

K. Madsen, An algorithm for the minimax solution of overdetermined systems of nonlinear equations. Journal of the Institute of Mathematics and its Applications. v. 16(3), pp. 321-328, 1975.

D.W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, SIAM Journal on Applied Mathematics 11, pp. 431-441, 1963.

J.J. Moré, The Levenberg-Marquardt algorithm: implementation and theory. Lecture Notes in Mathematics 630: Numerical Analysis, Springer-Verlag, New York, pp. 105-116, 1978.

J.J. Moré, B.S. Garbow, K.E. Hillstrom, Testing unconstrained optimization software, ACM Transactions on Mathematical Software, v. 7, pp. 17-41, 1981.

J. Nocedal, S.J. Wright, "Numerical Optimization". Springer, New York, 1999.

T. Steihaug, The conjugate gradient method and trust region in large scale optimization. SIAM Journal on Numerical Analysis, v. 20(3), pp. 626-637, 1983.

Ph.L. Toint, Towards an efficient sparsity exploiting Newton method for minimization, em "Sparse Matrix and Their Uses" (I. Duff, ed.), Academic Press, pp. 57-88, 1981.

Y. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least-squares. Numerical Algebra, Control and Optimization, v. 1, n. 1, pp. 15-34, 2011.

http://maxima.sourceforge.net.

Published

2013-04-21

How to Cite

Gardenghi, J. L. C., & Santos, S. A. (2013). Métodos de regiões de confiança para resolução do problema de quadrados mínimos: implementação e testes numéricos. Trends in Computational and Applied Mathematics, 14(1), 69–80. https://doi.org/10.5540/tema.2013.014.01.0069

Issue

Section

Original Article