Parallel algorithms for nonlinear programming problems

This paper describes several parallel algorithms for solving nonlinear programming problems. Two approaches where parallelism can successfully be introduced have been explored: a quadratic approximation method based on penalty function and a dual method. These methods are improved by using two algorithms originally proposed for solving unconstrained problems: the parallel variable metric algorithm and the parallel Jacobson-Oksman algorithm. Even though general problems are dealt with, particular emphasis is placed on the potential of these parallel methods for separable programming problems. The numerical effectiveness of the algorithms is demonstrated on a set of test problems using a Cray-1S vector computer and serial computers (with respect to sequential versions of the same methods).These studies were sponsored in part by the CERT. The author would particularly like to thank Ph. Berger (LSI-ENSEEIHT), the researchers of the DERI (CERT) and of the Groupe Structures, Aerospatiale, for their assistance.     

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.     

Parallel Newton two‐stage methods based on ILU factorizations for nonlinear systems

Parallel iterative algorithms based on the Newton method and on two of its variants, the Shamanskii method and the Chord method, for solving nonlinear systems are proposed. These algorithms are based on two‐stage multisplitting methods where incomplete LU factorizations are considered as a mean of constructing the inner splittings. Convergence properties of these parallel methods are studied for H‐matrices. Computational results of these methods on two parallel computing systems are discussed. The reported experiments show the effectiveness of these methods. Copyright © 2006 John Wiley & Sons, Ltd.     

New subgradient extragradient methods for common solutions to equilibrium problems

In this paper, three parallel hybrid subgradient extragradient algorithms are proposed for finding a common solution of a finite family of equilibrium problems in Hilbert spaces. The proposed algorithms originate from previously known results for variational inequalities and can be considered as modifications of extragradient methods for equilibrium problems. Theorems of strong convergence are established under the standard assumptions imposed on bifunctions. Some numerical experiments are given to illustrate the convergence of the new algorithms and to compare their behavior with other algorithms.     

Strong convergence theorems for equilibrium problems and fixed point problems in Banach spaces

The paper proposes two new iterative methods for solving pseudomonotone equilibrium problems involving fixed point problems for quasi-\(\phi \)-nonexpansive mappings in Banach spaces. The proposed algorithms combine the extended extragradient method or the linesearch method with the Halpern iteration. The strong convergence theorems are established under standard assumptions imposed on equilibrium bifunctions and mappings. The results in this paper have generalized and enriched existing algorithms for equilibrium problems in Banach spaces.     

Parallel radial basis function methods for the global optimization of expensive functions

We introduce a master–worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by Gutmann [Gutmann, H.M., 2001a. A radial basis function method for global optimization. Journal of Global Optimization 19(3), 201–227] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [Regis, R.G., Shoemaker, C.A., 2005. Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization 31, 153–171] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors.     

Making Augmented Lagrangian Methods Computer Amenable for Equilibrium Problems

ABSTRACT

We develop three algorithms to solve the subproblems generated by the augmented Lagrangian methods introduced by Iusem-Nasri (2010) for the equilibrium problem. The first algorithm that we propose incorporates the Newton method and the other two are instances of the subgradient projection method. One of our algorithms is also capable of solving nondifferentiable equilibrium problems. Using well-known test problems, all algorithms introduced here are implemented and numerical results are reported to compare their performances.     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Novel Hybrid Methods for Pseudomonotone Equilibrium Problems and Common Fixed Point Problems

The purpose of this article is to introduce some hybrid algorithms for finding a common element of the solution sets of pseudomonotone equilibrium problems and the fixed point sets of nonexpansive mappings in real Hilbert spaces. Our algorithms combine Mann’s iterative methods and Armijo line-search with parallel splitting-up and hybrid techniques. The strong convergence of the proposed algorithms are established without the assumption on the Lipschitz-type condition for the bifunctions involved.     

A comparison of some domain decomposition and ILU preconditioned iterative methods for nonsymmetric elliptic problems

In recent years, competitive domain-decomposed preconditioned iterative techniques of Krylov-Schwarz type have been developed for nonsymmetric linear elliptic systems. Such systems arise when convection-diffusion-reaction problems from computational fluid dynamics or heat and mass transfer are linearized for iterative solution. Through domain decomposition, a large problem is divided into many smaller problems whose requirements for coordination can be controlled to allow effective solution on parallel machines. A central question is how to choose these small problems and how to arrange the order of their solution. Different specifications of decomposition and solution order lead to a plethora of algorithms possessing complementary advantages and disadvantages. In this report we compare several methods, including the additive Schwarz algorithm, the classical multiplicative Schwarz algorithm, an accelerated multiplicative Schwarz algorithm, the tile algorithm, the CGK algorithm, the CSPD algorithm, and also the popular global ILU-family of preconditioners, on some nonsymmetric or indefinite elliptic model problems discretized by finite difference methods. The preconditioned problems are solved by the unrestarted GMRES method. A version of the accelerated multiplicative Schwarz method is a consistently good performer.     

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.     

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.     

Hybrid proximal methods for equilibrium problems

This paper concerns developing two hybrid proximal point methods (PPMs) for finding a common solution of some optimization-related problems. First we construct an algorithm to solve simultaneously an equilibrium problem and a variational inequality problem, combing the extragradient method for variational inequalities with an approximate PPM for equilibrium problems. Next we develop another algorithm based on an alternate approximate PPM for finding a common solution of two different equilibrium problems. We prove the global convergence of both algorithms under pseudomonotonicity assumptions.     

Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation

The Dirichlet-Neumann and Neumann-Neumann waveform relaxation methods are nonoverlapping spatial domain decomposition methods to solve evolution problems, while the parareal algorithm is in time parallel fashion. Based on the combinations of these space and time parallel strategies, we present and analyze two parareal algorithms based on the Dirichlet-Neumann and the Neumann-Neumann waveform relaxation method for the heat equation by choosing Dirichlet-Neumann/Neumann-Neumann waveform relaxation as two new kinds of fine propagators instead of the classical fine propagator. Both new proposed algorithms could be viewed as a space-time parallel algorithm, which increases the parallelism both in space and in time. We derive for the heat equation the convergence results for both algorithms in one spatial dimension. We also illustrate our theoretical results with numerical experiments finally.

     

A parallel algorithm for solving Toeplitz linear systems

Numerical methods of solution are considered for systems which are Toeplitz and symmetric. In our case, the coefficient matrix is essentially tridiagonal and sparse. There are two distinct approaches to be considered each of which is efficient in its own way. Here we will combine the two approaches which will allow application of the cyclic reduction method to coefficient matrices of more general forms. The convergence of the approximations to the exact solution will also be examined. Solving linear systems by the adapted cyclic reduction method can be parallel processed.     

Parallel hybrid extragradient methods for pseudomonotone equilibrium problems and nonexpansive mappings

In this paper we propose and analyze three parallel hybrid extragradient methods for finding a common element of the set of solutions of equilibrium problems involving pseudomonotone bifunctions and the set of fixed points of nonexpansive mappings in a real Hilbert space. Based on parallel computation we can reduce the overall computational effort under widely used conditions on the bifunctions and the nonexpansive mappings. A simple numerical example is given to illustrate the proposed parallel algorithms.     

Studies of an infinite element method for acoustical radiation

Infinite element computations are very efficient for predicting the vibro-acoustic response and sensitivities of a vibrating structure for an exterior acoustic domain. In addition, domain decomposition methods are very powerful algorithms for solving large linear systems in parallel. In this paper, an infinite element method is proposed and analyzed for parallel computations purpose. An original formulation of this method with Lagrange multipliers defined on (semi-)infinite space is presented. The implementation aspects of this method in an industrial acoustic software (SYSNOISE) are discussed. New numerical results illustrate the efficiency of the proposed method for realistic acoustical radiation problems.     

PARALLEL IMPLEMENTATIONS OF THE FAST SWEEPING METHOD

The fast sweeping method is an efficient iterative method for hyperbolic problems. It combines Gauss-Seidel iterations with alternating sweeping orderings. In this paper several parallel implementations of the fast sweeping method are presented. These parallel algorithms are simple and efficient due to the causality of the underlying partial different equations. Numerical examples are used to verify our algorithms.     

Two differential equation systems for equality-constrained optimization

This paper presents two differential systems, involving first and second order derivatives of problem functions, respectively, for solving equality-constrained optimization problems. Local minimizers to the optimization problems are proved to be asymptotically stable equilibrium points of the two differential systems. First, the Euler discrete schemes with constant stepsizes for the two differential systems are presented and their convergence theorems are demonstrated. Second, we construct algorithms in which directions are computed by these two systems and the stepsizes are generated by Armijo line search to solve the original equality-constrained optimization problem. The constructed algorithms and the Runge–Kutta method are employed to solve the Euler discrete schemes and the differential equation systems, respectively. We prove that the discrete scheme based on the differential equation system with the second order information has the locally quadratic convergence rate under the local Lipschitz condition. The numerical results given here show that Runge–Kutta method has better stability and higher precision and the numerical method based on the differential equation system with the second information is faster than the other one.     

Convergent iterative schemes for time parallelization

Parallel methods are usually not applied to the time domain because of the inherit sequentialness of time evolution. But for many evolutionary problems, computer simulation can benefit substantially from time parallelization methods. In this paper, we present several such algorithms that actually exploit the sequential nature of time evolution through a predictor-corrector procedure. This sequentialness ensures convergence of a parallel predictor-corrector scheme within a fixed number of iterations. The performance of these novel algorithms, which are derived from the classical alternating Schwarz method, are illustrated through several numerical examples using the reservoir simulator Athena.