Dual‐primal FETI methods for linear elasticity

Dual‐primal FETI methods are nonoverlapping domain decomposition methods where some of the continuity constraints across subdomain boundaries are required to hold throughout the iterations, as in primal iterative substructuring methods, while most of the constraints are enforced by Lagrange multipliers, as in one‐level FETI methods. These methods are used to solve the large algebraic systems of equations that arise in elliptic finite element problems. The purpose of this article is to develop strategies for selecting these constraints, which are enforced throughout the iterations, such that good convergence bounds are obtained that are independent of even large changes in the stiffness of the subdomains across the interface between them. The algorithms are described in terms of a change of basis that has proven to be quite robust in practice. A theoretical analysis is provided for the case of linear elasticity, and condition number bounds are established that are uniform with respect to arbitrarily large jumps in the Young's modulus of the material and otherwise depend only polylogarithmically on the number of unknowns of a single subdomain. The strategies have already proven quite successful in large‐scale implementations of these iterative methods. © 2006 Wiley Periodicals, Inc.     

Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem

For optimization problems that are structured both with respect to the constraints and with respect to the variables, it is possible to use primal–dual solution approaches, based on decomposition principles. One can construct a primal subproblem, by fixing some variables, and a dual subproblem, by relaxing some constraints and king their Lagrange multipliers, so that both these problems are much easier to solve than the original problem. We study methods based on these subproblems, that do not include the difficult Benders or Dantzig-Wolfe master problems, namely primal–dual subgradient optimization methods, mean value cross decomposition, and several comtbinations of the different techniques. In this paper, these solution approaches are applied to the well-known uncapacitated facility location problem. Computational tests show that some combination methods yield near-optimal solutions quicker than the classical dual ascent method of Erlenkotter     

Unified multipliers‐free theory of dual‐primal domain decomposition methods

The concept of dual‐primal methods can be formulated in a manner that incorporates, as a subclass, the non preconditioned case. Using such a generalized concept, in this article without recourse to “Lagrange multipliers,” we introduce an all‐inclusive unified theory of nonoverlapping domain decomposition methods (DDMs). One‐level methods, such as Schur‐complement and one‐level FETI, as well as two‐level methods, such as Neumann‐Neumann and preconditioned FETI, are incorporated in a unified manner. Different choices of the dual subspaces yield the different dual‐primal preconditioners reported in the literature. In this unified theory, the procedures are carried out directly on the matrices, independently of the differential equations that originated them. This feature reduces considerably the code‐development effort required for their implementation and permit, for example, transforming 2D codes into 3D codes easily. Another source of this simplification is the introduction of two projection‐matrices, generalizations of the average and jump of a function, which possess superior computational properties. In particular, on the basis of numerical results reported there, we claim that our jump matrix is the optimal choice of the B operator of the FETI methods. A new formula for the Steklov‐Poincaré operator, at the discrete level, is also introduced. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

Primal and Dual Penalty Methods for Contact Problems with Geometrical Non-linearities

The nonlinearity caused by two or more bodies in contact is often source of computational difficulties. Probably the most popular solution method is based on direct iterations with the non-penetration conditions imposed by the penalty method [1]. The method enables treatment of other non-linearities such as in the case of large displacements. In this paper we are concerned with application of a variant of the FETI domain decomposition method that enforces feasibility of Lagrange multipliers by the penalty [5]. The dual penalty method, which has been shown to be optimal for small displacements, is used in inner loop of the algorithm that treats large displacements. We give results of numerical experiments that demonstrate high efficiency of the FETI method with the dual penalty. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multipliers‐free dual‐primal domain decomposition methods for nonsymmetric matrices and their numerical testing

The most commonly used nonoverlapping domain decomposition algorithms, such as the FETI‐DP and BDDC, require the introduction of discontinuous vector spaces. Most of the works on such methods are based on approaches that originated in Lagrange multipliers formulations. Using a theory of partial differential equations formulated in discontinuous piecewise‐defined functions, introduced and developed by Herrera and his collaborators through a long time span, recently the authors have developed an approach to domain decomposition methods in which general problems with prescribed jumps are treated at the discrete level. This yields an elegant and general direct framework that permits analyzing the problems in greater detail. The algorithms derived using it have properties similar to those of well‐established methods such as FETI‐DP, but, in our experience, they are easier to implement. Also, they yield explicit matrix formulas that unify the different methods. Furthermore, this multipliers‐free framework has permitted us to extend such formulas to make them applicable to nonsymmetric matrices. The extension of the unifying matrix formulas to nonsymmetric matrices is the subject matter of the present article. A conspicuous result is that in numerical experiments in 2D and 3D, the MF‐DP algorithms for nonsymmetric matrices exhibit an efficiency of the same order as state‐of‐the‐art algorithms for symmetric matrices, such as BDDC, FETI‐DP, and MF‐DP.© 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1262‐1289, 2011     

FETI and Neumann‐Neumann iterative substructuring methods: Connections and new results

The FETI and Neumann‐Neumann families of algorithms are among the best known and most severely tested domain decomposition methods for elliptic partial differential equations. They are iterative substructuring methods and have many algorithmic components in common, but there are also differences. The purpose of this paper is to further unify the theory for these two families of methods and to introduce a new family of FETI algorithms. Bounds on the rate of convergence, which are uniform with respect to the coefficients of a family of elliptic problems with heterogeneous coefficients, are established for these new algorithms. The theory for a variant of the Neumann‐Neumann algorithm is also redeveloped stressing similarities to that for the FETI methods. © 2001 John Wiley & Sons, Inc.     

Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems

A variant of balancing domain decomposition method by constraints (BDDC) is proposed for solving a class of indefinite systems of linear equations of the form (K?σ²M)u=f, which arise from solving eigenvalue problems when an inverse shifted method is used and also from the finite element discretization of Helmholtz equations. Here, both K and M are symmetric positive definite. The proposed BDDC method is closely related to the previous dual–primal finite element tearing and interconnecting method (FETI‐DP) for solving this type of problems (Appl. Numer. Math. 2005; 54 :150–166), where a coarse level problem containing certain free‐space solutions of the inherent homogeneous partial differential equation is used in the algorithm to accelerate the convergence. Under the condition that the diameters of the subdomains are small enough, the convergence rate of the proposed algorithm is established, which depends polylogarithmically on the dimension of the individual subdomain problems and which improves with a decrease of the subdomain diameters. These results are supported by numerical experiments of solving a two‐dimensional problem. Copyright © 2009 John Wiley & Sons, Ltd.     

The multipliers‐free domain decomposition methods

This article concludes the development and summarizes a new approach to dual‐primal domain decomposition methods (DDM), generally referred to as “the multipliers‐free dual‐primal method.” Contrary to standard approaches, these new dual‐primal methods are formulated without recourse to Lagrange‐multipliers. In this manner, simple and unified matrix‐expressions, which include the most important dual‐primal methods that exist at present are obtained, which can be effectively applied to floating subdomains, as well. The derivation of such general matrix‐formulas is independent of the partial differential equations that originate them and of the number of dimensions of the problem. This yields robust and easy‐to‐construct computer codes. In particular, 2D codes can be easily transformed into 3D codes. The systematic use of the average and jump matrices, which are introduced in this approach as generalizations of the “average” and “jump” of a function, can be effectively applied not only at internal‐boundary‐nodes but also at edges and corners. Their use yields significant advantages because of their superior algebraic and computational properties. Furthermore, it is shown that some well‐known difficulties that occur when primal nodes are introduced are efficiently handled by the multipliers‐free dual‐primal method. The concept of the Steklov–Poincaré operator for matrices is revised by our theory and a new version of it, which has clear advantages over standard definitions, is given. Extensive numerical experiments that confirm the efficiency of the multipliers‐free dual‐primal methods are also reported here. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

A Dual-Primal FETI method for incompressible Stokes equations

In this paper, a dual-primal FETI method is developed for incompressible Stokes equations approximated by mixed finite elements with discontinuous pressures. The domain of the problem is decomposed into nonoverlapping subdomains, and the continuity of the velocity across the subdomain interface is enforced by introducing Lagrange multipliers. By a Schur complement procedure, the solution of an indefinite Stokes problem is reduced to solving a symmetric positive definite problem for the dual variables, i.e., the Lagrange multipliers. This dual problem is solved by the conjugate gradient method with a Dirichlet preconditioner. In each iteration step, both subdomain problems and a coarse level problem are solved by a direct method. It is proved that the condition number of this preconditioned dual problem is independent of the number of subdomains and bounded from above by the square of the product of the inverse of the inf-sup constant of the discrete problem and the logarithm of the number of unknowns in the individual subdomains. Numerical experiments demonstrate the scalability of this new method. This work is based on a doctoral dissertation completed at Courant Institute of Mathematical Sciences, New York University. This work was supported in part by the National Science Foundation under Grants NSF-CCR-9732208, and in part by the U.S. Department of Energy under contract DE-FG02-92ER25127.     

A comparison of alternative c-conjugate dual problems in infinite convex optimization

In this work, we obtain a Fenchel–Lagrange dual problem for an infinite dimensional optimization primal one, via perturbational approach and using a conjugation scheme called c-conjugation instead of classical Fenchel conjugation. This scheme is based on the generalized convex conjugation theory. We analyse some inequalities between the optimal values of Fenchel, Lagrange and Fenchel–Lagrange dual problems and we establish sufficient conditions under which they are equal. Examples where such inequalities are strictly fulfilled are provided. Finally, we study the relations between the optimal solutions and the solvability of the three mentioned dual problems.     

New formulation of iterative substructuring methods without Lagrange multipliers: Neumann–Neumann and FETI

This article is devoted to introduce a new approach to iterative substructuring methods that, without recourse to Lagrange multipliers, yields positive definite preconditioned formulations of the Neumann–Neumann and FETI types. To my knowledge, this is the first time that such formulations have been made without resource to Lagrange multipliers. A numerical advantage that is concomitant to such multipliers‐free formulations is the reduction of the degrees of freedom associated with the Lagrange multipliers. Other attractive features are their generality, directness, and simplicity. The general framework of the new approach is rather simple and stems directly from the discretization procedures that are applied; in it, the differential operators act on discontinuous piecewise‐defined functions. Then, the Lagrange multipliers are not required because in such an environment the functions‐discontinuities are not an anomaly that need to be corrected. The resulting algorithms and equations‐systems are also derived with considerable detail. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

Solving dual problems using a coevolutionary optimization algorithm

In solving certain optimization problems, the corresponding Lagrangian dual problem is often solved simply because in these problems the dual problem is easier to solve than the original primal problem. Another reason for their solution is the implication of the weak duality theorem which suggests that under certain conditions the optimal dual function value is smaller than or equal to the optimal primal objective value. The dual problem is a special case of a bilevel programming problem involving Lagrange multipliers as upper-level variables and decision variables as lower-level variables. Another interesting aspect of dual problems is that both lower and upper-level optimization problems involve only box constraints and no other equality of inequality constraints. In this paper, we propose a coevolutionary dual optimization (CEDO) algorithm for co-evolving two populations—one involving Lagrange multipliers and other involving decision variables—to find the dual solution. On 11 test problems taken from the optimization literature, we demonstrate the efficacy of CEDO algorithm by comparing it with a couple of nested smooth and nonsmooth algorithms and a couple of previously suggested coevolutionary algorithms. The performance of CEDO algorithm is also compared with two classical methods involving nonsmooth (bundle) optimization methods. As a by-product, we analyze the test problems to find their associated duality gap and classify them into three categories having zero, finite or infinite duality gaps. The development of a coevolutionary approach, revealing the presence or absence of duality gap in a number of commonly-used test problems, and efficacy of the proposed coevolutionary algorithm compared to usual nested smooth and nonsmooth algorithms and other existing coevolutionary approaches remain as the hallmark of the current study.     

Efficient algorithms for buffer space allocation

This paper describes efficient algorithms for determining how buffer space should be allocated in a flow line. We analyze two problems: a primal problem, which minimizes total buffer space subject to a production rate constraint; and a dual problem, which maximizes production rate subject to a total buffer space constraint. The dual problem is solved by means of a gradient method, and the primal problem is solved using the dual solution. Numerical results are presented. Profit optimization problems are natural generalizations of the primal and dual problems, and we show how they can be solved using essentially the same algorithms.     

Stabilized dynamic constraint aggregation for solving set partitioning problems

Dynamic constraint aggregation (DCA) and dual variable stabilization (DVS) are two methods that can reduce the negative impact of degeneracy when solving linear programs. The first uses a projection to reduce the primal space whereas the second acts in the dual space. In this paper, we develop a new method, called stabilized dynamic constraint aggregation (SDCA), that combines DCA and DVS for solving set partitioning problems. It allows to fight degeneracy from both primal and dual perspectives simultaneously. To assess the effectiveness of SDCA, we report computational results obtained for highly degenerate multi-depot vehicle scheduling problem instances solved by column generation. These results indicate that SDCA can reduce the average computational time of the master problem by a factor of up to 7 with respect to the best of the two combined methods. Furthermore, they show that its performance is robust with regard to increasing levels of degeneracy in test problems.     

On the convergence of a dual-primal substructuring method

Summary.   In the Dual-Primal FETI method, introduced by Farhat et al. [5], the domain is decomposed into non-overlapping subdomains, but the degrees of freedom on crosspoints remain common to all subdomains adjacent to the crosspoint. The continuity of the remaining degrees of freedom on subdomain interfaces is enforced by Lagrange multipliers and all degrees of freedom are eliminated. The resulting dual problem is solved by preconditioned conjugate gradients. We give an algebraic bound on the condition number, assuming only a single inequality in discrete norms, and use the algebraic bound to show that the condition number is bounded by for both second and fourth order elliptic selfadjoint problems discretized by conforming finite elements, as well as for a wide class of finite elements for the Reissner-Mindlin plate model. Received January 20, 2000 / Revised version received April 25, 2000 / Published online December 19, 2000     

Substructuring FE–XFE approaches applied to three-dimensional crack propagation

Two substructuring methods are investigated in order to allow for the use of the eXtended Finite Element Method (X-FEM) within commercial finite element (FE) codes without need for modifying their kernel. The global FE problem is decomposed into two subdomains, the safe domain and the cracked domain based on the value of the level sets representing the crack. The safe domain is treated by the host FE software while the cracked domain is treated by an independent XFE code. The first substructuring method consists of calculating the Schur matrix of a cracked super-element with the XFE code. The second technique introduces the finite element tearing and interconnecting method (FETI) which ensures the compatibility of the displacements at the interface between the cracked and safe subdomains. The stiffness matrices and nodal forces are provided by the XFE and FE codes for the cracked and safe subdomains, respectively. The solutions obtained with these two techniques are rigorously equivalent to those computed with the stand-alone XFE code. First, the computational efficiency of the two approaches is demonstrated. Second, a validation is proposed towards comparison with reference values of the stress intensity factors in simple 3D cracked geometries. Finally, this contribution presents an application of the FE–XFE–FETI method to the computation of the stress intensity factor induced by a crack inside a hydraulic cylinder under internal pressure.     

Numerical modeling of atomistic-to-continuum coupling based on bridging domain method

Nano-submodeling is an approach that enables insertion of nano-refined submodel (atomistic) in the global model (continuum). In this work analysis of the spurious effects that may arise in the concurrent atomistic-to-continuum coupling is performed. The coupling is based on the overlapping domain decomposition (ODD) method called bridging domain [1, 2] (similar is Arlequin [3] method) where different models are overlapped and the displacements compatibility is enforced via Lagrange multipliers (LM). Some coupling options such as energy weighting, coupling zone geometry and LM field interpolation are tested. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stable strong Fenchel and Lagrange duality for evenly convex optimization problems

By means of a conjugation scheme based on generalized convex conjugation theory instead of Fenchel conjugation, we build an alternative dual problem, using the perturbational approach, for a general optimization one defined on a separated locally convex topological space. Conditions guaranteeing strong duality for primal problems which are perturbed by continuous linear functionals and their respective dual problems, which is named stable strong duality, are established. In these conditions, the fact that the perturbation function is evenly convex will play a fundamental role. Stable strong duality will also be studied in particular for Fenchel and Lagrange primal–dual problems, obtaining a characterization for Fenchel case.     

Suitable iterative methods for solving the linear system arising in the three fields domain decomposition method

There are two approaches for applying substructuring preconditioner for the linear system corresponding to the discrete Steklov–Poincaré operator arising in the three fields domain decomposition method for elliptic problems. One of them is to apply the preconditioner in a common way, i.e. using an iterative method such as preconditioned conjugate gradient method [S. Bertoluzza, Substructuring preconditioners for the three fields domain decomposition method, I.A.N.-C.N.R, 2000] and the other one is to apply iterative methods like for instance bi-conjugate gradient method, conjugate gradient square and etc. which are efficient for nonsymmetric systems (the preconditioned system will be nonsymmetric). In this paper, second approach will be followed and extensive numerical tests will be presented which imply that the considered iterative methods are efficient.     

Two-level primal-dual decomposition technique for large-scale nonconvex optimization problems with constraints

A two-level decomposition method for nonconvex separable optimization problems with additional local constraints of general inequality type is presented and thoroughly analyzed in the paper. The method is of primal-dual type, based on an augmentation of the Lagrange function. Previous methods of this type were in fact three-level, with adjustment of the Lagrange multipliers at one of the levels. This level is eliminated in the present approach by replacing the multipliers by a formula depending only on primal variables and Kuhn-Tucker multipliers for the local constraints. The primal variables and the Kuhn-Tucker multipliers are together the higher-level variables, which are updated simultaneously. Algorithms for this updating are proposed in the paper, together with their convergence analysis, which gives also indications on how to choose penalty coefficients of the augmented Lagrangian. Finally, numerical examples are presented.