Robust handling of non‐linear constraints for GA optimization of aerodynamic shapes

A new approach to the robust handling of non‐linear constraints for GAs (genetic algorithms) optimization is proposed. A specific feature of the approach consists of the change in the conventional search strategy by employing search paths which pass through both feasible and infeasible points (contrary to the traditional approach where only feasible points may be included in a path). The method (driven by full Navier–Stokes computations) was applied to the problem of multiobjective optimization of aerodynamic shapes subject to various geometrical and aerodynamic constraints. The results demonstrated that the method retains high robustness of conventional GAs while keeping CFD computational volume to an acceptable level, which allowed the algorithm to be used in a demanding engineering environment. Copyright © 2004 John Wiley & Sons, Ltd.     

Gray code for derangements

We give a Gray code and constant average time generating algorithm for derangements, i.e., permutations with no fixed points. In our Gray code, each derangement is transformed into its successor either via one or two transpositions or a rotation of three elements. We generalize these results to permutations with number of fixed points bounded between two constants.     

Local approximations for maximum partial subgraph problem

We deal with MAXH₀-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ₀+1)/(B+2+ν₀), where B=max_v∈Vd_G(v), δ₀=min_v∈V(H0)d_H0(v) and ν₀=(|V(H₀)|+1)/δ₀. Next, we show that this ratio rises up to 3/(B+1) when H₀=K₃. Finally, we provide hardness results for MAXK₃-FREE PARTIAL SUBGRAPH.     

Equivalence of two linear programming relaxations for broadcast scheduling

A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. In this paper, we show the equivalence of two apparently different relaxations that have been considered for this problem.     

Strongly polynomial-time approximation for a class of bicriteria problems

Consider the following problem: given a ground set and two minimization objectives of the same type find a subset from a given subset-class that minimizes the first objective subject to a budget constraint on the second objective. Using Megiddo's parametric method we improve an earlier weakly polynomial time algorithm.     

On Weak Solutions of an Integral Equation Driven by a p-Semimartingale of Special Type

We consider the integral equation driven by a standard Brownian motion and by a fractional Brownian motion. Sufficient conditions under which the equation has a weak solution are obtained.     

Hausdorff dimension of a random invariant set

The notion of random attractor for a dissipative stochastic dynamical system has recently been introduced. It generalizes the concept of global attractor in the deterministic theory. It has been shown that many stochastic dynamical systems associated to a dissipative partial differential equation perturbed by noise do possess a random attractor. In this paper, we prove that, as in the case of the deterministic attractor, the Hausdorff dimension of the random attractor can be estimated by using global Lyapunov exponents. The result is obtained under very natural assumptions. As an application, we consider a stochastic reaction-diffusion equation and show that its random attractor has finite Hausdorff dimension.     

Decomposition Methods for Differentiable Optimization Problems over Cartesian Product Sets

This paper presents a unified analysis of decomposition algorithms for continuously differentiable optimization problems defined on Cartesian products of convex feasible sets. The decomposition algorithms are analyzed using the framework of cost approx imation algorithms. A convergence analysis is made for three decomposition algorithms: a sequential algorithm which extends the classical Gauss-Seidel scheme, a synchronized parallel algorithm which extends the Jacobi method, and a partially asynchronous parallel algorithm. The analysis validates inexact computations in both the subproblem and line search phases, and includes convergence rate results. The range of feasible step lengths within each algorithm is shown to have a direct correspondence to the increasing degree of parallelism and asynchronism, and the resulting usage of more outdated information in the algorithms.     

Parallel Algorithm for Unconstrained Optimization Based on Decomposition Techniques

We present a numerical implementation of the parallel gradient distribution (PGD) method for the solution of large-scale unconstrained optimization problems. The proposed parallel algorithm is characterized by a parallel phase which exploits the portions of the gradient of the objective function assigned to each processor; then, a coordination phase follows which, by a synchronous interaction scheme, optimizes over the partial results obtained by the parallel phase. The parallel and coordination phases are implemented using a quasi-Newton limited-memory BFGS approach. The computational experiments, carried out on a network of UNIX workstations by using the parallel software tool PVM, show that parallelization efficiency was problem dependent and ranged between 0.15 and 8.75. For the 150 problems solved by PGD on more than one processor, 85 cases had parallelization efficiency below 1, while 65 cases had a parallelization efficiency above 1.