On the convergence of the Bermúdez-Moreno algorithm with constant parameters

Summary. Bermúdez-Moreno [5] presents a duality numerical algorithm for solving variational inequalities of the second kind. The performance of this algorithm strongly depends on the choice of two constant parameters. Assuming a further hypothesis of the inf-sup type, we present here a convergence theorem that improves on the one presented in [5]: we prove that the convergence is linear, and we give the expression of the asymptotic error constant and the explicit form of the optimal parameters, as a function of some constants related to the variational inequality. Finally, we present some numerical examples that confirm the theoretical results. Received June 28, 1999 / Revised version received February 19, 2001 / Published online October 17, 2001     

A class of gap functions for variational inequalities

Recently Auchmuty (1989) has introduced a new class of merit functions, or optimization formulations, for variational inequalities in finite-dimensional space. We develop and generalize Auchmuty's results, and relate his class of merit functions to other works done in this field. Especially, we investigate differentiability and convexity properties, and present characterizations of the set of solutions to variational inequalities. We then present new descent algorithms for variational inequalities within this framework, including approximate solutions of the direction finding and line search problems. The new class of merit functions include the primal and dual gap functions, introduced by Zuhovickii et al. (1969a, 1969b), and the differentiable merit function recently presented by Fukushima (1992); also, the descent algorithm proposed by Fukushima is a special case from the class of descent methods developed in this paper. Through a generalization of Auchmuty's class of merit functions we extend those inherent in the works of Dafermos (1983), Cohen (1988) and Wu et al. (1991); new algorithmic equivalence results, relating these algorithm classes to each other and to Auchmuty's framework, are also given.Corresponding author.     

A generalized duality method for solving variational inequalities Applications to some nonlinear Dirichlet problems

Summary. In [2] Bermúdez and Moreno introduced a duality algorithm for the numerical solution of variational inequalities; this algorithm is based on some properties of the Yosida regularization of maximal monotone operators. The performances of this algorithm strongly depend on the choice of two constant parameters. A generalization of the algorithm with automatic choice of parameters was discussed in [13], where the constant parameters were replaced by scalar functions, thus improving the convergence of the algorithm. In this article we present a generalization of the Bermúdez-Moreno algorithm that allows the use of very general operators as parameters, extending some of the results in [2], [13] and [14]. As a particular case, we analyze the use of scalar and matrix-valued parameters in a L^p()^M context. We apply the results developed to some boundary value problems involving the p-Laplacian operator, where it is shown that the use of matrix-valued parameters improves the convergence of the algorithm.Mathematics Subject Classification (1991): 47J20 – 65N12     

Halpern projection methods for solving pseudomonotone multivalued variational inequalities in Hilbert spaces

In this paper, we introduce new approximate projection and proximal algorithms for solving multivalued variational inequalities involving pseudomonotone and Lipschitz continuous multivalued cost mappings in a real Hilbert space. The first proposed algorithm combines the approximate projection method with the Halpern iteration technique. The second one is an extension of the Halpern projection method to variational inequalities by using proximal operators. The strongly convergent theorems are established under standard assumptions imposed on cost mappings. Finally we introduce a new and interesting example to the multivalued cost mapping, and show its pseudomontone and Lipschitz continuous properties. We also present some numerical experiments to illustrate the behavior of the proposed algorithms.

     

Schwarz methods for inequalities with contraction operators

We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type.     

Minimization of inhomogeneous biharmonic eigenvalue problems

Biharmonic eigenvalue problems arise in the study of the mechanical vibration of plates. In this paper, we study the minimization of the first eigenvalue of a simplified model with clamped boundary conditions and Navier boundary conditions with respect to the coefficient functions which are of bang-bang type (the coefficient functions take only two different constant values). A rearrangement algorithm is proposed to find the optimal coefficient function based on the variational formula of the first eigenvalue. On various domains, such as square, circular and annular domains, the region where the optimal coefficient function takes the larger value may have different topologies. An asymptotic analysis is provided when two different constant values are close to each other. In addition, a symmetry breaking behavior is also observed numerically on annular domains.     

Estimates of deviations from exact solutions of variational inequalities based upon Payne–Weinberger inequality

A new method for obtaining computable estimates for the difference between exact solutions of elliptic variational inequalities and arbitrary functions in the respective energy space is suggested. The estimates are obtained by transforming the corresponding variational inequality without the use of variational duality arguments. These estimates are valid for any function in the energy class and contain no constants depending on the mesh used to find an approximate solution. This method for linear elliptic and parabolic problems was earlier suggested by the author. The guaranteed error bounds we derive can be of two types. Estimates of the first type contain only one global constant, which is a constant in the Friedrichs type inequality. Estimates of the second type are based on the decomposition of Ω into convex subdomains and the Payne–Weinberger inequalities for these subdomains. Bibliography: 20 titles. Translated from Problems in Mathematical Analysis 39 February, 2009, pp. 81–90.     

On variable-step relaxed projection algorithm for variational inequalities

Projection algorithms are practically useful for solving variational inequalities (VI). However some among them require the knowledge related to VI in advance, such as Lipschitz constant. Usually it is impossible in practice. This paper studies the variable-step basic projection algorithm and its relaxed version under weakly co-coercive condition. The algorithms discussed need not know constant/function associated with the co-coercivity or weak co-coercivity and the step-size is varied from one iteration to the next. Under certain conditions the convergence of the variable-step basic projection algorithm is established. For the practical consideration, we also give the relaxed version of this algorithm, in which the projection onto a closed convex set is replaced by another projection at each iteration and latter is easy to calculate. The convergence of relaxed scheme is also obtained under certain assumptions. Finally we apply these two algorithms to the Split Feasibility Problem (SFP).     

Iterative algorithms for systems of extended regularized nonconvex variational inequalities and fixed point problems

This paper points out some fatal errors in the equivalent formulations used in Noor 2011 [Noor MA. Projection iterative methods for solving some systems of general nonconvex variational inequalities. Applied Analysis. 2011;90:777–786] and consequently in Noor 2009 [Noor MA. System of nonconvex variational inequalities. Journal of Advanced Research Optimization. 2009;1:1–10], Noor 2010 [Noor MA, Noor KI. New system of general nonconvex variational inequalities. Applied Mathematics E-Notes. 2010;10:76–85] and Wen 2010 [Wen DJ. Projection methods for a generalized system of nonconvex variational inequalities with different nonlinear operators. Nonlinear Analysis. 2010;73:2292–2297]. Since these equivalent formulations are the main tools to suggest iterative algorithms and to establish the convergence results, the algorithms and results in the aforementioned articles are not valid. It is shown by given some examples. To overcome with the problems in these papers, we consider a new system of extended regularized nonconvex variational inequalities, and establish the existence and uniqueness result for a solution of the aforesaid system. We suggest and analyse a new projection iterative algorithm to compute the unique solution of the system of extended regularized nonconvex variational inequalities which is also a fixed point of a nearly uniformly Lipschitzian mapping. Furthermore, the convergence analysis of the proposed iterative algorithm under some suitable conditions is studied. As a consequence, we point out that one can derive the correct version of the algorithms and results presented in the above mentioned papers.     

Golden ratio algorithms with new stepsize rules for variational inequalities

In this paper, we introduce two golden ratio algorithms with new stepsize rules for solving pseudomonotone and Lipschitz variational inequalities in finite dimensional Hilbert spaces. The presented stepsize rules allow the resulting algorithms to work without the prior knowledge of the Lipschitz constant of operator. The first algorithm uses a sequence of stepsizes that is previously chosen, diminishing, and nonsummable, while the stepsizes in the second one are updated at each iteration and by a simple computation. A special point is that the sequence of stepsizes generated by the second algorithm is separated from zero. The convergence and the convergence rate of the proposed algorithms are established under some standard conditions. Also, we give several numerical results to show the behavior of the algorithms in comparison with other algorithms.     

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.     

关于一类变分不等式的LQP算法

本文研究一类ξ-单调的变分不等式问题.利用KKT条件将原问题转换为非线性互补问题(nonlinear complementarity problem,NCP)的方法,获得了基于logarithmic-quadratic proximal(LQP)的算法及其改进形式,推广了LQP算法的适用范围.     

Modified subgradient extragradient algorithms for solving monotone variational inequalities

ABSTRACT

In this paper, we introduce two new algorithms for solving classical variational inequalities problem with Lipschitz continuous and monotone mapping in real Hilbert space. We modify the subgradient extragradient methods with a new step size, the convergence of algorithms are established without the knowledge of the Lipschitz constant of the mapping. Finally, some numerical experiments are presented to show the efficiency and advantage of the proposed algorithms.     

Projection Method Approach for General Regularized Non-convex Variational Inequalities

In this paper, we investigate or analyze non-convex variational inequalities and general non-convex variational inequalities. Two new classes of non-convex variational inequalities, named regularized non-convex variational inequalities and general regularized non-convex variational inequalities, are introduced, and the equivalence between these two classes of non-convex variational inequalities and the fixed point problems are established. A projection iterative method to approximate the solutions of general regularized non-convex variational inequalities is suggested. Meanwhile, the existence and uniqueness of solution for general regularized non-convex variational inequalities is proved, and the convergence analysis of the proposed iterative algorithm under certain conditions is studied.     

Generalized multivalued nonlinear quasivariational inclusions

In this paper, we introduce and study a few classes of generalized multivalued nonlinear quasivariational inclusions and generalized nonlinear quasivariational inequalities, which include many classes of variational inequalities, quasivariational inequalities and variational inclusions as special cases. Using the resolvent operator technique for maximal monotone mapping, we construct some new iterative algorithms for finding the approximate solutions of these classes of quasivariational inclusions and quasivariational inequalities. We establish the existence of solutions for this generalized nonlinear quasivariational inclusions involving both relaxed Lipschitz and strongly monotone and generalized pseudocontractive mappings and obtain the convergence of iterative sequences generated by the algorithms. Under certain conditions, we derive the existence of a unique solution for the generalized nonlinear quasivariational inequalities and obtain the convergence and stability results of the Noor type perturbed iterative algorithm. The results proved in this paper represent significant refinements and improvements of the previously known results in this area.     

Stopping Problems of Certain Multiplicative Functionals and Optimal Investment with Transaction Costs

Optimal stopping and impulse control problems with certain multiplicative functionals are considered. The stopping problems are solved by showing the unique existence of the solutions of relevant variational inequalities. However, since functions defining the multiplicative costs change the signs, some difficulties arise in solving the variational inequalities. Through gauge transformation we rewrite the variational inequalities in different forms with the obstacles which grow exponentially fast but with positive killing rates. Through the analysis of such variational inequalities we construct optimal stopping times for the problems. Then optimal strategies for impulse control problems on the infinite time horizon with multiplicative cost functionals are constructed from the solutions of the risk-sensitive variational inequalities of "ergodic type" as well. Application to optimal investment with fixed ratio transaction costs is also considered.     

Stability and bifurcations on a finite time interval in variational inequalities

Sufficient conditions for stability on a finite time interval are derived for a class of evolution variational inequalities with the use of Lyapunov functions and frequency-domain conditions. These inequalities are considered for Hilbert spaces and Sobolev spaces of infinite order in the sense of Yu.A. Dubinskii. We show how to use the stability result on a finite interval to characterize bifurcations. An algorithm for finding observation functionals is presented that uses an isomorphism between the algebra of pseudodifferential operators with constant coefficients whose symbols are real-analytic functions in some domain and an algebra of analytic matrix-valued functions.     

Partitionable variational inequalities with applications to network and economic equilibria

In this paper, we describe a useful class of finite-dimensional variational inequalities which we call partitionable. These variational inequalities are characterized by state functions which can be thought of as nonlinear separable functions added to antisymmetric linear functions. In the case of partitionable variational inequalities, questions of the monotonicity and coercivity of the state function can be addressed by considering the monotonicity and coercivity of a series of lower-dimensional functions. These functions are generally simpler to investigate than the state function. In the applications, these lower-dimensional functions are usually the natural functions to consider. To demonstrate, we conclude the paper by reviewing several models in the recent literature which give rise to partitionable variational inequalities.     

Extragradient algorithms extended to equilibrium problems¶

We make use of the auxiliary problem principle to develop iterative algorithms for solving equilibrium problems. The first one is an extension of the extragradient algorithm to equilibrium problems. In this algorithm the equilibrium bifunction is not required to satisfy any monotonicity property, but it must satisfy a certain Lipschitz-type condition. To avoid this requirement we propose linesearch procedures commonly used in variational inequalities to obtain projection-type algorithms for solving equilibrium problems. Applications to mixed variational inequalities are discussed. A special class of equilibrium problems is investigated and some preliminary computational results are reported.     

直线上函数的Banach空间的Poincaré型不等式的变分公式

基于研究对数Sobolev,Nash和其它泛函不等式的需要,将Poincare不等式 的变分公式拓广到一大类直线上函数的Banach(Orlicz)空间.给出了这些不等式成立 与否的显式判准和显式估计. 作为典型应用,仔细考察了对数Sobolev常数.