Partially separable optimization and parallel computing

Parallel processors are becoming an attractive option for meeting the requirements to solve large nonlinear optimization problems and the partially separable methods are ideal candidates for parallel computing. This paper proposes implementation techniques for such methods. Computational experiments on an IBM 3090-200 and on a simulated multiprocessor are presented. The performance of both implementations is compared against a reference serial implementation.     

A parallel multiple reference point approach for multi-objective optimization

This paper presents a multiple reference point approach for multi-objective optimization problems of discrete and combinatorial nature. When approximating the Pareto Frontier, multiple reference points can be used instead of traditional techniques. These multiple reference points can easily be implemented in a parallel algorithmic framework. The reference points can be uniformly distributed within a region that covers the Pareto Frontier. An evolutionary algorithm is based on an achievement scalarizing function that does not impose any restrictions with respect to the location of the reference points in the objective space. Computational experiments are performed on a bi-objective flow-shop scheduling problem. Results, quality measures as well as a statistical analysis are reported in the paper.     

On proving existence of feasible points in equality constrained optimization problems

Various algorithms can compute approximate feasible points or approximate solutions to equality and bound constrained optimization problems. In exhaustive search algorithms for global optimizers and other contexts, it is of interest to construct bounds around such approximate feasible points, then to verify (computationally but rigorously) that an actual feasible point exists within these bounds. Hansen and others have proposed techniques for proving the existence of feasible points within given bounds, but practical implementations have not, to our knowledge, previously been described. Various alternatives are possible in such an implementation, and details must be carefully considered. Also, in addition to Hansen’s technique for handling the underdetermined case, it is important to handle the overdetermined case, when the approximate feasible point corresponds to a point with many active bound constraints. The basic ideas, along with experimental results from an actual implementation, are summarized here. This work was supported in part by National Science Foundation grant CCR-9203730.     

Parallel Information Algorithm with Local Tuning for Solving Multidimensional GO Problems

In this paper we propose a new parallel algorithm for solving global optimization (GO) multidimensional problems. The method unifies two powerful approaches for accelerating the search: parallel computations and local tuning on the behavior of the objective function. We establish convergence conditions for the algorithm and theoretically show that the usage of local information during the global search permits to accelerate solving the problem significantly. Results of numerical experiments executed with 100 test functions are also reported.     

Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains

We describe a distributed memory parallel Delaunay refinement algorithm for simple polyhedral domains whose constituent bounding edges and surfaces are separated by angles between 90° to 270° inclusive. With these constraints, our algorithm can generate meshes containing tetrahedra with circumradius to shortest edge ratio less than 2, and can tolerate more than 80% of the communication latency caused by unpredictable and variable remote gather operations.

Our experiments show that the algorithm is efficient in practice, even for certain domains whose boundaries do not conform to the theoretical limits imposed by the algorithm. The algorithm we describe is the first step in the development of much more sophisticated guaranteed-quality parallel mesh generation algorithms.     

An efficient interval computing technique for bound-constrained uncertain optimization problems

In this article, a competent interval-oriented approach is proposed to solve bound-constrained uncertain optimization problems. This new class of problems is considered here as an extension of the classical bound-constrained optimization problems in an inexact environment. The proposed technique is nothing but an imitation of the well-known interval analysis-based branch-and-bound optimization approach. Efficiency of this technique is strongly dependent on division, bounding, selection/rejection and termination criteria. The technique involves a multisection division criterion of the accepted/proposed search region. Then, we have employed the interval-ranking definitions with respect to the pessimistic decision makers’ point of view given by Mahato and Bhunia [Interval-arithmetic-oriented interval computing technique for global optimization, Appl. Math. Res. Express 2006 (2006), pp. 1–19] to compare the interval-valued objectives calculated in each subregion and also to select the subregion containing the best interval objective value. The process is continued until the interval width for each variable in the accepted subregion is negligible and ultimately the global or close-to-global interval-valued optimal solution is obtained. The proposed technique has been evaluated numerically using a wide set of newly introduced univariate/multivariate test problems. Finally, to compare the computational results obtained by the proposed method, the graphical representation for some test problems is given.     

Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems

We develop an iterative algorithm based on right-hand side decomposition for the solution of multicommodity network flow problems. At each step of the proposed iterative procedure the coupling constraints are eliminated by subdividing the shared capacity resource among the different commodities and a master problem is constructed which attempts to improve sharing of the resources at each iteration.As the objective function of the master problem is nonsmooth, we apply to it a new optimization technique which does not require the exact solutions of the single commodity flow subproblems. This technique is based on the notion of - subgradients instead of subgradients and is suitable for parallel implementation. Extensions to the nonlinear, convex separable case are also discussed.The work of this author has been supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410.     

A continuous method for computing bounds in integer quadratic optimization problems

In the graph partitioning problem, as in other NP-hard problems, the problem of proving the existence of a cut of given size is easy and can be accomplished by exhibiting a solution with the correct value. On the other hand proving the non-existence of a cut better than a given value is very difficult. We consider the problem of maximizing a quadratic function x ^T Q x where Q is an n × n real symmetric matrix with x an n-dimensional vector constrained to be an element of {–1, 1} ⁿ . We had proposed a technique for obtaining upper bounds on solutions to the problem using a continuous approach in [4]. In this paper, we extend this method by using techniques of differential geometry.     

Improvements in the treatment of stress constraints in structural topology optimization problems

Topology optimization of continuum structures is a relatively new branch of the structural optimization field. Since the basic principles were first proposed by Bendsøe and Kikuchi in 1988, most of the work has been dedicated to the so-called maximum stiffness (or minimum compliance) formulations. However, since a few years different approaches have been proposed in terms of minimum weight with stress (and/or displacement) constraints.These formulations give rise to more complex mathematical programming problems, since a large number of highly non-linear (local) constraints must be taken into account. In an attempt to reduce the computational requirements, in this paper, we propose different alternatives to consider stress constraints and some ideas about the numerical implementation of these algorithms. Finally, we present some application examples.     

Application of parallel heuristic algorithms for speeding up parallel implementations of the branch-and-bound method

A scheme for the parallel implementation of the combined branch-and-bound method and heuristic algorithms is proposed. Results of computations for the one-dimensional Boolean knapsack problem are presented that demonstrate the efficiency of the proposed approach. The main factors that affect the speedup of the solution when local optimization is used are discussed.     

Auxiliary problem principle and decomposition of optimization problems

The auxiliary problem principle allows one to find the solution of a problem (minimization problem, saddle-point problem, etc.) by solving a sequence of auxiliary problems. There is a wide range of possible choices for these problems, so that one can give special features to them in order to make them easier to solve. We introduced this principle in Ref. 1 and showed its relevance to decomposing a problem into subproblems and to coordinating the subproblems. Here, we derive several basic or abstract algorithms, already given in Ref. 1, and we study their convergence properties in the framework of i infinite-dimensional convex programming.     

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.     

Two-stage based ensemble optimization framework for large-scale global optimization

Large-scale global optimization (LSGO) is a very important and challenging task in optimization domain, which is embedded in many scientific and engineering applications. In order to strengthen both effectiveness and efficiency of LSGO algorithm, this paper designs a two-stage based ensemble optimization evolutionary algorithm (EOEA) framework, which serially implements two sub-optimizers. These two sub-optimizers mainly focus on exploration and exploitation separately. The EOEA framework can be easily generated, flexibly altered and modified, according to different implementation conditions. In order to analyze the effects of EOEA’s components, we compare its performance on diverse kinds of problems with its two sub-optimizers and three variants. To show its superiorities over the previous LSGO algorithms, we compare its performance with six classical LSGO algorithms on the LSGO test functions of IEEE Congress of Evolutionary Computation (CEC 2008). The performance of EOEA is further evaluated by experimental comparison with four state-of-the-art LSGO algorithms on the test functions of CEC 2010 LSGO competition. To benchmark the practical applicability of EOEA, we adopt EOEA to the parameter calibration problem of water pipeline system. Based on the experimental results on diverse scales of systems, EOEA performs steadily and robustly.     

Maximizing business value by optimal assignment of jobs to resources in grid computing

An important problem that arises in the area of grid computing is one of optimally assigning jobs to resources to achieve a business objective. In the grid computing area, however, such scheduling has mostly been done from the perspective of maximizing the utilization of resources. As this form of computing proliferates, the business aspects will become crucial for the overall success of the technology. Hence, we discuss the grid scheduling problem from a business perspective. We show that this problem is not only strongly NP-hard, but it is also non-approximable. Therefore, we propose heuristics for different variants of the problem and show that these heuristics provide near-optimal solution for a wide variety of problem instances. We show that the execution times of proposed heuristics are very low, and hence, they are suitable for solving problems in real-time. We also present several managerial implications and compare the performance of two widely used models in the real-time scheduling of grid computing.     

Planning under uncertainty using parallel computing

Industry and government routinely solve deterministic mathematical programs for planning and schelduling purposes, some involving thousands of variables with a linear or non-linear objective and inequality constraints. The solutions obtained are often ignored because they do not properly hedge against future contingencies. It is relatively easy to reformulate models to include uncertainty. The bottleneck has been (and is) our capability to solve them. The time is now ripe for finding a way to do so. To this end, we describe in this paper how large-scale system methods for solving multi-staged systems, such as Bender's Decomposition, high-speed sampling or Monte Carlo simulation, and parallel processors can be combined to solve some important planning problems involving uncertainty. For example, parallel processors may make it possible to come to better grips with the fundamental problems of planning, scheduling, design, and control of complex systems such as the economy, an industrial enterprise, an energy system, a water-resource system, military models for planning-and-control, decisions about investment, innovation, employment, and health-delivery systems.     

Solving non-linear portfolio optimization problems with the primal-dual interior point method

Stochastic programming is recognized as a powerful tool to help decision making under uncertainty in financial planning. The deterministic equivalent formulations of these stochastic programs have huge dimensions even for moderate numbers of assets, time stages and scenarios per time stage. So far models treated by mathematical programming approaches have been limited to simple linear or quadratic models due to the inability of currently available solvers to solve NLP problems of typical sizes. However stochastic programming problems are highly structured. The key to the efficient solution of such problems is therefore the ability to exploit their structure. Interior point methods are well-suited to the solution of very large non-linear optimization problems. In this paper we exploit this feature and show how portfolio optimization problems with sizes measured in millions of constraints and decision variables, featuring constraints on semi-variance, skewness or non-linear utility functions in the objective, can be solved with the state-of-the-art solver.     

Partitioning mathematical programs for parallel solution

This paper describes heuristics for partitioning a generalM × N matrix into arrowhead form. Such heuristics are useful for decomposing large, constrained, optimization problems into forms that are amenable to parallel processing. The heuristics presented can be easily implemented using publicly available graph partitioning algorithms. The application of such techniques for solving large linear programs is described. Extensive computational results on the effectiveness of our partitioning procedures and their usefulness for parallel optimization are presented. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This material is based on research supported by National Science Foundation Grants CCR-9157632 and CDA-9024618, the Air Force Office of Scientific Research Grant F49620-94-1-0036 and the AT&T Foundation.     

Dynamic Data Structures for a Direct Search Algorithm

The DIRECT (DIviding RECTangles) algorithm of Jones, Perttunen, and Stuckman (Journal of Optimization Theory and Applications, vol. 79, no. 1, pp. 157–181, 1993), a variant of Lipschitzian methods for bound constrained global optimization, has proved effective even in higher dimensions. However, the performance of a DIRECT implementation in real applications depends on the characteristics of the objective function, the problem dimension, and the desired solution accuracy. Implementations with static data structures often fail in practice, since it is difficult to predict memory resource requirements in advance. This is especially critical in multidisciplinary engineering design applications, where the DIRECT optimization is just one small component of a much larger computation, and any component failure aborts the entire design process. To make the DIRECT global optimization algorithm efficient and robust on large-scale, multidisciplinary engineering problems, a set of dynamic data structures is proposed here to balance the memory requirements with execution time, while simultaneously adapting to arbitrary problem size. The focus of this paper is on design issues of the dynamic data structures, and related memory management strategies. Numerical computing techniques and modifications of Jones' original DIRECT algorithm in terms of stopping rules and box selection rules are also explored. Performance studies are done for synthetic test problems with multiple local optima. Results for application to a site-specific system simulator for wireless communications systems (S ⁴ W) are also presented to demonstrate the effectiveness of the proposed dynamic data structures for an implementation of DIRECT.     

Algorithms for solving inverse geophysical problems on parallel computing systems

For solving inverse gravimetry problems, efficient stable parallel algorithms based on iterative gradient methods are proposed. For solving systems of linear algebraic equations with block-tridiagonal matrices arising in geoelectrics problems, a parallel matrix sweep algorithm, a square root method, and a conjugate gradient method with preconditioner are proposed. The algorithms are implemented numerically on a parallel computing system of the Institute of Mathematics and Mechanics (PCS-IMM), NVIDIA graphics processors, and an Intel multi-core CPU with some new computing technologies. The parallel algorithms are incorporated into a system of remote computations entitled “Specialized Web-Portal for Solving Geophysical Problems on Multiprocessor Computers.” Some problems with “quasi-model” and real data are solved.     

Global and uniform convergence of subspace correction methods for some convex optimization problems

This paper gives some global and uniform convergence estimates for a class of subspace correction (based on space decomposition) iterative methods applied to some unconstrained convex optimization problems. Some multigrid and domain decomposition methods are also discussed as special examples for solving some nonlinear elliptic boundary value problems.