×

zbMATH — the first resource for mathematics

On MATLAB experience in accelerating DIRECT-GLce algorithm for constrained global optimization through dynamic data structures and parallelization. (English) Zbl 07330168
Summary: In this paper, two different acceleration techniques for a deterministic DIRECT (DIviding RECTangles)-type global optimization algorithm, DIRECT-GLce, are considered. We adopt dynamic data structures for better memory usage in MATLAB implementation. We also study shared and distributed parallel implementations of the original DIRECT-GLce algorithm, and a distributed parallel version for the aggressive counterpart. The efficiency of DIRECT-type parallel versions is evaluated solving box- and generally constrained global optimizations problems with varying complexity, including a practical NASA speed reducer design problem. Numerical results show a good efficiency, especially for the distributed parallel version of the original DIRECT-GLce on a multi-core PC.

MSC:
90C26 Nonconvex programming, global optimization
90C56 Derivative-free methods and methods using generalized derivatives
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Jones, D. R.; Perttunen, C. D.; Stuckman, B. E., Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 1, 157-181 (1993) · Zbl 0796.49032
[2] Jones, D. R., The Direct global optimization algorithm, (Floudas, C. A.; Pardalos, P. M., The Encyclopedia of Optimization (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrect), 431-440
[3] Gablonsky, J. M.; Kelley, C. T., A locally-biased form of the DIRECT algorithm, J. Global Optim., 21, 1, 27-37 (2001) · Zbl 1039.90049
[4] Finkel, D. E.; Kelley, C. T., Additive scaling and the DIRECT algorithm, J. Glob. Optim., 36, 4, 597-608 (2006) · Zbl 1142.90488
[5] Liuzzi, G.; Lucidi, S.; Piccialli, V., A partition-based global optimization algorithm, J. Glob. Optim., 48, 1, 113-128 (2010) · Zbl 1230.90153
[6] Liuzzi, G.; Lucidi, S.; Piccialli, V., Exploiting derivative-free local searches in direct-type algorithms for global optimization, Comput. Optim. Appl., 65, 449-475 (2016) · Zbl 1370.90194
[7] Liu, Q.; Cheng, W., A modified DIRECT algorithm with bilevel partition, J. Glob. Optim., 60, 3, 483-499 (2014) · Zbl 1303.90083
[8] Paulavičius, R.; Chiter, L.; Žilinskas, J., Global optimization based on bisection of rectangles, function values at diagonals, and a set of Lipschitz constants, J. Glob. Optim., 71, 1, 5-20 (2018) · Zbl 1402.90134
[9] Paulavičius, R.; Sergeyev, Y. D.; Kvasov, D. E.; Žilinskas, J., Globally-biased DISIMPL algorithm for expensive global optimization, J. Glob. Optim., 59, 2-3, 545-567 (2014) · Zbl 1297.90130
[10] Paulavičius, R.; Žilinskas, J., Simplicial Lipschitz optimization without the Lipschitz constant, J. Glob. Optim., 59, 1, 23-40 (2013) · Zbl 1300.90031
[11] Paulavičius, R.; Žilinskas, J., Simplicial Global Optimization, SpringerBriefs in Optimization (2014), Springer New York: Springer New York New York, NY · Zbl 1401.90017
[12] Sergeyev, Y. D.; Kvasov, D. E., Global search based on diagonal partitions and a set of Lipschitz constants, SIAM J. Optim., 16, 3, 910-937 (2006) · Zbl 1097.65068
[13] Stripinis, L.; Paulavičius, R.; Žilinskas, J., Improved scheme for selection of potentially optimal hyper-rectangles in DIRECT, Optim. Lett., 12, 7, 1699-1712 (2018) · Zbl 1407.90264
[14] Paulavičius, R.; Sergeyev, Y. D.; Kvasov, D. E.; Žilinskas, J., Globally-biased BIRECT algorithm with local accelerators for expensive global optimization, Expert Syst. Appl., 144, 11305 (2020)
[15] Rios, L. M.; Sahinidis, N. V., Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 3, 1247-1293 (2012) · Zbl 1272.90116
[16] Baker, C. A.; Watson, L. T.; Grossman, B.; Mason, W. H.; Haftka, R. T., Parallel global aircraft configuration design space exploration, (Tentner, A., High Performance Computing Symposium 2000 (2000), Soc. for Computer Simulation Internat), 54-66
[17] 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) · Zbl 1017.90133
[18] 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) · Zbl 1079.90624
[19] 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. (2008) · Zbl 1140.68371
[20] Stripinis, L.; Paulavičius, R.; Žilinskas, J., Penalty functions and two-step selection procedure based -type algorithm for constrained global optimization, Struct. Multidiscip. Optim., 59, 6, 2155-2175 (2019)
[21] Zwolak, J. W.; Tyson, J. J.; Watson, L. T., Globally optimised parameters for a model of mitotic control in frog egg extracts, IEE Proc. Syst. Biol. (2005)
[22] Žilinskas, A., On strong homogeneity of two global optimization algorithms based on statistical models of multimodal objective functions, Appl. Math. Comput., 218, 16, 8131-8136 (2012) · Zbl 1245.90094
[23] Liuzzi, G.; Lucidi, S.; Piccialli, V., A direct-based approach exploiting local minimizations for the solution for large-scale global optimization problems, Comput. Optim. Appl., 45, 2, 353-375 (2010) · Zbl 1187.90275
[24] 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) · Zbl 1036.90055
[25] Horst, R.; Pardalos, P. M.; Thoai, N. V., Introduction to Global Optimization, Nonconvex Optimization and Its Application (1995), Kluwer Academic Publishers · Zbl 0836.90134
[26] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches (1996), Springer: Springer Berlin · Zbl 0867.90105
[27] Handbook of Global Optimization, (Pardalos, P. M.; Romeijn, H. E., 2 (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht) · Zbl 0991.00017
[28] Paulavičius, R.; Žilinskas, J., Analysis of different norms and corresponding Lipschitz constants for global optimization in multidimensional case, Inf. Technol. Control, 36, 4, 383-387 (2007)
[29] Sergeyev, Y. D.; Strongin, R. G.; Lera, D., Introduction to Global Optimization Exploiting Space-Filling Curves, SpringerBriefs in Optimization (2013), Springer: Springer New York · Zbl 1278.90005
[30] Sergeyev, Y. D.; Kvasov, D. E., Deterministic Global Optimization: An Introduction to the Diagonal Approach, SpringerBriefs in Optimization (2017), Springer · Zbl 1371.90112
[31] Paulavičius, R.; Žilinskas, J.; Grothey, A., Parallel branch and bound for global optimization with combination of Lipschitz bounds, Optim. Methods Softw., 26, 3, 487-498 (2011)
[32] Paulavičius, R.; Žilinskas, J., Parallel branch and bound algorithm with combination of Lipschitz bounds over multidimensional simplices for multicore computers, Parallel Scientific Computing and Optimization, 15, 93-102 (2009), Springer New York · Zbl 1188.68353
[33] Sergeev, Y. D.; Strongin, R., A global minimization algorithm with parallel iterations, USSR Comput. Math. Math. Phys., 29, 2, 7-15 (1989) · Zbl 0702.65064
[34] Sergeyev, Y. D.; Grishagin, V., A parallel method for finding the global minimum of univariate functions, J. Optim. Theory Appl., 80, 3, 513-536 (1994) · Zbl 0797.90098
[35] Sergeyev, Y.; Grishagin, V., Sequential and parallel global optimization algorithms, Optim. Methods Softw., 3, 111-124 (1994)
[36] Strongin, R. G.; Sergeyev, Y. D., Global multidimensional optimization on parallel computer, Parallel Comput., 18, 11, 1259-1273 (1992) · Zbl 0766.65052
[37] Strongin, R. G.; Sergeyev, Y. D., Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0987.90068
[38] Strongin, R. G.; Sergeyev, Y. D., Global optimization: fractal approach and non-redundant parallelism, J. Glob. Optim., 27, 1, 25-50 (2003) · Zbl 1035.90086
[39] Grishagin, V. A.; Sergeyev, Y. D.; Strongin, R. G., Parallel characteristical algorithms for solving problems of global optimization, J. Glob. Optim., 10, 2, 185-206 (1997) · Zbl 0880.90123
[40] Gablonsky, J. M., Modifications of the DIRECT Algorithm (2001), North Carolina State University, Ph.D. thesis · Zbl 1039.90049
[41] He, J.; Verstak, A.; Sosonkina, M.; Watson, L. T., Performance modeling and analysis of a massively parallel DIRECT-Part 2, Int. J. High Perform. Comput. Appl., 23, 1, 29-41 (2009)
[42] He, J.; Verstak, A.; Watson, L. T.; Sosonkina, M., Design and implementation of a massively parallel version of direct, Comput. Optim. Appl. (2008) · Zbl 1181.90138
[43] He, J.; Verstak, A.; Watson, L. T.; Sosonkina, M., Performance modeling and analysis of a massively parallel DIRECT-part 1, Int. J. High Perform. Comput. Appl., 23, 1, 14-28 (2009)
[44] He, J.; Watson, L. T.; Sosonkina, M., Algorithm 897: VTDIRECT95: serial and parallel codes for the global optimization algorithm DIRECT, ACM Trans. Math. Softw. (2010) · Zbl 06642864
[45] Paulavičius, R.; Žilinskas, J.; Herrera, J. F.; Casado, L. G., A parallel DISIMPL for pile placement optimization in grillage-type foundations, 2013 Eighth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, 525-530 (2013), IEEE
[46] Watson, L. T.; Baker, C. A., A fully-distributed parallel global search algorithm. engineering computations, Eng. Comput., 18, 1/2, 155-169 (2001) · Zbl 0999.74119
[47] Björkman, M.; Holmström, K., Global optimization using the DIRECT algorithm in Matlab, Adv. Model. Optim., 1, 2, 17-37 (1999) · Zbl 1115.90300
[48] Liu, H.; Xu, S.; Chen, X.; Wang, X.; Ma, Q., Constrained global optimization via a direct-type constraint-handling technique and an adaptive metamodeling strategy, Struct. Multidiscip. Optim., 55, 1, 155-177 (2017)
[49] Liu, Q.; Yang, G.; Zhang, Z.; Zeng, J., Improving the convergence rate of the DIRECT global optimization algorithm, J. Glob. Optim., 67, 4, 851-872 (2017) · Zbl 1370.90193
[50] L. Stripinis, R. Paulavičius, DIRECTLib – a library of global optimization problems for DIRECT-type methods, v1.1, 2019, 10.5281/zenodo.1403547
[51] L. Stripinis, Parallel DIRECT-type algorithms for generally constrained global optimization problems in MATLAB, 2020, (https://github.com/blockchain-group/pDIRECT-GLce).
[52] Törn, A.; Žilinskas, A., Global Optimization, 350 (1989), Springer · Zbl 0752.90075
[53] Gergel, V.; Goryachih, A., Multidimensional global optimization using numerical estimates of objective function derivatives, Optim. Methods Softw., 1-21 (2019)
[54] Zhigljavsky, A.; Zilinskas, A., Stochastic Global Optimization, 9 (2007), Springer Science & Business Media
[55] Mockus, J.; Paulavičius, R.; Rusakevičius, D.; Šešok, D.; Žilinskas, J., Application of reduced-set Pareto-Lipschitzian optimization to truss optimization, J. Glob. Optim., 67, 1-2, 425-450 (2017) · Zbl 1359.90131
[56] Liu, Q.; Zeng, J.; Yang, G., MrDIRECT: a multilevel robust DIRECT algorithm for global optimization problems, J. Glob. Optim., 62, 2, 205-227 (2015) · Zbl 1326.90065
[57] Liu, H.; Xu, S.; Wang, X.; Wu, X.; Song, Y., A global optimization algorithm for simulation-based problems via the extended direct scheme, Eng. Optim., 47, 11, 1441-1458 (2015)
[58] Basudhar, A.; Dribusch, C.; Lacaze, S.; Missoum, S., Constrained efficient global optimization with support vector machines, Struct. Multidiscip. Optim., 46, 2, 201-221 (2012) · Zbl 1274.90271
[59] Costa, M. F.P.; Rocha, A. M.A. C.; Fernandes, E. M.G. P., Filter-based direct method for constrained global optimization, J. Glob. Optim., 71, 3, 517-536 (2018) · Zbl 1402.90127
[60] Pillo, G. D.; Liuzzi, G.; Lucidi, S.; Piccialli, V.; Rinaldi, F., A DIRECT-type approach for derivative-free constrained global optimization, Comput. Optim. Appl., 65, 2, 361-397 (2016) · Zbl 1370.90189
[61] Pillo, G. D.; Lucidi, S.; Rinaldi, F., An approach to constrained global optimization based on exact penalty functions, J. Optim. Theory Appl., 54, 2, 251-260 (2010) · Zbl 1259.90099
[62] Finkel, D. E., Global Optimization with the Direct Algorithm (2005), North Carolina State University, Ph.D. thesis
[63] D.E. Finkel, MATLAB source code for DIRECT, 2004, (http://www4.ncsu.edu/ ctk/Finkel_Direct/) Online; accessed: 2017-03-22.
[64] Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math. Program., 91, 2, 239-269 (2002) · Zbl 1049.90088
[65] Gmys, J., Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems (2017), Université de Mons (UMONS) ; Université de Lille, Theses
[66] T.G. Crainic, B. Le Cun, C. Roucairol, Parallel Branch-and-Bound Algorithms, John Wiley & Sons, Ltd, pp. 1-28. 10.1002/9780470053928.ch1
[67] Gendron, B.; Crainic, T. G., Parallel branch-and-branch algorithms: survey and synthesis, Oper. Res., 42, 6, 1042-1066 (1994) · Zbl 0824.90096
[68] Herrera, J. F.; Salmerón, J. M.; Hendrix, E. M.; Asenjo, R.; Casado, L. G., On parallel branch and bound frameworks for global optimization, J. Glob. Optim., 69, 3, 547-560 (2017) · Zbl 1386.68213
[69] Paulavičius, R.; Žilinskas, J.; Grothey, A., Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds, Optim. Lett., 4, 2, 173-183 (2010) · Zbl 1189.90203
[70] Griffin, J. D.; Kolda, T. G., Asynchronous parallel hybrid optimization combining direct and GSS, Optim. Methods Softw., 25, 5, 797-817 (2010) · Zbl 1198.90397
[71] Sergeyev, Y. D., On convergence of “divide the best” global optimization algorithms, Optimization, 44, 3, 303-325 (1998) · Zbl 0986.90058
[72] Kolda, T. G.; Lewis, R. M.; Torczon, V., Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45, 3, 385-482 (2003) · Zbl 1059.90146
[73] Matlab, Parallel Computing Toolbox - User ’ s Guide, Book (2020) 1-729.
[74] Choy, R.; Edelman, A., Parallel MATLAB: doing it right, Proc. IEEE, 93, 2, 331-341 (2005)
[75] Sharma, G.; Martin, J., MATLAB®: a language for parallel computing, Int. J. Parallel Program., 37, 1, 3-36 (2009) · Zbl 1191.68892
[76] Travinin Bliss, N.; Kepner, J., pMATLAB Parallel MATLAB library, Int. J. High Perform. Comput. Appl., 21, 3, 336-359 (2007)
[77] Kepner, J.; Ahalt, S., MatlabMPI, J. Parallel Distrib. Comput. (2004) · Zbl 1067.68793
[78] Trefethen, A. E.; Menon, V. S.; Chang, C.-C.; Czajkowski, G.; Myers, C.; Trefethen, L. N., MultiMATLAB: MATLAB on multiple processors, Technical Report (1996), Cornell University
[79] Hudak, D. E.; Ludban, N.; Gadepally, V.; Krishnamurthy, A., Developing a computational science IDE for HPC systems, Third International Workshop on Software Engineering for High Performance Computing Applications (SE-HPC’07), 1-5 (2007), IEEE
[80] Luszczek, P., Parallel programming in MATLAB, Int. J. High Perform. Comput. Appl., 23, 3, 277-283 (2009)
[81] Ray, T.; Liew, K. M., Society and civilization: an optimization algorithm based on the simulation of social behavior, IEEE Trans. Evol. Comput., 7, 4, 386-396 (2003)
[82] A. Hedar, Test functions for unconstrained global optimization, 2005, (http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO.htm) Online; accessed: 2017-03-22.
[83] Liang, J. J.; Runarsson, T. P.; Clerc, M.; Suganthan, P. N.; Coello, C. A.C.; Deb, K., Problem definitions and evaluation criteria for the CEC 2006 special session on constrained real-parameter optimization, 1-24 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.