| [home] - [up] |
Abstract: In this talk the analysis of Lüthi and Büeler to solve variational inequalities will be extended to the case of approximate analytic centers, turning the previous conceptual algorithm into a practical algorithm. For strongly monotone variational inequality problems (VIP) convergence of an algorithm is investigated which, at each iteration k, adds a quadratic cut through an approximate analytic center x_k of the subsequently shrinking convex body. First it is shown that the sequence of x_k converges to the unique solution x* of the VIP at O(1/sqrt{k}).
Secondly we show that the arithmetic complexity to update from x_k to x_(k+1) after inserting a quadratic cut through x_k is bounded by a constant number of Newton iterations plus O(n \cdot ln ln[zeta \cdot k^2 / epsilon^4]), where n is the space-dimension, epsilon is the final solution accuracy ||x_k-x*||, and zeta depends on some problem-specific constants only. We want to point to the parallel work of Nesterov, Péton and Vial where a homogeneous analytic center cutting plane method (HACCPM) with approximate centers is analyzed. Due to the construction of their iterates by using a weighted average of analytic centers, the final accuracy determines the accuracy of all previous approximate centers. In our analysis we can avoid this severe restriction. As a disadvantage of our quadratic cuts, however, we have to accept an increase in the computational complexity for updating the analytic center when the iteration number grows. In case of HACCPM linearity of the cuts allows to keep the update complexity constant.
Finally, we show the application of the method for computing equilibria prices of CO_2-permits in an international trade.
Colloquium - 16:00
Abstract: More and more cars get equipped with route guidance systems, which guide the driver to the destination entered at the beginning of the journey. Simulations predict that the benefits of such systems, which simply compute shortest paths, will be lost once the number of equipped vehicles exceeds a certain threshhold. Thus a more sophisticated approach is needed.
One way is to model traffic as a network flow. The travel time along an arc is then assumed to be a monotonically inreasing function of the total flow on that arc. Arc capacities are used to bound the amount of arc flow. Given the starting points and destinations of the drivers, the goal is to meet all the requests while minimizing total travel time in the network. This leads to a minimum cost multicommodity flow problem. Unfortunately, static network flows do not capture traffic behaviour very well, instead we need to consider dynamic flows which "move" through the network with progressing time.
In this talk, I will introduce the concept of dynamic network flows, which relate to static network flows in a time-expanded graph. The concept of dynamic flows will then be extended to get a more realistic model describing traffic. More precisely, I will define the so-called "fan-graph". This graph captures both, flow-dependent travel times and the notion of dynamic flows. I will present some first results, among them some complexity proofs and an approximation for the single source - single sink case with geometrically increasing capacities.