Iterate averaging methods for solving non-linear programming problems

Abstract

Traffic congestion is an unresolved problem and it has effects not only to the transportation system, but also on other aspects of life (economic, spatial and social). The idea is that 'Road Pricing' can be used to solve this problem. There is a need for an appropriate tool for predicting the effects of 'Road Pricing'. Such a tool could be a traffic assignment model. Traffic is by nature dynamic and hence only dynamic models can describe traffic process adequately. It appears, however, that iterate averaging methods have not yet been applied to transportation network problems. In this research iterate averaging methods are investigated and also the possibility of applying these methods in transportation network problems. Recently the Polyak method was introduced, which is supposed to have better convergence qualities than the method that is normally used, the Method of Successive Averages (MSA). The three topics of this research of iterate averaging methods are: • To find out how the Polyak method works, after which the Polyak method is implemented. • To find out if the Polyak method indeed converges faster than MSA. • To find out if there exist alternative methods that are faster in convergence than the Polyak method and MSA. To find answers on these three topics the literature was studied. By reading the nature of the Polyak method is found out. When the Polyak method is understood, the method is implemented (and also MSA is implemented). That was needed for analysing the convergence of the methods. After the Polyak method is implemented research for alternative methods is done. Finally, all the described methods are compared and illustrations are given. In order to satisfy the increasing demand for more accurate model outcomes and to be able to compute the effects of different traffic policies, new and improved traffic assignment models are needed. While Static Traffic Assignment models may provide basic insights, only dynamic assignment models are able capture the true dynamic nature of traffic and therefore provide the analyst with more accurate forecast. An iterative process is needed to solve the Dynamic Traffic Assignment (DTA) model. This is because network conditions may change after performing network loading. At all the iterations, the path flows are updated by combining the results from the current iteration with the previous iteration. The 'classical' (e.g., derivative-based) fixed-point solution methods are often inappropriate for some problems. In such cases, the fixed-points are usually computed using one of the iterate averaging methods introduced by Robbins and Monro [3.1]. MSA, introduced by Sheffi and Powell [3.2], is probably the best­ known and most widely-used instance of iterate averaging methods. In iterate averaging methods estimates for the fixed-point are found. These estimates are called design points. MSA computes each new design point by adding a part of the observation evaluated in the previous design point with a part of the previous design point. MSA has the advantages of avoiding (potentially expensive) step size calculations, working directly with map outputs without requiring derivative calculations or other transformations, and being able to handle 'noisy' map evaluations (where the evaluation returns a value affected by a zero-mean disturbance). Other advantages of MSA are that it is simple to understand and that it is simple to implement. In many cases, however, the method's empirically observed convergence properties are disappointing: while it exhibits generally effective performance in the initial iterations, this is followed by a pronounced 'tail' effect, resulting in overall slow convergence. Approximately ten years ago, B.T. Polyak and J.A. Bather proposed two relatively minor modifications of iterate averaging methods which were rigorously shown to produce fixed-point estimates with asymptotically optimal properties. The Polyak method is a two-pass method. The first pass resembles MSA except that the step sizes are larger; this allows the algorithm to explore the solution space more aggressively but leads to greater variability in the outputs. The second pass is carried out offline (i.e., without influencing the first pass); it calculates an average of iterates that are generated by the first pass. The average calculated by the second pass at termination is the fixed-point solution estimate. A somewhat different approach was proposed by J.A. Bather. Here, the design point is derived from a combination of the average of previous design points with the average of previous evaluation results. Apart from the Polyak method and the Bather method, alternative methods are proposed. In total eight methods are applied and presented in this report. They were all compared with different stop criterions. MSA and the Polyak method were compared. To compare these methods and to compare also other methods a traffic problem with three cities and two routes is considered. This traffic problem is solved by using a DTA algorithm. For stopping this DTA algorithm there are different stop criteria. The stop criterion that is a combination of the route costs and flows is the best stop criterion for stopping the DTA algorithm. This stop criterion is reached after 190 iterations of MSA and after 226 iterations of the Polyak method. The conclusion is that MSA is faster in convergence than the Polyak method for this stop criterion. The Bather method, the Bliemer method and the Bliemer Moving method were compared. After 118 iterations of the Bather method, after 112 iterations of the Bliemer method and after 40 iterations of the Bliemer Moving method the stop criterion is reached. It can be concluded that the Bather method and the Bliemer method solve the problem in almost the same number of iterations. For different stop criterions the Bliemer Moving method much faster than is the four other methods. The Bliemer Moving method is the fastest method, but by combining two methods it's possible to get a method that is even faster in convergence than the methods shown before. Therefore, the MSA-Biiemer method, the MSA-Bather method and the Bliemer-Bather method are compared. The fastest method in convergence, for the stop criterion we chose, is the Bliemer-Bather method. The conclusion is that there are alternative methods that are much faster in convergence than the Method of Successive Averages and the Polyak method. The best alternative methods are the MSA-Bather method and the Bliemer-Bather method. The recommendation is to use the Bliemer-Bather method for solving Non­ Linear Programming (NLP) problems in transportation networks and to do further research how the values of the variables used in the Bliemer-Bather method have to be chosen.