Shape Optimization for Semi-Linear Elliptic Equations Based on an Embedding Domain Method

We study a class of shape optimization problems for semi-linear elliptic equations with Dirichlet boundary conditions in smooth domains in ℝ². A part of the boundary of the domain is variable as the graph of a smooth function. The problem is equivalently reformulated on a fixed domain. Continuity of the solution to the state equation with respect to domain variations is shown. This is used to obtain differentiability in the general case, and moreover a useful formula for the gradient of the cost functional in the case where the principal part of the differential operator is the Laplacian. Online publication 23 January 2004.     

An approximate proximal-extragradient type method for monotone variational inequalities

Proximal point algorithms (PPA) are attractive methods for monotone variational inequalities. The approximate versions of PPA are more applicable in practice. A modified approximate proximal point algorithm (APPA) presented by Solodov and Svaiter [Math. Programming, Ser. B 88 (2000) 371–389] relaxes the inexactness criterion significantly. This paper presents an extended version of Solodov–Svaiter's APPA. Building the direction from current iterate to the new iterate obtained by Solodov–Svaiter's APPA, the proposed method improves the profit at each iteration by choosing the optimal step length along this direction. In addition, the inexactness restriction is relaxed further. Numerical example indicates the improvement of the proposed method.     

Global Solution of Optimization Problems with Parameter-Embedded Linear Dynamic Systems

This paper develops a theory for the global solution of nonconvex optimization problems with parameter-embedded linear dynamic systems. A quite general problem formulation is introduced and a solution is shown to exists. A convexity theory for integrals is then developed to construct convex relaxations for utilization in a branch-and-bound framework to calculate a global minimum. Interval analysis is employed to generate bounds on the state variables implied by the bounds on the embedded parameters. These bounds, along with basic integration theory, are used to prove convergence of the branch-and-bound algorithm to the global minimum of the optimization problem. The implementation of the algorithm is then considered and several numerical case studies are examined thoroughly     

Compact directed acyclic word graphs for a sliding window

Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n denotes the length of w. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window.     

The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.     

Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.     

GA optimization on multi-segments muffler under space constraints

Whilst the space volume of muffler in noise control system is often constrained for maintenance in practical engineering work, the maximization on muffler’s performance becomes important and essential. In this paper, a novel approach genetic algorithms (GAs) based on the principles of natural biological evolution will be used to tackle this optimization of muffler design [M. Mitchell, An Introduction to Genetic Algorithms, The MIT Press, Cambridge, MA, 1996]. Here, the shape optimization of multi-segments muffler coupled with the GA searching technique is presented. The techniques of binary genetic algorithms (BGA) together with the commercial MATLAB package [G. Lindfield, J. Penny, Numerical Method Using Matlab, second ed., Prentice Hall, Englewood Cliffs, NJ, 2000] are applied in GA searching. In addition, a numerical case of pure tone elimination with 2-5 segments on muffler is introduced and fully discussed. To achieve the best optimization in GA, several GA parameters are on trial in various values. Results show that the GA operators, including crossover mutation and elitism, are essential in accuracy. Consequently, results verify that the optimal sound transmission loss at the designed frequency of 500 Hz is exactly maximized. The GA optimization on multi-segments muffler proposed in this study surely provides a quick and correct approach.     

Randomization helps to perform independent tasks reliably

This paper is about algorithms that schedule tasks to be performed in a distributed failure‐prone environment, when processors communicate by message‐passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly‐bounded adversaries may fail up to a constant fraction of the processors. Weakly‐adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure‐prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point‐to‐point messages. A randomized algorithm is developed, that attains both ??(n log*n) expected work and ??(n log*n) expected communication, against weakly‐adaptive linearly‐bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly‐adaptive linearly‐bounded adversaries, which has to be Ω(n log n/log log n) in terms of work. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Heuristic Rejection in Interval Global Optimization

Based on the investigation carried out in Ref. 1, this paper incorporates new studies about the properties of inclusion functions on subintervals while a branch-and-bound algorithm is solving global optimization problems. It is found that the relative place of the global minimum value within the inclusion function value of the objective function at the current interval indicates mostly whether the given interval is close to a minimizer point. This information is used in a heuristic interval rejection rule that can save a considerable amount of computation. Illustrative examples are discussed and an extended numerical study shows the advantages of the new approach.     

关于组合最优化理论的多媒体教学实践

本文讨论和分析了开发组合最比化理论系列课程多媒体课件的基本认识、课件的主要特色和体会，并提出了使用多媒体课件中应注意的问题．