A three-level BDDC algorithm for a saddle point problem

BDDC algorithms have previously been extended to the saddle point problems arising from mixed formulations of elliptic and incompressible Stokes problems. In these two-level BDDC algorithms, all iterates are required to be in a benign space, a subspace in which the preconditioned operators are positive definite. This requirement can lead to large coarse problems, which have to be generated and factored by a direct solver at the beginning of the computation and they can ultimately become a bottleneck. An additional level is introduced in this paper to solve the coarse problem approximately and to remove this difficulty. This three-level BDDC algorithm keeps all iterates in the benign space and the conjugate gradient methods can therefore be used to accelerate the convergence. This work is an extension of the three-level BDDC methods for standard finite element discretization of elliptic problems and the same rate of convergence is obtained for the mixed formulation of the same problems. Estimate of the condition number for this three-level BDDC methods is provided and numerical experiments are discussed.     

On a saddle point problem arising from magneto-elastic coupling

This paper deals with the analysis of a coupled problem arising from linear magneto-elastostatics. The model, which can be derived by an energy principle, gives valuable insight into the coupling mechanism and features a saddle point structure with the elastic displacement and magnetic scalar potential as independent variables. As main results, the existence and uniqueness of the solution are proven for the continuous and discrete cases and special properties of the corresponding bilinear forms are shown. In particular, the coupled magneto-elastic bilinear form satisfies an inf–sup condition for a certain class of magnetostrictive materials, that is essential for the stability of the problem.     

Block diagonally preconditioned PIU methods of saddle point problem

For large sparse saddle point problems, we firstly introduce the block diagonally preconditioned Gauss-Seidl method (PBGS) which reduces to the GSOR method [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38] and PIU method [Z.-Z. Bai, Z.-Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl. 428 (2008) 2900-2932] when the preconditioners equal to different matrices, respectively. Then we generalize the PBGS method to the PPIU method and discuss the sufficient conditions such that the spectral radius of the PPIU method is much less than one. Furthermore, some rules are considered for choices of the preconditioners including the splitting method of the (1, 1) block matrix in the PIU method and numerical examples are given to show the superiority of the new method to the PIU method.     

Large-scale semidefinite programming via a saddle point Mirror-Prox algorithm

In this paper, we first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We derive also the “dual counterpart” of the outlined representation, which expresses the possibility of positive semidefinite completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch of fully defined submatrices of the matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex–concave saddle point problems, which can be solved by a Prox-method developed in [6] with efficiency . Implementations and some numerical results for large-scale Lovász capacity and MAXCUT problems are finally presented.      

The saddle point property for focusing selfsimilar solutions in a free boundary problem

We establish the saddle point property of the focusing selfsimilar solution of a free boundary problem for the heat equation with free boundary conditions given by and .

     

Sign-changing saddle point

In this paper, the Saddle-point theorems are generalized to a new version by showing that there exists a “sign-changing” saddle point besides zero. The abstract result is applied to the semilinear elliptic boundary value problem

     

A re-scaled twin augmented Lagrangian algorithm for saddle point seeking

In [A. Ouorou, A primal-dual algorithm for monotropic programming and its application to network optimization, Computational Optimization and Application 15 (2002) 125–143], a block-wise Gauss–Seidel method has been developed for monotropic programming problems, using two different quadratic augmented Lagrangian functions defined for the primal and the dual problems. In this paper, we extend the concept by introducing a nonlinear re-scaling principle obtained recently by Polyak [R. Polyak, Nonlinear rescaling vs smoothing technique in constrained optimization, Mathematical Programming 92 (2002) 197–235].     

Convergence analysis of the corrected Uzawa algorithmfor symmetric saddle point problems简

For the large sparse saddle point problems, Pan and Li recently proposed in [H. K. Pan, W. Li, Math. Numer. Sinica, 2009, 31（3）： 231-242] a corrected Uzawa algorithm based on a nonlinear Uzawa algorithm with two nonlinear approximate inverses, and gave the detailed convergence analysis. In this paper, we focus on the convergence analysis of this corrected Uzawa algorithm, some inaccuracies in [H. K. Pan, W. Li, Math. Numer. Sinica, 2009, 31（3）： 231-242] are pointed out, and a corrected convergence theorem is presented. A special case of this modified Uzawa algorithm is also discussed.     

A convergence analysis of the nonlinear Uzawa algorithm for saddle point problems

In this paper we discuss the convergence behavior of the nonlinear inexact Uzawa algorithm for solving saddle point problems presented in a recent paper by Cao [Z.H. Cao, Fast Uzawa algorithm for generalized saddle point problems, Appl. Numer. Math. 46 (2003) 157–171]. We show that this algorithm converges under a condition weaker than that stated in this paper.     

An extragradient method for finding the saddle point in an optimal control problem

We propose an extragradient method for finding the saddle point of a convex-concave functional defined on solutions of controlled systems of linear ordinary differential equations. We prove the convergence of the method.     

Iterative proximal regularization method for finding a saddle point in the semicoercive Signorini problem

An algorithm for seeking a saddle point for the semicoercive variational Signorini inequality is studied. The algorithm is based on an iterative proximal regularization of a modified Lagrangian functional.     

Regularized extragradient method for finding a saddle point in an optimal control problem

We study n-dimensional cubical pseudomanifolds and their cellular mappings. In particular, we consider a discrete n-cube and all of its (n ? 1)-faces. Then, there exist either one or two or four faces of the cube each of which is mapped onto one face.     

The alternating-direction iterative method for saddle point problems

In the paper, a new alternating-direction iterative method is proposed based on matrix splittings for solving saddle point problems. The convergence analysis for the new method is given. When the better values of parameters are employed, the proposed method has faster convergence rate and less time cost than the Uzawa algorithm with the optimal parameter and the Hermitian and skew-Hermitian splitting iterative method. Numerical examples further show the effectiveness of the method.     

A sufficient condition for the convergence of the inexact Uzawa algorithm for saddle point problems

In this paper, the convergence property of the inexact Uzawa algorithm for solving symmetric indefinite linear systems is studied. A simple sufficient condition for the convergence of the inexact Uzawa algorithm is obtained. Two examples and numerical experiments illustrating the conclusion are provided.     

A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems

Numerical Algorithms - Efficient and accurate numerical schemes for solving the Helmholtz equation are critical to the success of various wave propagation–related inverse problems, for...     

Convergence analysis of generalized nonlinear inexact Uzawa algorithm for stabilized saddle point problems

This paper deals with a modified nonlinear inexact Uzawa (MNIU) method for solving the stabilized saddle point problem. The modified Uzawa method is an inexact inner-outer iteration with a variable relaxation parameter and has been discussed in the literature for uniform inner accuracy. This paper focuses on the general case when the accuracy of inner iteration can be variable and the convergence of MNIU with variable inner accuracy, based on a simple energy norm. Sufficient conditions for the convergence of MNIU are proposed. The convergence analysis not only greatly improves the existing convergence results for uniform inner accuracy in the literature, but also extends the convergence to the variable inner accuracy that has not been touched in literature. Numerical experiments are given to show the efficiency of the MNIU algorithm.