Finite convergence analysis and weak sharp solutions for variational inequalities

In this paper, we study the weak sharpness of the solution set of variational inequality problem (in short, VIP) and the finite convergence property of the sequence generated by some algorithm for finding the solutions of VIP. In particular, we give some characterizations of weak sharpness of the solution set of VIP without considering the primal or dual gap function. We establish an abstract result on the finite convergence property for a sequence generated by some iterative methods. We then apply such abstract result to discuss the finite termination property of the sequence generated by proximal point method, exact proximal point method and gradient projection method. We also give an estimate on the number of iterates by which the sequence converges to a solution of the VIP.     

On Finite Convergence of Iterative Methods for Variational Inequalities in Hilbert Spaces

In a Hilbert space, we study the finite termination of iterative methods for solving a monotone variational inequality under a weak sharpness assumption. Most results to date require that the sequence generated by the method converges strongly to a solution. In this paper, we show that the proximal point algorithm for solving the variational inequality terminates at a solution in a finite number of iterations if the solution set is weakly sharp. Consequently, we derive finite convergence results for the gradient projection and extragradient methods. Our results show that the assumption of strong convergence of sequences can be removed in the Hilbert space case.     

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.     

Weak Sharp Solutions for Nonsmooth Variational Inequalities

In this paper, we study the weak sharp solutions for nonsmooth variational inequalities and give a characterization in terms of error bound. Some characterizations of solution set of nonsmooth variational inequalities are presented. Under certain conditions, we prove that the sequence generated by an algorithm for finding a solution of nonsmooth variational inequalities terminates after a finite number of iterates provided that the solutions set of a nonsmooth variational inequality is weakly sharp. We also study the finite termination property of the gradient projection method for solving nonsmooth variational inequalities under weak sharpness of the solution set.     

Weak sharpness for set-valued variational inequalities and applications to finite termination of iterative algorithms

In this paper, we introduce the notion of weak sharpness for set-valued variational inequalities in the n-dimensional Euclidean space and then present some characterizations of weak sharpness. We also give some examples to illustrate this notion. Under the assumption of weak sharpness, by using the inner limit of a set sequence we establish a sufficient and necessary condition to guarantee the finite termination of an arbitrary algorithm for solving a set-valued variational inequality involving maximal monotone mappings. As an application, we show that the sequence generated by the hybrid projection-proximal point algorithm proposed by Solodov and Svaiter terminates at solutions in a finite number of iterations. These obtained results extend some known results of classical variational inequalities.     

Weak sharp solutions for generalized variational inequalities

We consider weak sharp solutions for the generalized variational inequality problem, in which the underlying mapping is set-valued, and not necessarily monotone. We extend the concept of weak sharpness to this more general framework, and establish some of its characterizations. We establish connections between weak sharpness and (1) gap functions for variational inequalities, and (2) global error bound. When the solution set is weak sharp, we prove finite convergence of the sequence generated by an arbitrary algorithm, for the monotone set-valued case, as well as for the case in which the underlying set-valued map is either Lipschitz continuous in the set-valued sense, for infinite dimensional spaces, or inner-semicontinuous when the space is finite dimensional.     

Differential mixed variational inequalities in finite dimensional spaces

In this paper, we introduce and study a class of differential mixed variational inequalities in finite dimensional Euclidean spaces. Under various conditions, we obtain linear growth and bounded linear growth of the solution set for the mixed variational inequalities. Moreover, we present some conclusions which enrich the literature on the mixed variational inequalities and generalize the corresponding results of [4]. In particular we prove existence theorems for weak solutions of a differential mixed variational inequality in the weak sense of Carathéodory by using a result on differential inclusions involving an upper semicontinuous set-valued map with closed convex values. Also by employing the results from differential inclusions we establish a convergence result on Euler time-dependent procedure for solving initial-value differential mixed variational inequalities.     

Hybrid Approximate Proximal Method with Auxiliary Variational Inequality for Vector Optimization

This paper studies a general vector optimization problem of finding weakly efficient points for mappings from Hilbert spaces to arbitrary Banach spaces, where the latter are partially ordered by some closed, convex, and pointed cones with nonempty interiors. To find solutions of this vector optimization problem, we introduce an auxiliary variational inequality problem for a monotone and Lipschitz continuous mapping. The approximate proximal method in vector optimization is extended to develop a hybrid approximate proximal method for the general vector optimization problem under consideration by combining an extragradient method to find a solution of the variational inequality problem and an approximate proximal point method for finding a root of a maximal monotone operator. In this hybrid approximate proximal method, the subproblems consist of finding approximate solutions to the variational inequality problem for monotone and Lipschitz continuous mapping, and then finding weakly efficient points for a suitable regularization of the original mapping. We present both absolute and relative versions of our hybrid algorithm in which the subproblems are solved only approximately. The weak convergence of the generated sequence to a weak efficient point is established under quite mild assumptions. In addition, we develop some extensions of our hybrid algorithms for vector optimization by using Bregman-type functions.     

Banach空间上变分不等式问题的新投影算法北大核心CSCD

本文在Banach空间上提出一种关于伪单调变分不等式问题的新算法.在对参数强加适当的条件下,我们证明由算法生成的序列强收敛到变分不等式的一个元素,所得结果推广和提高了很多最新结果.     

On a generalized proximal point method for solving equilibrium problems in Banach spaces

We introduce a regularized equilibrium problem in Banach spaces, involving generalized Bregman functions. For this regularized problem, we establish the existence and uniqueness of solutions. These regularizations yield a proximal-like method for solving equilibrium problems in Banach spaces. We prove that the proximal sequence is an asymptotically solving sequence when the dual space is uniformly convex. Moreover, we prove that all weak accumulation points are solutions if the equilibrium function is lower semicontinuous in its first variable. We prove, under additional assumptions, that the proximal sequence converges weakly to a solution.     

On the regularization of mixed complementarity problems

A variational inequality problem (VIP) satisfying a constraint qualification can be reduced to a mixed complementarity problem (MOP). Monotonicity of the VIP implies that the MOP is also monotone. Introducing regularizing perturbations, a sequence of strictly monotone mixed complementarity problems is generated. It is shown that, if the original problem is solvable, the sequence of computable inexact solutions of the strictly monotone MCP's is bounded and every accumulation point is a solution. Under an additional condition on the precision used for solving each subproblem, the sequence converges to the minimum norm solution of the MCP.     

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.     

Mann-Type Steepest-Descent and Modified Hybrid Steepest-Descent Methods for Variational Inequalities in Banach Spaces

In this paper, we propose three different kinds of iteration schemes to compute the approximate solutions of variational inequalities in the setting of Banach spaces. First, we suggest Mann-type steepest-descent iterative algorithm, which is based on two well-known methods: Mann iterative method and steepest-descent method. Second, we introduce modified hybrid steepest-descent iterative algorithm. Third, we propose modified hybrid steepest-descent iterative algorithm by using the resolvent operator. For the first two cases, we prove the convergence of sequences generated by the proposed algorithms to a solution of a variational inequality in the setting of Banach spaces. For the third case, we prove the convergence of the iterative sequence generated by the proposed algorithm to a zero of an operator, which is also a solution of a variational inequality.     

A Strongly Convergent Direct Method for Monotone Variational Inequalities in Hilbert Spaces

We introduce a two-step direct method, like Korpelevich's, for solving monotone variational inequalities. The advantage of our method over that one is that ours converges strongly in Hilbert spaces, whereas only weak convergence has been proved for Korpelevich's algorithm. Our method also has the following desirable property: the sequence converges to the solution of the problem that lies closest to the initial iterate.     

Finite Convergence of the Proximal Point Algorithm for Variational Inequality Problems

In this paper, we establish sufficient conditions for guaranteeing finite termination of an arbitrary algorithm for solving a variational inequality problem in a Banach space. Applying these conditions, it shows that sequences generated by the proximal point algorithm terminate at solutions in a finite number of iterations.     

Proximal alternating linearized minimization for nonconvex and nonsmooth problems

We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmooth minimization problems. Building on the powerful Kurdyka–?ojasiewicz property, we derive a self-contained convergence analysis framework and establish that each bounded sequence generated by PALM globally converges to a critical point. Our approach allows to analyze various classes of nonconvex-nonsmooth problems and related nonconvex proximal forward–backward algorithms with semi-algebraic problem’s data, the later property being shared by many functions arising in a wide variety of fundamental applications. A by-product of our framework also shows that our results are new even in the convex setting. As an illustration of the results, we derive a new and simple globally convergent algorithm for solving the sparse nonnegative matrix factorization problem.     

A New Hybrid Generalized Proximal Point Algorithm for Variational Inequality Problems

In this paper, we propose a modified Bregman-function-based proximal point algorithm for solving variational inequality problems. The algorithm adopts a similar constructive approximate criterion as the one developed by Solodov and Svaiter (Set Valued Analysis 7 (1999) 323) for solving the classical proximal subproblems. Under some suitable conditions, we can get an approximate solution satisfying the accuracy criterion via a single Newton-type step. We obtain the Fejér monotonicity to solutions of VIP for paramonotone operators. Some preliminary computational results are also reported to illustrate the method.     

Weak and Strong Convergence Theorems for Maximal Monotone Operators in a Banach Space

In this paper, we introduce an iterative sequence for finding a solution of a maximal monotone operator in a uniformly convex Banach space. Then we first prove a strong convergence theorem, using the notion of generalized projection. Assuming that the duality mapping is weakly sequentially continuous, we next prove a weak convergence theorem, which extends the previous results of Rockafellar [SIAM J. Control Optim. 14 (1976), 877–898] and Kamimura and Takahashi [J. Approx. Theory 106 (2000), 226–240]. Finally, we apply our convergence theorem to the convex minimization problem and the variational inequality problem.     

Characterization of weakly sharp solutions of a variational inequality by its primal gap function

Our aim is to study weakly sharp solutions of a variational inequality in terms of its primal gap function \(g\). We discuss sufficient conditions for the Lipschitz continuity and subdifferentiability of the primal gap function. Several sufficient conditions for the relevant mapping to be constant on the solutions have also been obtained. Based on these, we characterize the weak sharpness of the solutions of a variational inequality by \(g\). Some finite convergence results of algorithms for solving variational inequality problems are also included.     

The proximal point algorithm for pseudomonotone variational inequalities on Hadamard manifolds

In this paper, we investigate the proximal point algorithm (in short PPA) for variational inequalities with pseudomonotone vector fields on Hadamard manifolds. Under weaker assumptions than monotonicity, we show that the sequence generated by PPA is well defined and prove that the sequence converges to a solution of variational inequality, whenever it exists. The results presented in this paper generalize and improve some corresponding known results given in literatures.