具有滑动边界条件Stokes问题的自适应Uzawa块松弛算法

对一类具有非线性滑动边界条件的Stokes问题,得到了求其数值解的自适应Uzawa块松弛算法（SUBRM）.通过该问题导出的变分问题,引入辅助变量将原问题转化为一个基于增广Lagrange函数表示的鞍点问题,并采用Uzawa块松弛算法（UBRM）求解.为了提高算法性能,提出利用迭代函数自动选取合适罚参数的自适应法则.该算法的优点是每次迭代只需计算一个线性问题,同时显式计算辅助变量.对算法的收敛性进行了理论分析,最后用数值结果验证了该算法的可行性和有效性.     

Two algorithms for two-phase Stefan type problems

In this paper,the relaxation algorithm and two Uzawa type algorithms for solving discretized variational inequalities arising from the two-phase Stefan type problem are proposed.An analysis of their convergence is presented and the upper bounds of the convergence rates are derived.Some numerical experiments are shown to demonstrate that for the second Uzawa algorithm which is an improved version of the first Uzawa algorithm,the convergence rate is uniformly bounded away from 1 if τh^-2 is kept bounded,where τ is the time step size and h the space mesh size.     

Adaptive FE–BE coupling for strongly nonlinear transmission problems with Coulomb friction

We analyze an adaptive finite element/boundary element procedure for scalar elastoplastic interface problems involving friction, where a nonlinear uniformly monotone operator such as the p-Laplacian is coupled to the linear Laplace equation on the exterior domain. The problem is reduced to a boundary/domain variational inequality, a discretized saddle point formulation of which is then solved using the Uzawa algorithm and adaptive mesh refinements based on a gradient recovery scheme. The Galerkin approximations are shown to converge to the unique solution of the variational problem in a suitable product of L ^p - and L ²-Sobolev spaces.     

求解凸规划及鞍点问题定制的PPA 算法及其收敛速率

线性约束的凸优化问题和鞍点问题的一阶最优性条件是一个单调变分不等式. 在变分不等式框架下求解这些问题, 选取适当的矩阵G, 采用G- 模下的PPA 算法, 会使迭代过程中的子问题求解变得相当容易. 本文证明这类定制的PPA 算法的误差界有1/k 的收敛速率.     

On finite convergence of proximal point algorithms for variational inequalities

In this paper, we first characterize finite convergence of an arbitrary iterative algorithm for solving the variational inequality problem (VIP), where the finite convergence means that the algorithm can find an exact solution of the problem in a finite number of iterations. By using this result, we obtain that the well-known proximal point algorithm possesses finite convergence if the solution set of VIP is weakly sharp. As an extension, we show finite convergence of the inertial proximal method for solving the general variational inequality problem under the condition of weak g-sharpness.     

On preconditioned Uzawa methods and SOR methods for saddle-point problems

This paper studies convergence analysis of a preconditioned inexact Uzawa method for nondifferentiable saddle-point problems. The SOR-Newton method and the SOR-BFGS method are special cases of this method. We relax the Bramble-Pasciak-Vassilev condition on preconditioners for convergence of the inexact Uzawa method for linear saddle-point problems. The relaxed condition is used to determine the relaxation parameters in the SOR-Newton method and the SOR-BFGS method. Furthermore, we study global convergence of the multistep inexact Uzawa method for nondifferentiable saddle-point problems.     

关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注

Yair Censor,Aviv Gibali和Simeon Reich为求解变分不等式问题提出了 2-次梯度外梯度算法.关于此算法的收敛性,作者给出了部分证明,有一个问题:由算法产生的迭代点列能否收敛到变分不等式问题的一个解上,没有得到解决.此问题作为一个公开问题在文章"Extensions of Korpelevi...     

The corrected Uzawa method for solving saddle point problems

In this paper, we consider the solution of linear systems of saddle point type by correcting the Uzawa algorithm, which has been proposed in [K. Arrow, L. Hurwicz, H. Uzawa, Studies in nonlinear programming, Stanford University Press, Stanford, CA, 1958]. We call this method as corrected Uzawa (CU) method. The convergence of the CU method is analyzed for solving nonsingular saddle point problem as well as the semi‐convergence for the singular case. First, the corrected model for the Uzawa algorithm is established, and the CU algorithm is presented. Then we study the geometric meaning of the CU model. Moreover, we introduce the overall reduction coefficient α to measure the effect of the CU process. It is shown that the CU method converges faster than the Uzawa method and several other methods if the overall reduction coefficient α satisfies certain conditions. Numerical experiments are presented to illustrate the theoretical results and examine the numerical effectiveness of the CU method. Copyright © 2015 John Wiley & Sons, Ltd.     

Iterative Algorithm for Solving Triple-Hierarchical Constrained Optimization Problem

Many practical problems such as signal processing and network resource allocation are formulated as the monotone variational inequality over the fixed point set of a nonexpansive mapping, and iterative algorithms to solve these problems have been proposed. This paper discusses a monotone variational inequality with variational inequality constraint over the fixed point set of a nonexpansive mapping, which is called the triple-hierarchical constrained optimization problem, and presents an iterative algorithm for solving it. Strong convergence of the algorithm to the unique solution of the problem is guaranteed under certain assumptions.     

自由边界问题的自适应Uzawa块松弛算法

利用增广Lagrange乘子法和自适应法则，得到求解单侧障碍自由边界问题的自适应Uzawa块松弛法.单侧障碍自由边界问题离散为有限维线性互补问题，等价于一个用辅助变量和增广Lagrange函数表示的鞍点问题.采用Uzawa块松弛算法求解该问题得到一个两步迭代法，主要的子问题为一个线性问题，同时能显式求解辅助变量.由于Uzawa块松弛算法的收敛速度显著依赖于罚参数，而且对具体问题很难选择合适的罚参数.为提高算法的性能，提出了自适应法则，该方法自动调整每次迭代所需的罚参数.数值结果验证了该算法的理论分析.     

A nonsmooth Newton method for variational inequalities,I: Theory

This paper presents a modified damped Newton algorithm for solving variational inequality problems based on formulating this problem as a system of equations using the Minty map. The proposed modified damped-Newton method insures convergence and locally quadratic convergence under the assumption of regularity. Under the assumption ofweak regularity and some mild conditions, the modified algorithm is shown to always create a descent direction and converge to the solution. Hence, this new algorithm is often suitable for many applications where regularity does not hold. Part II of this paper presents the results of extensive computational testing of this new method.Corresponding author.     

Generalized variational inequalities with fuzzy relation

This paper studies generalized variational inequalities with fuzzy relation. It is shown that such problem can be reduced to a regular optimization problem with variational inequality constraints. A penalty function algorithm is introduced with a convergence proof, and a numerical example is included to illustrate the solution procedure.     

基于对偶混合变分形式的Uzawa型算法

基于弹性接触问题的三变量（应力，位移，接触边界位移）对偶混合变分形式，对混合有限元离散化的单边约束问题，提出了一种Uzawa型算法。首先证明了迭代算法的收敛性，然后用数值例子验证了迭代算法的有效性。     

Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: a unified approach

This paper focuses on some customized applications of the proximal point algorithm (PPA) to two classes of problems: the convex minimization problem with linear constraints and a generic or separable objective function, and a saddle-point problem. We treat these two classes of problems uniformly by a mixed variational inequality, and show how the application of PPA with customized metric proximal parameters can yield favorable algorithms which are able to make use of the models’ structures effectively. Our customized PPA revisit turns out to unify some algorithms including some existing ones in the literature and some new ones to be proposed. From the PPA perspective, we establish the global convergence and a worst-case O(1/t) convergence rate for this series of algorithms in a unified way.     

Convergent Algorithm Based on Progressive Regularization for Solving Pseudomonotone Variational Inequalities

In this paper, we extend the Moreau-Yosida regularization of monotone variational inequalities to the case of weakly monotone and pseudomonotone operators. With these properties, the regularized operator satisfies the pseudo-Dunn property with respect to any solution of the variational inequality problem. As a consequence, the regularized version of the auxiliary problem algorithm converges. In this case, when the operator involved in the variational inequality problem is Lipschitz continuous (a property stronger than weak monotonicity) and pseudomonotone, we prove the convergence of the progressive regularization introduced in Refs. 1, 2.     

A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints

The problem of recovering the low-rank and sparse components of a matrix is known as the stable principal component pursuit (SPCP) problem. It has found many applications in compressed sensing, image processing, and web data ranking. This paper proposes a generalized inexact Uzawa method for SPCP with nonnegative constraints. The main advantage of our method is that the resulting subproblems all have closed-form solutions and can be executed in distributed manners. Global convergence of the method is proved from variational inequalities perspective. Numerical experiments show that our algorithm converges to the optimal solution as other distributed methods, with better performances.     

求解变分不等式的Ishikawa类迭代算法

本文讨论Banach空间中子集非紧的情况下的变分不等式数值解.提出了求解相应问题的Ishikawa类迭代算法,证明了算法的子列收敛性和全局收敛性.同时也证明了变分不等式解的存在性.     

Weighted variational inequalities in non-pivot Hilbert spaces with applications

We introduce variational inequalities defined in non-pivot Hilbert spaces and we show some existence results. Then, we prove regularity results for weighted variational inequalities in non-pivot Hilbert space. These results have been applied to the weighted traffic equilibrium problem. The continuity of the traffic equilibrium solution allows us to present a numerical method to solve the weighted variational inequality that expresses the problem. In particular, we extend the Solodov-Svaiter algorithm to the variational inequalities defined in finite-dimensional non-pivot Hilbert spaces. Then, by means of a interpolation, we construct the solution of the weighted variational inequality defined in a infinite-dimensional space. Moreover, we present a convergence analysis of the method.     

Dynamics and variational inequalities

A terminal control problem with linear dynamics and a boundary condition given implicitly in the form of a solution of a variational inequality is considered. In the general control theory, this problem belongs to the class of stabilization problems. A saddle-point method of the extragradient type is proposed for its solution. The method is proved to converge with respect to all components of the solution, i.e., with respect to controls, phase and adjoint trajectories, and the finite-dimensional variables of the terminal problem.     

On the Convergence of Coderivative of SAA Solution Mapping for a Parametric Stochastic Variational Inequality

The aim of this paper is to investigate the convergence properties for Mordukhovich’s coderivative of the solution map of the sample average approximation (SAA) problem for a parametric stochastic variational inequality with equality and inequality constraints. The notion of integrated deviation is introduced to characterize the outer limit of a sequence of sets. It is demonstrated that, under suitable conditions, both the cosmic deviation and the integrated deviation between the coderivative of the solution mapping to SAA problem and that of the solution mapping to the parametric stochastic variational inequality converge almost surely to zero as the sample size tends to infinity. Moreover, the exponential convergence rate of coderivatives of the solution maps to the SAA parametric stochastic variational inequality is established. The results are used to develop sufficient conditions for the consistency of the Lipschitz-like property of the solution map of SAA problem and the consistency of stationary points of the SAA estimator for a stochastic bilevel program.