Distributed Adaptive Resource Allocation:An Uncertain Saddle-Point Dynamics Viewpoint

This paper addresses distributed adaptive optimal resource allocation problems over weight-balanced digraphs.By leveraging state-of-the-art adaptive coupling designs for multiagent systems,two adaptive algorithms are proposed,namely a directed-spanning-tree-based algorithm and a node-based algorithm.The benefits of these algorithms are that they require neither sufficiently small or unitary step sizes,nor global knowledge of Laplacian eigenvalues,which are widely required in the literature.It is shown that both algorithms belong to a class of uncertain saddle-point dynamics,which can be tackled by repeatedly adopting the Peter-Paul inequality in the framework of Lyapunov theory.Thanks to this new viewpoint,global asymptotic convergence of both algorithms can be proven in a unified way.The effectiveness of the proposed algorithms is validated through numerical simulations and case studies in IEEE 30-bus and 118-bus power systems.

Semi-regularized Hermitian and Skew-Hermitian Splitting Preconditioning for Saddle-Point Linear Systems

In this paper,a two-step semi-regularized Hermitian and skew-Hermitian splitting(SHSS)iteration method is constructed by introducing a regularization matrix in the(1,1)-block of the first iteration step,to solve the saddle-point linear system.By carefully selecting two different regularization matrices,two kinds of SHSS preconditioners are proposed to accelerate the convergence rates of the Krylov subspace iteration methods.Theoretical analysis about the eigenvalue distribution demonstrates that the proposed SHSS preconditioners can make the eigenvalues of the corresponding preconditioned matrices be clustered around 1 and uniformly bounded away from 0.The eigenvector distribution and the upper bound on the degree of the minimal polynomial of the SHSS-preconditioned matrices indicate that the SHSS-preconditioned Krylov subspace iterative methods can converge to the true solution within finite steps in exact arithmetic.In addition,the numerical example derived from the optimal control problem shows that the SHSS preconditioners can significantly improve the convergence speeds of the Krylov subspace iteration methods,and their convergence rates are independent of the discrete mesh size.

GENERALIZED AUGMENTED LAGRANGIAN-SOR ITERATION METHOD FOR SADDLE-POINT SYSTEMS ARISING FROM DISTRIBUTED CONTROL PROBLEMS＊

In this paper, a generalized augmented Lagrangian-successive over-relaxation （GAL- SOR） iteration method is presented for solving saddle-point systems arising from distributed control problems. The convergence properties of the GAL-SOR method are studied in the spectral properties for the precondidetail. Moreover, when0 ≤ω≤ 1 and Q=1/γI , tioned matrix are analyzed. Numerical experiments show that if the mass matrix from the distributed control problems is not easy to inverse and the regularization parameter β is very small, the GAL-SOR iteration method can work well.

An Augmented Lagrangian Uzawa IterativeMethod for Solving Double Saddle-Point Systems with Semidefinite(2,2)Block and its Application to DLM/FDMethod for Elliptic Interface Problems

.In this paper,an augmented Lagrangian Uzawa iterative method is developed and analyzed for solving a class of double saddle-point systems with semidefinite(2,2)block.Convergence of the iterativemethod is proved under the assumption that the double saddle-point problem exists a unique solution.An application of the iterative method to the double saddle-point systems arising from the distributed Lagrange multiplier/fictitious domain(DLM/FD)finite element method for solving elliptic interface problems is also presented,in which the existence and uniqueness of the double saddle-point system is guaranteed by the analysis of the DLM/FD finite element method.Numerical experiments are conducted to validate the theoretical results and to study the performance of the proposed iterative method.

Exact propagator for an electron in a quadratic saddle-point potential and a magnetic field

We study the propagator for an electron moving in a two-dimensional （2D） quadratic saddle-point potential, in the presence of a perpendicular uniform magnetic field. A closed-form expression for the propagator is derived using the Feynmann path integrals.

On the Preconditioning Properties of RHSS Preconditioner for Saddle-Point Linear Systems

In this paper,for the regularized Hermitian and skew-Hermitian splitting(RHSS)preconditioner introduced by Bai and Benzi(BIT Numer Math 57:287–311,2017)for the solution of saddle-point linear systems,we analyze the spectral properties of the preconditioned matrix when the regularization matrix is a special Hermitian positive semidefinite matrix which depends on certain parameters.We accurately describe the numbers of eigenvalues clustered at(0,0)and(2,0),if the iteration parameter is close to 0.An estimate about the condition number of the corresponding eigenvector matrix,which partly determines the convergence rate of the RHSS-preconditioned Krylov subspace method,is also studied in this work.

Accelerated RHSS Iteration Method for Stabilized Saddle-Point Problems

For stabilized saddle-point problems, we apply the two iteration parameters idea for regularized Hermitian and skew-Hermitian splitting (RHSS) method and establish accelerated RHSS (ARHSS) iteration method. Theoretical analysis shows that the ARHSS method converges unconditionally to the unique solution of the saddle point problem. Finally, we use a numerical example to confirm the effectiveness of the method.

EQUIVALENCY THEOREM FOR “SADDLE-POINT” FINITE ELEMENT SCHEMES AND TWO CRITERIA OF STRONG BABUSKA-BREZZI CONDITION

This paper is concerned with the general study in the existence,uniqueness and error estimationof finite element solutions for a larger class of 'saddle-point' schemes. The established theory inthe form of Lax-like equivalency theorem includes Brezzi’s theory that has been treated as a specialcase.Two criteria are presented so as to help the practical verification of S-Babuska condition.

ON AUGMENTED LAGRANGIAN METHODS FOR SADDLE-POINT LINEAR SYSTEMS WITH SINGULAR OR SEMIDEFINITE （1, 1） BLOCKS

An effective algorithm for solving large saddle-point linear systems, presented by Krukier et al., is applied to the constrained optimization problems. This method is a modification of skew-Hermitian triangular splitting iteration methods. We consider the saddle-point linear systems with singular or semidefinite （1, 1） blocks. Moreover, this method is applied to precondition the GMRES. Numerical results have confirmed the effectiveness of the method and showed that the new method can produce high-quality preconditioners for the Krylov subspace methods for solving large sparse saddle-point linear systems.

LEAST-SQUARES MIXED FINITE ELEMENT METHOD FOR SADDLE-POINT PROBLEM

In this paper, a least-squares mixed finite element method for the solution of the primal saddle-point problem is developed. It is proved that the approximate problem is consistent ellipticity in the conforming finite element spaces with only the discrete BB-condition needed for a smaller auxiliary problem. The abstract error estimate is derived. [ABSTRACT FROM AUTHOR]

Generalized Accelerated Hermitian and Skew-Hermitian Splitting Methods for Saddle-Point Problems

We generalize the accelerated Hermitian and skew-Hermitian splitting(AHSS)iteration methods for large sparse saddle-point problems.These methods involve four iteration parameters whose special choices can recover the precondi-tioned HSS and accelerated HSS iteration methods.Also a new efficient case is in-troduced and we theoretically prove that this new method converges to the unique solution of the saddle-point problem.Numerical experiments are used to further examine the effectiveness and robustness of iterations.

Fenchel-Lagrange Duality and Saddle-Points for Constrained Vector Optimization

The aim of this paper is to apply a perturbation approach to deal with Fenchel- Lagrange duality based on weak efficiency to a constrained vector optimization problem. Under the stability criterion, some relationships between the solutions of primal problem and the Fenchel-Lagrange duality are discussed. Moreover, under the same condition, two saddle-points theorems are proved.

BLOCK-SYMMETRIC AND BLOCK-LOWER-TRIANGULAR PRECONDITIONERS FOR PDE-CONSTRAINED OPTIMIZATION PROBLEMS＊

Optimization problems with partial differential equations as constraints arise widely in many areas of science and engineering, in particular in problems of the design. The solution of such class of PDE-constrained optimization problems is usually a major computational task. Because of the complexion for directly seeking the solution of PDE-constrained op- timization problem, we transform it into a system of linear equations of the saddle-point form by using the Galerkin finite-element discretization. For the discretized linear system, in this paper we construct a block-symmetric and a block-lower-triangular preconditioner, for solving the PDE-constrained optimization problem. Both preconditioners exploit the structure of the coefficient matrix. The explicit expressions for the eigenvalues and eigen- vectors of the corresponding preconditioned matrices are derived. Numerical implementa- tions show that these block preconditioners can lead to satisfactory experimental results for the preconditioned GMRES methods when the regularization parameter is suitably small.

A Splitting Primal-dual Proximity Algorithm for Solving Composite Optimization Problems

Our work considers the optimization of the sum of a non-smooth convex function and a finite family of composite convex functions, each one of which is composed of a convex function and a bounded linear operator. This type of problem is associated with many interesting challenges encoun- tered in the image restoration and image reconstruction fields. We developed a splitting primal-dual proximity algorithm to solve this problem. Furthermore, we propose a preconditioned method~ of which the iterative parameters are obtained without the need to know some particular operator norm in advance. Theoretical convergence theorems are presented. We then apply the proposed methods to solve a total variation regularization model, in which the L2 data error function is added to the L1 data error function. The main advantageous feature of this model is its capability to combine different loss functions. The numerical results obtained for computed tomography （CT） image recon- struction demonstrated the ability of the proposed algorithm to reconstruct an image with few and sparse projection views while maintaining the image quality.

Adaptive Parallel Primal-Dual Method for Saddle Point Problems

The primal-dual hybrid gradient method is a classic way to tackle saddle-point problems.However,its convergence is not guaranteed in general.Some restric-tions on the step size parameters,e.g.,τσ≤1/||A^(T)A||,are imposed to guarantee the convergence.In this paper,a new convergent method with no restriction on parame-ters is proposed.Hence the expensive calculation of ||A^(T)A|| is avoided.This method produces a predictor like other primal-dual methods but in a parallel fashion,which has the potential to speed up the method.This new iterate is then updated by a sim-ple correction to guarantee the convergence.Moreover,the parameters are adjusted dynamically to enhance the efficiency as well as the robustness of the method.The generated sequence monotonically converges to the solution set.A worst-case O(1/t)convergence rate in ergodic sense is also established under mild assumptions.The nu-merical efficiency of the proposed method is verified by applications in LASSO problem and Steiner tree problem.

Several Variants of the Primal-Dual Hybrid Gradient Algorithm with Applications

By reviewing the primal-dual hybrid gradient algorithm(PDHG)pro-posed by He,You and Yuan(SIAM J.Image Sci.,7(4)(2014),pp.2526–2537),in this paper we introduce four improved schemes for solving a class of saddle-point problems.Convergence properties of the proposed algorithms are ensured based on weak assumptions,where none of the objective functions are assumed to be strongly convex but the step-sizes in the primal-dual updates are more flexible than the pre-vious.By making use of variational analysis,the global convergence and sublinear convergence rate in the ergodic/nonergodic sense are established,and the numer-ical efficiency of our algorithms is verified by testing an image deblurring problem compared with several existing algorithms.

An Exact l(1) Penalty Approach for Interval-Valued Programming Problem

The objective of this paper is to propose an exact l1 penalty method for constrained interval-valued programming problems which transform the constrained problem into an unconstrained interval-valued penalized optimization problem.Under some suitable conditions,we establish the equivalence between an optimal solution of interval-valued primal and penalized optimization problem.Moreover,saddle-point type optimality conditions are also established in order to find the relation between an optimal solution of penalized optimization problem and saddle-point of Lagrangian function.Numerical examples are given to illustrate the derived results.

Augmented Lagrangian Methods for p-Harmonic Flows with the Generalized Penalization Terms and Application to Image Processing

In this paper,we propose a generalized penalization technique and a convex constraint minimization approach for the p-harmonic flow problem following the ideas in[Kang&March,IEEE T.Image Process.,16(2007),2251–2261].We use fast algorithms to solve the subproblems,such as the dual projection methods,primal-dual methods and augmented Lagrangian methods.With a special penalization term,some special algorithms are presented.Numerical experiments are given to demonstrate the performance of the proposed methods.We successfully show that our algorithms are effective and efficient due to two reasons:the solver for subproblem is fast in essence and there is no need to solve the subproblem accurately(even 2 inner iterations of the subproblem are enough).It is also observed that better PSNR values are produced using the new algorithms.