Global optimization by random perturbation of the gradient method with a fixed parameter

The paper deals with the global minimization of a differentiable cost function mapping a ball of a finite dimensional Euclidean space into an interval of real numbers. It is established that a suitable random perturbation of the gradient method with a fixed parameter generates a bounded minimizing sequence and leads to a global minimum: the perturbation avoids convergence to local minima. The stated results suggest an algorithm for the numerical approximation of global minima: experiments are performed for the problem of fitting a sum of exponentials to discrete data and to a nonlinear system involving about 5000 variables. The effect of the random perturbation is examined by comparison with the purely deterministic gradient method.     

无约束全局优化的一个可调参数的填充函数

A filled function with adjustable parameters is suggested in this paper for finding a global minimum point of a general class of nonlinear programming problems with a bounded and closed domain. This function has two adjustable parameters. We will discuss the properties of the proposed filled function. Conditions on this function and on the values of parameters are given so that the constructed function has the desired properties of traditional filled function.     

集值映射的切导数与向量优化问题的最优性条件

利用集值映射切导数与半可微概念，给出了无约束与具约束的集值向量优化问题局部真有效解与局部强有效解的最优性条件。     

Difference schemes on uniform grids performed by general discrete operators

Our aim is to set the foundations of a discrete vectorial calculus on uniform n-dimensional grids, that can be easily reformulated on general irregular grids. As a key tool we first introduce the notion of tangent space to any grid node. Then we define the concepts of vector field, field of matrices and inner products on the space of grid functions and on the space of vector fields, mimicking the continuous setting. This allows us to obtain the discrete analogous of the basic first order differential operators, gradient and divergence, whose composition define the fundamental second order difference operator. As an application, we show that all difference schemes, with constant coefficients, for first and second order differential operators with constant coefficients can be seen as difference operators of the form for suitable choices of q, and  . In addition, we characterize special properties of the difference scheme, such as consistency, symmetry and positivity in terms of q, and  .     

An embedding domain approach for a class of 2-d shape optimization problems: mathematical analysis

This contribution combines a shape optimization approach to free boundary value problems of Bernoulli type with an embedding domain technique. A theoretical framework is developed which allows to prove continuous dependence of the primal and dual variables in the resulting saddle point problems with respect to the domain. This ensures the existence of a solution of a related shape optimization problem in a sufficiently large class of admissible domains.     

Asymptotic Properties of Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is a NP-hard combinatorial optimization problem, occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.     

Branch and win: OR tree search algorithms for solving combinatorial optimisation problems

Currently, most combinatorial optimisation problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. We propose Branch and Win, a general formulation for understanding and synthesising the different tree search procedures that have been presented in the literature of operations research as well as in that of artificial intelligence. Several general ideas are also presented, whose application allows designing new hybrid search algorithms, in order to implement the procedure.     

Algorithms for Finite and Semi-Infinite Min–Max–Min Problems Using Adaptive Smoothing Techniques

We develop two implementable algorithms, the first for the solution of finite and the second for the solution of semi-infinite min-max-min problems. A smoothing technique (together with discretization for the semi-infinite case) is used to construct a sequence of approximating finite min-max problems, which are solved with increasing precision. The smoothing and discretization approximations are initially coarse, but are made progressively finer as the number of iterations is increased. This reduces the potential ill-conditioning due to high smoothing precision parameter values and computational cost due to high levels of discretization. The behavior of the algorithms is illustrated with three semi-infinite numerical examples.     

On the Image Regularity Condition

In this paper, we continue the analysis of the image regularity condition (IRC) as introduced in a previous paper where we have proved that IRC implies the existence of generalized Lagrange-John multipliers with first component equal to 1. The term generalized is connected with the fact that the separation (in the image space) is not necessarily linear (when we have classic Lagrange-John multipliers), but it can be also nonlinear. Here, we prove that the IRC guarantees, also in the nondifferentiable case, the fact that 0 is a solution of the first-order homogeneized (linearized) problem obtained by means of the Dini-Hadamard derivatives.     

Finding Robust Solutions Using Local Search

This paper investigates how a local search metaheuristic for continuous optimisation can be adapted so that it finds broad peaks, corresponding to robust solutions. This is relevant in problems in which uncertain or noisy data is present. When using a genetic or evolutionary algorithm, it is standard practice to perturb solutions once before evaluating them, using noise from a given distribution. This approach however, is not valid when using population-less techniques like local search and other heuristics that use local search. For those algorithms to find robust solutions, each solution needs to be perturbed and evaluated several times, and these evaluations need to be combined into a measure of robustness. In this paper, we examine how many of these evaluations are needed to reliably find a robust solution. We also examine the effect of the parameters of the noise distribution. Using a simple tabu search procedure, the proposed approach is tested on several functions found in the literature. This revised version was published online in August 2006 with corrections to the Cover Date.