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

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.     

PPA BASED PREDICTION-CORRECTION METHODS FOR MONOTONE VARIATIONAL INEQUALITIES

In this paper we study the proximal point algorithm (PPA) based prediction-correction (PC) methods for monotone variational inequalities. Each iteration of these methods consists of a prediction and a correction. The predictors are produced by inexact PPA steps. The new iterates are then updated by a correction using the PPA formula. We present two profit functions which serve two purposes: First we show that the profit functions are tight lower bounds of the improvements obtained in each iteration. Based on this conclusion we obtain the convergence inexactness restrictions for the prediction step. Second we show that the profit functions are quadratically dependent upon the step lengths, thus the optimal step lengths are obtained in the correction step. In the last part of the paper we compare the strengths of different methods based on their inexactness restrictions.     

The prox-Tikhonov regularization method for the proximal point algorithm in Banach spaces

It is known, by Rockafellar (SIAM J Control Optim 14:877–898, 1976), that the proximal point algorithm (PPA) converges weakly to a zero of a maximal monotone operator in a Hilbert space, but it fails to converge strongly. Lehdili and Moudafi (Optimization 37:239–252, 1996) introduced the new prox-Tikhonov regularization method for PPA to generate a strongly convergent sequence and established a convergence property for it by using the technique of variational distance in the same space setting. In this paper, the prox-Tikhonov regularization method for the proximal point algorithm of finding a zero for an accretive operator in the framework of Banach space is proposed. Conditions which guarantee the strong convergence of this algorithm to a particular element of the solution set is provided. An inexact variant of this method with error sequence is also discussed.     

Solution Methods for Pseudomonotone Variational Inequalities

We extend some results due to Thanh-Hao (Acta Math. Vietnam. 31: 283–289, [2006]) and Noor (J. Optim. Theory Appl. 115:447–452, [2002]). The first paper established a convergence theorem for the Tikhonov regularization method (TRM) applied to finite-dimensional pseudomonotone variational inequalities (VIs), answering in the affirmative an open question stated by Facchinei and Pang (Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, [2003]). The second paper discussed the application of the proximal point algorithm (PPA) to pseudomonotone VIs. In this paper, new facts on the convergence of TRM and PPA (both the exact and inexact versions of PPA) for pseudomonotone VIs in Hilbert spaces are obtained and a partial answer to a question stated in (Acta Math. Vietnam. 31:283–289, [2006]) is given. As a byproduct, we show that the convergence theorem for inexact PPA applied to infinite-dimensional monotone variational inequalities can be proved without using the theory of maximal monotone operators. This research was supported in part by a grant from the National Sun Yat-Sen University, Kaohsiung, Taiwan. It has been carried out under the agreement between the National Sun Yat-Sen University, Kaohsiung, Taiwan and the University of Pisa, Pisa, Italy. The authors thank the anonymous referee for useful comments and suggestions.     

A convergence rate of the proximal point algorithm in Banach spaces

We consider the convergence rate of the proximal point algorithm (PPA) for finding a minimizer of proper lower semicontinuous convex functions. In the Hilbert space setting, Güler showed that the big-O rate of the PPA can be improved to little-o when the sequence generated by the algorithm converges strongly to a minimizer. In this paper, we establish little-o rate of the PPA in Banach spaces without requiring this assumption. Then we apply the result to give new results on the convergence rate for sequences of alternating and averaged projections.     

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.     

A proximal point algorithm converging strongly for general errors

In this paper a proximal point algorithm (PPA) for maximal monotone operators with appropriate regularization parameters is considered. A strong convergence result for PPA is stated and proved under the general condition that the error sequence tends to zero in norm. Note that Rockafellar (SIAM J Control Optim 14:877–898, 1976) assumed summability for the error sequence to derive weak convergence of PPA in its initial form, and this restrictive condition on errors has been extensively used so far for different versions of PPA. Thus this Note provides a solution to a long standing open problem and in particular offers new possibilities towards the approximation of the minimum points of convex functionals.     

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.     

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.     

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.     

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.     

一种求解半定规划的邻近外梯度算法

本文提出了一种求解半定规划的邻近外梯度算法.通过转化半定规划的最优性条件为变分不等式,在变分不等式满足单调性和Lipschitz连续的前提下,构造包含原投影区域的半空间,产生邻近点序列来逼近变分不等式的解,简化了投影的求解过程.将该算法应用到教育测评问题中,数值实验结果表明,该方法是解大规模半定规划问题的一种可行方法.     

A projection-type method for variational inequalities on Hadamard manifolds and verification of solution existence

In this paper, we extend a projection-type method for variational inequalities from Euclidean spaces to Hadamard manifolds. The proposed method has the following nice features: (i) the algorithm is well defined whether the solution set of the problem is non-empty or not, under weak assumptions; (ii) if the solution set is non-empty, then the sequence generated by the method is convergent to the solution, which is closest to the initial point; and (iii) the existence of the solutions to variational inequalities can be verified through the behaviour of the generated sequence. The results presented in this paper generalize and improve some known results given in literatures.     

Split systems of general nonconvex variational inequalities and fixed point problems

The purpose of this paper is to introduce and study split systems of general nonconvex variational inequalities. Taking advantage of the projection technique over uniformly prox-regularity sets and utilizing two nonlinear operators, we propose and analyze an iterative scheme for solving the split systems of general nonconvex variational inequalities and fixed point problems. We prove that the sequence generated by the suggested iterative algorithm converges strongly to a common solution of the foregoing split problem and fixed point problem. The result presented in this paper extends and improves some well-known results in the literature. Numerical example illustrates the theoretical result.     

Tikhonov regularization methods for inverse variational inequalities

The purpose of this paper is to study Tikhonov regularization methods for inverse variational inequalities. A rather weak coercivity condition is given which guarantees that the solution set of regularized inverse variational inequality is nonempty and bounded. Moreover, the perturbation analysis for the solution set of regularized inverse variational inequality is established. As an application, we show that solutions of regularized inverse variational inequalities form a minimizing sequence of the D-gap function under a mild condition.     

Existence of Solutions to Generalized Vector Quasi-Variational-Like Inequalities with Set-Valued Mappings

In this paper, we introduce and study a class of generalized vector quasi-variational-like inequality problems, which includes generalized nonlinear vector variational inequality problems, generalized vector variational inequality problems and generalized vector variational-like inequality problems as special cases. We use the maximal element theorem with an escaping sequence to prove the existence results of a solution for generalized vector quasi-variational-like inequalities without any monotonicity conditions in the setting of locally convex topological vector space.     

Existence of Solutions to Generalized Vector Quasi-variational-like Inequalities with Set-valued Mappings

In this paper, we introduce and study a class of generalized vector quasivariational-like inequality problems, which includes generalized nonlinear vector variational inequality problems, generalized vector variational inequality problems and generalized vector variational-like inequality problems as special cases. We use the maximal element theorem with an escaping sequence to prove the existence results of a solution for generalized vector quasi-variational-like inequalities without any monotonicity conditions in the setting of locally convex topological vector space.     

On different geometric formulations of Lagrangian formalism

We consider two geometric formulations of Lagrangian formalism on fibred manifolds: Krupka's theory of finite order variational sequences, and Vinogradov's infinite order variational sequence associated with the -spectral sequence. On one hand, we show that the direct limit of Krupka's variational bicomplex is a new infinite order variational bicomplex which yields a new infinite order variational sequence. On the other hand, by means of Vinogradov's -spectral sequence, we provide a new finite order variational sequence whose direct limit turns out to be the Vinogradov's infinite order variational sequence. Finally, we provide an equivalence of the two finite order and infinite order variational sequences modulo the space of Euler-Lagrange morphisms.     

An approximate proximal-extragradient type method for monotone variational inequalities

Proximal point algorithms (PPA) are attractive methods for monotone variational inequalities. The approximate versions of PPA are more applicable in practice. A modified approximate proximal point algorithm (APPA) presented by Solodov and Svaiter [Math. Programming, Ser. B 88 (2000) 371–389] relaxes the inexactness criterion significantly. This paper presents an extended version of Solodov–Svaiter's APPA. Building the direction from current iterate to the new iterate obtained by Solodov–Svaiter's APPA, the proposed method improves the profit at each iteration by choosing the optimal step length along this direction. In addition, the inexactness restriction is relaxed further. Numerical example indicates the improvement of the proposed method.     

On inertial proximal algorithm for split variational inclusion problems

ABSTRACT

In this paper, a hybrid proximal algorithm with inertial effect is introduced to solve a split variational inclusion problem in real Hilbert spaces. Under mild conditions on the parameters, we establish weak convergence results for the proposed algorithm. Unlike the earlier iterative methods, we do not impose any conditions on the sequence generated by the proposed algorithm. Also, we extend our results to find a common solution of a split variational inclusion problem and a fixed-point problem. Finally, some numerical examples are given to discuss the convergence and superiority of the proposed iterative methods.