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.     

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.     

An adaptive stochastic global optimization algorithm for one-dimensional functions

In this paper a new algorithm is proposed, based upon the idea of modeling the objective function of a global optimization problem as a sample path from a Wiener process. Unlike previous work in this field, in the proposed model the parameter of the Wiener process is considered as a random variable whose conditional (posterior) distribution function is updated on-line. Stopping criteria for Bayesian algorithms are discussed and detailed proofs on finite-time stopping are provided.This research has been partially supported by Progetto MURST 40% Metodi di Ottimizzazione per le Decisioni.     

Global and superlinear convergence of an algorithm for one-dimensional minimization of convex functions

This paper studies an algorithm for minimizing a convex function based upon a combination of polyhedral and quadratic approximation. The method was given earlier, but without a good specification for updating the algorithm's curvature matrix. Here, for the case of onedimensional minimization, we provide a specification that insures convergence even in cases where the curvature scalar tends to zero or infinity. Under mild additional assumptions, we show that the convergence is superlinear.     

Robust analysis and global minimization of a class of discontinuous functions (I)

In this paper we define and investigate robust points, sets and functions which will be utilized to study a global minimization problem of a discontinuous function over a disconnected set by an integral approach.The project is supported by the National Natural Science Foundation of China.     

Robust analysis and global minimization of a class of discontinuous functions (II)

In this paper we continue to investigate global minimization problems. An integral approach is applied to treat a global minimization problem of a discontinuous function. With the help of the theory of measure (Q-measure) and integration, optimality conditions of a robust function over a robust set are derived. Algorithms and their implementations for finding global minima are proposed. Numerical tests and applications show that the algorithms are effective.Project supported by the National Natural Science Foundation of China.     

A parallel algorithm for constrained concave quadratic global minimization

The global minimization of large-scale concave quadratic problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of both a concave part (nonlinear variables) and a strictly linear part, which are coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. A linear underestimating function to the concave part of the objective is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and linear underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results are presented for problems with 25 and 50 nonlinear variables and up to 400 linear variables. These results were obtained on a four processor CRAY2 using both sequential and parallel implementations of the algorithm. The average parallel solution time was approximately 15 seconds for problems with 400 linear variables and a relative tolerance of 0.001. For a relative tolerance of 0.1, the average computation time appears to increase only linearly with the number of linear variables.     

A trust region algorithm for minimization of locally Lipschitzian functions

The classical trust region algorithm for smooth nonlinear programs is extended to the nonsmooth case where the objective function is only locally Lipschitzian. At each iteration, an objective function that carries both first and second order information is minimized over a trust region. The term that carries the first order information is an iteration function that may not explicitly depend on subgradients or directional derivatives. We prove that the algorithm is globally convergent. This convergence result extends the result of Powell for minimization of smooth functions, the result of Yuan for minimization of composite convex functions, and the result of Dennis, Li and Tapia for minimization of regular functions. In addition, compared with the recent model of Pang, Han and Rangaraj for minimization of locally Lipschitzian functions using a line search, this algorithm has the same convergence property without assuming positive definiteness and uniform boundedness of the second order term. Applications of the algorithm to various nonsmooth optimization problems are discussed.This author's work was supported in part by the Australian Research Council.This author's work was carried out while he was visiting the Department of Applied Mathematics at the University of New South Wales.     

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.     

Consistency of a myopic Bayesian algorithm for one-dimensional global optimization

A sequential Bayesian method for finding the maximum of a function based on myopically minimizing the expected dispersion of conditional probabilities is described. It is shown by example that an algorithm that generates a dense set of observations need not converge to the correct answer for some priors on continuous functions on the unit interval. For the Brownian motion prior the myopic algorithm is consistent; for any continuous function, the conditional probabilities converge weakly to a point mass at the true maximum.     

A new class of test functions for global optimization

In this paper we propose a new class of test functions for unconstrained global optimization problems. The class depends on some parameters through which the difficulty of the test problems can be controlled. As a basis for future comparison, we propose a selected set of these functions, with increasing difficulty, and some computational experiments with two simple global optimization algorithms.     

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.     

Conical algorithm for the global minimization of linearly constrained decomposable concave minimization problems

In this paper, we are concerned with the linearly constrained global minimization of the sum of a concave function defined on ap-dimensional space and a linear function defined on aq-dimensional space, whereq may be much larger thanp. It is shown that a conical algorithm can be applied in a space of dimensionp + 1 that involves only linear programming subproblems in a space of dimensionp +q + 1. Some computational results are given.This research was accomplished while the second author was a Fellow of the Alexander von Humboldt Foundation, University of Trier, Trier, Germany.     

A parallel algorithm for partially separable non-convex global minimization: Linear constraints

The global minimization of large-scale partially separable non-convex problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of a separable concave part, an unseparated convex part, and a strictly linear part, which are all coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. An important special class of problems which can be reduced to this form are the synomial global minimization problems. Such problems often arise in engineering design, and previous computational methods for such problems have been limited to the convex posynomial case. In the current work, a convex underestimating function to the objective function is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and convex underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results obtained on the four processor Cray 2, both sequentially and in parallel on all four processors, are also presented.     

Approximation algorithm for a class of global optimization problems

In this paper we develop and derive the computational cost of an ${\varepsilon}$ -approximation algorithm for a class of global optimization problems, where a suitably defined composition of some ratio functions is minimized over a convex set. The result extends a previous one about a class of Linear Fractional/Multiplicative problems.     

Decomposition approach for the global minimization of biconcave functions over polytopes

A decomposition approach is proposed for minimizing biconcave functions over polytopes. Important special cases include concave minimization, bilinear and indefinite quadratic programming for which new algorithms result. The approach introduces a new polyhedral partition and combines branch-and-bound techniques, outer approximation, and projection of polytopes in a suitable way.The authors are indebted to two anonymous reviewers for suggestions which have considerably improved this article.     

最小化三个凸函数之和的一个简单原始-对偶算法

提出一个简单的原始-对偶算法求解三个凸函数之和的最小化问题, 其中目标函数包含有梯度李普希兹连续的光滑函数, 非光滑函数和含有复合算子的非光滑函数. 在新方法中, 对偶变量迭代使用预估-矫正的方案. 分析了算法的收敛性和收敛速率. 最后, 数值实验说明了算法的有效性.     

Descent algorithm for a class of convex nondifferentiable functions

We present first an -descent basic method for minimizing a convex minmax problem. We consider first- and second-order information in order to generate the search direction. Preliminarily, we introduce some properties for the second-order information, the subhessian, and its characterization for max functions. The algorithm has -global convergence. Finally, we give a generalization of this algorithm for an unconstrained convex problem having second-order information. In this case, we obtain global -convergence.This research was supported in part by CAPES (Coordinação de Aperfeiçoamento de Pessoal de Nivel Superior) and in part by the IM-COPPE/UFRJ, Brazil. The authors wish to thank Nguyen Van Hien and Jean-Jacques Strodiot for their constructive remarks on an earlier draft of the paper. This work was completed while the first author was with the Department of Mathematics of the Facultés Universitaires de Namur. The authors are also grateful for the helpful comments of two anonymous referees.