Variational inequalities and discrete and continuum models of network equilibrium problems

In this paper, we present different equilibrium models (the traffic equilibrium model in the static, in the dynamic and in the continuum case, the market equilibrium problem in the static and in the dynamic case) and we find the variational inequality related to each problem. We propose also a computational procedure for the calculation of the equilibrium solution and present the dual formulation of the variational inequality related to the traffic equilibrium problem.     

A TRUST REGION-TYPE METHOD FOR SOLVINGMONOTONE VARIATIONAL INEQUALITY

1.IntroductionLetSbeanonemptyclosedconvexsubsetofR"andletF:R"-R"beacontinuousmapping.ThevariatiollalillequalityproblemFindx*6Ssuchthat(F(x*),x--x*)20forallxeS(VIP)iswidelyusedtostudyvariousequilibriummodelsarisingilleconomic,operatiollsresearch,transportatiollandregionalsciellces[2'3I?where(.,.)dellotestheinnerproductinR".Manyiterativemethodsfor(VIP)havebeendeveloped,forexample,projectionmethods[7ts],thenonlinearJacobimethod[5],thesuccessiveoverrelaxation.ethod[9]andgeneralizedgradient.…     

Simultaneously optimizing link tolls and signal settings in a road network

The problem of determining link tolls to reduce traffic congestion is often referred as a toll design problem. In this paper, optimal tolls are determined for signal-controlled junctions in urban traffic road networks where the rerouting traffic is properly taken into account. This problem can be formulated as a mathematical program with equilibrium constraints (MPEC) where the user equilibrium is expressed as a variational inequality problem. Due to the non-differentiability of the equilibrium problem, an efficient convergent solution scheme is established. Numerical calculations are conducted on a variety of example road networks and comparisons are made with earlier methods.     

A MIXED FINITE ELEMENT METHOD FOR THE CONTACT PROBLEM IN ELASTICITY

Based on the analysis of [7] and [10], we present the mixed finite element approximation of the variational inequality resulting from the contact problem in elasticity. The convergence rate of the stress and displacement field are both improved from O（h3/4） to quasi-optimal O（h│logh│^1/4）. If stronger but reasonable regularity is available, the convergence rate can be optimal O（h）.     

A hybrid extragradient method for approximating the common solutions of a variational inequality, a system of variational inequalities, a mixed equilibrium problem and a fixed point problem

In this paper, we give a hybrid extragradient iterative method for finding the approximate element of the common set of solutions of a generalized equilibrium problem, a system of variational inequality problems, a variational inequality problem and a fixed point problem for a strictly pseudocontractive mapping in a real Hilbert space. Further we establish a strong convergence theorem based on this method. The results presented in this paper improves and generalizes the results given in Yao et al. [36] and Ceng et al. [7], and some known corresponding results in the literature.     

Note on: N.E. Aguilera, M.S. Escalante, G.L. Nasini, “The disjunctive procedure and blocker duality”

Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–13] give a generalization of a theorem of Lehman through an extension of the disjunctive procedure defined by Balas, Ceria and Cornuéjols. This generalization can be formulated as(A) For every clutter , the disjunctive index of its set covering polyhedron coincides with the disjunctive index of the set covering polyhedron of its blocker, .In Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–3], (A) is indeed a corollary of the stronger result(B) .Motivated by the work of Gerards et al. [Math. Oper. Res. 28 (2003) 884–885] we propose a simpler proof of (B) as well as an alternative proof of (A), independent of (B). Both of them are based on the relationship between the “disjunctive relaxations” obtained by and the set covering polyhedra associated with some particular minors of .     

An efficient algorithm for computing traffic equilibria using TRANSYT model

Computing traffic equilibria with signal settings using TRANSYT model for an area traffic control road system is considered in this paper. Following Wardrop’s first principle, this problem can be formulated as a variational inequality problem. In this paper, we propose a novel algorithm to efficiently solve this equilibrium traffic assignment with global convergence. Numerical calculations are conducted on a grid-size road network. As it shows, the proposed method achieved greater savings in computational overheads than did those conventional methods for solving traffic equilibria when signal settings are particularly taken into account.     

弹性接触问题的对偶混合有限元分析

１．引言用混合有限元方法求解弹性力学问题,其优点在于可同时求解位移和应力．力学问题的混合变分形式是混合有限元方法的基础．对于弹性接触问题,文献［６］给出了一种混合变分形式,以及相应的混合有限元分析（也可见［１０］）．其混合变分形式是直接从位移交分方程和Ｈｏｏｋ方程导出的,获得了应力ａ在Ｌ２（Ω）而位移、在Ｈ１（Ω）的一个闭凸子集上求解的混合变分问题．本文在［９］中提出的混合变分形式的基础上,再引入另一个Ｌａｐｒａｎｇｅ乘子,获得了三重组混合变分形式．它能同时求解物体内点的应力,位移和接触边界上的…     

A new algorithm for solving variational inequalities with application to the traffic assignment problem

The variational inequality problem in Euclidian space is formulated as a nonconvex, nondifferentiable optimization problem. We show that any stationary point is optimal, and we propose a solution algorithm that decreases the nondifferential objective monotonically. Application to the asymmetric traffic assignment problem is considered.Research supported by C.R.S.H. (Canada) grant #410-81-0722-RL and F.C.A.C. (Québec) grant # 83-AS-0026.     

A new contribution to a dynamic competitive equilibrium problem

The aim of this paper is to study the Walrasian equilibrium problem when the data are time dependent. For this model an existence result is provided using the variational inequality theory in infinite dimensional spaces. Our results are the generalization of some of the results obtained by several authors in the static case (see e.g. Donato et al. (2008) [5], Donato et al. (2008) [4] and Mordukhovich (2006) [11], Nagurney (1993) [2] and the references therein).     

Exact and stable least squares solution to the linear programming problem

A linear programming problem is transformed to the finding an element of polyhedron with the minimal norm. According to A. Cline [6], the problem is equivalent to the least squares problem on positive ortant. An orthogonal method for solving the problem is used. This method was presented earlier by the author and it is based on the highly developed least squares technique. First of all, the method is meant for solving unstable and degenerate problems. A new version of the artifical basis method (M-method) is presented. Also, the solving of linear inequality systems is considered.     

Strong convergence theorems for countable families of asymptotically relatively nonexpansive mappings with applications

The purpose of this paper is by using the hybrid iterative method to prove some strong convergence theorems for approximating a common element of the set of solutions to a system of generalized mixed equilibrium problems and the set of common fixed points for two countable families of closed and asymptotically relatively nonexpansive mappings in Banach space. The results presented in the paper improve and extend the corresponding results of Su et al. [Y.F. Su, H.K. Xu, X. Zhang, Strong convergence theorems for two countable families of weak relatively nonexpansive mappings and applications, Nonlinear Anal. 73 (2010) 3890-3906], Li and Su [H.Y. Li, Y.F. Su, Strong convergence theorems by a new hybrid for equilibrium problems and variational inequality problems, Nonlinear Anal. 72 (2) (2010) 847-855], Chang et al. [S.S. Chang, H.W. Joseph Lee, Chi Kin Chan, A new hybrid method for solving a generalized equilibrium problem solving a variational inequality problem and obtaining common fixed points in Banach spaces with applications, Nonlinear Anal. TMA 73 (2010) 2260-2270], Kang et al. [J. Kang, Y. Su, X. Zhang, Hybrid algorithm for fixed points of weak relatively nonexpansive mappings and applications, Nonlinear Anal. HS 4 (4) (2010) 755-765], Matsushita and Takahashi [S. Matsushita, W. Takahashi, A strong convergence theorem for relatively nonexpansive mappings in Banach spaces, J. Approx. Theory 134 (2005) 257-266], Tan et al. [J.F. Tan, S.S. Chang, M. Liu, J.I. Liu, Strong convergence theorems of a hybrid projection algorithm for a family of quasi-?-asymptotically nonexpansive mappings, Opuscula Math. 30 (3) (2010) 341-348], Takahashia and Zembayashi [W. Takahashi, K. Zembayashi, Strong and weak convergence theorems for equilibrium problems and relatively nonexpansive mappings in Banach spaces, Nonlinear Anal. 70 (2009) 45-57] and Wattanawitoon and Kumam [K. Wattanawitoon, P. Kumam, Strong convergence theorems by a new hybrid projection algorithm for fixed point problem and equilibrium problems of two relatively quasi-nonexpansive mappings, Nonlinear Anal. Hybrid Systems 3 (2009) 11-20] and others.     

Numerical Solution of Non-Steady State Porous Flow Free Boundary Problems

The aim of this paper is the study of the convergence of a finite element approximation for a variational inequality related to free boundary problems in non-steady fluid flow through porous media. There have been many results in the stationary case, for example, the steady dam problems, the steady flow well problems, etc. In this paper we shall deal with the axisymmetric non-steady porous flow well problem. It is well know that by means of Torelli's transform this problem, similar to the non-steady rectangular dam problem, can be reduced a variational, inequality, and the existence, uniqueness and regularity of the solution can be obtained ([12, 7]). Now we study the numerical solution of this variational inequality. The main results are as follows: 1. We establish new regularity properties for the solution $W$ of the variation inequality. We prove that $W \in L^\infty(0, T; H^2(D))$, $γ_0W\in L^\infty(0, T; H^2(T_n))$ and $D_1γ_0W\in L^2(0, T; H^1(T_n))$ (see Theorem 2.5). Friedman and Torelli [7] obtained $W\in L^2(0, T; H^2(D))$. Our new regularity properties will be used for error estimation. 2. We prove that the error estimate for the finite element solution of the variational inequality is $$ ( \sum^N_{i=1}\| W^1 - W^1_h \|^2_{H^1(D)}\Delta t)^{1/2} = O(h+\Delta t^{1/2})$$ (see Theorem 3.4). In the stationary case the error estimate is $\|W-W_h\|_{H^1(D)} = O(k)$ ([3,6]). 3. We give a numerical example and compare the result with the corresponding result in the stationary case. The result of this paper are valid for the non-ready rectangular dam problem with stationary or quasi-stationary initial data (see [7], p.534).     

随机交通均衡配流模型及其等价的变分不等式问题

本文讨论了交通网络系统的随机用户均衡原理的数学表述问题.在路段出行成本是流量的单调函数的较弱条件下,对具有固定需求和弹性需求的模式,首次证明了随机均衡配流模型可表示为一个变分不等式问题,同时也说明了该变分不等式问题与相应的互补问题以及一个凸规划问题之间的等价关系.     

Two-stage stochastic variational inequalities: an ERM-solution procedure

We propose a two-stage stochastic variational inequality model to deal with random variables in variational inequalities, and formulate this model as a two-stage stochastic programming with recourse by using an expected residual minimization solution procedure. The solvability, differentiability and convexity of the two-stage stochastic programming and the convergence of its sample average approximation are established. Examples of this model are given, including the optimality conditions for stochastic programs, a Walras equilibrium problem and Wardrop flow equilibrium. We also formulate stochastic traffic assignments on arcs flow as a two-stage stochastic variational inequality based on Wardrop flow equilibrium and present numerical results of the Douglas–Rachford splitting method for the corresponding two-stage stochastic programming with recourse.     

On a variational inequality associated with a stopping game combined with a control

We study a non-linear elliptic variational inequality which corresponds to a zero-sum stopping game (Dynkin game) combined with a control. Our result is a generalization of the existing works by Bensoussan [ Stochastic Control by Functional Analysis Methods (North-Holland, Amsterdam), 1982], Bensoussan and Lions [ Applications des Inéquations Variationnelles en Contrôle Stochastique (Dunod, Paris), 1978] and Friedman [ Stochastic Differential Equations and Applications (Academic Press, New York), 1976] in the sense that a non-linear term appears in the variational inequality, or equivalently, that the underlying process for the corresponding stopping game is subject to a control. By using the dynamic programming principle and the method of penalization, we show the existence and uniqueness of a viscosity solution of the variational inequality and describe it as the value function of the corresponding combined-stochastic game problem.     

The game problem on the dolichobrachistochrone : PMM vol.40, n 6, 1976, pp. 1003–1013

The capture and evasion sets, the players' optimal strategies and the game value determined for the game problem on the dolichobrachistochrone, analysed within the framework of a position formalism similar to [1]. Singularities inherent in the game of the minimax-maximin time to contact [1, 2] become apparent; they are determined in the given problem by the specific behavior of the optimal paths close to the target set. Isaacs [4] examined the game problem on the dolichobrachistochrone, being the game analog of the classical variational problem on the brachistochrone [3]. However, as was shown in [5], the solution proposed by Isaacs contains erroneous statements.     

Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems

Whether or not the general asymmetric variational inequality problem can be formulated as a differentiable optimization problem has been an open question. This paper gives an affirmative answer to this question. We provide a new optimization problem formulation of the variational inequality problem, and show that its objective function is continuously differentiable whenever the mapping involved in the latter problem is continuously differentiable. We also show that under appropriate assumptions on the latter mapping, any stationary point of the optimization problem is a global optimal solution, and hence solves the variational inequality problem. We discuss descent methods for solving the equivalent optimization problem and comment on systems of nonlinear equations and nonlinear complementarity problems.     

An existence theorem for generalized variational inequalities with discontinuous and pseudomonotone operators

This paper gives a solution existence theorem for a generalized variational inequality problem with an operator which is defined on an infinite dimensional space, which is C-pseudomonotone in the sense of Inoan and Kolumbán [D. Inoan, J. Kolumbán, On pseudomonotone set-valued mappings, Nonlinear Analysis 68 (2008) 47-53], but which may not be upper semicontinuous on finite dimensional subspaces. The proof of the theorem provides a new technique which reduces infinite variational inequality problems to finite ones. Two examples are given and analyzed to illustrate the theorem. Moreover, an example is presented to show that the C-pseudomonotonicity of the operator cannot be omitted in the theorem.     

无单调性集值变分不等式的一种投影算法

本文给出了求解无单调性集值变分不等式的一个新的投影算法,该算法所产生的迭代序列在Minty变分不等式解集非空且映射满足一定的连续性条件下收敛到解.对比文献[10]中的算法,本文中的算法使用了不同的线性搜索和半空间,在计算本文所引的两个数值例子时,该算法比文献[10]中的算法所需迭代步更少.