Algorithm 829: Software for generation of classes of test functions with known local and global minima for global optimization

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.

REFERENCES

• 1: 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.
• 2: Dixon, L. C. W. and Szegö, G. P., Eds. 1978. Towards Global Optimization. Vol. 2. North-Holland, Amsterdam.
• 3: Francisco Facchinei , Joaquim Júdice , João Soares, Generating box-constrained optimization problems, ACM Transactions on Mathematical Software (TOMS), v.23 n.3, p.443-447, Sept. 1997 [doi>10.1145/275323.275331]
• 4: Christodoulos A. Floudas , Panos M. Pardalos, A collection of test problems for constrained global optimization algorithms, Springer-Verlag New York, Inc., New York, NY, 1990
• 5: 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.
• 6: M. Gaviano , D. Lera, Test Functions with Variable Attraction Regions for GlobalOptimization Problems, Journal of Global Optimization, v.13 n.2, p.207-223, September 1998 [doi>10.1023/A:1008225728209]
• 7: Horst, R. and Pardalos, P. M., Eds. 1995. Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht.
• 8: B Kalantari , J B Rosen, Construction of large-scale global minimum concave quadratic test problems, Journal of Optimization Theory and Applications, v.48 n.2, p.303-313, Feb. 1986 [doi>10.1007/BF00940675]
• 9: B. N. Khoury , P. M. Pardalos , D.-Z. Du, A test problem generator for the Steiner problem in graphs, ACM Transactions on Mathematical Software (TOMS), v.19 n.4, p.509-522, Dec. 1993 [doi>10.1145/168173.168420]
• 10: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 11: Li, Y. and Pardalos, P. M. 1992. Generating quadratic assignement test problems with known optimal permutations. Comp. Optim. Appl. 1, 2, 163--184.
• 12: M. Locatelli, A Note on the Griewank Test Function, Journal of Global Optimization, v.25 n.2, p.169-174, February 2003 [doi>10.1023/A:1021956306041]
• 13: Jorge J. Moré , Burton S. Garbow , Kenneth E. Hillstrom, Testing Unconstrained Optimization Software, ACM Transactions on Mathematical Software (TOMS), v.7 n.1, p.17-41, March 1981 [doi>10.1145/355934.355936]
• 14: K. Moshirvaziri, Construction of test problems for a class of reverse convex programs, Journal of Optimization Theory and Applications, v.81 n.2, p.343-354, May 1994 [doi>10.1007/BF02191668]
• 15: 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.
• 16: Panos M. Pardalos, Generation of large-scale quadratic programs for use as global optimization test problems, ACM Transactions on Mathematical Software (TOMS), v.13 n.2, p.133-137, June 1987 [doi>10.1145/328512.328516]
• 17: Panos M. Pardalos, Construction of test problems in quadratic bivalent programming, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.74-87, March 1991 [doi>10.1145/103147.103156]
• 18: 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.
• 19: Schittkowski, K. 1980. Nonlinear Programming Codes. Springer Verlag, Berlin--New York.
• 20: Klaus Schittkowski, More test examples for nonlinear programming codes, Springer-Verlag New York, Inc., New York, NY, 1987
• 21: Schoen, F. 1993. A wide class of test functions for global optimization. J. Global Optimizat. 3, 133--137.
• 22: Sung, Y. Y. and Rosen, J. B. 1982. Global minimum test problem construction. Math. Progr. 24, 353--355.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Global optimization, known local minima, test problems generation