Department of Mathematics

Search

Optimization seminar

×

Modal title

Modal content

Spring Semester 2010

Date / Time Speaker Title Location
1 March 2010
16:30-18:00 		Prof. Dr. Michael Jünger
University of Cologne, Germany
Event Details

Optimization Seminar

Title Crossing Minimization in Automatic Graph Drawing
Speaker, Affiliation Prof. Dr. Michael Jünger, University of Cologne, Germany
Date, Time 1 March 2010, 16:30-18:00
Location HG G 19.1
Abstract After a brief introduction to the field of Automatic Graph Drawing we stress the importance of crossing minimum representations of graphs on the plane. We then focus on two variants: Layered drawing of directed acyclic graphs and the general case. The first variant is motivated by a "classical" layered drawing style introduced by Sugiyama, Tagawa, and Toda in 1981. Initially, only heuristics were used for crossing minimization. Then it turned out that certain (NP-hard) special cases could be solved to optimality in reasonable computation time. By now, there are promising approaches to the exact solution of the general case. The general crossing minimization problem has a long and interesting history, starting in 1944 when Turan worked in a labor camp. This problem is notoriously hard. E.g., a minimum crossing drawing is not known for the complete graph on 13 vertices. There were no practical algorithms and therefore, no software, until recently. In both cases, we shall survey the development from the beginning to the state-of-the-art.
Crossing Minimization in Automatic Graph Drawingread_more
HG G 19.1
8 March 2010
16:30-18:00 		Kenneth L. Judd
Hoover Institution, Stanford University, USA
Event Details

Optimization Seminar

Title Computing Equilibria of Dynamic Games
Speaker, Affiliation Kenneth L. Judd, Hoover Institution, Stanford University, USA
Date, Time 8 March 2010, 16:30-18:00
Location HG G 19.1
Abstract The nature of repeated interaction has been extensively studied in the repeated game literature. Abreu, Pearce and Stacchetti, and Cronshaw and Lenberger characterized the set of Nash equilibria in repeated games by computing the set of present values of subgame perfect equilibrium strategies for each player. Judd, Yeltekin, and Conklin (2003) developed computational methods using convex geometry and linear programming for constructing approximations to those sets. Many interesting examples of strategic interaction arise in environments with state variables, and lead to dynamic games, not repeated games. We argue that the set of equilibrium values of subgame perfect equilibria in dynamic games is a finite collection of convex sets, one for each possible state. We construct a map that takes N convex sets and constructs N convex sets, show that the map is monotone under the subset partial ordering, and discuss computational methods for finding the largest fixed point. (Joint work with Sevin Yeltekin, Carnegie-Mellon University)
Computing Equilibria of Dynamic Gamesread_more
HG G 19.1
15 March 2010
16:30-18:00 		Johan Löfberg
Linköping University, Sweeden
Event Details

Optimization Seminar

Title Automatic Robust Convex Programming
Speaker, Affiliation Johan Löfberg, Linköping University, Sweeden
Date, Time 15 March 2010, 16:30-18:00
Location HG G 19.1
Abstract A considerable amount of optimization problems arising in the control and systems theory field can be seen as special instances of robust optimization. Much of the modeling effort in these cases is spent on converting an uncertain problem to a robust counterpart without uncertainty. Since many of these conversions follow standard procedures, it is amenable to software support. This talk presents the robust optimization framework in the modeling language YALMIP, which carries out the uncertainty elimination automatically and allows the user to concentrate on the high-level model instead.
Automatic Robust Convex Programmingread_more
HG G 19.1
22 March 2010
16:30-18:00 		Antonis Papachristodoulou
University of Oxford, UK
Event Details

Optimization Seminar

Title Nonlinear Systems Analysis using Convex Optimization
Speaker, Affiliation Antonis Papachristodoulou, University of Oxford, UK
Date, Time 22 March 2010, 16:30-18:00
Location HG G 19.1
Abstract The use of Linear Matrix Inequality and Semidefinite Programming techniques is very common in modern control systems analysis and design. At the same time, positive polynomials can help formulate a large number of problems in robust control, non-linear control and non-convex optimization - consider, for example, the use of Lyapunov functions for stability analysis of equilibria of nonlinear dynamical systems. The fact that polynomial positivity conditions can be formulated efficiently in terms of Linear Matrix Inequalities opens up new directions in nonlinear systems analysis and design. In this talk I will first present how ideas from dynamical systems, positive polynomials and convex optimization can be used to analyze the stability, robust stability, performance and robust performance of systems described by nonlinear ODEs. I will also discuss briefly how hybrid/switched systems and time-delay systems can be analyzed before describing how other, more interesting analysis questions can be answered using these tools. This approach for systems analysis, although entirely algorithmic, is currently not scalable to large system instances. To address this, I will first consider the analysis of large-scale networked systems and discuss how the system structure (both the dynamics at the nodes and the topology of the underlying network) can help generate robust functionality conditions that scale with the system size. I will finally talk about some of the most recent work on how to analyze "medium-sized" dynamical systems, combining ideas from graph partitioning and the theory of interconnected systems.
Nonlinear Systems Analysis using Convex Optimizationread_more
HG G 19.1
29 March 2010
16:30-18:00 		Danny Ralph
University of Cambridge, UK
Event Details

Optimization Seminar

Title Introduction to Mathematical Programs with Cone Complementarity Constraints
Speaker, Affiliation Danny Ralph, University of Cambridge, UK
Date, Time 29 March 2010, 16:30-18:00
Location HG G 19.1
Abstract Semidefinite programs (SPDs) - optimization problems involving symmetric positive semidefinite matrix variables - are well studied for instance in engineering control and structural mechanics. Mathematical programs with semidefinite complementarity constraints are nonconvex optimization problems arise, eg, as inverse problems when the forward model is an SDP. Analogous to standard mathematical programs with complementarity constraints, in which the variables are nonnegative & orthogonal vectors, the complementarity (orthogonality) constraint will be treated via a penalty in the objective function. The resulting problem is a nonlinear and nonconvex optimization problem with matrix (and vector) variables and constraints. We will present a simple form of the problem and analyse it's stationary conditions. Then we will use an application from structural optimization solve this numerically using the code PENNON. Co-author: Michal Kocvara, The University of Birmingham, School of Mathematics, kocvara@maths.bham.ac.uk
Introduction to Mathematical Programs with Cone Complementarity Constraintsread_more
HG G 19.1
12 April 2010
16:30-18:00 		Jan Heerda
Humboldt University Berlin, Germany
Event Details

Optimization Seminar

Title The exponent of Hoelder calmness for level sets of polynomials
Speaker, Affiliation Jan Heerda, Humboldt University Berlin, Germany
Date, Time 12 April 2010, 16:30-18:00
Location HG G 19.1
Abstract Since solutions of optimization problems may often only be found approximately, it is usefull to think about their (local) stability, i.e. to analyze the behaviour of the set of solutions under perturbations. In particular this plays a role in multilevel programs where one uses preliminary results to solve another problem. One tool for such analysis is the stability property called calmness, which can be generalized to some Hoelder type characteristic. Hoelder calmness of (nonempty) solution sets of inequality systems may be described in terms of (local) error bounds. In 1952 Hoffman showed that for (finite) systems of affine functions there is an error bound which yields calmness of the solution set. Using the Hoermander-Lojasiewicz inequality Luo/Luo and Luo/Pang gave a proof of Hoelder calmness for systems of polynomials and even analytic functions. But since the Hoermander-Lojasiewicz inequality is based on the Tarski-Seidenberg principle one only knows that there is an exponent for Hoelder calmness but cannot say more about it. Here we will show that for solution sets of one quadratic polynomial the exponent is one-half and give some ideas clarifying the correlation between the degree of the polynomials defining some set and the exponent of Hoelder calmness.
The exponent of Hoelder calmness for level sets of polynomialsread_more
HG G 19.1
26 April 2010
16:30-18:00 		Dirk Helbing
ETH Zürich, Switzerland
Event Details

Optimization Seminar

Title Self-Organization and Self-Optimization of Traffic Flows on Freeways and in Urban Networks
Speaker, Affiliation Dirk Helbing, ETH Zürich, Switzerland
Date, Time 26 April 2010, 16:30-18:00
Location HG G 19.1
Abstract The lecture introduces microscopic and macroscopic traffic flow models for freeway and urban traffic flow. Moreover, it discusses typical kinds of congestion phenomena and the underlying mechanisms producing them. Based on an understanding of breakdowns of free traffic flow, we propose new ways to support a fluid traffic operation. Through mechanism design, it is possible to specify local interactions between system elements in a way that gives rise to a high performance of traffic systems. In other words, we show how one can create order through self-organization and reach high efficiency on a systemic level without the need for central control.
Self-Organization and Self-Optimization of Traffic Flows on Freeways and in Urban Networksread_more
HG G 19.1
3 May 2010
16:30-18:00 		Tamas Szantai
Budapest University of Technology and Economics, Hungary
Event Details

Optimization Seminar

Title On Numerical Calculation of Probabilities According to Dirichlet Distribution
Speaker, Affiliation Tamas Szantai, Budapest University of Technology and Economics, Hungary
Date, Time 3 May 2010, 16:30-18:00
Location HG G 19.1
Abstract Dirichlet distribution is a continuous multivariate probability distribution having all beta one dimensional marginal distributions. Although it may have many interesting applications in statistics, inventory control, PERT modeling and stochastic programming, the numerical calculation of probability values according to this distribution became possible only in the last decade. In my talk I will give algorithms for the numerical calculation of the cumulative distribution function (c.d.f.) values of Dirichlet distribution. These algorithms use the so called Lauricella hypergeometric functions in low dimension and in higher dimensions they utilize the so called hyper-multitree bounds introduced by Jozsef Bukszar and variance reduction simulation procedures based on these bounds. There will be given formulae for the calculation of the first and second order partial derivatives, too. The common property of these formulae is that they involve only lower dimensional Dirichlet c. d. f. calculations. Some other multivariate distributions deriving from the Dirichlet distribution will also be mentioned. In the second part of my talk I will show how the Sequential Conditional Sampling (SCS) procedure works in the case of the Dirichlet distribution. On the base of this sampling technique one can apply importance sampling algorithms called Sequential conditional Importance Sampling (SCIS) for the estimation of extremely small c.d.f. values of the Dirichlet distribution. All results of this talk were achieved jointly with my earlier Egyptian PhD student Ashraf Gouda.
On Numerical Calculation of Probabilities According to Dirichlet Distributionread_more
HG G 19.1
10 May 2010
16:30-18:00 		Sven de Vries
University of Trier, Germany
Event Details

Optimization Seminar

Title Faster Separation of wheel inqualities for stable set polytopes
Speaker, Affiliation Sven de Vries, University of Trier, Germany
Date, Time 10 May 2010, 16:30-18:00
Location HG G 19.1
Abstract A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of finding a maximum weight stable set is one of the most basic NP-hard problems. An important approach to this problem is to formulate it as the problem of optimizing a linear function over the convex hull STAB(G) of incidence vectors of stable sets. Then one has to solve separation problems over it. Cheng and Cunningham (1997) introduced the wheel inequalities and presented an algorithm for their separation using time O(n4) for a graph with n vertices and m edges. We present a new separation algorithm running in O(mn2 + n3 log n).
Faster Separation of wheel inqualities for stable set polytopesread_more
HG G 19.1
17 May 2010
16:30-18:00 		Evanthia Papadopoulou
University of Lugano, Switzerland
Event Details

Optimization Seminar

Title Generalized Voronoi Diagrams, Geometric Min-Cuts, and VLSI Critical Area Extraction
Speaker, Affiliation Evanthia Papadopoulou, University of Lugano, Switzerland
Date, Time 17 May 2010, 16:30-18:00
Location HG G 19.1
Abstract The Voronoi diagram is a powerful mathematical object encoding nearest neighbor information with numerous applications in diverse areas. In this talk I will present work on generalized Voronoi diagrams such as the Hausdorff Voronoi diagram and higher order Voronoi diagrams of segments as motivated by the VLSI Critical Area extraction problem in VLSI designs. Critical Area is a measure reflecting the sensitivity of a VLSI design to random defects during the chip manufacturing process, and its extraction is essential for modern VLSI manufacturing especially when Design for Manufacturability (DFM) changes are under consideration. I will address the critical area extraction problem for various types of faults, such as shorts, open faults, via blocks, using generalized Voronoi diagrams. The talk will concentrate on open faults. To model open faults we formulate a geometric version of the classic min-cut problem in graphs, termed the geometric min-cut problem, and address it through variants of generalized Voronoi diagrams. The basis of this work has resulted in an IBM-Cadence CAD tool (Voronoi CAA) currently used extensively in production mode by IBM Microelectronics for critical area analysis and the prediction of yield.
Generalized Voronoi Diagrams, Geometric Min-Cuts, and VLSI Critical Area Extractionread_more
HG G 19.1
31 May 2010
16:30-18:00 		Prof. em. Dr. Halil Mete Soner
ETH Zurich, Switzerland
Event Details

Optimization Seminar

Title Liquidity affects in option pricing
Speaker, Affiliation Prof. em. Dr. Halil Mete Soner, ETH Zurich, Switzerland
Date, Time 31 May 2010, 16:30-18:00
Location HG G 19.1
Abstract Models of illiquid markets and investment and pricing problems in these models still are not well developed. Research in this area has focused on several different aspects. In one direction one studies the optimal strategies for the execution of large trades. In the second direction affects of a large trader on the price process is investigated. In a recent model of Cetin, Jarrow and Protter models the temporary price affects caused by a small investor in a phenomenological manner. This results in a tractable model which captures some of the stylized features of the markets. In this talk, I will outline this model and discuss the question of option pricing and hedging. I will also outline the properties of the Binomial approximation.
Liquidity affects in option pricingread_more
HG G 19.1

Note: if you want you can subscribe to the iCal/ics Calender.

Organizers: Komei Fukuda, Bernd Gärtner, Diethard Klatte, Hans-Jakob Lüthi, John Lygeros, János Mayer, Manfred Morari, Karl Schmedders

Archive: SS 22 SS 20 AS 19 SS 19 AS 18 SS 18 AS 17 SS 17 AS 16 SS 16 AS 15 SS 15 AS 14 SS 14 AS 13 SS 13 AS 12 SS 12 AS 11 SS 11 AS 10 SS 10 AS 09

JavaScript has been disabled in your browser