Abstract
We present a modification of the DIRECT (DIviding RECTangles) algorithm, called DIRECT-G, to solve a box-constrained global optimization problem arising in the detection of gravitational waves emitted by coalescing binary systems of compact objects. This is a hard problem, since the objective function is highly nonlinear and expensive to evaluate, has a huge number of local extrema and unavailable derivatives. DIRECT performs a sampling of the feasible domain over a set of points that becomes dense in the limit, thus ensuring the everywhere dense convergence; however, it becomes ineffective on significant instances of the problem under consideration, because it tends to produce a uniform coverage of the feasible domain, by oversampling regions that are far from the optimal solution. DIRECT has been modified by embodying information provided by a suitable discretization of the feasible domain, based on the signal theory, which takes into account the variability of the objective function. Numerical experiments show that DIRECT-G largely outperforms DIRECT and the grid search, the latter being the reference algorithm in the astrophysics community. Furthermore, DIRECT-G is comparable with a genetic algorithm specifically developed for the problem. However, DIRECT-G inherits the convergence properties of DIRECT, whereas the genetic algorithm has no guarantee of convergence.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79(1), 157–181 (1993)
Jones, D.R.: DIRECT global optimization. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 725–735. Springer, Berlin (2009)
Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization, 2nd edn. Kluwer Academic, Dordrecht (2000)
Bartholomew-Biggs, M.C., Parkhurst, S.C., Wilson, S.P.: Using DIRECT to solve an aircraft routing problem. Comput. Optim. Appl. 21(3), 311–323 (2002)
Carter, R.G., Gablonsky, J.M., Patrick, A., Kelley, C.T., Eslinger, O.J.: Algorithms for noisy problems in gas transmission pipeline optimization. Optim. Eng. 2(2), 139–157 (2001)
Cox, S.E., Haftka, R.T., Baker, C.A., Grossman, B., Mason, W.H., Watson, L.T.: A comparison of global optimization methods for the design of a high-speed civil transport. J. Glob. Optim. 21(4), 415–433 (2001)
He, J., Watson, L.T., Ramakrishnan, N., Shaffer, C.A., Verstak, A., Jiang, J., Bae, K., Tranter, W.H.: Dynamic data structures for a direct search algorithm. Comput. Optim. Appl. 23(1), 5–25 (2002)
Gablonsky, J.M., Kelley, C.T.: A locally-biased form of the DIRECT algorithm. J. Glob. Optim. 21(1), 27–37 (2001)
Liuzzi, G., Lucidi, S., Piccialli, V.: A partition-based global optimization algorithm. Journal of Global Optimization (2010)
Liuzzi, G., Lucidi, S., Piccialli, V.: A DIRECT-based approach exploiting local minimizations for the solution of large-scale global optimization problems. Comput. Optim. Appl. 45(2), 253–375 (2010)
Panning, T.D., Watson, L.T., Allen, N.A., Chen, K.C., Shaffer, C.A., Tyson, J.J.: Deterministic parallel global parameter estimation for a model of the budding yeast cell cycle. J. Glob. Optim. 40, 719–738 (2008)
Thorne, K.S.: Gravitational radiation. In: Hawking, S.W., Israel, W. (eds.) 300 Years of Gravitation, pp. 330–458. Cambridge University Press, Cambridge (1987)
Babak, S., Balasubramanian, R., Churches, D., Cokelaer, T., Sathyaprakash, B.S.: A template bank to search for gravitational waves from inspiralling compact binaries I: physical models. Class. Quantum Gravity 23, 5477–5504 (2006)
di Serafino, D., Gomez, S., Milano, L., Riccio, F., Toraldo, G.: A genetic algorithm for a global optimization problem arising in the detection of gravitational waves. J. Glob. Optim. 48(1), 41–55 (2010)
di Serafino, D., Riccio, F.: On the application of multiple-deme parallel genetic algorithms in astrophysics. In: Proceedings of the 18th Euromicro International Conference on Parallel Distributed and Network-Based Processing, pp. 231–237 (2010)
Milano, L., Barone, F., Milano, M.: Time domain amplitude and frequency detection of gravitational waves from coalescing binaries. Phys. Rev. D 55(8), 4537–4554 (1997)
Mohanty, S.D.: Hierarchical search strategy for the detection of gravitational waves from coalescing binaries: extension to post-Newtonian waveforms. Phys. Rev. D 57(2), 630–658 (1998)
Mohanty, S.D., Dhurandhar, S.V.: Hierarchical search strategy for the detection of gravitational waves from coalescing binaries. Phys. Rev. D 54(12), 7108–7128 (1996)
Owen, B.J.: Search templates for gravitational waves from inspiraling binaries: choice of template spacing. Phys. Rev. D 53(12), 6749–6761 (1996)
Blanchet, L., Rlyer, B., Wiseman, A.G.: Gravitational waveforms from inspiralling compact binaries to second-post-Newtonian order. Class. Quantum Gravity 13, 575–584 (1996)
Prix, R.: Template-based searches for gravitational waves: efficient lattice covering of flat parameter spaces. Class. Quantum Gravity 24, S481–S490 (2007)
Rasio, A.R., Shapiro, S.L.: Coalescing binary neutron stars. Class. Quantum Gravity 16(6), R1–R29 (1999)
Allen, B., et al.: LAL Software Documentation. Revision 1.44, 2005
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Ryan P. Russell.
We thank Stefano Lucidi for useful discussions on DIRECT and on strategies to accelerate its convergence. We are also thankful to the anonymous Referees and the journal Editors for their careful reading of the paper and their insightful comments that helped us improving the paper. This work was supported by the Italian Ministry for Education, University and Research, under the PRIN Project Nonlinear Optimization, Variational Inequalities and Equilibrium Problems.
Rights and permissions
About this article
Cite this article
di Serafino, D., Liuzzi, G., Piccialli, V. et al. A Modified DIviding RECTangles Algorithm for a Problem in Astrophysics. J Optim Theory Appl 151, 175–190 (2011). https://doi.org/10.1007/s10957-011-9856-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-011-9856-9