Marco Gaviano
Abstract
A procedure for generating non-differentiable, continuously differentiable, and twice continuously differentiable classes of test functions for multiextremal multidimensional box-constrained global optimization is presented. Each test class consists of 100 functions. Test functions are generated by defining a convex quadratic function systematically distorted by polynomials in order to introduce local minima. To determine a class, the user defines the following parameters: (i) problem dimension, (ii) number of local minima, (iii) value of the global minimum, (iv) radius of the attraction region of the global minimizer, (v) distance from the global minimizer to the vertex of the quadratic function. Then, all other necessary parameters are generated randomly for all 100 functions of the class. Full information about each test function including locations and values of all local minima is supplied to the user. Partial derivatives are also generated where possible.
Supplemental Material
Available for Download
Software for Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization
- Ali, M. M., Khompatraporn, C., and Zabinsky, Z. B. To appear. A numerical evaluation of several global optimization algorithms on selected benchmark test problems. J. Global Optimizat. Google Scholar
- Dixon, L. C. W. and Szegö, G. P., Eds. 1978. Towards Global Optimization. Vol. 2. North-Holland, Amsterdam.Google Scholar
- Facchinei, F., Júdice, J., and Soares, J. 1997. Generating box-constrained optimization problems. ACM Trans. Math. Soft. 23, 3 (Sept.), 443--447. Google Scholar
- Floudas, C. A. and Pardalos, P. M. 1990. A collection of test problems for constrained global optimization algorithms. In Lecture Notes in Computer Science, G. Goos and J. Hartmanis, Eds. Vol. 455. Springer Verlag, Berlin--New York. Google Scholar
- Floudas, C. A., Pardalos, P. M., Adjiman, C., Esposito, W., Gümüs, Z., Harding, S., Klepeis, J., Meyer, C., and Schweiger, C. 1999. Handbook of Test Problems in Local and Global Optimization. Kluwer Academic Publishers, Dordrecht.Google Scholar
- Gaviano, M. and Lera, D. 1998. Test functions with variable attraction regions for global optimization problems. J. Global Optimizat. 13, 2 (Sept.), 207--223. Google Scholar
- Horst, R. and Pardalos, P. M., Eds. 1995. Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht.Google Scholar
- Kalantari, B. and Rosen, J. B. 1986. Construction of large-scale global minimum concave quadratic test problems. J. Optim. Theory Appl. 48, 2, 303--313. Google Scholar
- Khoury, B. N., Pardalos, P. M., and Du, D.-Z. 1993. A test problem generator for the Steiner problem in graphs. ACM Trans. Math. Soft. 19, 4 (Dec.), 509--522. Google Scholar
- Knuth, D. 1997. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, third ed. Addison-Wesley, Reading, Massachusetts. Google Scholar
- Li, Y. and Pardalos, P. M. 1992. Generating quadratic assignement test problems with known optimal permutations. Comp. Optim. Appl. 1, 2, 163--184.Google Scholar
- Locatelli, M. 2003. A note on the Griewank test function. J. Global Optimizat. 25, 2 (Feb.), 169--174. Google Scholar
- Moré, J., Garbow, B., and Hillstrom, K. 1981. Testing unconstrained optimization software. ACM Trans. Math. Soft. 7, 1 (Mar.), 17--41. Google Scholar
- Moshirvaziri, K. 1994. Construction of test problems for a class of reverse convex programs. J. Optim. Theory Appl. 81, 2, 343--354. Google Scholar
- Moshirvaziri, K., Amouzegar, M. A., and Jacobsen, S. E. 1996. Test problem construction for linear bilevel programming problem. Special Issue: Hierarchical and Bilevel Programming, J. Global Optimizat. 8, 3 (Apr.), 235--244.Google Scholar
- Pardalos, P. M. 1987. Generation of large-scale quadratic programs for use as global optimization test problems. ACM Trans. Math. Soft. 13, 2 (June), 133--137. Google Scholar
- Pardalos, P. M. 1991. Construction of test problems in quadratic bivalent programming. ACM Trans. Math. Soft. 17, 1 (Mar.), 74--87. Google Scholar
- Pintér, J. 2002. Global optimization: Software, test problems, and applications. In Handbook of Global Optimization, P. M. Pardalos and H. E. Romeijn, Eds. Vol. 2. Kluwer Academic Publishers, Dordrecht, 515--569.Google Scholar
- Schittkowski, K. 1980. Nonlinear Programming Codes. Springer Verlag, Berlin--New York.Google Scholar
- Schittkowski, K. 1987. More Test Examples for Nonlinear Programming Codes. Springer Verlag, Berlin--New York. Google Scholar
- Schoen, F. 1993. A wide class of test functions for global optimization. J. Global Optimizat. 3, 133--137.Google Scholar
- Sung, Y. Y. and Rosen, J. B. 1982. Global minimum test problem construction. Math. Progr. 24, 353--355.Google Scholar
Index Terms
- Algorithm 829: Software for generation of classes of test functions with known local and global minima for global optimization
Recommendations
A Derivative-Free Algorithm for Constrained Global Optimization Based on Exact Penalty Functions
Constrained global optimization problems can be tackled by using exact penalty approaches. In a preceding paper, we proposed an exact penalty algorithm for constrained problems which combines an unconstrained global minimization technique for minimizing ...
Globally-biased Disimpl algorithm for expensive global optimization
Direct-type global optimization algorithms often spend an excessive number of function evaluations on problems with many local optima exploring suboptimal local minima, thereby delaying discovery of the global minimum. In this paper, a globally-biased ...
An Information Global Optimization Algorithm with Local Tuning
We propose an algorithm using only the values of the objective function for solving unconstrained global optimization problems. This algorithm belongs to the class of the information methods introduced by Strongin [Numerical Methods in Multiextremal ...
Comments