[home] - [up] |

Lectures and Colloquia during the semester

Technische Universität Berlin

Straße des 17. Juni 136, 10623 Berlin

Math building - Room MA 042 - map -

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

[home] - [up] - [top]