International Journal of Nonlinear Analysis and Applications
A family of parallel quasi-Newton algorithms for unconstrained minimization
Document Type : Research Paper
Authors
Department of Mathematics, Faculty of Science, Al-Azhar University (Assiut Branch), Assiut, Egypt
Abstract
This paper deals with the solution of the unconstrained optimization problems on parallel computers using quasi-Newton methods. The algorithm is based on that parallelism can be exploited in function and derivative evaluation costs and linear algebra calculations in the standard sequential algorithm. Computational problem is reported for showing that the parallel algorithm is superior to the sequential one.
Keywords
[1] A.I. Ahmed, A new parameter free filled function for solving unconstrained global optimization problems, Int. J. Comput. Math. 98 (2021) 106–119.
[2] C.G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comput. 19 (1965) 577–593.
[3] R.H. Byrd, R.B. Schnabel and G.A. Shultz, Parallel quasi-Newton methods for solving the unconstrained optimization, Math. Prog. 42 (1988) 273–306.
[4] D. Chazan and W.L. Miranker, A nongradient and parallel algorithm for unconstrained minimization, SIAM J. Cont. 8 (1970) 207–217.
[5] J.J. E. Dennis and V. Torczon, Direct search methods in parallel machines, SIAM J. Opt. 1 (1991) 448–474.
[6] T.M. El–Gindy, M.S. Salim and A.I. Ahmed, A Modified partial quadratic interpolation method for unconstrained optimization, J. Conc. Appl. Math. 11 (2013) 136–146.
[7] T.M. El-Gindy, M.S. Salim and A.I. Ahmed, A new filled function method applied to unconstrained global optimization, Appl. Math. Comput. 273 (2016) 1246–1256.
[8] H. Fischer and K. Ritter, An asynchronous parallel Newton method, Math. Prog. 42 (1988) 363–374.
[9] M. Fukushima, Parallel variable transformation in unconstrained optimization, SIAM J. Opt. 8 (1998) 658–672.
[10] P.E. Gill, W. Murray and M. H. Wright, Practical optimization, Academic Press, London, 1981.
[11] L. Grandinetti, Factorization versus nonfactorization in quasi-Newtonian methods for differentiable optimization, Report N5, Dipartimento di Sistemi, Universita della Calabria 1978.
[12] H.Y. Huang, Unified approach to quadratically convergent algorithms for function minimization, J. Opt. Theo. Appl. 5 (1970) 405–423.
[13] J.K. Liu and S.J. Li, New three–term conjugate gradient method with guaranteed global convergence, Int. J. Comput. Math. 91 (2014) 1744–1754.
[14] F.A. Lootsma, Parallel Newton–Raphson methods for unconstrained minimization with asynchronous updates of the Hessian matrix or its inverse, M. Grauer, D.B. Pressmar (Eds.), Parallel computing and mathematical optimization, Springer-Verlag, Berlin, 1991, pp. 1-18.
[15] O.L. Mangasarian, Parallel gradient distribution in unconstrained optimization, SIAM J. Cont. Opt. 33 (1995) 1916–1925.
[16] J. Moreau, Proximite et dualite dans un espace hilbertien, Bull. Soc. Math. France 93 (1965) 273–299.
[17] J.J. More, B.S. Garbow and K.E. Hillstrome, Testing unconstrained optimization software, ACM Trans. Math. Soft. 7 (1981) 17–41.
[18] J.A. Nelder and R. Mead, A simplex method for function minimization, Comput. J. 7 (1965) 308–313.
[19] L.P. Pang and Z.Q. Xia, A PVT-TYPE algorithm for minimization a nonsmooth convex function, Serdica Math. J. 29 (2003) 11–32.
[20] K.D. Patel, Implementation of a parallel (SIMD) modified Newton method on the ICL DAP, Technical Report No. 131, Numerical Optimization Centre, The Hatfield Polytechnic (1982).
[21] P.K.-H. Phua, W. Fan, Y. Zeng, Parallel algorithms for large-scale nonlinear optimization, Int. Trans. Opl Res. 5 (1998) 67–77.
[22] M.J.D. Powell, An efficient method for finding the minimum of a function of several variables without calculating derivatives, Comput. J. 7 (1964) 155–162.
[23] K. Ritter, Private communications in symposium on parallel optimization 3, July 1993.
[24] M.S. Salim and A.I. Ahmed, A piecewise polynomial approximation for solving nonlinear optimal control problems, Far East J. Appl. Math. 95 (2016) 195–213.
[25] M.S. Salim and A.I. Ahmed, A family of quasi-Newton methods for unconstrained optimization problems, Opt. 67 (2018) 1717–1727.
[26] M.S. Salim and A.I. Ahmed, A quasi-Newton augmented Lagrangian algorithm for constrained optimization problems, J. Intel. Fuzzy Syst. 35 (2018) 2373–2382.
[27] F. Sloboda, Parallel method of conjugate directions for minimization, Appl. Mat. 20 (1975) 436–446.
[28] F. Sloboda, A conjugate directions method and its applications, Proc. 8th IFIP Conf. Optim. Tech., 1977.
[29] C. H. Still, Parallel quasi-Newton methods for unconstrained optimization, Proc. fifth Distrib. Memory Comput. Conf., 1990, April 8–12, 263-271.
[30] C.H. Still, The parallel BFGS Method for unconstrained minimization, Proc. Sixth Distrib. Memory Comput. Conf., 1991, April 28–May 1, pp. 347-354.
[31] T.A. Straeter, A parallel variable metric optimization algorithm, Technical report D-7329 NASA Langley Research center, Hampton, Va, 1973.
[32] C. Sutti, A new method for unconstrained minimization without derivatives, 277–289, In Towards global optimization, North Holland, 1978.
[33] C. Sutti, Nongradient minimization methods for parallel processing computers, Part 1, J. Opt. Theo. Appl. 39 (1983) 465-474.
[34] C. Sutti, Nongradient minimization methods for parallel processing computers, Part 2, J. Opt. Theo. Appl. 39 (1983) 475–488.
[35] A.J. Umbarkar, M.S. Joshi and W.-Ch. Hong, Multithreaded parallel dual population genetic algorithm (MPDPGA) for unconstrained function optimizations on a multi-core system, Appl. Math. Comput. 243 (2014) 936–949.
[36] P.J.M. van Laarhoven, Parallel variable matrix Algorithms for unconstrained optimization, Math. Prog. 33 (1985) 68-81.
[37] Y. Xiao, Z. Wei and Z. Wang, A limited memory BFGS–type method for large–scale unconstrained optimization, Comput. Math. Appl. 56(4) (2008) 1001–1009.
[38] K. Yosida, Functional analysis, Springer Verlag, Berlin, 1964.
[39] W.I. Zangwill, Minimizing a function without calculating derivatives, Comput. J. 10 (1967) 293–296.
)
Volume 12, Issue 1
May 2021Pages 1123-1133
- Receive Date: 13 January 2019
- Revise Date: 04 November 2019
- Accept Date: 10 November 2019