A parallel asynchronous Newton algorithm for unconstrained optimization

A new approach to the solution of unconstrained optimization problems is introduced. It is based on the exploitation of parallel computation techniques and in particular on an asynchronous communication model for the data exchange among concurrent processes. The proposed approach arises by interpreting the Newton method as being composed of a set of iterative and independent tasks that can be mapped onto a parallel computing system for the execution.Numerical experiments on the resulting algorithm have been carried out to compare parallel versions using synchronous and asynchronous communication mechanisms in order to assess the benefits of the proposed approach on a variety of parallel computing architectures. It is pointed out that the proposed asynchronous Newton algorithm is preferable for medium and large-scale problems, in the context of both distributed and shared memory architectures.This research work was partially supported by the National Research Council of Italy, within the special project Sistemi Informatici e Calcolo Parallelo, under CNR Contract No. 90.00675.PF69.     

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.     

Pseudo-conjugate directions for the solution of the nonlinear unconstrained optimization problem on a parallel computer

Parallel algorithms and test case results for the solution of the unconstrained optimization problem are presented. The algorithms involve the use of pseudo-conjugate directions (directions which tend to become conjugate as the solution is approached). It is shown that the algorithms are both fast and robust. Although all the algorithms of this paper involve the parallel execution of linear search procedures, a critical differentiation can be made among them, depending on whether the linear searches are performed along the same direction (parallel unidirectional algorithms) or different directions (parallel multidirectional algorithms).     

Block truncated-Newton methods for parallel optimization

Truncated-Newton methods are a class of optimization methods suitable for large scale problems. At each iteration, a search direction is obtained by approximately solving the Newton equations using an iterative method. In this way, matrix costs and second-derivative calculations are avoided, hence removing the major drawbacks of Newton's method. In this form, the algorithms are well-suited for vectorization. Further improvements in performance are sought by using block iterative methods for computing the search direction. In particular, conjugate-gradient-type methods are considered. Computational experience on a hypercube computer is reported, indicating that on some problems the improvements in performance can be better than that attributable to parallelism alone.Partially supported by Air Force Office of Scientific Research grant AFOSR-85-0222.Partially supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research.     

Proximal Alternating Directions Method for Structured Variational Inequalities

In the alternating directions method, the relaxation factor by Glowinski is useful in practical computations for structured variational inequalities. This paper points out that the same restriction region of the relaxation factor is also valid in the proximal alternating directions method. The research was supported by the NSFC of China Grant 10571083 and MOEC Grant 20060284001. The author thanks the anonymous referees for valuable suggestions.     

Accelerated conjugate direction methods for unconstrained optimization

A family of accelerated conjugate direction methods, corresponding to the Broyden family of quasi-Newton methods, is described. It is shown thatall members of the family generate the same sequence of points approximating the optimum and the same sequence of search directions, provided only that each direction vector is normalized before the stepsize to be taken in that direction is determined.With minimal restrictions on how the stepsize is determined (sufficient only for convergence), the accelerated methods applied to the optimization of a function ofn variables are shown to have an (n+1)-step quadratic rate of convergence. Furthermore, the information needed to generate an accelerating step can be stored in a singlen-vector, rather than the usualn×n symmetric matrix, without changing the theoretical order of convergence.The relationships between this family of methods and existing conjugate direction methods are discussed, and numerical experience with two members of the family is presented.This research was sponsored by the United States Army under Contract No. DAAG29-75-C-0024.The author gratefully acknowledges the valuable assistance of Julia H. Gray, of the Mathematics Research Center, University of Wisconsin, Madison, who painstakingly programmed these methods and obtained the computational results.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

可分离凸优化问题的非精确平行分裂算法

针对一类可分离凸优化问题提出了一种非精确平行分裂算法.该算法充分利用了所求解问题的可分离结构,并对子问题进行非精确求解.在适当的条件下,证明了所提出的非精确平行分裂算法的全局收敛性,初步的数值实验说明了算法有效性.     

Alternating direction algorithms for solving Hamilton-Jacobi-Bellman equations

We focus on numerically solving a typical type of Hamilton-Jacobi-Bellman (HJB) equations arising from a class of optimal controls with a standard multidimensional diffusion model. Solving such an equation results in the value function and an optimal feedback control law. The Bellman's curse of dimensionality seems to be the main obstacle to applicability of most numerical algorithms for solving HJB. We decompose HJB into a number of lower-dimensional problems, and discuss how the usual alternating direction method can be extended for solving HJB. We present some convergence results, as well as preliminary experimental outcomes.This research was funded in part by an RGC grant from the University of Alabama.     

Local and global optimization by parallel algorithms for MIMD systems

This paper describes an implementation on the Neptune system at Loughborough University of Sutti's parallel (MIMD) algorithm [1–3] and an analysis of its performance. Parallel asynchronous versions of Powell's method [6] and Price's algorithm [7] are proposed, designed for efficient implementation on MIMD systems.This work has been developed during the author's stay at the Numerical Optimization Centre, Hatfield Polytechnic, England.     

A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs

We propose a modified alternating direction method for solving convex quadratically constrained quadratic semidefinite optimization problems. The method is a first-order method, therefore requires much less computational effort per iteration than the second-order approaches such as the interior point methods or the smoothing Newton methods. In fact, only a single inexact metric projection onto the positive semidefinite cone is required at each iteration. We prove global convergence and provide numerical evidence to show the effectiveness of this method.     

An implementation of a parallel primal-dual interior point method for block-structured linear programs

An implementation of the primal-dual predictor-corrector interior point method is specialized to solve block-structured linear programs with side constraints. The block structure of the constraint matrix is exploited via parallel computation. The side constraints require the Cholesky factorization of a dense matrix, where a method that exploits parallelism for the dense Cholesky factorization is used. For testing, multicommodity flow problems were used. The resulting implementation is 65%–90% efficient, depending on the problem instance. For a problem with K commodities, an approximate speedup for the interior point method of 0.8K is realized.     

Global optimization method using adaptive and parallel ensemble of surrogates for engineering design optimization

As a robust and efficient technique for global optimization, surrogate-based optimization method has been widely used in dealing with the complicated and computation-intensive engineering design optimization problems. It’s hard to select an appropriate surrogate model without knowing the behaviour of the real system a priori in most cases. To overcome this difficulty, a global optimization method using an adaptive and parallel ensemble of surrogates combining three representative surrogate models with optimized weight factors has been proposed. The selection of weight factors is treated as an optimization problem with the desired solution being one that minimizes the generalized mean square cross-validation error. The proposed optimization method is tested by considering several well-known numerical examples and one industrial problem compared with other optimization methods. The results show that the proposed optimization method can be a robust and efficient approach in surrogate-based optimization for locating the global optimum.     

Speedup estimates for some variants of the parallel implementations of the branch-and-bound method

The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered.     

A variable-penalty alternating directions method for convex optimization

We study a generalized version of the method of alternating directions as applied to the minimization of the sum of two convex functions subject to linear constraints. The method consists of solving consecutively in each iteration two optimization problems which contain in the objective function both Lagrangian and proximal terms. The minimizers determine the new proximal terms and a simple update of the Lagrangian terms follows. We prove a convergence theorem which extends existing results by relaxing the assumption of uniqueness of minimizers. Another novelty is that we allow penalty matrices, and these may vary per iteration. This can be beneficial in applications, since it allows additional tuning of the method to the problem and can lead to faster convergence relative to fixed penalties. As an application, we derive a decomposition scheme for block angular optimization and present computational results on a class of dual block angular problems. This material is based on research supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410 and by NSF Grants CCR-8907671, CDA-9024618 and CCR-9306807.     

Two-dimensional block partitionings for the parallel sparse Cholesky factorization

This paper presents a discussion on 2D block mappings for the sparse Cholesky factorization on parallel MIMD architectures with distributed memory. It introduces the fan-in algorithm in a general manner and proposes several mapping strategies. The grid mapping with row balancing, inspired by Rothberg's work (1994), is proved to be more robust than the original fan-out algorithm. Even more efficient is the proportional mapping, as shown by the experiments on a 32 processor IBM SP1 and on a Cray T3D. Subforest-to-subcube mappings are also considered and give good results on the T3D. This revised version was published online in August 2006 with corrections to the Cover Date.     

Unified steerable phase I-phase II method of feasible directions for semi-infinite optimization

In this paper, we complete a cycle in the construction of methods of feasible directions for solving semi-infinite constrained optimization problems. Earlier phase I-phase II methods of feasible directions used one search direction rule in all of ⁿ with two stepsize rules, one for feasible points and one for infeasible points. The algorithm presented in this paper uses both a single search direction rule and a single stepsize rule in all of ⁿ . In addition, the new algorithm incorporates a steering parameter which can be used to control the speed with which feasibility is achieved. The new algorithm is simpler to analyze and performs somewhat better than existing, first order, phase I-phase II methods. The new algorithm is globally convergent, with linear rate.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-8713334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, and the State of California MICRO Program Grant 532410-19900.The authors would like to thank Dr. J. Higgins for providing the C-code of Algorithm 3.1.     

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.     

Optimal equi-partition of rectangular domains for parallel computation

We present an efficient method for the partitioning of rectangular domains into equi-area sub-domains of minimum total perimeter. For a variety of applications in parallel computation, this corresponds to a load-balanced distribution of tasks that minimize interprocessor communication. Our method is based on utilizing, to the maximum extent possible, a set of optimal shapes for sub-domains. We prove that for a large class of these problems, we can construct solutions whose relative distance from a computable lower bound converges to zero as the problem size tends to infinity. PERIX-GA, a genetic algorithm employing this approach, has successfully solved to optimality million-variable instances of the perimeter-minimization problem and for a one-billion-variable problem has generated a solution within 0.32% of the lower bound. We report on the results of an implementation on a CM-5 supercomputer and make comparisons with other existing codes.This research was partially funded by Air Force Office of Scientific Research grant F496-20-94-1-0036 and National Science Foundation grants CDA-9024618 and CCR-9306807.     

A modified Newton direction for unconstrained optimization

In this article, a modification on Newton's direction for solving problems of unconstrained optimization is presented. As it is known, a major disadvantage of Newton's method is its slowness or non-convergence for the initial point not being close to optima's neighbourhood. The proposed method generally guarantees the decrement of the norm of the gradient or the value of the objective function at every iteration, contributing to the efficiency of Newton's method. The quadratic convergence of the proposed iterative scheme and the enlargement of the radius of convergence area are proved. The proposed algorithm has been implemented and tested on several well-known test functions.