Ferris, M. and O. Mangasarian: 1994, `Parallel Variable Distribution'. SIAM Journal on Optimization 4, 815-832.  @ NUS  Home/Search   Document Details and Download   Summary   Related Articles   Check

....such as BlockJacobi [2] updated conjugate subspaces [10] coordinate descent [21] and parallel gradient distribution [14] de ne (P l ) as a minimization problem on the l th block of variables, i.e. in . More recently, Parallel Variable Distribution (PVD) algorithms, introduced in [6] and further studied and extended in [19, 20, 7] advocated subproblems (P l ) of slightly higher dimensions than n l . In the l th subproblem, in addition to the associated primary optimization variables x l , there are p 1 secondary variables representing in a condensed form all the ....

....fashion (in a subspace of dimension p 1) the additional computational burden of solving such enlarged subproblems is not big. The idea is that the forget me not terms add an extra degree of freedom yielding algorithms with better robustness and faster convergence. We refer the reader to [6, 22, 12] for numerical validation of PVD type methods. We note that not having any variables in parallel subproblems completely xed can be especially important in the constrained case, i.e. when C 6= in (1.1) Without this, the method can simply fail. We shall return to this issue later on. 1.1. ....

[Article contains additional citation context not shown here]

Ferris, M. and O. Mangasarian: 1994, `Parallel Variable Distribution'. SIAM Journal on Optimization 4, 815-832.

....Algorithm 1 belongs to the class of optimization algorithms which use parallel variable distribution. It is known that if the constraint set is in the form of a Cartesian product (i.e. no coupling between the sets of variables of different users) then the algorithm converges to a stationary point [5]. From Theorem 1 in [11] this stationary point achieves the sum capacity of circulant ISI channels. Notice that there are three computational loops in Algorithm 1. The inner loop is used to compute the optimal # ### # ## given all # ### with # . The solution is computed analytically using ....

M. C. Ferris and O. L. Mangasarian, "Parallel variable distribution," SIAM Journal on Optimization, vol. 4, pp. 815--832, 1994.

....and redistributes data sent by the slaves. Fork Join coordination is quite popular in parallel optimization; it is employed by many decomposition algorithms such as: the Dantzig Wolfe decomposition [19] the Schultz Meyer shifted barrier 6 method [92] the Parallel Variable Distribution [33], and Parallel Constraint Distribution [32] algorithms of Ferris and Mangasarian, and the Diagonal Quadratic Approximation method of Mulvey and Ruszczy nski [71] Methods that employ fork join coordination are popular in other areas of scientific computing, as well. For instance, Kowalik and ....

....the algorithm, as measured again its serial implementation; this degree is reflected better in the relative speedup. Thus, in the recent mathematical programming literature, one also finds measurements of parallel efficiency based on the relative speedup (Mangasarian with Deleone [21] and Ferris [33]. In our efficiency estimates for the ADI algorithm in section 7.5.1.3, we will also adopt this approach. Observe now that s p p, since we can simulate an algorithm running on p processors as p serial copies running on a single processor, in roughly p fold time. Super linear speedup can be ....

[Article contains additional citation context not shown here]

M.C. Ferris and O.L. Mangasarian. Parallel variable distribution. SIAM Journal on Optimization, 4(4):815--832, 1994.

....K is large, convergence may be slow, so alternatives are proposed in the remainder of this chapter. 46 3.3.1 Convergence of the method Establishing convergence of the algorithm when coordination is performed as in Step 2 and the minimization in Step 1 is exact is an application of Theorem 3. 6 of Ferris Mangasarian (1993). The following proposition gives the formal statement of this result. Proposition 8 If F 2 LC 1 M (R n1 n2 : nK ) then each accumulation point of the sequence fx t g 1 t=1 computed by the NJA with Step 2a is stationary. An alternative coordination method uses a fixed length step in ....

Ferris, M.C. & O.L. Mangasarian (1993), Parallel variable distribution, Technical Report 1175, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin.

....presented here to other classes of optimization algorithms (for example, 61, 40] is an interesting subject of future research. 81 Chapter 4 Partially Asynchronous Inexact Parallel Variable Distribution Algorithms We consider the recently proposed parallel variable distribution (PVD) algorithm [12] for solving optimization problems in which the variables are distributed among p processors. Each processor has the primary responsibility for updating its block of variables while allowing the remaining secondary variables to change in a restricted fashion along some easily computable ....

....show that nonmonotone synchronization schemes are admissible, which further improves flexibility of PVD approach. 4.1 Introduction We consider the general unconstrained optimization problem min x2 n f(x) 4.1. 1) where f( Delta) 2 C 1 L ( n ) We first state the original PVD algorithm [12]. Let x 2 n be partitioned into p blocks x 1 ; x p , such that x l 2 n l , P p l=1 n l = n. These blocks of variables are then distributed among p parallel processors. Each processor has the primary responsibility for updating its block of variables by solving a subproblem (see ....

[Article contains additional citation context not shown here]

M.C. Ferris and O.L. Mangasarian. Parallel variable distribution. SIAM Journal on Optimization, 4(4):815--832, 1994.

....One needs to do as much work as possible in the parallel phase and try to minimize the drawback of the sequential phase. In [4] Dennis and Steihaug outline a block Jacobi algorithm for the solution of linear least squares problems adapting a method by Mangasarian [9] and Ferris and Mangasarian [6] to least squares problems. This algorithm is a potential candidate for parallelization. The parallel behavior of algorithms are usually more complicated to analyze than their sequential counterparts. Hence, we first build a model In Proceedings of Nordic MPS 99. 1 that gives the outline of ....

....convergence can be enforced by introducing a line search. 4 Renaut in [11] and Dennis and Steihaug in [4] introduced a subspace correction step after each Jacobi loop for the solution of linear least squares problems. They base their correction on Mangasarian [9] and Ferris and Mangasarian [6], where Deltax k = x k 1 Gamma x k is chosen minimizing f(x k Deltax) f = min x kAx Gamma bk M ) in the subspace spanned by d i ; i = 1; g. Let b A = Theta A d k 1 : A d k g , where b A 2 IR m Thetag . A single surrogate variable is chosen to represent the ....

[Article contains additional citation context not shown here]

M. C. Ferris and O. L. Mangasarian, Parallel variable distribution, SIAM J. Optimization 4, pp. 815--832, 1994.

.... been developed such as parallel direct search methods by Dennis and Torczon [90, 34] and Torczon [90] parallel methods for optimization of linked subsystems by Dennis and Lewis [32] and Dennis , Li, and Williamson [33] and variable and constraint distribution schemes by Ferris and Mangasarian [37, 38]. Parallel global optimization has been one of the most active areas in parallel continuous optimization. Work in this area is motivated by important applications in chemical and biological disciplines such as cluster simulation and protein modeling. Algorithms and software developed in recent ....

....(11) but there are other ways to pose optimization with linked subsystems than the straightforward (11) and CO has the comforting feature of mimicing the way parallel teams of disciplinary specialists would attach such problems. 6 Variable and Constraint Distribution Ferris and Mangasarian [37, 38] developed two classes of parallel algorithms for constrained optimization problems. Algorithms of the first class distribute the variables on multiple processors. Each processor updates its own variables in parallel while allowing the other variables to change in a restricted fashion. Once a new ....

[Article contains additional citation context not shown here]

M. C. Ferris and O. L. Mangasarian. Parallel variable distribution. SIAM Journal on Optimization, 4(4):815--832, 1994.

....augmented Lagrangian 15 algorithm. This approach allows use of parallelism on the time consuming portion of the algorithm (step 1 of the augmented Lagrangian algorithm) in an efficient manner. This is an application of the parallel variable distribution method developed by Ferris and Mangasarian [6] to the augmented Lagrangian formulation of the BAP. Barrier Function Methods We dedicate the next chapter to explanation of barrier function methods and Schultz Meyer decomposition scheme for solution of barrier problems. The method developed here is a decomposition method related to ....

M.C. Ferris and O.L. Mangasarian. Parallel variable distribution. Technical Report 1175, Centre for Parallel Optimization, University of Wisconsin, Computer Sciences Dept., 1993.

....17] e.g. In the present paper we apply the same space decomposition principle in order to obtain (parallel) iterative methods for minimizing f . Our work is based on [17] and [15] where such iterative space decomposition methods have been studied for general strongly convex functionals, and on [4] where the parallel variable distribution (PVD) algorithm was introduced. We show that for quadratic functionals the convergence results from [15] can be extended to allow for a certain amount of over relaxation. As a special case, our results will Department of Mathematics, University of ....

....of the relationship of our results to previous work, particularly linear least squares and multisplitting methods. Auxiliary required results are presented in the appendix. In a future paper we will describe the extension of this theory to include results for constrained problems, cf. 3] [4], and [13] 2. Space decomposition. Throughout the whole paper we denote by V i ; i = 1; m; a collection of m (non trivial) subspaces of V = R n which span the whole of V , i.e. V = m X i=1 V i : 2.1) We do not assume that this sum is direct, so a vector in V may have several ....

[Article contains additional citation context not shown here]

M.C. Ferris and O.L. Mangasarian, Parallel Variable Distribution, SIAM J. Optim. 4 (1994), 815--832.

....University, AZ 85287 1804. Fax. 602) 965 0461, Tel. 602) 965 6595, e mail mittelmann math.la.asu.edu. 2 Renaut et al. sequential algorithms for the solution of reduced size subproblems. Algorithms which attack (2) and (3) in this way are presented, for example, by Ferris and Mangasarian [6], and Bertsekas and Tsitsiklis [2] Although not presented as such, these latter algorithms can be considered as algorithms of multisplitting type. In this paper the multisplitting technique is extended to allow for the solution of the constrained problems (2) and (3) Results demonstrating the ....

....19 (7) 1.2 33 (11) 2.4 64 19 (6) 7 33 (10) 1.3 128 20 (6) 6 34 (13) 1.1 256 19 (7) 5 30 (10) 1.1 an unconstrained one and using the techniques of the previous section, the preferable alternative appears to be the reduction to a problem with separable constraints. One such way was suggested in [6], another one could be based on [15] Both use exact penalty functions, an advantage of the latter would be that it is parameter free. We choose the first approach. As was shown in [8] the constrained problem, 3) may under suitable conditions be replaced by min x min u0 f Gammaf (x) Gamma ....

M. C. Ferris and O. L. Mangasarian, Parallel Variable Distribution, CS Dept., University of Wisconsin (1993)

....MMCF has shown this approach to be efficient in practice, especially on problems where the number of commodities is high w.r.t. the dimension of the graph. During the last few years, a large theoretical and practical effort [ZM88] Me90] CCZ91] Fe91] FM91] Ze91] PZ92] GH93] LGM93] FH94] [FM94] [Ko94] LKM94] Ze93] ZaA95] ZaG95] has been done to develop parallel approaches to MMCF, demonstrating the interest that the solution of large scale Multicommodity flow problems has in the OR community: in this work, the results obtained by the parallelization of the efficient Bundle type code ....

.... are the Parallel Constraint Distribution (PCD) method [FM91] that distributes the constraints among the PEs and modifies each subproblem objective function with augmented Lagrangean terms from other PEs, and the Parallel Variable Distribution Paola Cappanera and Antonio Frangioni 5 (PVD) method [FM94], that distributes the variables among the PEs, so that each PE has primary responsibility for updating its own block of variables while allowing the remaining ones to change in a restricted fashion the process is followed by a Master problem of controlled size, in which the affine hull of (some ....

M.C. FERRIS, O.L. MANGASARIAN "Parallel Variable Distribution" SIAM J. on Optimization 4(4), p. 815-832, 1994

....as it was done in [12] This approach is in a way more appealing because it offers the possibility of continued use of welltested sequential algorithms and codes for the solution of reduced size problems. Algorithms which attack optimization problems in this way are considered, for example, in [3]. In fact, their conclusion, it seems that the only sensible way to distribute variables for problems with inseparable constraints is to convert them to unconstrained problems or to problems with separable constraints and their suggestion to use dual differentiable exact penalty functions for ....

.... constraints is to convert them to unconstrained problems or to problems with separable constraints and their suggestion to use dual differentiable exact penalty functions for that purpose partly lead to our earlier paper [12] However, a key difference between their approach as used in [3] for unconstrained problems only and ours, both in [12] and in the present paper, is that the subproblem solved on each processor in their algorithm makes use of all variables and, in fact, updates all of them. On the other hand, in our algorithm which is of block Jacobi type we completely ....

M.C. Ferris and O.L. Mangasarian, Parallel variable distribution, SIAM J. Optim. 4 (1994), 815--832.

....de Matematica Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botanico, Rio de Janeiro, RJ, CEP 22460 320, Brazil Received June 26, 1995; Revised October 24, 1995 Editor: Abstract. We consider the recently proposed parallel variable distribution (PVD) algorithm of Ferris and Mangasarian [4] for solving optimization problems in which the variables are distributed among p processors. Each processor has the primary responsibility for updating its block of variables while allowing the remaining secondary variables to change in a restricted fashion along some easily computable ....

....improves flexibility of PVD approach. Keywords: Parallel optimization, load balancing, unconstrained minimization, linear convergence 1. Introduction We consider the general unconstrained optimization problem min x2 n f(x) 1) where f : n . We first state the original PVD algorithm [4]. Let x 2 n be partitioned into p blocks x 1 ; x p , such that x l 2 n l , P p l=1 n l = n. These blocks of variables are then distributed among p parallel processors. Each processor has the primary responsibility for updating its block of variables by solving the parallelization ....

[Article contains additional citation context not shown here]

M.C. Ferris and O.L. Mangasarian. Parallel variable distribution. SIAM Journal on Optimization, 4(4):815--832, 1994.

....results are presented for the solution of multicommodity flow problems with these three techniques on the TMC CM 5 parallel supercomputer. As with many other decomposition methods (Dantzig Wolfe decomposition [7] the Schultz Meyer shifted barrier method [28] the Parallel Variable Distribution [13] and Parallel Constraint Distribution [12] algorithms of Ferris and Mangasarian, and the Diagonal Quadratic Approximation method of Mulvey and Ruszczynski [24] these procedures use the fork join protocol for the global organization of the computation. In this computational model, there is a data ....

M.C. Ferris and O.L. Mangasarian. Parallel variable distribution. Technical Report 1175, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 1993.

....Sports and Culture, Japan. 1. Introduction In the last several years, a number of novel parallel algorithms for solving nonlinear optimization problems have been developed. Among others, Mangasarian [8] proposed the parallel gradient distribution (PGD) algorithm, and Ferris and Mangasarian [2] presented the parallel variable distribution (PVD) algorithm, which was further studied by Solodov [13] More recently, one of the authors [4] presented a general framework for unconstrained nonlinear optimization called the parallel variable transformation (PVT) algorithm that encompasses the ....

....broad enough to contain a number of existing parallel optimization algorithms. In fact, it was shown in [4] that the parallel gradient distribution (PGD) algorithm of Mangasarian [8] the unconstrained version of the parallel variable distribution (PVD) algorithm proposed by Ferris and Mangasarian [2] and further studied by Solodov [13] belong to the class of the PVT algorithm. The updated conjugate subspaces (UCS) method of Han [5] was also shown to be closely related to the PVT algorithm [4] In this section, we focus on the special case of the PVT algorithm that was suggested in [4] This ....

[Article contains additional citation context not shown here]

M.C. Ferris and O.L. Mangasarian, \Parallel variable distribution," SIAM J. on Optimization, vol. 4, pp. 102-126, 1994.

.... Applied Mathematics Rice University Houston TX 77005 1892 Trond Steihaug Department of Informatics University of Bergen Hyteknologisenteret N 5020 Bergen Norway May 1, 1998 Abstract This note specializes to linear least squares problems an approach suggested by Ferris and Mangasarian [4] for solving constrained optimization problems on parallel computers. It will be shown here that this specialization leads to an algorithm which is mathematically equivalent to an acceleration and convergence forcing modification of the block Jacobi iteration applied to the normal equations. ....

....Research supported by The Research Council of Norway and VISTA a research cooperation between the Norwegian Academy of Science and Den norske stats oljeselskap a. s (Statoil) 1 Introduction This note specializes to linear least squares problems an approach suggested by Ferris and Mangasarian [4] for solving constrained optimization problems on parallel computers. It will be shown here that this specialization leads to an acceleration and convergence forcing mechanism for the block Jacobi iteration applied to the normal equations. We do not form the full normal equations, but our ....

[Article contains additional citation context not shown here]

M. C. Ferris and O. L. Mangasarian, Parallel variable distribution, SIAM J. Optimization 4(1994) 815-832.

....with millions of variables can be solved with present day state of the art methods, large scale databases are amenable to the proposed linear programming based methods. In addition there is a large body of literature on the parallel solution and decomposition of large scale mathematical programs [7, 16, 17, 19] where for many of the algorithms only part of the data is loaded into memory at a time. Such parallel and decomposition algorithms extend further the applicability of the proposed methods to very large scale databases. From a numerical standpoint, mathematical programming codes, and especially ....

M. C. Ferris and O. L. Mangasarian. Parallel variable distribution. SIAM Journal on Optimization, 4(4):815--832, 1994.

....constraints and variables. a) Decomposing constraints and variables into subsets. The parallel constraint distribution approach of [49] is one way of decomposing problem constraints among parallel processors or parallel virtual machines (PVM) 56, 77] while the parallel variable distribution of [50] can be similarly applied when dealing with databases with a very large number of attributes. b) Algorithms for dealing with constraints and variables sequentially. Mathematical programming approaches that deal with problem data in a sequential manner are very useful for processing large ....

M. C. Ferris and O. L. Mangasarian. Parallel variable distribution. SIAM Journal on Optimization, 4(4):815--832, 1994.

....programs. The analysis of this paper does not rely on the linearity of the constraints. Nonlinear programs can use the same technique to exploit underlying structure in the constraint set and enable the efficient solution of such problems using decomposition techniques such as those found in [5,6,29]. Furthermore, although many modern modeling languages and systems allow block structure to be specified during problem formulation, the techniques we outline here can be used to modify such a partition to take full advantage of the number and relative performance of the available parallel ....

M. C. Ferris and O. L. Mangasarian, "Parallel variable distribution", SIAM Journal on Optimization 4 (1994) 815--832.

.... and Applied Mathematics Rice University Houston TX 77005 1892 Trond Steihaug y Department of Informatics University of Bergen H yteknologisenteret N 5020 Bergen Norway May 1, 1998 Abstract This note specializes to linear least squares problems an approach suggested by Ferris and Mangasarian [4] for solving constrained optimization problems on parallel computers. It will be shown here that this specialization leads to an algorithm which is mathematically equivalent to an acceleration and convergence forcing modification of the block Jacobi iteration applied to the normal equations. The ....

....Research supported by The Research Council of Norway and VISTA a research cooperation between the Norwegian Academy of Science and Den norske stats oljeselskap a. s (Statoil) 1 Introduction This note specializes to linear least squares problems an approach suggested by Ferris and Mangasarian [4] for solving constrained optimization problems on parallel computers. It will be shown here that this specialization leads to an acceleration and convergence forcing mechanism for the block Jacobi iteration applied to the normal equations. We do not form the full normal equations, but our ....

[Article contains additional citation context not shown here]

M. C. Ferris and O. L. Mangasarian, Parallel variable distribution, SIAM J. Optimization 4(1994) 815-832.

Online articles have much greater impact   More about CiteSeer.IST at NUS   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.