Transformation of Quasiconvex Functions to Eliminate Local Minima

Quasiconvex functions present some difficulties in global optimization, because their graph contains “flat parts”; thus, a local minimum is not necessarily the global minimum. In this paper, we show that any lower semicontinuous quasiconvex function may be written as a composition of two functions, one of which is nondecreasing, and the other is quasiconvex with the property that every local minimum is global minimum. Thus, finding the global minimum of any lower semicontinuous quasiconvex function is equivalent to finding the minimum of a quasiconvex function, which has no local minima other than its global minimum. The construction of the decomposition is based on the notion of “adjusted sublevel set.” In particular, we study the structure of the class of sublevel sets, and the continuity properties of the sublevel set operator and its corresponding normal operator.     

A successive descent algorithm over a system of local minima

A successive descent algorithm over a system of local minima has been developed to find the global minimum of a function of many variables defined on a simply connected compact set. If the number of local minima is finite and a bound on the global minimum is given, the algorithm finds the global minimum in finitely many steps. Test examples are presented. Translated from Prikladnaya Matematika i Informatika, No. 30, pp. 46–54, 2008.     

Exclusion regions for optimization problems

Branch and bound methods for finding all solutions of a global optimization problem in a box frequently have the difficulty that subboxes containing no solution cannot be easily eliminated if they are close to the global minimum. This has the effect that near each global minimum, and in the process of solving the problem also near the currently best found local minimum, many small boxes are created by repeated splitting, whose processing often dominates the total work spent on the global search. This paper discusses the reasons for the occurrence of this so-called cluster effect, and how to reduce the cluster effect by defining exclusion regions around each local minimum found, that are guaranteed to contain no other local minimum and hence can safely be discarded. In addition, we will introduce a method for verifying the existence of a feasible point close to an approximate local minimum. These exclusion regions are constructed using uniqueness tests based on the Krawczyk operator and make use of first, second and third order information on the objective and constraint functions.     

The classic differential evolution algorithm and its convergence properties

Differential evolution algorithms represent an up to date and efficient way of solving complicated optimization tasks. In this article we concentrate on the ability of the differential evolution algorithms to attain the global minimum of the cost function. We demonstrate that although often declared as a global optimizer the classic differential evolution algorithm does not in general guarantee the convergence to the global minimum. To improve this weakness we design a simple modification of the classic differential evolution algorithm. This modification limits the possible premature convergence to local minima and ensures the asymptotic global convergence. We also introduce concepts that are necessary for the subsequent proof of the asymptotic global convergence of the modified algorithm. We test the classic and modified algorithm by numerical experiments and compare the efficiency of finding the global minimum for both algorithms. The tests confirm that the modified algorithm is significantly more efficient with respect to the global convergence than the classic algorithm.     

Global optimization of a quadratic functional with quadratic equality constraints

In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. While it is obvious that, for a nonempty constraint set, there exists a global minimum cost, a method to determine if a given local solution yields the global minimum cost has not been established. We develop a necessary and sufficient condition that will guarantee that solutions of the optimization problem yield the global minimum cost. This constrained optimization problem occurs naturally in the computation of the phase margin for multivariable control systems. Our results guarantee that numerical routines can be developed that will converge to the global solution for the phase margin.     

Unifying local–global type properties in vector optimization

It is well-known that all local minimum points of a semistrictly quasiconvex real-valued function are global minimum points. Also, any local maximum point of an explicitly quasiconvex real-valued function is a global minimum point, provided that it belongs to the intrinsic core of the function’s domain. The aim of this paper is to show that these “local min–global min” and “local max–global min” type properties can be extended and unified by a single general local–global extremality principle for certain generalized convex vector-valued functions with respect to two proper subsets of the outcome space. For particular choices of these two sets, we recover and refine several local–global properties known in the literature, concerning unified vector optimization (where optimality is defined with respect to an arbitrary set, not necessarily a convex cone) and, in particular, classical vector/multicriteria optimization.     

Inclusion functions and global optimization II

This paper discusses algorithms of Moore, Skelboe, Ichida, Fujii and Hansen for solving the global unconstrained optimization problem. These algorithms have been tried on computers, but a thorough theoretical discussion of their convergence properties has been missing. The discussion was started in part I of this paper (Mathematical Programming 33 (1985) 300–317) where the convergence to the global minimum was studied. The present paper is concerned with the different behaviours of these algorithms when they are used for the determination of global minimum points. The solution sets of the algorithms can be a subset of the set of global minimum points,G, a superset ofG, or exactlyG. The algorithms are applicable to a very general class of functions: functions which are continuous, and have suitable inclusion functions. The number of global minimum points can be infinite.This work was supported by the Deutsche Forschungsgemeinschaft.     

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.     

Iterative Convex Quadratic Approximation for Global Optimization in Protein Docking

An algorithm for finding an approximate global minimum of a funnel shaped function with many local minima is described. It is applied to compute the minimum energy docking position of a ligand with respect to a protein molecule. The method is based on the iterative use of a convex, general quadratic approximation that underestimates a set of local minima, where the error in the approximation is minimized in the L¹ norm. The quadratic approximation is used to generate a reduced domain, which is assumed to contain the global minimum of the funnel shaped function. Additional local minima are computed in this reduced domain, and an improved approximation is computed. This process is iterated until a convergence tolerance is satisfied. The algorithm has been applied to find the global minimum of the energy function generated by the Docking Mesh Evaluator program. Results for three different protein docking examples are presented. Each of these energy functions has thousands of local minima. Convergence of the algorithm to an approximate global minimum is shown for all three examples.     

A global optimization using linear relaxation for generalized geometric programming

Many local optimal solution methods have been developed for solving generalized geometric programming (GGP). But up to now, less work has been devoted to solving global optimization of (GGP) problem due to the inherent difficulty. This paper considers the global minimum of (GGP) problems. By utilizing an exponential variable transformation and the inherent property of the exponential function and some other techniques the initial nonlinear and nonconvex (GGP) problem is reduced to a sequence of linear programming problems. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Test results indicate that the proposed algorithm is extremely robust and can be used successfully to solve the global minimum of (GGP) on a microcomputer.     

一类全局优化问题的线性化方法

本文对带有不定二次约束且目标函数为非凸二次函数的最优化问题提出了一类新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了原规划的松弛线性规划,通过对松弛线性规划可行域的细分以及一系列松弛线性规划的求解过程,得到原问题的全局最优解.我们从理论上证明了算法能收敛到原问题的全局最优解.     

On the convergence of the Baba and Dorea random optimization methods

The Baba and Dorea global minimization methods have been applied to two physical problems. The first one is that of finding the global minimum of the transformer design function of six variables subject to constraints. The second one is the problem of fitting the orbit of a satellite using a set of observations. The latter problem is reduced to that of finding the global minimum of the sum of the squares of the differences between the observed values of the azimuth, elevation, and range at certain intervals of time from the epoch and the computed values of the azimuth, elevation, and range at the same intervals of time. Baba and Dorea established theoretically that the random optimization methods converge to the global minimum with probability one. The numerical experiments carried out for the above two problems show that convergence is very slow for the first problem and is even slower for the second problem. In both cases, it has not been possible to reach the global minimum if the search domains of the variables are wide, even after a very large number of function evaluations.The author thanks the referee for his suggestions on improving the presentation of the paper.     

Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

Nonconvex Piecewise-Quadratic Underestimation for Global Minimization

Motivated by the fact that important real-life problems, such as the protein docking problem, can be accurately modeled by minimizing a nonconvex piecewise-quadratic function, a nonconvex underestimator is constructed as the minimum of a finite number of strictly convex quadratic functions. The nonconvex underestimator is generated by minimizing a linear function on a reverse convex region and utilizes sample points from a given complex function to be minimized. The global solution of the piecewise-quadratic underestimator is known exactly and gives an approximation to the global minimum of the original function. Successive shrinking of the initial search region to which this procedure is applied leads to fairly accurate estimates, within 0.0060%, of the global minima of synthetic nonconvex functions for which the global minima are known. Furthermore, this process can approximate a nonconvex protein docking function global minimum within four-figure relative accuracy in six refinement steps. This is less than half the number of refinement steps required by previous models such as the convex kernel underestimator (Mangasarian et al., Computational Optimization and Applications, to appear) and produces higher accuracy here.     

A simple method to compute economic order quantities

In this note, a simple method by using the arithmetic–geometric-mean-inequality theorem is proposed to computer the global minimum economic order quantities without taking complex differential calculus or using tedious algebraic manipulations. In contrast to (Minner, S., 2007. A note on how to compute economic order quantity without derivatives by cost comparisons. International Journal of Production Economics 105, 293–296; Wee, H.M., Wang, W.T., Chung, C.J., 2009. A modified method to computer economic order quantities without derivatives by cost-difference comparisons. European Journal of Operational Research) based on a local cost minimum initially to derive the solution and then proven it’s the global minimum, the proposed method yields the global minimum cost immediately and explicitly without using the cost comparisons and letting the time horizon to infinity.     

Global Optimization of a Quadratic Functional with Quadratic Equality Constraints, Part 2

In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. It is assumed that the cost functional is positive definite and that the constraints are both feasible and regular (but otherwise they are unrestricted quadratic functions). Thus, the existence of a global constrained minimum is assured. We develop a necessary and sufficient condition that completely characterizes the global minimum cost. Such a condition is of essential importance in iterative numerical methods for solving the constrained minimization problem, because it readily distinguishes between local minima and global minima and thus provides a stopping criterion for the computation. The result is similar to one obtained previously by the authors. In the previous result, we gave a characterization of the global minimum of a constrained quadratic minimization problem in which the cost functional was an arbitrary quadratic functional (as opposed to positive-definite here) and the constraints were at least positive-semidefinite quadratic functions (as opposed to essentially unrestricted here).     

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 Smoothing Method of Global Optimization that Preserves Global Minima

A new smoothing method of global optimization is proposed in the present paper, which prevents shifting of global minima. In this method, smoothed functions are solutions of a heat diffusion equation with external heat source. The source helps to control the diffusion such that a global minimum of the smoothed function is again a global minimum of the cost function. This property, and the existence and uniqueness of the solution are proved using results in theory of viscosity solutions. Moreover, we devise an iterative equation by which smoothed functions can be obtained analytically for a class of cost functions. The effectiveness and potential of our method are then demonstrated with some experimental results.     

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.     

On functions whose local minima are global

In this paper, necessary and sufficient conditions for a local minimum to be global are derived. The main result is that a real function, defined on a subset ofR ⁿ, has the property that every local minimum is global if, and only if, its level sets are lower-semicontinuous point-to-set mappings.