On a new stochastic global optimization algorithm based on censored observations

In this paper a new algorithm is proposed for global optimization problems. The main idea is that of modifying a standard clustering approach by sequentially sampling the objective function while adaptively deciding an appropriate sample size. Theoretical as well as computational results are presented.     

多点收缩混沌优化方法及全局收敛性证明

针对目前混沌优化算法在选取局部搜索空间时的盲目性,提出一种具有自适应调节局部搜索空间能力的多点收缩混沌优化方法.该方法在当前搜索空间搜索时保留多个较好搜索点,之后利用这些点来确定之后的局部搜索空间,以达到对不同的函数和当前搜索空间内已进行搜索次数的自适应效果.给出了该算法以概率1收敛的证明.仿真结果表明该算法有效的提高了混沌优化算法的性能,改善了混沌算法的实用性.     

On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems

In this paper, we analyse the convergence rate of the sequence of objective function values of a primal-dual proximal-point algorithm recently introduced in the literature for solving a primal convex optimization problem having as objective the sum of linearly composed infimal convolutions, nonsmooth and smooth convex functions and its Fenchel-type dual one. The theoretical part is illustrated by numerical experiments in image processing.     

On a smoothed penalty-based algorithm for global optimization

This paper presents a coercive smoothed penalty framework for nonsmooth and nonconvex constrained global optimization problems. The properties of the smoothed penalty function are derived. Convergence to an \(\varepsilon \)-global minimizer is proved. At each iteration k, the framework requires the \(\varepsilon ^{(k)}\)-global minimizer of a subproblem, where \(\varepsilon ^{(k)} \rightarrow \varepsilon \). We show that the subproblem may be solved by well-known stochastic metaheuristics, as well as by the artificial fish swarm (AFS) algorithm. In the limit, the AFS algorithm convergence to an \(\varepsilon ^{(k)}\)-global minimum of the real-valued smoothed penalty function is guaranteed with probability one, using the limiting behavior of Markov chains. In this context, we show that the transition probability of the Markov chain produced by the AFS algorithm, when generating a population where the best fitness is in the \(\varepsilon ^{(k)}\)-neighborhood of the global minimum, is one when this property holds in the current population, and is strictly bounded from zero when the property does not hold. Preliminary numerical experiments show that the presented penalty algorithm based on the coercive smoothed penalty gives very competitive results when compared with other penalty-based methods.     

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

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

On the convergence of global methods in multiextremal optimization

A general class of derivative-free optimization procedures is presented including the corresponding convergence theory. This theory turns out to be very constructive, in the sense that the convergence conditions not only can be verified easily for many existing algorithms, but also allow one to construct new procedures. It is shown that popular methods such as branch-and-bound concepts, Pintér's general class of procedures, the algorithms of Pijavskii, Shubert, and Mladineo, and the approach of Zheng and Galperin can not only be subsumed under this class of methods, but also partly be improved by regarding them within the framework presented.     

Study of multiscale global optimization based on parameter space partition

Inverse problems in geophysics are usually described as data misfit minimization problems, which are difficult to solve because of various mathematical features, such as multi-parameters, nonlinearity and ill-posedness. Local optimization based on function gradient can not guarantee to find out globally optimal solutions, unless a starting point is sufficiently close to the solution. Some global optimization methods based on stochastic searching mechanisms converge in the limit to a globally optimal solution with probability 1. However, finding the global optimum of a complex function is still a great challenge and practically impossible for some problems so far. This work develops a multiscale deterministic global optimization method which divides definition space into sub-domains. Each of these sub-domains contains the same local optimal solution. Local optimization methods and attraction field searching algorithms are combined to determine the attraction basin near the local solution at different function smoothness scales. With Multiscale Parameter Space Partition method, all attraction fields are to be determined after finite steps of parameter space partition, which can prevent redundant searching near the known local solutions. Numerical examples demonstrate the efficiency, global searching ability and stability of this method.     

求解凸规划及鞍点问题定制的PPA 算法及其收敛速率

线性约束的凸优化问题和鞍点问题的一阶最优性条件是一个单调变分不等式. 在变分不等式框架下求解这些问题, 选取适当的矩阵G, 采用G- 模下的PPA 算法, 会使迭代过程中的子问题求解变得相当容易. 本文证明这类定制的PPA 算法的误差界有1/k 的收敛速率.     

A filter trust-region algorithm for unconstrained optimization with strong global convergence properties

We present a new filter trust-region approach for solving unconstrained nonlinear optimization problems making use of the filter technique introduced by Fletcher and Leyffer to generate non-monotone iterations. We also use the concept of a multidimensional filter used by Gould et?al. (SIAM J. Optim. 15(1):17?C38, 2004) and introduce a new filter criterion showing good properties. Moreover, we introduce a new technique for reducing the size of the filter. For the algorithm, we present two different convergence analyses. First, we show that at least one of the limit points of the sequence of the iterates is first-order critical. Second, we prove the stronger property that all the limit points are first-order critical for a modified version of our algorithm. We also show that, under suitable conditions, all the limit points are second-order critical. Finally, we compare our algorithm with a natural trust-region algorithm and the filter trust-region algorithm of Gould et al. on the CUTEr unconstrained test problems Gould et?al. in ACM Trans. Math. Softw. 29(4):373?C394, 2003. Numerical results demonstrate the efficiency and robustness of our proposed algorithms.     

On the convergence rate of the simulated annealing algorithm

The convergence rate of the simulated annealing algorithm is examined. It is shown that, if the objective function is nonsingular, then the number of its evaluations required to obtain the desired accuracy ɛ in the solution can be a slowly (namely, logarithmically) growing function as ɛ approaches zero.     

On the superlinear convergence of a trust region algorithm for nonsmooth optimization

It is proved that the second order correction trust region algorithm of Fletcher [5] ensures superlinear convergence if some mild conditions are satisfied.     

The convergence rate of a regularized ranking algorithm

In this paper, we investigate the generalization performance of a regularized ranking algorithm in a reproducing kernel Hilbert space associated with least square ranking loss. An explicit expression for the solution via a sampling operator is derived and plays an important role in our analysis. Convergence analysis for learning a ranking function is provided, based on a novel capacity independent approach, which is stronger than for previous studies of the ranking problem.     

Convergence rates of a global optimization algorithm

Second order conditions for the (pseudo-) convexity of a function restricted to an affine subspace are obtained by extending those already known for functions on ⁿ . These results are then used to analyse the (pseudo-) convexity of potential functions of the type introduced by Karmarkar.This research was completed while the first author was on sabbatical leave at the Département d'Informatiques et de Recherche Opérationelle, Université de Montréal, and supported by NSERC (grant Q015807). This research was also supported by NSERC (grants A8312 and A5408) and la Coopération franco-québécoise (project 20-02-13).     

On the convergence rate of the Markov homogeneous monotone optimization method

An estimate of the convergence rate of some homogeneous Markov monotone random search optimization algorithms is obtained.     

A counterexample to a global optimization algorithm

A counterexample to an algorithm of Dien (1988) for solving a minimization problem with a quasiconcave objective function and both linear and a reverse-convex constraint shows that this algorithm needn't lead to a solution of the given problem.     

Global convergence rate analysis of unconstrained optimization methods based on probabilistic models

Mathematical Programming - We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain...     

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.     

Convergence qualification of adaptive partition algorithms in global optimization

Following the presentation of a general partition algorithm scheme for seeking the globally best solution in multiextremal optimization problems, necessary and sufficient convergence conditions are formulated, in terms of respectively implied or postulated properties of the partition operator. The convergence results obtained are pertinent to a number of deterministic algorithms in global optimization, permitting their diverse modifications and generalizations.     

A partition-based global optimization algorithm

This paper is devoted to the study of partition-based deterministic algorithms for global optimization of Lipschitz-continuous functions without requiring knowledge of the Lipschitz constant. First we introduce a general scheme of a partition-based algorithm. Then, we focus on the selection strategy in such a way to exploit the information on the objective function. We propose two strategies. The first one is based on the knowledge of the global optimum value of the objective function. In this case the selection strategy is able to guarantee convergence of every infinite sequence of trial points to global minimum points. The second one does not require any a priori knowledge on the objective function and tries to exploit information on the objective function gathered during progress of the algorithm. In this case, from a theoretical point of view, we can guarantee the so-called every-where dense convergence of the algorithm.