Department of Mathematics

Search

Optimization seminar

×

Modal title

Modal content

Spring Semester 2015

Date / Time Speaker Title Location
2 March 2015
16:30-17:30 		Matthias Claus
Universität Duisburg-Essen, Germany
Event Details

Optimization Seminar

Title On Continuity and Distribution Sensitivity of Stochastic Programs with Risk Aversion
Speaker, Affiliation Matthias Claus, Universität Duisburg-Essen, Germany
Date, Time 2 March 2015, 16:30-17:30
Location HG G 19.1
Abstract Measuring and managing risk has become crucial in modern decision making under stochastic uncertainty. For classes of stochastic programming models with mean-risk objectives and with stochastic dominance constraints we discuss structural properties and put them into perspective with their stability behavior with respect to perturbation of the underlying probability measure, sometimes called distribution sensitivity. The first part of the talk is devoted to a unified presentation of stochastic-programming related risk measures and their continuity with respect to suitable weak topologies. With atomless probability measures, this allows to extend known stability results for two-stage stochastic programs to models with mixed-integer convex recourse and quadratic integer recourse, respectively. In the second part we turn our attention to minimizing a disutility function under first-order stochastic dominance constraints. For stochastic programs with linear recourse, this leads to an optimization problem with uncountably many chance constraints. Metric regularity of the resulting constraint function is the key to stability of the solution set mapping. We focus the discussion at verifiable sufficient conditions based on local linear growth.
On Continuity and Distribution Sensitivity of Stochastic Programs with Risk Aversionread_more
HG G 19.1
9 March 2015
16:30-17:30 		Prof. Dr. Pierre Cardaliaguet
Université Paris-Dauphine, Paris, France
Event Details

Optimization Seminar

Title The Master Equation in Mean Field Games
Speaker, Affiliation Prof. Dr. Pierre Cardaliaguet, Université Paris-Dauphine, Paris, France
Date, Time 9 March 2015, 16:30-17:30
Location HG G 19.1
Abstract In this joint work with François Delarue, we investigate the so-called "Master equation" in mean field game theory. Mean Field Games is a developing area which allows to model the dynamics of large number of agents. In this setting, the solution of the master equation has been conjectured to describe the general behavior of these agents. We show here that the master equation is well-posed and can be obtained as the limit of Nash equilibria of differential games when the number of players tends to infinity.
The Master Equation in Mean Field Gamesread_more (CANCELLED)
HG G 19.1
16 March 2015
16:30-17:30 		Prof. Dr. Marco Molinaro
TU Delft, Netherlands
Event Details

Optimization Seminar

Title How Good Are Sparse Cutting-Planes?
Speaker, Affiliation Prof. Dr. Marco Molinaro, TU Delft, Netherlands
Date, Time 16 March 2015, 16:30-17:30
Location HG G 19.1
Abstract Sparse cutting-planes are often the ones used in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope P (e.g. the integer hull of a MIP), let Pk be its best approximation using cuts with at most k non-zero coefficients. In our first result, we present general upper bounds on how well Pk approximates P that depend on the number of vertices in the polytope and exhibits three phases as k increases. Our bounds imply that if P has polynomially many vertices, using half sparsity already approximates it very well. Second, we present a lower bound for random polytopes that show that the upper bounds are quite tight. Third, we show that for a class of hard packing IPs, sparse cutting-planes do not approximate the integer hull well. Finally, we show that using sparse cutting-planes in extended formulations is at least as good as using them in the original polyhedron, and give an example where the former is actually much better. Joint work with Santanu Dey and Qianyi Wang.
How Good Are Sparse Cutting-Planes?read_more
HG G 19.1
23 March 2015
16:30-17:30 		Dr. Andreas Wiese
Max-Planck-Institut für Informatik, Saarbrücken, Germany
Event Details

Optimization Seminar

Title Approximation schemes for maximum weight independent set of geometric objects
Speaker, Affiliation Dr. Andreas Wiese, Max-Planck-Institut für Informatik, Saarbrücken, Germany
Date, Time 23 March 2015, 16:30-17:30
Location HG G 19.1
Abstract In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g., in data mining, map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1+ε) approximation algorithm for the MWISR problem with quasi-polynomial running time 2^poly(log n/ε). In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(loglogn) (unweighted case) and O(logn/loglogn) (weighted case). Key to our result is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. Finally, I will give an overview of recent follow-up work, in particular a generalization of the above result to arbitrary polygons. (joint work with Anna Adamaszek)
Approximation schemes for maximum weight independent set of geometric objectsread_more
HG G 19.1
30 March 2015
16:30-17:30 		Dr. Panos Parpas
Imperial College London, London, United Kingdom
Event Details

Optimization Seminar

Title Multiresolution Optimisation Algorithms: Theory and Applications
Speaker, Affiliation Dr. Panos Parpas, Imperial College London, London, United Kingdom
Date, Time 30 March 2015, 16:30-17:30
Location HG G 19.1
Abstract Multiresolution optimisation algorithms are applicable when the underlying optimisation model can be modelled using varying levels of fidelity. Typical examples include optimisation of systems governed by differential equations in computer vision and optimal control, the number of features in machine learning applications, the number of states in a Markov Decision Processes, and so on. Indeed anytime a finite dimensional optimisation model arises from an infinite dimensional model it is straightforward to define such a hierarchy of optimisation models. In this talk we discuss how to take advantage of the availability of a hierarchy of models in a consistent manner. We posit that when the so called approximation property does not hold then the best one can hope for is to match the complexity of the single resolution algorithm. However, when additional assumptions can be made about the relationship between the coarse and fine models it is possible to improve the complexity of the optimisation algorithm. We illustrate our points by developing a multiresolution proximal point algorithm for non-smooth optimisation and a multiresolution value iteration algorithm for Markov Decision Processes. We establish the worst case complexity of the proposed methods and compare them with the state-of-the-art in terms of theoretical convergence guarantees and numerical performance.
Multiresolution Optimisation Algorithms: Theory and Applicationsread_more
HG G 19.1
20 April 2015
16:30-17:30 		Prof. Dr. Fredi Tröltzsch
Technische Universität Berlin, Berlin, Germany
Event Details

Optimization Seminar

Title Optimal and Feedback Control of wave-type solutions of reaction-diffusion equations
Speaker, Affiliation Prof. Dr. Fredi Tröltzsch, Technische Universität Berlin, Berlin, Germany
Date, Time 20 April 2015, 16:30-17:30
Location HG G 19.1
Abstract Wave type solutions are characteristic for some nonlinear parabolic reaction diffusion equations. For instance, traveling wave fronts solve the Schlögl model (also known as Nagumo equation), while spiral waves are solutions to the FitzHugh-Nagumo equations. In the first part, the talk surveys results on associated optimal control problems. In particular, theory and numerical application of sparse optimal controls are discussed. Here, the objective functional includes a non-differentiable convex part. Next, some results on feedback control are presented, where nonlocal feedback operators with timedelay have to be designed in an optimal way. The theory will be illustrated by various numerical examples.
Optimal and Feedback Control of wave-type solutions of reaction-diffusion equationsread_more
HG G 19.1
27 April 2015
16:30-17:30 		Prof. Dr. Jens Vygen
Universität Bonn, Bonn, Germany
Event Details

Optimization Seminar

Title Reassembling Trees for the Traveling Salesman
Speaker, Affiliation Prof. Dr. Jens Vygen, Universität Bonn, Bonn, Germany
Date, Time 27 April 2015, 16:30-17:30
Location HG G 19.1
Abstract Many recent approximation algorithms for different variants of the traveling salesman problem (asymmetric TSP, graph TSP, s-t-path TSP) exploit the well-known fact that a solution of the natural linear programming relaxation can be written as convex combination of spanning trees. The main argument then is that randomly sampling a tree from such a distribution and then completing the tree to a tour at minimum cost yields a better approximation guarantee than simply taking a minimum cost spanning tree (as in Christofides' algorithm). We argue that an additional step can help: reassembling the spanning trees before sampling. Exchanging two edges in a pair of spanning trees can improve their properties under certain conditions. We demonstrate the usefulness for the metric s-t-path TSP by devising a deterministic polynomial-time algorithm that improves on Sebő’s previously best approximation ratio of 8/5.
Reassembling Trees for the Traveling Salesmanread_more
HG G 19.1
4 May 2015
16:30-17:30 		Prof. Dr. Daniel Robinson
Johns Hopkins University, Baltimore, USA
Event Details

Optimization Seminar

Title Globalizing Local Methods
Speaker, Affiliation Prof. Dr. Daniel Robinson, Johns Hopkins University, Baltimore, USA
Date, Time 4 May 2015, 16:30-17:30
Location HG G 43
Abstract I present recent work in the development of robust algorithms for continuous nonlinear constrained optimization. Specifically, I give an overview of the key ideas that underpin a new active-set method and a new interior-point method. Both algorithms are motivated by iterative schemes that have strong local convergence properties, but have lacked a mechanism to ensure convergence to a meaningful point when started from an arbitrary initial guess. Importantly, both algorithms asymptotically reduce to the desired local methods.
Globalizing Local Methodsread_more
HG G 43
11 May 2015
16:30-17:30 		Dr. David Adjiashvili
Institute for Operations Research, ETH Zurich
Event Details

Optimization Seminar

Title Non-Uniform Robust Network Design in Planar Graphs
Speaker, Affiliation Dr. David Adjiashvili, Institute for Operations Research, ETH Zurich
Date, Time 11 May 2015, 16:30-17:30
Location HG G 19.1
Abstract Robust optimization is concerned with constructing solutions that remain feasible also when a limited number of resources is removed from the solution. Most studies of robust combinatorial optimization to date made the assumption that every resource is equally vulnerable, and that the set of scenarios is implicitly given by a single budget constraint. This talk is concerned with a robustness model of a different kind. We focus on Bulk-Robustness, a model recently introduced for addressing the need to model non-uniform failure patterns in systems. We start by motivating the model and presenting a number of applications. We then describe an algorithmic framework for approximating bulk-robust network design problems in planar graphs. Our techniques use an augmentation framework, combined with linear programming (LP) rounding that depends on a planar embedding of the input graph. A connection to cut covering problems and the dominating set problem in circle graphs is established. Our methods use few of the specifics of bulk-robust optimization, hence it is conceivable that they can be adapted to solve other robust network design problems.
Non-Uniform Robust Network Design in Planar Graphsread_more
HG G 19.1
18 May 2015
16:30-17:30 		Dr. Marc Deisenroth
Imperial College London, London, United Kingdom
Event Details

Optimization Seminar

Title Statistical Machine Learning for Autonomous Systems and Robots
Speaker, Affiliation Dr. Marc Deisenroth, Imperial College London, London, United Kingdom
Date, Time 18 May 2015, 16:30-17:30
Location HG G 19.1
Abstract Statistical machine learning has been a promising direction in control and robotics for more than a decade since learning models and controllers from data allows us to reduce the amount of engineering knowledge that is otherwise required. In real systems, such as robots, many experiments, which are often required for machine learning and reinforcement learning methods, can be impractical and time consuming. To address this problem, current learning approaches typically require task-specific knowledge in form of expert demonstrations, pre-shaped policies, or the underlying dynamics. In the first part of the talk, I follow a different approach and speed up learning by efficiently extracting information from sparse data. In particular, I propose to learn a probabilistic, non-parametric Gaussian process dynamics model. By explicitly incorporating model uncertainty in long-term planning and controller learning my approach reduces the effects of model errors, a key problem in model-based learning. Compared to state-of-the art reinforcement learning my model-based policy search method achieves an unprecedented speed of learning. I demonstrate its applicability to autonomous learning from scratch in real robot and control tasks. In the second part of my talk, I will discuss an alternative method for learning controllers for bipedal locomotion based on Bayesian Optimization, where it is hard to learn models of the underlying dynamics due to ground contacts. Using Bayesian optimization, we sidestep this modeling issue and directly optimize the controller parameters without the need of modeling the robot's dynamics. If time permits, in the third part of my talk, I will discuss state estimation in dynamical systems (filtering and smoothing) from a machine learning perspective. I will present a unifying view on Bayesian latent-state estimation, which allows both to re-derive common filters (e.g., the Kalman filter) and devise novel smoothing algorithms in dynamical systems. I will demonstrate the applicability of this approach to intention inference in robot table tennis.
Statistical Machine Learning for Autonomous Systems and Robotsread_more
HG G 19.1

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

Organizers: Diethard Klatte, John Lygeros, Manfred Morari, Karl Schmedders, Roy Smith, Robert Weismantel, Rico Zenklusen

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