DETERMINISTIC GLOBAL OPTIMIZATION USING THE LIPSCHITZ CONDITION

Yaroslav D. Sergeyev

University of Calabria, Rende, Italy

e-mail:

In this lecture, the global optimization problem of a multidimensional function satisfying the Lipschitz condition over a hyperinterval with an unknownLipschitz constant is considered. It is supposed that the objective functioncan be “black box”, multiextremal, and non-differentiable. It is also assumedthat evaluation of the objective function at a point is a time-consuming operation. Many algorithms for solving this problem have been discussed inliterature. They can be distinguished, for example, by the way of obtainingan information about the Lipschitz constant and by the strategy of exploration of the search domain.

Different exploration techniques based on variousadaptive partition strategies are analyzed. The main attention is dedicatedto diagonal algorithms for solving the stated problem, since they have anumber of attractive theoretical properties and have proved to be efficientin solving applied problems. In these algorithms, the search hyperinterval isadaptively partitioned into smaller hyperintervals and the objective functionis evaluated only at two vertices corresponding to the main diagonal of thegenerated hyperintervals.

It is demonstrated that the traditional diagonal partition strategies donot fulfil the requirements of computational efficiency because of executing many redundant evaluations of the objective function. A new adaptivediagonal partition strategy that allows one to avoid such computational redundancy is described. Some powerful multidimensional global optimizationalgorithms based on the new strategy are introduced. Results of extensivenumerical experiments performed to test the methods proposed demonstratetheir advantages with respect to diagonal algorithms in terms of both number of trials of the objective function and qualitative analysis of the searchdomain, which is characterized by the number of generated hyperintervals.

Selected references

  1. Strongin R.G., Sergeyev Ya.D.Globaloptimizationwithnon-convexconstraints: Sequentialandparallelalgorithms, KluwerAcademicPublishers, Dordrecht,2000, 728 p.
  2. Kvasov D.E., Sergeyev Ya.D. A univariate global search working with a set of Lipschitz constants for the first derivative, Optimization Letters, 2009, Vol. 3, no. 2, pp. 303-318.
  3. Sergeyev Ya.D., Kvasov D.E. Global search based on efficient diagonalpartitions and a set of Lipschitz constants,SIAM J. Optimization,2006,Vol. 16, no. 3, pp. 910–937.
  4. Sergeyev Ya.D. Efficient partition of N-dimensional intervals in the framework of one-point-based algorithms,J. Optimization Theory Applications,2005,Vol. 124, no. 2, pp. 503–510.
  5. Gaviano M., Kvasov D.E., Lera D., Sergeyev Ya.D. Algorithm 829: Software for generation of classes of test functions withknown local and global minima for global optimization,ACM Transactions on Mathematical Software,2003,Vol. 29, no. 4, pp. 469–480.
  6. Sergeyev Ya.D., Pugliese P., Famularo D. Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints,Mathematical Programming,2003,Vol. 96, no. 3, pp. 489–512.
  7. Sergeyev Ya.D., Daponte P., Grimaldi D., Molinaro A.Two methods for solving optimization problems arising in electronicmeasurements and electrical engineering,SIAM J. Optimization,1999,Vol. 10, no. 1, pp. 1–21.
  8. Sergeyev Ya.D. Global one-dimensional optimization using smooth auxiliary functions,Mathematical Programming,1998,Vol. 81, no. 1, pp. 127–146.