JIMO
Existence of anonymous link tolls for decentralizing an oligopolistic game and the efficiency analysis
Deren Han Xiaoming Yuan
Journal of Industrial & Management Optimization 2011, 7(2): 347-364 doi: 10.3934/jimo.2011.7.347
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
JIMO
Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities
Gang Qian Deren Han Lingling Xu Hai Yang
Journal of Industrial & Management Optimization 2013, 9(1): 255-274 doi: 10.3934/jimo.2013.9.255
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
JIMO
A proximal alternating direction method for multi-block coupled convex optimization
Foxiang Liu Lingling Xu Yuehong Sun Deren Han
Journal of Industrial & Management Optimization 2018, 13(5): 1-15 doi: 10.3934/jimo.2018067

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.

keywords: Convex optimization correction step multi-block proximal alternating direction method coupled quadratic function
NACO
A modification of the forward-backward splitting method for maximal monotone mappings
Xiao Ding Deren Han
Numerical Algebra, Control & Optimization 2013, 3(2): 295-307 doi: 10.3934/naco.2013.3.295
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.
JIMO
Global convergence of an inexact operator splitting method for monotone variational inequalities
Zhili Ge Gang Qian Deren Han
Journal of Industrial & Management Optimization 2011, 7(4): 1013-1026 doi: 10.3934/jimo.2011.7.1013
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
JIMO
A new parallel splitting descent method for structured variational inequalities
Kai Wang Lingling Xu Deren Han
Journal of Industrial & Management Optimization 2014, 10(2): 461-476 doi: 10.3934/jimo.2014.10.461
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.
JIMO
A practical trial-and-error implementation of marginal-cost pricing on networks
Deren Han Hai Yang Xiaoming Yuan
Journal of Industrial & Management Optimization 2010, 6(2): 299-313 doi: 10.3934/jimo.2010.6.299
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
JIMO
Congestion control with pricing in the absence of demand and cost functions: An improved trial and error method
Gang Qian Deren Han Hongjin He
Journal of Industrial & Management Optimization 2010, 6(1): 103-121 doi: 10.3934/jimo.2010.6.103
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
JIMO
Bounds on price of anarchy on linear cost functions
Fan Sha Deren Han Weijun Zhong
Journal of Industrial & Management Optimization 2015, 11(4): 1165-1173 doi: 10.3934/jimo.2015.11.1165
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
JIMO
Linearized block-wise alternating direction method of multipliers for multiple-block convex programming
Zhongming Wu Xingju Cai Deren Han
Journal of Industrial & Management Optimization 2018, 14(3): 833-855 doi: 10.3934/jimo.2017078

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.

keywords: Convex programming separable structure multiple-block alternating direction method of multipliers linearization technique global convergence

Year of publication

Related Authors

Related Keywords

[Back to Top]