Researches On Splitting Methods For Optimization Problems And The Morning Peak-period Congestion Problems

Convex Programming and Variational Inequality (VI) problems provide a unified and general framework for a wide class of problems arising from mathematics, man-agement science, economics and some other research fields. As the increasingly close relationship between disciplines, more and more problems can be characterized as a convex optimization problem or a VI problem. With the era of big data coming, more and more information are involved in the practical problems resulting in much larger problems. Therefore, it is very necessary and urgent to design some fast numerical algorithms for these problems, which is of great practical significance. At present, a large number of iterative algorithms have been proposed to solve the numerical so-lution of variational inequality problems. Some classical methods include: proximal point algorithm, alternating direction method of multipliers, projection method, split-ting method, Newton method and so on.The aim of this work is to present some new numerical methods for solving varia-tional inequality problems, such as forward-backward splitting method, alternating di-rection method of multipliers, alternating linearization method and projection method,and then apply them to solve complementarity problems, traffic network equilibrium problems, image restoration problems, compressive sensing problems, signal recovery problems and the problem of the projection onto ellipsoid. Compared with the existing algorithms, the new numerical methods can solve these problems better. In addition,this paper also carries on some research on the traffic congestion in the morning peak hours, and provides some reasonable suggestions for managers, which make the total system travel time cost attain minimal.Splitting methods solve the original variational inequality problems by solving a series of well-posed subproblems. However, the selection range of the parameter,which plays the role of step-size in the algorithm, has great influence on the efficien-cy of the algorithm. With a simple relaxation step, the convergence of the forward-backward method can be guaranteed for the range of the parameter being enlarged doubly; Meanwhile, we allow the inaccurate evaluation of the subproblem in each iteration, which greatly improves the efficiency and practicability of the algorithm.Alternating direction method of multipliers (ADMM) is simple and fast for solv-ing the separable convex optimization problems. Recently, we apply ADMM to solve the projection problem on the ellipsoid, and find the high efficiency of it, comparing with the algorithms of Dai [27]. Further, we have also made an appropriate modi-fication to the existing symmetric alternating direction method (i.e., the alternating linearization method). A new proximal alternating linearization method is proposed,which can solve some more general separable convex optimization problems. Final-ly, it should be noted that, when the objective function is the sum of three or more individual functions without crossed variables, the direct ADMM can not guarantee the convergence under the convexity. Han and Yuan [54] gave the proof of conver-gence under strong convexity. We weaken the convergence conditions properly and show that when the objective function is the sum of three or more separable composite functions (the composite of strong convex and linear functions), the convergence can be given, and this model is corresponded to an example in traffic.The projection algorithm, whose computational amount in each iteration is s-mall, is quite suitable for solving large-scale problems. This algorithm only needs to deal with the projection onto the feasible set and the calculation of the function val-ues. However, the convergence conditions of the existing algorithms are harsh, how to weaken the condition is the work we need to do. Based on the projected steepest descent method proposed by Teschke and Borries, we propose an efficient projection algorithm for the nonlinear inverse problem in signal recovery, and give the conver-gence proof under weaker condition. The selection range of parameter which plays the role of step-size is relaxed, and the select manner of it is also modified. All these improve the applicability and efficiency of the algorithm.Traffic congestion in the morning peak hours has been one of the most challeng-ing problems faced by many modern cities in the world. Road pricing is an effective and feasible means to alleviate traffic congestion. However, most of the current charg-ing models are aimed at the individual traveling in the network, however, in many Asian cities, a new kind of traveling way appears, i.e., household travels. The study of this new way of travel is still in its infancy. Based on the existing results of departure rate of individual travelers under the equilibrium, we analyze the departure rate of the household travelers quantitatively, and propose reasonable measures on the setting of the school-work start time, charging windows and fees for managers to minimize the total system travel cost. Finally, replacing such a charging model by the tradable credit model, we can reduce the time cost of each household in the network simultaneously.