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.     

A new filled function algorithm for constrained global optimization problems

A new filled function with one parameter is proposed for solving constrained global optimization problems without the coercive condition, in which the filled function contains neither exponential term nor fractional term and is easy to be calculated. A corresponding filled function algorithm is established based on analysis of the properties of the filled function. At last, we perform numerical experiments on some typical test problems using the algorithm and the detailed numerical results show that the algorithm is effective.     

A filled function method for constrained global optimization

In this paper, a filled function method for solving constrained global optimization problems is proposed. A filled function is proposed for escaping the current local minimizer of a constrained global optimization problem by combining the idea of filled function in unconstrained global optimization and the idea of penalty function in constrained optimization. Then a filled function method for obtaining a global minimizer or an approximate global minimizer of the constrained global optimization problem is presented. Some numerical results demonstrate the efficiency of this global optimization method for solving constrained global optimization problems.     

A new constructing auxiliary function method for global optimization

A new auxiliary function method based on the idea which executes a two-stage deterministic search for global optimization is proposed. Specifically, a local minimum of the original function is first obtained, and then a stretching function technique is used to modify the objective function with respect to the obtained local minimum. The transformed function stretches the function values higher than the obtained minimum upward while it keeps the ones with lower values unchanged. Next, an auxiliary function is constructed on the stretched function, which always descends in the region where the function values are higher than the obtained minimum, and it has a stationary point in the lower area. We optimize the auxiliary function and use the found stationary point as the starting point to turn to the first step to restart the search. Repeat the procedure until termination. A theoretical analysis is also made. The main feature of the new method is that it relaxes significantly the requirements for the parameters. Numerical experiments on benchmark functions with different dimensions (up to 50) demonstrate that the new algorithm has a more rapid convergence and a higher success rate, and can find the solutions with higher quality, compared with some other existing similar algorithms, which is consistent with the analysis in theory.     

A new filled function method for unconstrained global optimization

In this paper, a new filled function which has better properties is proposed for identifying a global minimum point for a general class of nonlinear programming problems within a closed bounded domain. An algorithm for unconstrained global optimization is developed from the new filled function. Theoretical and numerical properties of the proposed filled function are investigated. The implementation of the algorithm on seven test problems is reported with satisfactory numerical results.     

A new global optimization approach for convex multiplicative programming

In this paper, by solving the relaxed quasiconcave programming problem in outcome space, a new global optimization algorithm for convex multiplicative programming is presented. Two kinds of techniques are employed to establish the algorithm. The first one is outer approximation technique which is applied to shrink relaxation area of quasiconcave programming problem and to compute appropriate feasible points and to raise the capacity of bounding. And the other one is branch and bound technique which is used to guarantee global optimization. Some numerical results are presented to demonstrate the effectiveness and feasibility of the proposed algorithm.     

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 particle swarm pattern search method for bound constrained global optimization

In this paper we develop, analyze, and test a new algorithm for the global minimization of a function subject to simple bounds without the use of derivatives. The underlying algorithm is a pattern search method, more specifically a coordinate search method, which guarantees convergence to stationary points from arbitrary starting points. In the optional search phase of pattern search we apply a particle swarm scheme to globally explore the possible nonconvexity of the objective function. Our extensive numerical experiments showed that the resulting algorithm is highly competitive with other global optimization methods also based on function values. Support for Luís N. Vicente was provided by Centro de Matemática da Universidade de Coimbra and by FCT under grant POCI/MAT/59442/2004.     

Unified theory of augmented Lagrangian methods for constrained global optimization

We classify in this paper different augmented Lagrangian functions into three unified classes. Based on two unified formulations, we construct, respectively, two convergent augmented Lagrangian methods that do not require the global solvability of the Lagrangian relaxation and whose global convergence properties do not require the boundedness of the multiplier sequence and any constraint qualification. In particular, when the sequence of iteration points does not converge, we give a sufficient and necessary condition for the convergence of the objective value of the iteration points. We further derive two multiplier algorithms which require the same convergence condition and possess the same properties as the proposed convergent augmented Lagrangian methods. The existence of a global saddle point is crucial to guarantee the success of a dual search. We generalize in the second half of this paper the existence theorems for a global saddle point in the literature under the framework of the unified classes of augmented Lagrangian functions.     

A new hybrid method for solving global optimization problem

In this paper we present a new hybrid method, called the SASP method. The purpose of this method is the hybridization of the simulated annealing (SA) with the descent method, where we estimate the gradient using simultaneous perturbation. Firstly, the new hybrid method finds a local minimum using the descent method, then SA is executed in order to escape from the currently discovered local minimum to a better one, from which the descent method restarts a new local search, and so on until convergence.The new hybrid method can be widely applied to a class of global optimization problems for continuous functions with constraints. Experiments on 30 benchmark functions, including high dimensional functions, show that the new method is able to find near optimal solutions efficiently. In addition, its performance as a viable optimization method is demonstrated by comparing it with other existing algorithms. Numerical results improve the robustness and efficiency of the method presented.     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

A convexification method for a class of global optimization problems with applications to reliability optimization

A convexification method is proposed for solving a class of global optimization problems with certain monotone properties. It is shown that this class of problems can be transformed into equivalent concave minimization problems using the proposed convexification schemes. An outer approximation method can then be used to find the global solution of the transformed problem. Applications to mixed-integer nonlinear programming problems arising in reliability optimization of complex systems are discussed and satisfactory numerical results are presented.     

Tight convex underestimators for {{\mathcal C}^2}-continuous problems: I. univariate functions

A novel method for the convex underestimation of univariate functions is presented in this paper. The method is based on a piecewise application of the well-known αBB underestimator, which produces an overall underestimator that is piecewise convex. Subsequently, two algorithms are used to identify the linear segments needed for the construction of its -continuous convex envelope, which is itself a valid convex underestimator of the original function. The resulting convex underestimators are very tight, and their tightness benefits from finer partitioning of the initial domain. It is theoretically proven that there is always some finite level of partitioning for which the method yields the convex envelope of the function of interest. The method was applied on a set of univariate test functions previously presented in the literature, and the results indicate that the method produces convex underestimators of high quality in terms of both lower bound and tightness over the whole domain under consideration.     

Bayesian approach to global optimization and application to multiobjective and constrained problems

In this paper, the Bayesian methods of global optimization are considered. They provide the minimal expected deviation from the global minimum. It is shown that, using the Bayesian methods, the asymptotic density of calculations of the objective function is much greater around the point of global minimum. The relation of this density to the parameters of the method and to the function is defined.Algorithms are described which apply the Bayesian methods to problems with linear and nonlinear constraints. The Bayesian approach to global multiobjective optimization is defined. Interactive procedures and reduction of multidimensional data in the case of global optimization are discussed.     

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 filled function method with one parameter for unconstrained global optimization

The filled function method is considered as an efficient approach to solve the global optimization problems. In this paper, a new filled function method is proposed. Its main idea is as follows: a new continuously differentiable filled function with only one parameter is constructed for unconstrained global optimization when a minimizer of the objective function is found, then a minimizer of the filled function will be found in a lower basin of the objective function, thereafter, a better minimizer of the objective function will be found. The above process is repeated until the global optimal solution is found. The numerical experiments show the efficiency of the proposed filled function method.     

A global optimization method for the molecular replacement problem in X-ray crystallography

The primary technique for determining the three-dimensional structure of a protein molecule is X-ray crystallography, from which the molecular replacement (MR) problem often arises as a critical step. The MR problem is a global optimization problem to locate an optimal position of a model protein so that at this position the model will produce calculated intensities closest to those observed from an X-ray crystallography experiment involving a protein with unknown but similar atomic structure. Improving the applicability and robustness of MR methods is an important research topic because commonly used traditional MR methods, though often successful, have their limitations in solving difficult problems.We introduce a new global optimization strategy that combines a coarse-grid search, using a surrogate function, with extensive multi-start local optimization. A new MR code, called SOMoRe, based on this strategy is developed and tested on four realistic problems, including two difficult problems that traditional MR codes failed to solve directly. SOMoRe was able to solve each test problem without any complication, and SOMoRe solved an MR problem using a less complete model than the models required by three other programs. These results indicate that the new method is promising and should enhance the applicability and robustness of the MR methodology.     

Computational comparison of two methods for constrained global optimization

For constrained concave global minimization problems, two very different solution techniques have been investigated. The first such method is a stochastic mulitstart approach which typically finds, with high probability, all local minima for the problem. The second method is deterministic and guarantees a global minimum solution to within any user specified tolerance. It is the purpose of this paper to make a careful comparison of these two methods on a range of test problems using separable concave objectives over compact polyhedral sets, and to investigate in this way the advantages and disadvantages of each method. A direct computational comparison, on the same set of over 140 problems, is presented.     

A review of recent advances in global optimization

This paper presents an overview of the research progress in deterministic global optimization during the last decade (1998–2008). It covers the areas of twice continuously differentiable nonlinear optimization, mixed-integer nonlinear optimization, optimization with differential-algebraic models, semi-infinite programming, optimization with grey box/nonfactorable models, and bilevel nonlinear optimization.     

基于随机搜索的一个约束优化问题的全局收敛算法

讨论了具有一般约束的全局优化问题,给出该问题的一个随机搜索算法,证明了该算法依概率1收敛到问题的全局最优解．数值结果显示该方法是有效的．