Institute for Operations Research

Search

en

Optimization Seminar

×

Modal title

Modal content

Spring Semester 2014

Date / Time Speaker Title Location
17 February 2014
16:30-18:00 		Prof. Dr. Vassili Kolokoltsov
University of Warwick
Event Details

Optimization Seminar

Title Inspection games: evolutionary and mean-field game perspectives.
Speaker, Affiliation Prof. Dr. Vassili Kolokoltsov, University of Warwick
Date, Time 17 February 2014, 16:30-18:00
Location HG G 19.1
Abstract The inspection games is the well studied class of games with the variety of application from nuclear arms control to tax collection regulation. For the first time we suggest new perspectives for this class of games arising, roughly speaking, from the consideration of the limit of the large number of players. We consider two frameworks: evolutionary games and mean-field games, both getting a new twist in this context.
Inspection games: evolutionary and mean-field game perspectives.read_more
HG G 19.1
3 March 2014
16:30-18:00 		Prof. Dr. Jean Bernard Lasserre
LAAS-CNRS, Toulouse
Event Details

Optimization Seminar

Title The moment-LP and moment-SOS approach in Optimization
Speaker, Affiliation Prof. Dr. Jean Bernard Lasserre, LAAS-CNRS, Toulouse
Date, Time 3 March 2014, 16:30-18:00
Location HG G 19.1
Abstract We review and compare basic properties of the moment-LP and moment-SOS hierarchies for polynomial optimization problems P: min {f(x): x in K} where "f" is a polynomial and "K" is a compact basic semi-algebraic set. Thanks to powerful positivity certificates from real algebraic geometry, both approaches provide a sequence of lower bounds which converge to the global minimum of P: We also describe an alternative hierarchy based on a different characterization of nonnegativity on K which now yields a sequence of upper bounds that converges to the global minimum of P (provided that the (non necessarily compact) set K is such that one may compute moments of a measure whose support is exactly K).
The moment-LP and moment-SOS approach in Optimizationread_more
HG G 19.1
10 March 2014
16:30-18:00 		Prof. Dr. Dario Bauso
Università degli Studi di Palermo, Italy
Event Details

Optimization Seminar

Title Robust Mean-Field Games
Speaker, Affiliation Prof. Dr. Dario Bauso, Università degli Studi di Palermo, Italy
Date, Time 10 March 2014, 16:30-18:00
Location HG G 19.1
Abstract Within the realm of mean field games under uncertainty, we study a population of players with individual states driven by a standard Brownian motion and a disturbance term. The contribution is three-fold: First, we establish a mean field system for such robust games. Second, we analyze robust mean field equilibria. Third, we show that the dimension of the mean field system can be significantly reduced by considering a functional of the first moment of the mean field process. Applications to production, opinion dynamics and cyber-physical systems will be discussed. Jointly with Tamer Basar and Hamidou Tembine
Robust Mean-Field Gamesread_more
HG G 19.1
31 March 2014
16:30-18:00 		Prof. Dr. Daniel Kuhn
EPF Lausanne
Event Details

Optimization Seminar

Title Interdiction Games on Markovian PERT Networks
Speaker, Affiliation Prof. Dr. Daniel Kuhn, EPF Lausanne
Date, Time 31 March 2014, 16:30-18:00
Location HG G 19.1
Abstract In a stochastic interdiction game a proliferator aims to minimize the expected duration of a nuclear weapons development project, while an interdictor endeavors to maximize the project duration by delaying some of the project tasks. We formulate static and dynamic versions of the interdictor's decision problem where the interdiction plan is either pre-committed or adapts to new information revealed over time, respectively. The static model gives rise to a stochastic program, while the dynamic model is formalized as a multiple optimal stopping problem in continuous time and with decision-dependent information. Under a Markov assumption, we prove that the static model reduces to a mixed integer linear program, while the dynamic model reduces to a finite Markov decision process in discrete time that can be solved via efficient value iteration. We then generalize the dynamic model to account for uncertainty in the outcomes of the interdiction actions. We also discuss a crashing game where the proliferator can use limited resources to expedite tasks so as to counterbalance the interdictor's efforts. The resulting problem can be formulated as a robust Markov decision process.
Interdiction Games on Markovian PERT Networksread_more
HG G 19.1
7 April 2014
16:30-18:00 		Prof. Dr. Ola Svensson
EPF Lausanne
Event Details

Optimization Seminar

Title LP-Based Algorithms For Capacitated Facility Location
Speaker, Affiliation Prof. Dr. Ola Svensson, EPF Lausanne
Date, Time 7 April 2014, 16:30-18:00
Location HG G 19.1
Abstract Many of our best (approximation) algorithms for hard combinatorial optimization problems rely on linear programming relaxations. A typical example is the uncapacitated facility location problem. Starting with a natural linear programming relaxation of that problem, a sequence of algorithms exploiting and developing known techniques, such as primal-dual and randomized rounding, have refined our understanding of the problem and have resulted in close to optimal algorithms. For the more general capacitated facility location problem, the situation is drastically different as all proposed relaxations fail to give any reasonable guarantees on the value of an optimal solution. As a result, the vast amount of algorithmic tools based on LPs have not yet been applicable to the capacitated facility location problem. In fact, the only known algorithms with good performance guarantees are based on the local search paradigm. We overcome this difficulty by giving the first relaxation of the capacitated facility location with a constant performance guarantee. Informally, our relaxation is based on formulating the constraint that each client should be able to connect to an open facility even after fixing a partial assignment of clients. Our result opens up the possibility to approach the capacitated problem with known powerful LP based techniques and, as such techniques often are robust, we hope that further study will also lead to an increased understanding of other related capacitated problems. This is joint work with Hyung-Chan An and Mohit Singh.
LP-Based Algorithms For Capacitated Facility Locationread_more
HG G 19.1
14 April 2014
16:30-18:00 		Martin Seydenschwanz
Universität Jena
Event Details

Optimization Seminar

Title Discretization and Regularization of Linear-Quadratic Optimal Control Problems with Bang-Bang Solutions
Speaker, Affiliation Martin Seydenschwanz, Universität Jena
Date, Time 14 April 2014, 16:30-18:00
Location HG G 19.1
Abstract Optimal control theory is a powerful framework for modelling and solving application problems in technology, economy, biology and lots of other areas of science and industry. In this talk we will focus on a class of linear-quadratic control problems with ordinary differential equations and box constraints on the control. Especially we are interested in problems with discontinuous optimal controls, so called "bang-bang controls". Since these solutions generally cannot be determined analytically, one is highly interesed in numerical solving methods. Therefore we present different discretization methods and a combined regularization-discretization approach. Under generalized assumptions on the structure of the switching function we show convergence and prove corresponding error estimates. The theoretical findings will be illustrated by examples.
Discretization and Regularization of Linear-Quadratic Optimal Control Problems with Bang-Bang Solutionsread_more
HG G 19.1
5 May 2014
16:30-18:00 		Bart Van Parys
Automatic Control Laboratory, ETH Zürich
Event Details

Optimization Seminar

Title Generalized Gauss Inequalities via Semidefinite Programming
Speaker, Affiliation Bart Van Parys, Automatic Control Laboratory, ETH Zürich
Date, Time 5 May 2014, 16:30-18:00
Location HG G 19.1
Abstract A sharp upper bound on the probability of a random vector falling outside a polytope, based solely on the first and second moments of its distribution, can be computed efficiently using semidefinite programming. These bounds are widely used across many different application domains, ranging from distributionally robust optimization to chance-constrained programming, stochastic control, machine learning, signal processing, option pricing, portfolio selection and hedging. However, these Chebyshev-type bounds tend to be overly conservative since they are determined by a discrete worst-case distribution. In this talk we present a less pessimistic Gauss-type bound by imposing the additional requirement that the random vector's distribution must be unimodal. We show that this generalized Gauss bound still admits an exact and tractable semidefinite representation. Moreover, we demonstrate that both the Chebyshev and Gauss bounds can be obtained within a unified framework using a generalized notion of unimodality. We also offer new perspectives on the computational solution of generalized moment problems, since we used concepts from Choquet theory instead of traditional duality arguments to derive semidefinite representations for worst-case probability bounds.
Generalized Gauss Inequalities via Semidefinite Programmingread_more
HG G 19.1
12 May 2014
16:30-18:00 		Prof. Dr. Amitabh Basu
Johns Hopkins University, Baltimore, USA
Event Details

Optimization Seminar

Title A Unified Approach to Semi-Infinite Linear Programs with applications to Convex Optimization
Speaker, Affiliation Prof. Dr. Amitabh Basu, Johns Hopkins University, Baltimore, USA
Date, Time 12 May 2014, 16:30-18:00
Location HG G 19.1
Abstract We extend Fourier-Motzkin elimination to semi-infinite linear programs. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap. Our approach yields a new classification of variables that is used to determine the existence of duality gaps. Our approach has interesting applications in finite-dimensional convex optimization, such as completely new proofs of Slater's condition for strong duality.
A Unified Approach to Semi-Infinite Linear Programs with applications to Convex Optimizationread_more
HG G 19.1
19 May 2014
16:30-18:00 		Prof. Dr. Hector Ramirez Cabrera
Universidad de Chile, Santiago
Event Details

Optimization Seminar

Title On the Graphical Derivative of Solution Maps to Parameterized Equilibria with Conic Constraints
Speaker, Affiliation Prof. Dr. Hector Ramirez Cabrera, Universidad de Chile, Santiago
Date, Time 19 May 2014, 16:30-18:00
Location HG G 19.1
Abstract This presentation presents new calculations of the graphical derivative for the solution map to parameterized generalized equations/KKT systems associated with conic constraints. We first compute new second-order generalized di fferential constructions based on the graphical derivative of the normal cone mapping appearing in the KKT system. These computations were derived in [5] provided the feasible set appearing in the KKT system is convex. They provide verifi able conditions for isolated calmness of the corresponding solution map. Then, in [6], the application of a "dilatation" technique permitted to extend this computation to the non convex case. The latter requires, however, an additional condition of geometric nature imposed on the considered cone. This is related to the σ-term associated with projection onto this cone and has a local character (see [1, 2]). Under this condition our formula for the graphical derivative has the same form as the formula resulting from [8, Chapters 10 and 13] and so it can be viewed as its generalization to a class of nonpolyhedral cones. The main results obtained in this general conic programming setting are speci fied for and illustrated by the second-order cone programming.
On the Graphical Derivative of Solution Maps to Parameterized Equilibria with Conic Constraintsread_more
HG G 19.1
26 May 2014
16:30-18:00 		Prof. Dr. Samuel Fiorini
Université libre de Bruxelles, Belgien
Event Details

Optimization Seminar

Title Cut-dominant and forbidden minors
Speaker, Affiliation Prof. Dr. Samuel Fiorini, Université libre de Bruxelles, Belgien
Date, Time 26 May 2014, 16:30-18:00
Location HG G 19.1
Abstract The cut-dominant of a connected graph G is the polyhedron that corresponds to the problem of computing global min-cuts in G. Despite the fact that computing a global min-cut can be done in polynomial time, the geometry of the cut-dominant is far from being understood. We study graphs for which all facets of the corresponding cut-dominant have right-hand side at most a fixed integer k. These graphs form a minor-closed collection. We give a complete list of forbidden minors for k <= 2. This is then applied to the TSP to give shorter proofs of a classic result of Fonlupt and Naddef (Math. Prog., 1992) that characterizes TSP-perfect graphs. This work in progress is joint with Kanstantsin Pashkovich (Brussels) and Michele Conforti (Padova).
Cut-dominant and forbidden minorsread_more
HG G 19.1

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

Organizers: Bernd Gärtner, 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