Interior Proximal Method for Variational Inequalities: Case of Nonparamonotone Operators

For variational inequalities characterizing saddle points of Lagrangians associated with convex programming problems in Hilbert spaces, the convergence of an interior proximal method based on Bregman distance functionals is studied. The convergence results admit a successive approximation of the variational inequality and an inexact treatment of the proximal iterations.An analogous analysis is performed for finite-dimensional complementarity problems with multi-valued monotone operators.     

Inexact proximal point method for general variational inequalities

In this paper, we suggest and analyze a new inexact proximal point method for solving general variational inequalities, which can be considered as an implicit predictor-corrector method. An easily measurable error term is proposed with further relaxed error bound and an optimal step length is obtained by maximizing the profit-function and is dependent on the previous points. Our results include several known and new techniques for solving variational inequalities and related optimization problems. Results obtained in this paper can be viewed as an important improvement and refinement of the previously known results. Preliminary numerical experiments are included to illustrate the advantage and efficiency of the proposed method.     

On the proximal point method in Hadamard spaces

Proximal point method is one of the most influential procedure in solving nonlinear variational problems. It has recently been introduced in Hadamard spaces for solving convex optimization, and later for variational inequalities. In this paper, we study the general proximal point method for finding a zero point of a maximal monotone set-valued vector field defined on a Hadamard space and valued in its dual. We also give the relation between the maximality and Minty’s surjectivity condition, which is essential for the proximal point method to be well-defined. By exploring the properties of monotonicity and the surjectivity condition, we were able to show under mild assumptions that the proximal point method converges weakly to a zero point. Additionally, by taking into account the metric subregularity, we obtained the local strong convergence in linear and super-linear rates.     

Convergence analysis of non-quadratic proximal methods for variational inequalities in Hilbert spaces

We consider a general approach for the convergence analysis of proximal-like methods for solving variational inequalities with maximal monotone operators in a Hilbert space. It proves to be that the conditions on the choice of a non-quadratic distance functional depend on the geometrical properties of the operator in the variational inequality, and –- in particular –- a standard assumption on the strict convexity of the kernel of the distance functional can be weakened if this operator possesses a certain `reserve of monotonicity'. A successive approximation of the `feasible set' is performed, and the arising auxiliary problems are solved approximately. Weak convergence of the proximal iterates to a solution of the original problem is proved.     

The Proximal Point Method for Nonmonotone Variational Inequalities

We consider an application of the proximal point method to variational inequality problems subject to box constraints, whose cost mappings possess order monotonicity properties instead of the usual monotonicity ones. Usually, convergence results of such methods require the additional boundedness assumption of the solutions set. We suggest another approach to obtaining convergence results for proximal point methods which is based on the assumption that the dual variational inequality is solvable. Then the solutions set may be unbounded. We present classes of economic equilibrium problems which satisfy such assumptions.     

关于单调变分不等式的不精确邻近点算法的收敛性分析

We consider a proximal point algorithm(PPA) for solving monotone variational inequalities. PPA generates a sequence by solving a sequence of strongly monotone subproblems .However,solving the subproblems is either expensive or impossible. Some inexact proximal point algorithms(IPPA) have been developed in many literatures. In this paper, we present a criterion for approximately solving subproblems. It only needs one simple additional work on the basis of original algorithm, and the convergence criterion becomes milder. We show that this method converges globally under new criterion provided that the solution set of the problem is nonempty.     

On Some Properties of Generalized Proximal Point Methods for Variational Inequalities

We discuss here generalized proximal point methods applied to variational inequality problems. These methods differ from the classical point method in that a so-called Bregman distance substitutes for the Euclidean distance and forces the sequence generated by the algorithm to remain in the interior of the feasible region, assumed to be nonempty. We consider here the case in which this region is a polyhedron (which includes linear and nonlinear programming, monotone linear complementarity problems, and also certain nonlinear complementarity problems), and present two alternatives to deal with linear equality constraints. We prove that the sequences generated by any of these alternatives, which in general are different, converge to the same point, namely the solution of the problem which is closest, in the sense of the Bregman distance, to the initial iterate, for a certain class of operators. This class consists essentially of point-to-point and differentiable operators such that their Jacobian matrices are positive semidefinite (not necessarily symmetric) and their kernels are constant in the feasible region and invariant through symmetrization. For these operators, the solution set of the problem is also a polyhedron. Thus, we extend a previous similar result which covered only linear operators with symmetric and positive-semidefinite matrices.     

Proximal Methods for Mixed Quasivariational Inequalities

A proximal method for solving mixed quasivariational inequalities is suggested and analyzed by using the auxiliary principle technique. We show that the convergence of the proposed method requires only the pseudomonotonicity, which is a weaker condition than monotonicity. Since mixed quasivariational inequalities include variational and complementarity problems as special cases, the result proved in this paper continues to hold for these problems.     

Some Methods Based on the D-Gap Function for Solving Monotone Variational Inequalities

The D-gap function has been useful in developing unconstrained descent methods for solving strongly monotone variational inequality problems. We show that the D-gap function has certain properties that are useful also for monotone variational inequality problems with bounded feasible set. Accordingly, we develop two unconstrained methods based on them that are similar in spirit to a feasible method of Zhu and Marcotte based on the regularized-gap function. We further discuss a third method based on applying the D-gap function to a regularized problem. Preliminary numerical experience is also reported.     

Proximal Methods for Mixed Variational Inequalities

A proximal point method for solving mixed variational inequalities is suggested and analyzed by using the auxiliary principle technique. It is shown that the convergence of the proposed method requires only the pseudomonotonicity of the operator, which is a weaker condition than monotonicity. As special cases, we obtain various known and new results for solving variational inequalities and related problems. Our proof of convergence is very simple as compared with other methods.     

Some proximal algorithms for linearly constrained general variational inequalities

Based on the classical proximal point algorithm (PPA), some PPA-based numerical algorithms for general variational inequalities (GVIs) have been developed recently. Inspired by these algorithms, in this article we propose some proximal algorithms for solving linearly constrained GVIs (LCGVIs). The resulted subproblems are regularized proximally, and they are allowed to be solved either exactly or approximately.     

Error bounds for proximal point subproblems and associated inexact proximal point algorithms

We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem, and of the closely related problem of finding a zero of a maximal monotone operator. A new merit function is proposed for proximal point subproblems associated with the latter. This merit function is based on Burachik-Iusem-Svaiter’s concept of ε-enlargement of a maximal monotone operator. For variational inequalities, we establish a precise relationship between the regularized gap function, which is a natural error measure in this context, and our new merit function. Some error bounds are derived using both merit functions for the corresponding formulations of the proximal subproblem. We further use the regularized gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact proximal point method preserves all the desirable global and local convergence properties of the classical exact/inexact method, while providing a constructive error tolerance criterion, suitable for further practical applications. The use of other tolerance rules is also discussed. Received: April 28, 1999 / Accepted: March 24, 2000?Published online July 20, 2000     

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

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

Improvements of Some Projection Methods for Monotone Nonlinear Variational Inequalities

In this paper, we study the relationship of some projection-type methods for monotone nonlinear variational inequalities and investigate some improvements. If we refer to the Goldstein–Levitin–Polyak projection method as the explicit method, then the proximal point method is the corresponding implicit method. Consequently, the Korpelevich extragradient method can be viewed as a prediction-correction method, which uses the explicit method in the prediction step and the implicit method in the correction step. Based on the analysis in this paper, we propose a modified prediction-correction method by using better prediction and correction stepsizes. Preliminary numerical experiments indicate that the improvements are significant.     

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.     

Proximal-Point Algorithm Using a Linear Proximal Term

Proximal-point algorithms (PPAs) are classical solvers for convex optimization problems and monotone variational inequalities (VIs). The proximal term in existing PPAs usually is the gradient of a certain function. This paper presents a class of PPA-based methods for monotone VIs. For a given current point, a proximal point is obtained via solving a PPA-like subproblem whose proximal term is linear but may not be the gradient of any functions. The new iterate is updated via an additional slight calculation. Global convergence of the method is proved under the same mild assumptions as the original PPA. Finally, profiting from the less restrictions on the linear proximal terms, we propose some parallel splitting augmented Lagrangian methods for structured variational inequalities with separable operators. B.S. He was supported by NSFC Grant 10571083 and Jiangsu NSF Grant BK2008255.     

Extragradient Methods for Pseudomonotone Variational Inequalities

We consider and analyze some new extragradient-type methods for solving variational inequalities. The modified methods converge for a pseudomonotone operator, which is a much weaker condition than monotonicity. These new iterative methods include the projection, extragradient, and proximal methods as special cases. Our proof of convergence is very simple as compared with other methods.     

Entropic proximal decomposition methods for convex programs and variational inequalities

We consider convex optimization and variational inequality problems with a given separable structure. We propose a new decomposition method for these problems which combines the recent logarithmic-quadratic proximal theory introduced by the authors with a decomposition method given by Chen-Teboulle for convex problems with particular structure. The resulting method allows to produce for the first time provably convergent decomposition schemes based on C ^∞ Lagrangians for solving convex structured problems. Under the only assumption that the primal-dual problems have nonempty solution sets, global convergence of the primal-dual sequences produced by the algorithm is established. Received: October 6, 1999 / Accepted: February 2001?Published online September 17, 2001     

Banach空间中解变分包含问题的超松弛临界点算法

把Verma关于解变分包含问题的超松弛临界点算法(over-relaxed proximalpoint algorithm)从Hilbert空间扩展为q一致光滑Banach空间.并且导出了更为广义的超松弛临界点算法,在较弱的条件下证明了它的收敛性质.因此,研究结果可以应用于L~p,W~(m,p)(Ω)(p1)等空间.     

广义非凸变分不等式解的存在性与投影算法

本文运用Banach压缩映象原理和投影技巧研究一类新的广义非凸变分不等式问题解的存在唯一性,并在非凸集上建立一个逼近广义非凸变分不等式解的三步投影算法,在一定条件下证明了该投影算法所产生的迭代序列的收敛性.