Stability Index Method for Global Minimization

The Stability Index Method (SIM) combines stochastic and deterministic algorithms to find global minima of multidimensional functions. The functions may be nonsmooth and may have multiple local minima. The method examines the change of the diameters of the minimizing sets for its stopping criterion. At first, the algorithm uses the uniform random distribution in the admissible set. Then normal random distributions of decreasing variation are used to focus on probable global minimizers. To test the method, it is applied to seven standard test functions of several variables. The computational results show that the SIM is efficient, reliable and robust.The authors thank the referees for valuable suggestions.     

Global Optimization Using Diffusion Perturbations with Large Noise Intensity

This work develops an algorithm for global optimization.The algorithm is of gradient ascent typeand uses random perturbations.In contrast to the annealing type procedurcs,the perturbation noise intensityis large.We demonstrate that by properly varying the noise intensity,approximations to the global maximumcan be achieved.We also show that the expected time to reach the domain of attraction of the global maximum,which can be approximated by the solution of a boundary value problem,is finite.Discrete-time algorithmsare proposed;recursive algorithms with occasional perturbations involving large noise intensity are developed.Numerical examples are provided for illustration.     

Progressive global random search of continuous functions

A sequential random search method for the global minimization of a continuous function is proposed. The algorithm gradually concentrates the random search effort on areas neighboring the global minima. A modification is included for the case that the function cannot be exactly evaluated. The global convergence and the asymptotical optimality of the sequential sampling procedure are proved for both the stochastic and deterministic optimization problem.The research is sponsored in part by the Air Force under Grant AFOSR-72-2371.     

The global weak sharp minima with explicit exponents in polynomial vector optimization problems

In this paper we discuss the global weak sharp minima property for vector optimization problems with polynomial data. Exploiting the imposed polynomial structure together with tools of variational analysis and a quantitative version of ?ojasiewicz’s gradient inequality due to D’Acunto and Kurdyka, we establish the Hölder type global weak sharp minima with explicitly calculated exponents.     

An extension of the entropic perturbation method of linear programming

In this paper, an extended form of the entropic perturbation method of linear programming is given, which can overcome the weakness of the original method - being easy of overflow in computing. Moreover, the global convergence of the gradient algorithm for the method is discussed.     

A natural order in dynamical systems based on Conley–Markov matrices

We introduce a natural order to study properties of dynamical systems, especially their invariant sets. The new concept is based on the classical Conley index theory and transition probabilities among neighborhoods of different invariant sets when the dynamical systems are perturbed by white noises. The transition probabilities can be determined by the Fokker–Planck equation and they form a matrix called a Markov matrix. In the limiting case when the random perturbation is reduced to zero, the Markov matrix recovers the information given by the Conley connection matrix. The Markov matrix also produces a natural order from the least to the most stable invariant sets for general dynamical systems. In particular, it gives the order among the local extreme points if the dynamical system is a gradient-like flow of an energy functional. Consequently, the natural order can be used to determine the global minima for gradient-like systems. Some numerical examples are given to illustrate the Markov matrix and its properties.     

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

Growth of Nanophase Clusters and Potential Energy Minima: Hysteresis, Oscillations, and Phase Transitions

The structures of small Lennard-Jones clusters (local and global minima) in the range n = 30 - 55 atoms are investigated during growth by random atom deposition using Monte Carlo simulations. The cohesive energy, average coordination number, and bond angles are calculated at different temperatures and deposition rates. Deposition conditions which favor thermodynamically stable (global minima) and metastable (local minima) are determined. We have found that the transition from polyicosahedral to quasicrystalline structures during cluster growth exhibits hysteresis at low temperatures. A minimum critical size is required for the evolution of the quasicrystalline family, which is larger than the one predicted by thermodynamics and depends on the temperature and the deposition rate. Oscillations between polyicosahedral and quasicrystalline structures occur at high temperatures in a certain size regime. Implications for the applicability of global optimization techniques to cluster structure determination are also discussed.     

A global optimization algorithm using adaptive random search

A new random-search global optimization is described in which the variance of the step-size distribution is periodically optimized. By searching over a variance range of 8 to 10 decades, the algorithm finds the step-size distribution that yields the best local improvement in the criterion function. The variance search is then followed by a specified number of iterations of local random search where the step-size variance remains fixed. Periodic wide-range searches are introduced to ensure that the process does not stop at a local minimum. The sensitivity of the complete algorithm to various search parameters is investigated experimentally for a specific test problem. The ability of the method to locate global minima is illustrated by an example. The method also displays considerable problem independence, as demonstrated by two large and realistic example problems: (1) the identification of 25 parameters in a nonlinear model of a five-degrees-of-freedom mechanical dynamic system and (2) solution of a 24-parameter inverse problem required to identify a pulse train whose frequency spectrum matched a desired reference spectrum.     

Solving an optimization packing problem of circles and non-convex polygons with rotations into a multiply connected region

This paper deals with the packing problem of circles and non-convex polygons, which can be both translated and rotated into a strip with prohibited regions. Using the Φ-function technique, a mathematical model of the problem is constructed and its characteristics are investigated. Based on the characteristics, a solution approach to the problem is offered. The approach includes the following methods: an optimization method by groups of variables to construct starting points, a modification of the Zoutendijk feasible direction method to search for local minima and a special non-exhaustive search of local minima to find an approximation to a global minimum. A number of numerical results are given. The numerical results are compared with the best known ones.     

DC-GRASP: directing the search on continuous-GRASP

Several papers in the scientific literature use metaheuristics to solve continuous global optimization. To perform this task, some metaheuristics originally proposed for solving combinatorial optimization problems, such as Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search and Simulated Annealing, among others, have been adapted to solve continuous global optimization problems. Proposed by Hirsch et al., the Continuous-GRASP (C-GRASP) is one example of this group of metaheuristics. The C-GRASP is an adaptation of GRASP proposed to solve continuous global optimization problems under box constraints. It is simple to implement, derivative-free and widely applicable method. However, according to Hedar, due to its random construction, C-GRASP may fail to detect promising search directions especially in the vicinity of minima, which may result in a slow convergence. To minimize this problem, in this paper we propose a set of methods to direct the search on C-GRASP, called Directed Continuous-GRASP (DC-GRASP). The proposal is to combine the ability of C-GRASP to diversify the search over the space with some efficient local search strategies to accelerate its convergence. We compare the DC-GRASP with the C-GRASP and other metaheuristics from literature on a set of standard test problems whose global minima are known. Computational results show the effectiveness and efficiency of the proposed methods, as well as their ability to accelerate the convergence of the C-GRASP.     

Convergence of a random optimization method for constrained optimization problems

Matyas' random optimization method (Ref. 1) is applied to the constrained nonlinear minimization problem, and its convergence properties are studied. It is shown that the global minimum can be found with probability one, even if the performance function is multimodal (has several local minima) and even if its differentiability is not ensured.The author would like to thank Professors Y. Sawaragi (Kyoto University), T. Soeda (Tokushima University), and T. Shoman (Tokushima University) for their kind advice.     

On the eigenvalues of the saddle point matrices discretized from Navier–Stokes equations

In this paper, we proposed an implementation of stochastic perturbation of reduced gradient and bisection (SPRGB) method for optimizing a non-convex differentiable function subject to linear equality constraints and non-negativity bounds on the variables. In particular, at each iteration, we compute a search direction by reduced gradient, and optimal line search by bisection algorithm along this direction yields a decrease in the objective value. SPRGB method is desired to establish the global convergence of the algorithm. An implementation and tests of SPRGB algorithm are given, and some numerical results of large-scale problems are presented, which show the efficient of this approach.     

A Combined Topographical Search Strategy with Ellipsometric Application

A comparison deals with the advantages and disadvantages of the classical random-base, exhaustive and gradient searches and presents a precise local search combined global search control strategy including a new, systematic point selection which makes possible the escape from local minima by time. As a demonstration electrochemically etched porous silicon (PS) samples were investigated by spectroscopic ellipsometry (SE). The evaluation process (a global optimisation task) was made in different ways to see the difficulties and the differences among the evaluating possibilities. The new, topographical search (named Gradient Cube search) was compared with some classical methods (Grid search, Random or Monte-Carlo search, and Levenberg-Marquardt gradient search) and with two more complex algorithms (Genetic Algorithms and Simulated Annealing) by evaluating real measurements. The application results prove that the classical methods have difficulties to give enough reliability and precision at the same time in global optimisation tasks if the error surface is hilly. There is therefore a hard need of escaping from local minima, and a need of a systematic evaluation to avoid the uncertainty of random-base evaluation. The Gradient Cube search is an effective, systematic hill-climbing search with high precision and so it can be useful in ellipsometry.     

环面上具有间断梯度的势函数的模拟退火

本文证明了环面上具有间断梯度的势函数的模拟退火过程：dXt=-VU(Xt)dt √2dWt概率收敛到势函数的全局极小集附近。     

求解全局优化问题的填充函数算法

填充函数法是求解多变量、多极值函数全局优化问题的有效方法.这种方法的关键是构造填充函数.本文在无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.     

Linearized perturbation method for stochastic analysis of a rill erosion model

The linearization and correction method (LCM) proposed by He is a simple and effective perturbation technique to solve nonlinear equations. To analyze the random properties of rill erosion model, a new stochastic perturbation technique called linearized perturbation method is developed by combining the traditional stochastic perturbation method with the LCM. Comparisons between the numerical results obtained by the linearized perturbation method and those obtained by Monte Carlo method indicated an excellent agreement. However, the calculation efficiency of the linearized perturbation method is higher.     

Solución de la cinemática directa de la plataforma Gough-Stewart general usando un algoritmo híbrido de optimización

The direct kinematics problem for parallel robots can be stated as follows: given values of the joint variables, the corresponding Cartesian variable values, the pose of the end-effector, must be found. Most of the times the direct kinematics problem involves the solution of a system of non-linear equations. The most efficient methods to solve such kind of equations assume convexity in a cost function which minimum is the solution of the non-linear system. In consequence, the capacity of such methods depends on the knowledge about an starting point which neighboring region is convex, hence the method can find the global minimum. This article propose a method based on probabilistic learning about an adequate starting point for the Dogleg method which assumes local convexity of the function. The proposed method efficiently avoids the local minima, without need of human intervention or apriori knowledge, thus it shows a more robust performance than the simple Dogleg method or other gradient based methods. To demonstrate the performance of the proposed hybrid method, numerical experiments and the respective discussion are presented. The proposal can be extended to other structures of closed-kinematics chains, to the general solution of systems of non-linear equations, and to the minimization of non-linear functions.