On Timonov's algorithm for global optimization of univariate Lipschitz functions

Timonov proposes an algorithm for global maximization of univariate Lipschitz functions in which successive evaluation points are chosen in order to ensure at each iteration a maximal expected reduction of the region of indeterminacy, which contains all globally optimal points. It is shown that such an algorithm does not necessarily converge to a global optimum.     

An algorithm for global optimization of Lipschitz continuous functions

An algorithm is presented which locates the global minimum or maximum of a function satisfying a Lipschitz condition. The algorithm uses lower bound functions defined on a partitioned domain to generate a sequence of lower bounds for the global minimum. Convergence is proved, and some numerical results are presented.     

Efficient domain partitioning algorithms for global optimization of rational and Lipschitz continuous functions

A domain partitioning algorithm for minimizing or maximizing a Lipschitz continuous function is enhanced to yield two new, more efficient algorithms. The use of interval arithmetic in the case of rational functions and the estimates of Lipschitz constants valid in subsets of the domain in the case of others and the addition of local optimization have resulted in an algorithm which, in tests on standard functions, performs well.     

A univariate global search working with a set of Lipschitz constants for the first derivative

In the paper, a global optimization problem is considered where the objective function f (x) is univariate, black-box, and its first derivative f ′(x) satisfies the Lipschitz condition with an unknown Lipschitz constant K. In the literature, there exist methods solving this problem by using an a priori given estimate of K, its adaptive estimates, and adaptive estimates of local Lipschitz constants. Algorithms working with a number of Lipschitz constants for f ′(x) chosen from a set of possible values are not known in spite of the fact that a method working in this way with Lipschitz objective functions, DIRECT, has been proposed in 1993. A new geometric method evolving its ideas to the case of the objective function having a Lipschitz derivative is introduced and studied in this paper. Numerical experiments executed on a number of test functions show that the usage of derivatives allows one to obtain, as it is expected, an acceleration in comparison with the DIRECT algorithm. This research was supported by the RFBR grant 07-01-00467-a and the grant 4694.2008.9 for supporting the leading research groups awarded by the President of the Russian Federation.     

Global optimization of univariate Lipschitz functions: I. Survey and properties

We consider the following global optimization problems for a univariate Lipschitz functionf defined on an interval [a, b]: Problem P: find a globally optimal value off and a corresponding point; Problem P: find a globally-optimal value off and a corresponding point; Problem Q: localize all globally optimal points; Problem Q: find a set of disjoint subintervals of small length whose union contains all globally optimal points; Problem Q: find a set of disjoint subintervals containing only points with a globally-optimal value and whose union contains all globally optimal points.We present necessary conditions onf for finite convergence in Problem P and Problem Q, recall the concepts necessary for a worst-case and an empirical study of algorithms (i.e., those ofpassive and ofbest possible algorithms), summarize and discuss algorithms of Evtushenko, Piyavskii-Shubert, Timonov, Schoen, Galperin, Shen and Zhu, presenting them in a simplified and uniform way, in a high-level computer language. We address in particular the problems of using an approximation for the Lipschitz constant, reducing as much as possible the expected length of the region of indeterminacy which contains all globally optimal points and avoiding remaining subintervals without points with a globally-optimal value. New algorithms for Problems P and Q and an extensive computational comparison of algorithms are presented in a companion paper.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426 and FCAR grant 89EQ4144. We thank N. Paradis for drawing some of the figures.     

Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison

We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem P: find a globally-optimal value off and a corresponding point; Problem Q: find a set of disjoint subintervals of [a, b] containing only points with a globally-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P. In phase I, this algorithm obtains rapidly a solution which is often globally-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves the-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally-optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small, the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for problem Q. A sufficient condition onf is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426, FCAR grant 89EQ4144 and partially by AFOSR grant 0066. We thank Nicole Paradis for her help in drawing the figures.     

Cord-slope form of Taylor's expansion in univariate global optimization

Interval arithmetic and Taylor's formula can be used to bound the slope of the cord of a univariate function at a given point. This leads in turn to bounding the values of the function itself. Computing such bounds for the function, its first and second derviatives, allows the determination of intervals in which this function cannot have a global minimum. Exploiting this information together with a simple branching rule yields an efficient algorithm for global minimization of univariate functions. Computational experience is reported.The first and second authors have been supported by FCAR (Fonds pour la Formation de Chercheurs et l'Aide à la Recherche) Grant 92EQ1048 and AFOSR Grant 90-0008 to Rutgers University. The first author has also been supported by NSERC (Natural Sciences and Engineering Research Council of Canada) Grant to HEC and NSERC Grant GP0105574. The second author has been supported by NSERC Grant GP0036426, FCAR Grant 90NC0305, and a NSF Visiting Professorship for Women in Science at Princeton University. Work of the third author was done in part while he was a graduate student at the Department of Mathematics, Rutgers University, New Brunswick, New Jersey, USA and during a visit to GERAD, June–August 1991.     

A global minimization algorithm for Lipschitz functions

The global optimization problem with and f(x) satisfying the Lipschitz condition , is considered. To solve it a region-search algorithm is introduced. This combines a local minimum algorithm with a procedure that at the ith iteration finds a region S _i where the global minimum has to be searched for. Specifically, by making use of the Lipschitz condition, S _i , which is a sequence of intervals, is constructed by leaving out from S _i-1 an interval where the global minimum cannot be located. A convergence property of the algorithm is given. Further, the ratio between the measure of the initial feasible region and that of the unexplored region may be used as stop rule. Numerical experiments are carried out; these show that the algorithm works well in finding and reducing the measure of the unexplored region.     

Multidimensional Lipschitz global optimization based on efficient diagonal partitions

This is a summary of the author’s PhD thesis, supervised by Yaroslav D. Sergeyev and defended on May 5, 2006, at the University of Rome “La Sapienza”. The thesis is written in English and is available from the author upon request. In this work, the global optimization problem of a multidimensional “black-box” function satisfying the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant is considered. The objective function is assumed hard to evaluate. A new efficient diagonal scheme for constructing fast algorithms for solving this problem is examined and illustrated by developing several powerful global optimization methods. A deep theoretical study is performed which highlights the benefit of the approach introduced over traditionally used diagonal algorithms. Theoretical conclusions are confirmed by results of extensive numerical experiments.      

Lipschitz constants and logarithmic Sobolev inequality

We revisit two results of  [3]; they are a logarithmic Sobolev inequality on Rⁿ${\mathbb{R}}^n$ with Lipschitz constants and an expression of Lipschitz constants as the limit of a functional by the entropy. We have two goals in this paper. The first goal is to clarify when the strict inequality holds in this inequality. The second goal is to investigate the asymptotic behavior of this functional by the Abelian and Tauberian theorems of Laplace transforms.     

An optimal logarithmic Sobolev inequality with Lipschitz constants

In this paper, we give an optimal logarithmic Sobolev inequality on Rn with Lipschitz constants. This inequality is a limit case of the Lp-logarithmic Sobolev inequality of Gentil (2003) [7] as p→∞. As a result of our inequality, we show that if a Lipschitz continuous function f on Rn fulfills some condition, then its Lipschitz constant can be expressed by using the entropy of f. We also show that a hypercontractivity of exponential type occurs in the heat equation on Rn. This is due to the Lipschitz regularizing effect of the heat equation.     

New LP bound in multivariate Lipschitz optimization: Theory and applications

Most numerically promising methods for solving multivariate unconstrained Lipschitz optimization problems of dimension greater than two use rectangular or simplicial branch-and-bound techniques with computationally cheap but rather crude lower bounds.Generalizations to constrained problems, however, require additional devices to detect sufficiently many infeasible partition sets. In this article, a new lower bounding procedure is proposed for simplicial methods yielding considerably better bounds at the expense of two linear programs in each iteration. Moreover, the resulting approach can solve easily linearly constrained problems, since in this case infeasible partition sets are automatically detected by the lower bounding procedure.Finally, it is shown that the lower bounds can be further improved when the method is applied to solve systems of inequalities. Implementation issues, numerical experiments, and comparisons are discussed in some detail.The authors are indebted to the Editor-in-Chief of this journal for his valuable suggestions which have considerably improved the final version of this article.     

Preservation of Lipschitz constants by Bernstein type operators

Summary We obtain preservation inequalities for Lipschitz constants of higher order in simultaneous approximation processes by Bernstein type operators. From such inequalities we derive the preservation of the corresponding Lipschitz spaces.     

Global optimization of Hölder functions

We propose a branch-and-bound framework for the global optimization of unconstrained Hölder functions. The general framework is used to derive two algorithms. The first one is a generalization of Piyavskii's algorithm for univariate Lipschitz functions. The second algorithm, using a piecewise constant upper-bounding function, is designed for multivariate Hölder functions. A proof of convergence is provided for both algorithms. Computational experience is reported on several test functions from the literature.     

Simple global minimization algorithm for one-variable rational functions

Sturm's chain technique for evaluation of a number of real roots of polynomials is applied to construct a simple algorithm for global optimization of polynomials or generally for rational functions of finite global minimal value. The method can be applied both to find the global minimum in an interval or without any constraints. It is shown how to use the method to minimize globally a truncated Fourier series. The results of numerical tests are presented and discussed. The cost of the method scales as the square of the degree of the polynomial.     

Outer approximation algorithm for nondifferentiable optimization problems

It is known that the problem of minimizing a convex functionf(x) over a compact subsetX of ⁿ can be expressed as minimizing max{g(x, y)|y X}, whereg is a support function forf[f(x) g(x, y), for ally X andf(x)=g(x, x)]. Standard outer-approximation theory can then be employed to obtain outer-approximation algorithms with procedures for dropping previous cuts. It is shown here how this methodology can be extended to nonconvex nondifferentiable functions.This research was supported by the Science and Engineering Research Council, UK, and by the National Science Foundation under Grant No. ECS-79-13148.     

Outer approximation algorithm for nondifferentiable optimization problems

Omissions from the list of references of Ref. 1 are corrected.     

A class of test functions for global optimization

We suggest weighted least squares scaling, a basic method in multidimensional scaling, as a class of test functions for global optimization. The functions are easy to code, cheap to calculate, and have important applications in data analysis. For certain data these functions have many local minima. Some characteristic features of the test functions are investigated.This paper was written while the second author was a visiting Professor at Aachen University of Technology, funded by the Deutsche Forschungsgemeinschaft.     

Evaluating Lipschitz Constants for Functions Given by Algorithms

This paper describes an efficient method (O(n)) to evaluate the Lipschitz constant for functions described in some algorithmic language. Considering arithmetical operations as the basis of the algorithmic language and supported by control structures, the rules to evaluate such Lipschitz constants are presented and their correctness is proved. An extension of the method to evaluate Lipschitz constants over interval domains is also presented. Examples are presented, but the effectiveness of the method is doubtful when compared to other approaches, and effective enhancements based on slope evaluations are also explored.     

An improved univariate global optimization algorithm with improved linear lower bounding functions

Recently linear lower bounding functions (LLBF's) were proposed and used to find -global minima. Basically an LLBF over an interval is a linear function which lies below a given function over the interval and matches the function value at one end point. By comparing it with the best function value found, it can be used to eliminate subregions which do not contain -global minima. To develop a more efficient LLBF algorithm, two important issues need to be addressed: how to construct a better LLBF and how to use it efficiently. In this paper, an improved LLBF for factorable functions overn-dimensional boxes is derived, in the sense that the new LLBF is always better than those in [3] for continuously differentiable functions. Exploration of the properties of the LLBF enables us to develop a new LLBF-based univariate global optimization algorithm, which is again better than those in [3]. Numerical results on some standard test functions indicate the high potential of our algorithm.This work was supported in part by VLSI Technology Inc. and Tyecin Systems Inc. through the University of California MICRO proram with grant number 92-024.