Existence of anonymous link tolls for decentralizing an oligopolistic game and the efficiency analysis
Deren Han Xiaoming Yuan
To apply the traditional marginal-cost pricing to drive a user equilibrium of the oligopolistic game to the system optimum, it requires to classify the users into different classes and then charge discriminatory tolls across user classes. By realizing the difficulty of discriminating users when they differ in some unobservable ways, Yang and Zhang investigated existence of anonymous link tolls for transportation networks recently. In this paper, we consider the anonymous link tolls for the oligopolistic game with nonseparable, nonlinear and asymmetric cost functions with fixed demands. With similar techniques developed by Yang and Zhang, we first prove the existence of anonymous link tolls to decentralize the system optimum to a user equilibrium. Then, by deriving some bounds on the so-called price of anarchy, we analyze the efficiency of such a toll strategy when the tolls are considered as part of the system cost.
keywords: Asymmetric cost functions. System optimum Anonymous link tolls Oligopolistic games Price of anarchy User equilibrium
Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities
Gang Qian Deren Han Lingling Xu Hai Yang
In the last decade, as calibrations of the classical traffic equilibrium problems, various models of traffic equilibrium problems with nonadditive route costs have been proposed. For solving such models, this paper develops a self-adaptive projection-auxiliary problem method for monotone variational inequality (VI) problems. It first converts the original problem where the feasible set is the intersection of a linear manifold and a simple set to an augmented VI with simple set, which makes the projection easy to implement. The self-adaptive strategy avoids the difficult task of choosing `suitable' parameters, and leads to fast convergence. Under suitable conditions, we prove the global convergence of the method. Some preliminary computational results are presented to illustrate the ability and efficiency of the method.
keywords: auxiliary problem principle self-adaptive strategy. projection method Traffic equilibrium and nonadditive cost variational inequality problem
A modification of the forward-backward splitting method for maximal monotone mappings
Xiao Ding Deren Han
In this paper, we propose a modification of the forward-backward splitting method for maximal monotone mappings, where we adopt a new step-size scheme in generating the next iterate. This modification is motivated by the ingenious rule proposed by He and Liao in modified Korpelevich's extra-gradient method [13]. Under suitable conditions, we prove the global convergence of the new algorithm. We apply our method to solve some monotone variational inequalities and report its numerical results. Comparisons with modified Khobotov-Korpelevich's extragradient method [13,14] and Tseng's method [30] show the significance of our work.
keywords: co-coercive variational inequality Forward-backward splitting method maximal monotone projection.
A new parallel splitting descent method for structured variational inequalities
Kai Wang Lingling Xu Deren Han
In this paper, we propose a new parallel splitting descent method for solving a class of variational inequalities with separable structure. The new method can be applied to solve convex optimization problems in which the objective function is separable with three operators and the constraint is linear. In the framework of the new algorithm, we adopt a new descent strategy by combining two descent directions and resolve the descent direction which is different from the methods in He (Comput. Optim. Appl., 2009, 42: 195-212.) and Wang et al. (submitted to J. Optimiz. Theory App.). Theoretically, we establish the global convergence of the new method under mild assumptions. In addition, we apply the new method to solve problems in management science and traffic equilibrium problem. Numerical results indicate that the new method is efficient and reliable.
keywords: variational inequalities Alternating direction method parallel computing augmented Lagrangian method separable structure.
A practical trial-and-error implementation of marginal-cost pricing on networks
Deren Han Hai Yang Xiaoming Yuan
This paper proposes a trial-and-error implementation of marginal-cost pricing on transportation networks in the absence of both demand functions and travel time functions. Assuming that the corresponding link flows for given trial tolls are observable and that the approximations of the exact travel time functions are provided, the new trial is obtained via solving a system of equations. The new trial-and-error implementation is proved to be convergent globally under mild assumptions, and its improvements over existing methods are verified by some numerical experiments.
keywords: marginal cost trial-and-error. variational inequality Network pricing problems
Congestion control with pricing in the absence of demand and cost functions: An improved trial and error method
Gang Qian Deren Han Hongjin He
Without the information of the origin-destination demand function and users' valuation for travel time saving, the precise estimation of the road tolls for various pricing schemes must go in a trial-and-error manner, as suggested by [2] and [15], and recently realized by [6, 7, 11, 22, 24]. For a trial of the tolls pattern, the responses of the users can be observed and used to update the toll pattern for the next trial. Since getting the responses of the users is expensive, it is desirable to use the acquired information exhaustively; That is, we need to make the method converge to an approximate solution of the problem within as little number of changes as possible.
   In this paper, we propose to update the link tolls pattern in an improved manner, where the profit direction is the combination of two known directions. This combined manner makes the method more efficient than the method using solely one of them. We prove the global convergence of the method under suitable conditions as those in [6, 7, 24]. Some preliminary computational results are also reported.
keywords: unknown mappings. transportation network variational inequality problems trial-and-error Congestion pricing
Bounds on price of anarchy on linear cost functions
Fan Sha Deren Han Weijun Zhong
The price of anarchy (POA) is a quite powerful tool to characterize the efficiency loss of competition on networks. In this paper, we derive a bound for POA for the case that the cost function is linear but asymmetric. The result is a generalization of that of Han et. al. in the sense that the involved matrix is only assumed to be positive semidefinite, but not positive definite. Consequently, the range of application of the result is widened. We give two simple examples to illustrate our result.
keywords: price of anarchy system optimum cost function. Nash equilibrium network
Global convergence of an inexact operator splitting method for monotone variational inequalities
Zhili Ge Gang Qian Deren Han
Recently, Han (Han D, Inexact operator splitting methods with self-adaptive strategy for variational inequality problems, Journal of Optimization Theory and Applications 132, 227-243 (2007)) proposed an inexact operator splitting method for solving variational inequality problems. It has advantage over the classical operator splitting method of Douglas-Peaceman-Rachford-Varga operator splitting methods (DPRV methods) and some of their variants, since it adopts a very flexible approximate rule in solving the subproblem in each iteration. However, its convergence is established under somewhat stringent condition that the underlying mapping $F$ is strongly monotone. In this paper, we mainly establish the global convergence of the method under weaker condition that the underlying mapping $F$ is monotone, which extends the fields of applications of the method relatively. Some numerical results are also presented to illustrate the method.
keywords: self-adaptive strategy. Monotone variational inequalities operator splitting methods approximate rules
An efficient projection method for nonlinear inverse problems with sparsity constraints
Deren Han Zehui Jia Yongzhong Song David Z. W. Wang
In this paper, we propose a modification of the accelerated projective steepest descent method for solving nonlinear inverse problems with an $\ell_1$ constraint on the variable, which was recently proposed by Teschke and Borries (2010 Inverse Problems 26 025007). In their method, there are some parameters need to be estimated, which is a difficult task for many applications. We overcome this difficulty by introducing a self-adaptive strategy in choosing the parameters. Theoretically, the convergence of their algorithm was guaranteed under the assumption that the underlying mapping $F$ is twice Fréchet differentiable together with some other conditions, while we can prove weak and strong convergence of the proposed algorithm under the condition that $F$ is Fréchet differentiable, which is a relatively weak condition. We also report some preliminary computational results and compare our algorithm with that of Teschke and Borries, which indicate that our method is efficient.
keywords: weak and strong convergence. sparsity self-adaptive nonlinear inverse problems Projection method

Year of publication

Related Authors

Related Keywords

[Back to Top]