Search

We propose a new proximal alternating direction method of multipliers (ADMM) for solving a class of three-block nonconvex optimization problems with linear constraints. The proposed method updates the third primal variable twice per iteration and introduces semidefinite proximal terms to the subproblems with the first two blocks. The method can be regarded as an extension of the method proposed in Sun et al. (2015) which is specialized to the convex case with the third block of the objective function being quadratic. Based on the powerful Kurdyka–Łojasiewicz property, we prove that each bounded sequence generated by the proposed method converges to a critical point of the considered problem. Some numerical results are reported to indicate the effectiveness and superiority of the proposed method.

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.

Projecting a point onto an ellipsoid is one of the fundamental problems in convex analysis and numerical algorithms. Recently, several fast algorithms were proposed for solving this problem such as Lin–Han algorithm, maximum 2-dimensional inside ball algorithm, sequential 2-dimensional projection algorithm and hybrid projection algorithms of Dai. In this paper, we rewrite the problem as a constrained convex optimization problem with separable objective functions, which enables the use of the alternating direction method of multipliers (ADMM). Furthermore, since the efficiency of ADMM depends on the penalty parameter, we choose it in a self-adaptive manner, resulting in the self-adaptive ADMM (S-ADMM). All these methods converge with a global linear rate. We compare them theoretically and numerically and find that S-ADMM is the most efficient one. We also illustrate the flexibility of ADMM by applying it to the more general problem of projecting a point onto the intersection of several ellipsoids, Dantzig selector, and image restoration and reconstruction.

In this paper, a modified Hestenes–Stiefel conjugate gradient method for unconstrained problems is developed, which can achieves the twin goals of generating sufficient descent direction at each iteration as well as being close to the Newton direction. In our methods, the hybridization parameter can also be obtained based on other kinds of conjugacy conditions. Under mild condition, we establish their global convergence for general objective functions. Numerical experimentation with the new method indicates that it efficiently solves the test problems and therefore is promising.

For solving minimization problems whose objective function is the sum of two functions without coupled variables and the constrained function is linear, the alternating direction method of multipliers (ADMM) has exhibited its efficiency and its convergence is well understood. When either the involved number of separable functions is more than two, or there is a nonconvex function, ADMM or its direct extended version may not converge. In this paper, we consider the multi-block separable optimization problems with linear constraints and absence of convexity of the involved component functions. Under the assumption that the associated function satisfies the Kurdyka- Lojasiewicz inequality, we prove that any cluster point of the iterative sequence generated by ADMM is a critical point, under the mild condition that the penalty parameter is sufficiently large. We also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.

The logarithmic quadratic proximal (LQP) regularization is a popular and powerful proximal regularization technique for solving monotone variational inequalities with nonnegative constraints. In this paper, we propose an implementable two-step method for solving structured variational inequality problems by combining LQP regularization and projection method. The proposed algorithm consists of two parts. The first step generates a pair of predictors via inexactly solving a system of nonlinear equations. Then, the second step updates the iterate via a simple correction step. We establish the global convergence of the new method under mild assumptions. To improve the numerical performance of our new method, we further present a self-adaptive version and implement it to solve a traffic equilibrium problem. The numerical results further demonstrate the efficiency of the proposed method.

In variational inequalities arising from applications such as engineering, economics and transportation, partial mappings are usually unknown, e.g., the demand function in traffic assignment problem. As a consequence, classical methods can not deal with this class of problems. On the other hand, the recently developed methods require restrictive conditions such as strong monotonicity of some mappings, which excludes many interesting applications. In this paper, we propose an operator splitting method with a new perturbation strategy for solving variational inequality problems with partially unknown mappings. Under the mild condition that the underlying mapping is monotone, we prove the global convergence of the method. We also report some preliminary numerical results which show that the new algorithm is also interesting from the numerical point of view.

The efficiency of the classic alternating direction method of multipliers has been exhibited by various applications for large-scale separable optimization problems, both for convex objective functions and for nonconvex objective functions. While there are a lot of convergence analysis for the convex case, the nonconvex case is still an open problem and the research for this case is in its infancy. In this paper, we give a partial answer on this problem. Specially, under the assumption that the associated function satisfies the Kurdyka–Łojasiewicz inequality, we prove that the iterative sequence generated by the alternating direction method converges to a critical point of the problem, provided that the penalty parameter is greater than 2L, where L is the Lipschitz constant of the gradient of one of the involved functions. Under some further conditions on the problem's data, we also analyse the convergence rate of the algorithm.

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 Frechet differentiable together with some other conditions, while we can prove weak and strong convergence of the proposed algorithm under the condition that $F$ is Frechet 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.

The alternating direction method of multipliers (ADMM) is a benchmark for solving a two-block linearly constrained convex minimization model whose objective function is the sum of two functions without coupled variables. Meanwhile, it is known that the convergence is not guaranteed if the ADMM is directly extended to a multiple-block convex minimization model whose objective function has more than two functions. Recently, some authors have actively studied the strong convexity condition on the objective function to sufficiently ensure the convergence of the direct extension of ADMM or the resulting convergence when the original scheme is appropriately twisted. We focus on the three-block case of such a model whose objective function is the sum of three functions, and discuss the convergence of the direct extension of ADMM. We show that when one function in the objective is strongly convex, the penalty parameter and the operators in the linear equality constraint are appropriately restricted, it is sufficient to guarantee the convergence of the direct extension of ADMM. We further estimate the worst-case convergence rate measured by the iteration complexity in both the ergodic and nonergodic senses, and derive the globally linear convergence in asymptotical sense under some additional conditions.

The numerical success of the alternating direction method of multipliers (ADMM) inspires much attention in analyzing its theoretical convergence rate. While there are several results on the iterative complexity results implying sublinear convergence rate for the general case, there are only a few results for the special cases such as linear programming, quadratic programming, and nonlinear programming with strongly convex functions. In this paper, we consider the convergence rate of ADMM when applying to the convex optimization problems that the subdifferentials of the underlying functions are piecewise linear multifunctions, including LASSO, a well-known regression model in statistics, as a special case. We prove that due to its inherent polyhedral structure, a recent global error bound holds for this class of problems. Based on this error bound, we derive the linear rate of convergence for ADMM. We also consider the proximal based ADMM and derive its linear convergence rate.

In diffusion-weighted magnetic resonance imaging, the estimation of the orientations of multiple nerve fibers in each voxel (the fiber orientation distribution (FOD)) is a critical issue for exploring the connection of cerebral tissue. In this paper, we establish a convex semidefinite programming (CSDP) model for the FOD estimation. One feature of the new model is that it can ensure the statistical meaning of FOD since as a probability density function, FOD must be nonnegative and have a unit mass. To construct such a statistically meaningful FOD, we consider its approximation by a sum of squares (SOS) polynomial and impose the unit-mass by a linear constraint. Another feature of the new model is that it introduces a new regularization based on the sparsity of nerve fibers. Due to the sparsity of the orientations of nerve fibers in cerebral white matter, a heuristic regularization is raised, which is inspired by the Z-eigenvalue of a symmetric tensor that closely relates to the SOS polynomial. To solve th...

The heuristic Cross-Hill method proposed by Qi et?al. (2009) 14 was recently extended from finding the Z-eigenvalues of tensors to quantum separation problem by Han and Qi (2013) 5. In this paper, we show that it can be extended to solve general global optimization problems. The heuristic Cross-Hill method is a combination of a local optimization method and a global optimization method with lower dimension. At each iteration, it first uses the local optimization method to find a local solution. Then, using this point and an arbitrary orthogonal vector, it solves a two-dimensional optimization problem to find a better solution than that the local approach was able to find. Preliminary experimental results are very encouraging.

In this paper, we introduce a splitting method for solving Dantzig selector problem, a new linear regression model that was extensively studied in the literature in the past few years. The new method is very simple in the sense that, per iteration, it only performs a projection onto a box, and does some matrix-vector products. We prove the global convergence of the method and report some promising numerical results, which demonstrate that the new method is competitive with some state-of-the-art methods recently developed in the literature.

A customized Douglas-Rachford splitting method (DRSM) was recently proposed to solve two-block separable convex optimization problems with linear constraints and simple abstract constraints. The algorithm has advantage over the well-known alternating direction method of multipliers (ADMM), the dual application of DRSM to the two-block convex minimization problem, in the sense that the subproblems can have larger opportunity of possessing closed-form solutions since they are unconstrained. In this paper, we further study along this way by considering the primal application of DRSM for the general case m?3, i.e., we consider the multi-block separable convex minimization problem with linear constraints where the objective function is separable into m individual convex functions without coupled variables. The resulting method fully exploits the separable structure and enjoys decoupled subproblems which can be solved simultaneously. Both the exact and inexact versions of the new method are presented in a unified framework. Under mild conditions, we manage to prove the global convergence of the algorithm. Preliminary numerical experiments for extracting the background from corrupted surveillance video verify the encouraging efficiency of the new algorithm.

We consider a class of variational inequality problems with linear constraints, where the mapping is unknown and the system is an oracle. The capacitated traffic congestion pricing problem of transportation is such an application, and many classical methods cannot deal with this class of problems. Note that the cost of the observation (observe the exact solution of the subproblem) is very expensive. It is important to get an inexact solution instead of an exact solution, especially when the iteration is far from the solution set. In this paper, we propose a modified inexact prediction–correction method. Under the mild condition that the underlying mapping is strongly monotone, we prove the global convergence. Some numerical examples are presented to illustrate the efficiency of the inexact strategy.

In this paper, we propose a novel alternating projection based prediction–correction method for solving the monotone variational inequalities with separable structures. At each iteration, we adopt the weak requirements for the step sizes to derive the predictors, which affords fewer trial and error steps to accomplish the prediction phase. Moreover, we design a new descent direction for the merit function in correction phase. Under some mild assumptions, we prove the global convergence of the modified method. Some preliminary computational results are reported to demonstrate the promising and attractive performance of the modified method compared to some state-of-the-art prediction–contraction methods.

This work is motivated by a recent work on an extended linear proximal point algorithm PPA [B.S. He, X.L. Fu, and Z.K. Jiang, Proximal-point algorithm using a linear proximal term, J. Optim. Theory Appl. 141 2009, pp. 299–319], which aims at relaxing the requirement of the linear proximal term of classical PPA. In this paper, we make further contributions along the line. First, we generalize the linear PPA-based contraction method by using a nonlinear proximal term instead of the linear one. A notable superiority over traditional PPA-like methods is that the nonlinear proximal term of the proposed method may not necessarily be a gradient of any functions. In addition, the nonlinearity of the proximal term makes the new method more flexible. To avoid solving a variational inequality subproblem exactly, we then propose an inexact version of the developed method, which may be more computationally attractive in terms of requiring lower computational cost. Finally, we gainfully employ our new methods to solve linearly constrained convex minimization and variational inequality problems.

Following the recent work Schaeffer and Osher (SIAM J Imaging Sci 6:226---262, 2013), the low patch-rank interpretation for the oscillating patterns of an image validates the application of matrix-rank optimization to image decomposition. Therein, the problem was mathematically modeled as a separable convex programming with three-block (a total variation semi-norm for regularizing the cartoon, a low-rank constraint for extracting the texture, and a data fidelity term for approximating the target image), and was algorithmically handled by the split Bregman method with inner Gauss-Seidel sweep loops. In this paper, we develop an alternating direction method of multipliers (ADMM) based prediction---correction method for solving the low patch-rank model with all resulting subproblems admitting closed-form solutions. As a surrogate of the direct extension of ADMM, which was recently proved to be not necessarily convergent, the new method is globally convergent under some mild conditions. Numerical simulations are conducted, which demonstrate the promising performance of the new 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.

In this paper, we propose a proximal parallel decomposition algorithm for solving the optimization problems where the objective function is the sum of m separable functions (i.e., they have no crossed variables), and the constraint set is the intersection of Cartesian products of some simple sets and a linear manifold. The m subproblems are solved simultaneously per iterations, which are sum of the decomposed subproblems of the augmented Lagrange function and a quadratic term. Hence our algorithm is named as the 'proximal parallel splitting method'. We prove the global convergence of the proposed algorithm under some mild conditions that the underlying functions are convex and the solution set is nonempty. To make the subproblems easier, some linearized versions of the proposed algorithm are also presented, together with their global convergence analysis. Finally, some preliminary numerical results are reported to support the efficiency of the new algorithms.

We consider applying the Douglas---Rachford splitting method (DRSM) to the convex minimization problem with linear constraints and a separable objective function. The dual application of DRSM has been well studied in the literature, resulting in the well known alternating direction method of multipliers (ADMM). In this paper, we show that the primal application of DRSM in combination with an appropriate decomposition can yield an efficient structure-exploiting algorithm for the model under consideration, whose subproblems could be easier than those of ADMM. Both the exact and inexact versions of this customized DRSM are studied; and their numerical efficiency is demonstrated by some preliminary numerical results.

SUMMARY Recent studies on the new congestion reduction method―tradable credit scheme rely on the full information of speed-flow relationship, demand function, and generalized cost. As analytical travel demand, functions are difficult to establish in practice. This paper develops a trial and error method for selecting optimal credit schemes for general networks in the absence of demand functions. After each trial of tradable credit scheme, the credit charging scheme and total amount of credits to be distributed are updated by both observed link flows at traffic equilibrium and revealed credit price at market equilibrium. The updating strategy is based on the method of successive averages and its convergence is established theoretically. Our numerical experiments demonstrate that the method of successive averages based trial and error method for tradable credit schemes has a lower convergence speed in comparison with its counterpart for congestion pricing and could be enhanced by exploring more efficient methods that make full use of credit price information. Copyright © 2013 John Wiley & Sons, Ltd.

Alternating direction method ADM, which decomposes a large-scale original variational inequality VI problem into a series of smaller scale subproblems, is very attractive for solving a class of VI problems with a separable structure. This type of method can greatly improve the efficiency, but cannot avoid solving VI subproblems. In this paper, we propose a hybrid splitting method with variable parameters for separable VI problems. Specifically, the proposed method solves only one strongly monotone VI subproblem and a well-posed system of nonlinear equations in each iteration. The global convergence of the new method is established under some standard assumptions as those in classical ADMs. Finally, some preliminary numerical results show that the proposed method performs favourably in practice.

In this paper, we propose a new parallel splitting augmented Lagrangian method for solving the nonlinear programs where the objective function is separable with three operators and the constraint is linear. The method is an improvement of the method of He (Comput. Optim. Appl., 2(42):195–212, 2009), where we generate a predictor using the same parallel splitting augmented Lagrangian scheme as that in He (Comput. Optim. Appl., 2(42):195–212, 2009), while adopting a new strategy to get the next iterate. Under the mild assumptions of convexity of the underlying mappings and the non-emptiness of the solution set, we prove that the proposed algorithm is globally convergent. We apply the new method in the area of image processing and to solve some quadratic programming problems. The preliminary numerical results indicate that the new method is efficient.

The nonnegative tensor (matrix) factorization finds more and more applications in various disciplines including machine learning, data mining, and blind source separation, etc. In computation, the optimization problem involved is solved by alternatively minimizing one factor while the others are fixed. To solve the subproblem efficiently, we first exploit a variable regularization term which makes the subproblem far from ill-condition. Second, an augmented Lagrangian alternating direction method is employed to solve this convex and well-conditioned regularized subproblem, and two accelerating skills are also implemented. Some preliminary numerical experiments are performed to show the improvements of the new method.

The Douglas--Rachford alternating direction method of multipliers (ADMM) has been widely used in various areas. The global convergence of ADMM is well known, while research on its convergence rate ...

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 new partial splitting augmented Lagrangian method for solving the separable constrained convex programming problem where the objective function is the sum of three separable convex functions and the constraint set is also separable into three parts. The proposed algorithm combines the alternating direction method (ADM) and parallel splitting augmented Lagrangian method (PSALM), where two operators are handled by a parallel method, while the third operator and the former two are dealt with by an alternating manner. Under mild conditions, we prove the global convergence of the new method. We also report some preliminary numerical results on constrained matrix optimization problem, illustrating the advantage of the new algorithm over the most recently PADALM of Peng and Wu (2010) [12].

We consider the convex minimization problem with linear constraints and a block-separable objective function which is represented as the sum of three functions without coupled variables. To solve this model, it is empirically effective to extend straightforwardly the alternating direction method of multipliers (ADM for short). But, the convergence of this straightforward extension of ADM is still not proved theoretically. Based on ADM's straightforward extension, this paper presents a new splitting method for the model under consideration, which is empirically competitive to the straightforward extension of ADM and meanwhile the global convergence can be proved under standard assumptions. At each iteration, the new method corrects the output of the straightforward extension of ADM by some slight correction computation to generate a new iterate. Thus, the implementation of the new method is almost as easy as that of ADM's straightforward extension. We show the numerical efficiency of the new method by some applications in the areas of image processing and statistics.

In this paper, we propose a new correction strategy for some first-order primal-dual algorithms arising from solving, e.g., total variation image restoration. With this strategy, we can prove the convergence of the algorithm under more flexible conditions than those proposed most recently. Some preliminary numerical results of image deblurring support that the new correction strategy can improve the numerical efficiency.

In this paper, we propose efficient neural network models for solving a class of variational inequality problems. Our first model can be viewed as a generalization of the basic projection neural network proposed by Friesz et al. [3]. As the basic projection neural network, it only needs some function evaluations and projections onto the constraint set, which makes the model very easy to implement, especially when the constraint set has some special structure such as a box, or a ball. Under the condition that the underlying mapping F is pseudo-monotone with respect to a solution, a condition that is much weaker than those required by the basic projection neural network, we prove the global convergence of the proposed neural network. If F is strongly pseudo-monotone, we prove its globally exponential stability. Then to improve the efficient of the neural network, we modify it by choosing a new direction that is bounded away from zero. Under the condition that the underlying mapping F is co-coercive, a condition that is a little stronger than pseudo-monotone but is still weaker than those required by the basic projection neural network, we prove the exponential stability and global convergence of the improved model. We also reported some computational results, which illustrated that the new method is more efficient than that of Friesz et al. [3].

Since the appearance of the Barzilai–Borwein (BB) step sizes strategy for unconstrained optimization problems, it received more and more attention of the researchers. It was applied in various fields of the nonlinear optimization problems and recently was also extended to optimization problems with bound constraints. In this paper, we further extend the BB step sizes to more general variational inequality (VI) problems, i.e., we adopt them in projection methods. Under the condition that the underlying mapping of the VI problem is strongly monotone and Lipschitz continuous and the modulus of strong monotonicity and the Lipschitz constant satisfy some further conditions, we establish the global convergence of the projection methods with BB step sizes. A series of numerical examples are presented, which demonstrate that the proposed methods are convergent under mild conditions, and are more efficient than some classical projection-like methods.

The alternating direction methods are attractive for solving separable variational inequality problems, which solve the original large-scale problems via solving a series of small-scale problems. However, the two subproblems solved per iteration are still variational inequality problems, which are structurally as difficult to solve as the original problems. In this paper, we propose a new alternating direction method, which, per iteration, solves a variational inequality problem and a system of nonlinear equations. The nonlinear equation is wellconditioned and many efficient methods, such as Newton-type methods, can be adopted directly to solve it. Moreover, from numerical point of view, nonlinear equations are much easier to solve than variational inequality problems in many cases. Under the same mild assumptions as those in classical alternating direction methods, we prove global convergence of the new method. We also present some preliminary numerical results, which show that our method is efficient.

The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his payoff function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of Zhang et al. (2010) .

We derive new bounds for the price of anarchy under nonlinear and asymmetric costs. The bounds depend on an additional factor called the intrinsic cost of the system and therefore tend to be more accurate than the current bounds that are dependent only on the degree of asymmetry of the Jacobian and the degree of the nonlinearity of the cost function.

In signal processing, data analysis and scientific computing, one often encounters the problem of decomposing a tensor into a sum of contributions. To solve such problems, both the search direction and the step size are two crucial elements in numerical algorithms, such as alternating least squares algorithm (ALS). Owing to the nonlinearity of the problem, the often used linear search direction is not always powerful enough. In this paper, we propose two higher-order search directions. The first one, geometric search direction, is constructed via a combination of two successive linear directions. The second one, algebraic search direction, is constructed via a quadratic approximation of three successive iterates. Then, in an enhanced line search along these directions, the optimal complex step size contains two arguments: modulus and phase. A current strategy is ELSCS that finds these two arguments alternately. So it may suffer from a local optimum. We broach a direct method, which determines these two arguments simultaneously, so as to obtain the global optimum. Finally, numerical comparisons on various search direction and step size schemes are reported in the context of blind separation-equalization of convolutive DS-CDMA mixtures. The results show that the new search directions have greatly improve the efficiency of ALS and the new step size strategy is competitive.

We propose a new decomposition method for solving a class of monotone variational inequalities with linear constraints. The proposed method needs only to solve a well-conditioned system of nonlinear equations, which is much easier than a variational inequality, the subproblem in the classic alternating direction methods. To make the method more flexible and practical, we solve the sub-problems approximately. We adopt a self-adaptive rule to adjust the parameter, which can improve the numerical performance of the algorithm. Under mild conditions, the underlying mapping be monotone and the solution set of the problem be nonempty, we prove the global convergence of the proposed algorithm. Finally, we report some preliminary computational results, which demonstrate the promising performance of the new algorithm.

The multiple-sets split feasibility problem (MSFP) captures various applications arising in many areas. Recently, by introducing a function measuring the proximity to the involved sets, Censor et al. proposed to solve the MSFP via minimizing the proximity function, and they developed a class of simultaneous methods to solve the resulting constrained optimization model numerically. In this paper, by combining the ideas of the proximity function and the operator splitting methods, we propose an efficient simultaneous method for solving the constrained MSFP. The efficiency of the new method is illustrated by some numerical experiments.

Road space rationing based on vehicle plate numbers restricts vehicle access to a network based upon the license number on pre-established days. It has been used in some large cities especially when there are some major events. This paper analyzes the efficiency of road space rationing schemes by establishing the bounds of the reduction in the system cost associated with the restricted flow pattern at user equilibrium in comparison with the system cost at the original user equilibrium. The bounds are established under the general traffic equilibrium model formulated as variational inequalities and illustrated with a simple example.

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 [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.

This paper enhances a trial-and-error implementation scheme of marginal-cost pricing on a transportation network, in the absence of explicit expression of the demand function. Link tolls and link flows are updated for the next trial with the revealed link flows for given current trial toll pattern. The method is quite simple, requiring only some function evaluations. Also, the step size is not required to be square summable, thereby leading to the improvement of the efficiency of the algorithm. The global convergence of the method is proved and some numerical results are reported to illustrate its performance.

In a class of variational inequality problems arising frequently from applications, the underlying mappings have no explicit expression, which make the subproblems involved in most numerical methods for solving them difficult to implement. In this paper, we propose a generalized proximal-point-based prediction-correction method for solving such problems. At each iteration, we first find a prediction point, which only needs several function evaluations; then using the information from the prediction, we update the iteration. Under mild conditions, we prove the global convergence of the method. The preliminary numerical results illustrate the simplicity and effectiveness of the method.

We derive several bounds for the price of anarchy of the noncooperative congestion games with elastic demands and asymmetric linear or nonlinear cost functions. The bounds established depend on a constant from the cost functions as well as the ratio between user benefit and social surplus at Nash equilibrium. The results can be viewed a generalization of that of Chau and Sim [C.K. Chau, K.M. Sim, The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands, Operations Research Letters 31 (2003) 327–334] for the symmetric case, or a generalization of Perakis [G. Perakis, The price of anarchy when costs are nonseparable and asymmetric, Lecture Notes in Computer Science 3064 (2004) 46–58] to the elastic demand.

In this paper, we propose a new operator splitting method for solving a class of variational inequality problems in which part of the underlying mappings are unknown. This class of problems arises frequently from engineering, economics and transportation equilibrium problems. At each iteration, by using the information observed from the system, the method solves a system of nonlinear equations, which is well-defined. Under mild assumptions, the global convergence of the method is proved, and its efficiency is demonstrated with numerical examples.

In this paper, we propose a hybrid nonlinear decomposition–projection method for solving a class of monotone variational inequality problems. The algorithm utilizes the problems’ structure conductive to decomposition and a projection step to get the next iterate. To make the method more practical, we allow solving of the subproblems approximately and adopt the constructive accuracy criterion developed recently by Solodov and Svaiter for classical proximal point algorithm and by the author for generalized proximal point algorithm. The Fejér monotonicity to the solution set of the problem is obtained by only assuming the underlying mapping is monotone and the solution set is nonempty. The parameter is allowed to vary in a larger interval than that of Auslender and Teboulle, and we also propose some improved self-adaptive strategies to choose the sequence of parameters, which makes the algorithm more flexible.