Parallel Characteristical Algorithms for Solving Problems of Global Optimization

A class of parallel characteristical algorithms for global optimization ofone-dimensional multiextremal functions is introduced. General convergence andefficiency conditions for the algorithms of the class introduced areestablished. A generalization for the multidimensional case is considered.Examples of parallel characteristical algorithms and numerical experiments arepresented.     

A one-dimensional local tuning algorithm for solving GO problems with partially defined constraints

Lipschitz one-dimensional constrained global optimization (GO) problems where both the objective function and constraints can be multiextremal and non-differentiable are considered in this paper. Problems, where the constraints are verified in a priori given order fixed by the nature of the problem are studied. Moreover, if a constraint is not satisfied at a point, then the remaining constraints and the objective function can be undefined at this point. The constrained problem is reduced to a discontinuous unconstrained problem by the index scheme without introducing additional parameters or variables. A new geometric method using adaptive estimates of local Lipschitz constants is introduced. The estimates are calculated by using the local tuning technique proposed recently. Numerical experiments show quite a satisfactory performance of the new method in comparison with the penalty approach and a method using a priori given Lipschitz constants.This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, PRIN 2005017083-002, and RFBR 04-01-00455-a. The authors would like to thank anonymous referees for their subtle suggestions.     

Global Optimization: Fractal Approach and Non-redundant Parallelism

More and more optimization problems arising in practice can not be solved by traditional optimization techniques making strong suppositions about the problem (differentiability, convexity, etc.). This happens because very often in real-life problems both the objective function and constraints can be multiextremal, non-differentiable, partially defined, and hard to be evaluated. In this paper, a modern approach for solving such problems (called global optimization problems) is described. This approach combines the following innovative and powerful tools: fractal approach for reduction of the problem dimension, index scheme for treating constraints, non-redundant parallel computations for accelerating the search. Through the paper, rigorous theoretical results are illustrated by figures and numerical examples.     

最优化问题的并行算法

本文对求解非线性最优化问题的几种主要并行思想，即按变量分裂的并行算法，函数值、梯度值的并行计算，计算步骤并行的算法等，作了简要的综述，并介绍了近几年在这方面取得的进展．     

Local Optimization Method with Global Multidimensional Search

This paper presents a new method for solving global optimization problems. We use a local technique based on the notion of discrete gradients for finding a cone of descent directions and then we use a global cutting angle algorithm for finding global minimum within the intersection of the cone and the feasible region. We present results of numerical experiments with well-known test problems and with the so-called cluster function. These results confirm that the proposed algorithms allows one to find a global minimizer or at least a deep local minimizer of a function with a huge amount of shallow local minima.     

Parallel Simulated Annealing Algorithms in Global Optimization

Global optimization involves the difficult task of the identification of global extremities of mathematical functions. Such problems are often encountered in practice in various fields, e.g., molecular biology, physics, industrial chemistry. In this work, we develop five different parallel Simulated Annealing (SA) algorithms and compare them on an extensive test bed used previously for the assessment of various solution approaches in global optimization. The parallel SA algorithms consist of various categories: the asynchronous approach where no information is exchanged among parallel runs and the synchronous approaches where solutions are exchanged using genetic operators, or where solutions are transmitted only occasionally, or where highly coupled synchronization is achieved at every iteration. One of these approaches, which occasionally applies partial information exchanges (controlled in terms of solution quality), provides particularly notable results for functions with vast search spaces of up to 400 dimensions. Previous attempts with other approaches, such as sequential SA, adaptive partitioning algorithms and clustering algorithms, to identify the global optima of these functions have failed without exception.     

非线性约束优化问题的一个修正 Lagrangian 算法

基于一个含有控制参数的修正Lagrangian函数,该文建立了一个求解非线性约束优化问题的修正Lagrangian算法.在一些适当的条件下,证明了控制参数存在一个阀值,当控制参数小于这一阀值时,由这一算法产生的序列解局部收敛于问题的Kuhn-Tucker点,并且建立了解的误差上界.最后给出一些约束优化问题的数值结果.     

求一类非凸规划问题全局解的确定性算法

本文对一类非凸规划问题(NP)给出一确定性全局优化算法.这类问题包括:在非凸的可行域上极小化有限个带指数的线性函数乘积的和与差,广义线性多乘积规划,多项式规划等.通过利用等价问题和线性化技巧提出的算法收敛到问题(NP)的全局极小.     

Solving Large Quadratic Assignment Problems in Parallel

Quadratic Assignment problems are in practice among the mostdifficult to solve in the class of NP-complete problems. Theonly successful approach hitherto has been Branch-and-Bound-basedalgorithms, but such algorithms are crucially dependent on good boundfunctions to limit the size of the space searched. Much work hasbeen done to identify such functions for the QAP, but with limitedsuccess.Parallel processing has also been used in order to increase the sizeof problems solvable to optimality. The systems used have, however, oftenbeen systems with relatively few, but very powerful vector processors, andhave hence not been ideally suited for computations essentially involving non-vectorizable computations on integers.In this paper we investigate the combination of one of the best bound functions for a Branch-and-Bound algorithm (the Gilmore-Lawler bound) and various testing, variable binding and recalculation of bounds between branchings when used in aparallel Branch-and-Bound algorithm. The algorithm has been implemented on a 16-processor MEIKO Computing Surface with Intel i860processors. Computational results from the solution of a number of large QAPs, including the classical Nugent 20 are reported.     

Solving Problems with Min-Type Functions by Disjunctive Programming

We consider applications of disjunctive programming to global optimization and problems with equilibrium constraints. We propose a modification of the algorithm of F. Beaumont for disjunctive programming problems and show its numerical efficiency.     

求解互补问题的一种序列二次规划方法

通过将互补问题转化为一种带非负约束的极小化问题 ,给出了求解互补问题的一种序列二次规划方法 .该方法中每一个子问题都是可解的 ,迭代产生的序列是非负的 ,在适当的条件下 ,分别证明了算法的全局收敛性、局部超线收敛性以及局部二次收敛性 .     

Simple Genetic Algorithm with Local Tuning: Efficient Global Optimizing Technique

Genetic algorithms are known to be efficient for global optimizing. However, they are not well suited to perform finely-tuned local searches and are prone to converge prematurely before the best solution has been found. This paper uses genetic diversity measurements to prevent premature convergence and a hybridizing genetic algorithm with simplex downhill method to speed up convergence. Three case studies show the procedure to be efficient, tough, and robust.     

解并行处理机最优映射问题的遗传算法

该文给出了一种用于多处理机系统中实现并行计算的最优映射问题的遗传算法,它对于在固定结构的并行系统中充分利用计算资源,提高计算效率具有实用价值,实践表明,采用遗传算法是解决任务最优映射问题的有效的方法．     

Global Interval Methods for Local Nonsmooth Optimization

An interval method for determining local solutions of nonsmooth unconstrained optimization problems is discussed. The objective function is assumed to be locally Lipschitz and to have appropriate interval inclusions. The method consists of two parts, a local search and a global continuation and termination. The local search consists of a globally convergent descent algorithm showing similarities to -bundle methods. While -bundle methods use polytopes as inner approximations of the -subdifferentials, which are the main tools of almost all bundle concepts, our method uses axes parallel boxes as outer approximations of the -subdifferentials. The boxes are determined almost automatically with inclusion techniques of interval arithmetic. The dimension of the boxes is equal to the dimension of the problem and remains constant during the whole computation. The application of boxes does not suffer from the necessity to invest methodical and computational efforts to adapt the polytopes to the latest state of the computation as well as to simplify them when the number of vertices becomes too large, as is the case with the polytopes. The second part of the method applies interval techniques of global optimization to the approximative local solution obtained from the search of the first part in order to determine guaranteed error bounds or to improve the solution if necessary. We present prototype algorithms for both parts of the method as well as a complete convergence theory for them and demonstrate how outer approximations can be obtained.     

A Parallel Grasp for the Steiner Tree Problem in Graphs Using a Hybrid Local Search Strategy

In this paper, we present a parallel greedy randomized adaptive search procedure (GRASP) for the Steiner problem in graphs. GRASP is a two-phase metaheuristic. In the first phase, solutions are constructed using a greedy randomized procedure. Local search is applied in the second phase, leading to a local minimum with respect to a specified neighborhood. In the Steiner problem in graphs, feasible solutions can be characterized by their non-terminal nodes (Steiner nodes) or by their key-paths. According to this characterization, two GRASP procedures are described using different local search strategies. Both use an identical construction procedure. The first uses a node-based neighborhood for local search, while the second uses a path-based neighborhood. Computational results comparing the two procedures show that while the node-based variant produces better quality solutions, the path-based variant is about twice as fast. A hybrid GRASP procedure combining the two neighborhood search strategies is then proposed. Computational experiments with a parallel implementation of the hybrid procedure are reported, showing that the algorithm found optimal solutions for 45 out of 60 benchmark instances and was never off by more than 4% of the optimal solution value. The average speedup results observed for the test problems show that increasing the number of processors reduces elapsed times with increasing speedups. Moreover, the main contribution of the parallel algorithm concerns the fact that larger speedups of the same order of the number of processors are obtained exactly for the most difficult problems.     

解椭圆边值问题的有限元并行算法

本文研究椭圆边值问题有限元方程的求解，在对限元基函数一种特定的“红黑”排序基础上，构造出具有异步并行计算结构的迭代算法，并证明了算法的收敛性。     

A Smoothing-Type Algorithm for Solving Linear Complementarity Problems with Strong Convergence Properties

In this paper, we construct an augmented system of the standard monotone linear complementarity problem (LCP), and establish the relations between the augmented system and the LCP. We present a smoothing-type algorithm for solving the augmented system. The algorithm is shown to be globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, if the LCP has a solution, then the algorithm either generates a maximal complementary solution of the LCP or detects correctly solvability of the LCP, and in the latter case, an existing smoothing-type algorithm can be directly applied to solve the LCP without any additional assumption and it generates a maximal complementary solution of the LCP; and that if the LCP is infeasible, then the algorithm detect correctly infeasibility of the LCP. To the best of our knowledge, such properties have not appeared in the existing literature for smoothing-type algorithms. This work was partially supported by the National Natural Science Foundation of China (Grant No. 10571134), the Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

A Finite Algorithm for Solving Infinite Dimensional Optimization Problems

We consider the general optimization problem (P) of selecting a continuous function x over a -compact Hausdorff space T to a metric space A, from a feasible region X of such functions, so as to minimize a functional c on X. We require that X consist of a closed equicontinuous family of functions lying in the product (over T) of compact subsets Y _t of A. (An important special case is the optimal control problem of finding a continuous time control function x that minimizes its associated discounted cost c(x) over the infinite horizon.) Relative to the uniform-on-compacta topology on the function space C(T,A) of continuous functions from T to A, the feasible region X is compact. Thus optimal solutions x ^* to (P) exist under the assumption that c is continuous. We wish to approximate such an x ^* by optimal solutions to a net {P _i }, iI, of approximating problems of the form min_{xX i} c i(x) for each iI, where (1) the net of sets {X _i } _I converges to X in the sense of Kuratowski and (2) the net {c _i } _I of functions converges to c uniformly on X. We show that for large i, any optimal solution x ^* _i to the approximating problem (P _i ) arbitrarily well approximates some optimal solution x ^* to (P). It follows that if (P) is well-posed, i.e., limsupX _i ^* is a singleton {x ^*}, then any net {x _i ^*} _I of (P _i )-optimal solutions converges in C(T,A) to x ^*. For this case, we construct a finite algorithm with the following property: given any prespecified error and any compact subset Q of T, our algorithm computes an i in I and an associated x _i ^* in X _i ^* which is within of x ^* on Q. We illustrate the theory and algorithm with a problem in continuous time production control over an infinite horizon.     

Parallel direct methods for solving the system of linear equations with pipelining on a multicore using OpenMP

Recent developments in high performance computer architecture have a significant effect on all fields of scientific computing. Linear algebra and especially the solution of linear systems of equations lie at the heart of many applications in scientific computing. This paper describes and analyzes three parallel versions of the dense direct methods such as the Gaussian elimination method and the LU form of Gaussian elimination that are used in linear system solving on a multicore using an OpenMP interface. More specifically, we present two naive parallel algorithms based on row block and row cyclic data distribution and we put special emphasis on presenting a third parallel algorithm based on the pipeline technique. Further, we propose an implementation of the pipelining technique in OpenMP. Experimental results on a multicore CPU show that the proposed OpenMP pipeline implementation achieves good overall performance compared to the other two naive parallel methods. Finally, in this work we propose a simple, fast and reasonably analytical model to predict the performance of the direct methods with the pipelining technique.     

模糊人工蜂群算法的多选择多维背包问题求解

针对传统人工蜂群算法早熟收敛问题,基于模糊化处理和蜂群寻优的特点,提出一种模糊人工蜂群算法。将模糊输入输出机制引入到算法中来保持蜜源访问概率的动态更新。根据算法计算过程中的不同阶段对蜜源访问概率有效调整,避免算法陷入局部极值。通过对多选择多维背包问题的仿真实验和与其他算法的比较,表明本算法可行有效,有良好的鲁棒性。