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
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.
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 . 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  show the significance of our work.
In this paper, we propose a proximal alternating direction method (PADM) for solving the convex optimization problems with linear constraints whose objective function is the sum of multi-block separable functions and a coupled quadratic function. The algorithm generates the iterate via a simple correction step, where the descent direction is based on the PADM. We prove the convergence of the generated sequence under some mild assumptions. Finally, some familiar numerical results are reported for the new algorithm.
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.
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.
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.
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  and
, 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.
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.
The alternating direction method of multipliers (ADMM) is an efficient approach for two-block separable convex programming, while it is not necessarily convergent when extending this method to multiple-block case directly. One appealing method is that converts the multiple-block variables into two groups firstly and then adopts the classic ADMM with inexact solving to the resulting model, which is so-called block-wise ADMM. However, solving the subproblems in block-wise ADMM are usually difficult when the linear mappings in the constraints are not diagonal or the proximal operator of the objective function is not easy to evaluate. Therefore, in this paper, we adopt the linearization technique to different terms presented in the block-wise ADMM subproblems, and obtain three kinds of linearized block-wise ADMM which make the subproblems easy to solve in general case. Moreover, under some mild conditions, we prove the global convergence of the three new methods and report some preliminary numerical results to indicate the feasibility and effectiveness of the linearization strategy.