On using estimates of Lipschitz constants in global optimization

Several authors have proposed estimating Lipschitz constants in global optimization by a multiple of the largest slope (in absolute value) between successive evaluation points. A class of univariate functions is exhibited for which the global optimum will be missed when using such a procedure, even if the multiple is arbitrarily large.Research of the first and third authors was supported by AFOSR Grants 0271 and 0066 to Rutgers University. Research of the second author was supported by NSERC Grant GP0036426 and FCAR Grant 90NC0305.This research was done while the first author was Professor and the third author was Graduate Student at RUTCOR, Rutgers University.     

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.     

Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints

In this paper, Lipschitz univariate constrained global optimization problems where both the objective function and constraints can be multiextremal are considered. The constrained problem is reduced to a discontinuous unconstrained problem by the index scheme without introducing additional parameters or variables. A Branch-and-Bound method that does not use derivatives for solving the reduced problem is proposed. The method either determines the infeasibility of the original problem or finds lower and upper bounds for the global solution. Not all the constraints are evaluated during every iteration of the algorithm, providing a significant acceleration of the search. Convergence conditions of the new method are established. Extensive numerical experiments are presented.     

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.     

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.     

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 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.     

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.     

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.     

A parallel method for finding the global minimum of univariate functions

We describe a new parallel method for solving global optimization problems. The formulation of the decision rules of this method is presented. We examine convergence conditions of the proposed algorithm and establish conditions which guarantee a considerable speedup with respect to the sequential version of the algorithm. We also present some numerical experiments executed on Alliant FX/80 for one class of multiextremal functions.The authors are greatly indebted to R. G. Strongin who stimulated the fulfillment of this research. They also would like to thank the anonymous referees for their useful suggestions.The research of the first author was partially supported by Grant 9494/NC/89 from the Italian Government under the Italian-Soviet Agreement about the Cultural and Scientific Exchange in 1990–1991. He thanks the Systems Department, University of Calabria, where he was a Visitor.     

A global optimization procedure for the location of a median line in the three-dimensional space

A global optimization procedure is proposed to find a line in the Euclidean three-dimensional space which minimizes the sum of distances to a given finite set of three-dimensional data points.Although we are using similar techniques as for location problems in two dimensions, it is shown that the problem becomes much harder to solve. However, a problem parameterization as well as lower bounds are suggested whereby we succeeded in solving medium-size instances in a reasonable amount of computing time.     

A new global optimization method for univariate constrained twice-differentiable NLP problems

In this paper, a new global optimization method is proposed for an optimization problem with twice-differentiable objective and constraint functions of a single variable. The method employs a difference of convex underestimator and a convex cut function, where the former is a continuous piecewise concave quadratic function, and the latter is a convex quadratic function. The main objectives of this research are to determine a quadratic concave underestimator that does not need an iterative local optimizer to determine the lower bounding value of the objective function and to determine a convex cut function that effectively detects infeasible regions for nonconvex constraints. The proposed method is proven to have a finite ε-convergence to locate the global optimum point. The numerical experiments indicate that the proposed method competes with another covering method, the index branch-and-bound algorithm, which uses the Lipschitz constant.     

A Metropolis algorithm combined with Hooke-Jeeves local search method applied to global optimization

A hybridization of a recently introduced Metropolis algorithm named the Particle Collision Algorithm (PCA) and the Hooke-Jeeves local search method is applied to a testbed of global optimization functions and to real-world chemical equilibrium nonlinear systems. The results obtained by this method, called HJPCA, are compared against those achieved by two state-of-the-art global optimization methods, C-GRASP and GLOBAL. HJPCA performs better than both algorithms, thus demonstrating its potential for other applications.     

A search technique for global optimization in a chaotic environment

We describe a new algorithm which uses the trajectories of a discrete dynamical system to sample the domain of an unconstrained objective function in search of global minima. The algorithm is unusually adept at avoiding nonoptimal local minima and successfully converging to a global minimum. Trajectories generated by the algorithm for objective functions with many local minima exhibit chaotic behavior, in the sense that they are extremely sensitive to changes in initial conditions and system parameters. In this context, chaos seems to have a beneficial effect: failure to converge to a global minimum from a given initial point can often be rectified by making arbitrarily small changes in the system parameters.     

Lipschitz properties of the scalarization function and applications

The scalarization functions were used in vector optimization for a long period. Similar functions were introduced and used in economics under the name of shortage function or in mathematical finance under the name of (convex or coherent) measures of risk. The main aim of this article is to study Lipschitz continuity properties of such functions and to give some applications for deriving necessary optimality conditions for vector optimization problems using the Mordukhovich subdifferential.     

满足递推式紧集的Lipschitz等价性

设紧集U满足一个不交并递推式,U=(rU+(?))∪U_1.证明了若U_1与一个满足强分离条件的自相似集T Lipschitz等价,则U与T也是Lipschitz等价.并举例说明定理在自相似并集间的Lipschitz等价中的应用.     

A novel three-phase trajectory informed search methodology for global optimization

A new deterministic method for solving a global optimization problem is proposed. The proposed method consists of three phases. The first phase is a typical local search to compute a local minimum. The second phase employs a discrete sup-local search to locate a so-called sup-local minimum taking the lowest objective value among the neighboring local minima. The third phase is an attractor-based global search to locate a new point of next descent with a lower objective value. The simulation results through well-known global optimization problems are shown to demonstrate the efficiency of the proposed method.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

A multi-start global minimization algorithm with dynamic search trajectories

A new multi-start algorithm for global unconstrained minimization is presented in which the search trajectories are derived from the equation of motion of a particle in a conservative force field, where the function to be minimized represents the potential energy. The trajectories are modified to increase the probability of convergence to a comparatively low local minimum, thus increasing the region of convergence of the global minimum. A Bayesian argument is adopted by which, under mild assumptions, the confidence level that the global minimum has been attained may be computed. When applied to standard and other test functions, the algorithm never failed to yield the global minimum.The first author wishes to thank Prof. M. Levitt of the Department of Chemical Physics of the Weizmann Institute of Science for suggesting this line of research and also Drs. T. B. Scheffler and E. A. Evangelidis for fruitful discussions regarding Conjecture 2.1. He also acknowledges the exchange agreement award received from the National Council for Research and Development in Israel and the Council for Scientific and Industrial Research in South Africa, which made possible the visit to the Weizmann Institute where this work was initiated.     

A one-dimensional local tuning algorithm for solving GO problems with partially defined constraints

Lipschitz one-dimensional constrained global optimization (GO) problems where both the objective function and constraints can be multiextremal and non-differentiable are considered in this paper. Problems, where the constraints are verified in a priori given order fixed by the nature of the problem are studied. Moreover, if a constraint is not satisfied at a point, then the remaining constraints and the objective function can be undefined at this point. The constrained problem is reduced to a discontinuous unconstrained problem by the index scheme without introducing additional parameters or variables. A new geometric method using adaptive estimates of local Lipschitz constants is introduced. The estimates are calculated by using the local tuning technique proposed recently. Numerical experiments show quite a satisfactory performance of the new method in comparison with the penalty approach and a method using a priori given Lipschitz constants.This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, PRIN 2005017083-002, and RFBR 04-01-00455-a. The authors would like to thank anonymous referees for their subtle suggestions.