Department of Mathematics

Search

Optimization seminar

×

Modal title

Modal content

Autumn Semester 2013

Date / Time Speaker Title Location
23 September 2013
16:30-18:00 		Lilli Bergner
EPF, Lausanne, CH
Event Details

Optimization Seminar

Title Integrality Gap of Bin Packing
Speaker, Affiliation Lilli Bergner, EPF, Lausanne, CH
Date, Time 23 September 2013, 16:30-18:00
Location HG G 19.1
Abstract Bin packing is a problem from the field of combinatorial optimization in which a set of items with given sizes smaller than 1 is to be assigned to a minimum number of subsets, each of sum at most 1. It is an important open question to determine whether the integrality gap of the Gilmore-Gomory LP formulation of bin packing can be bounded by a small constant such as 2. A $O(\log^2 n)$ upper bound has been proven 30 years ago, however, numerous experiments suggest that even finding instances with gap equal to or slightly larger than 1 is very difficult. The presentation will focus on the algorithmic complexity of the problem of finding instances with large integrality gap. I show that this problem can be formulated as a bilevel integer linear program, thus conjecturing its $\Sigma_2$-hardness. Finally, I will present a heuristic approach to solving this problem.
Integrality Gap of Bin Packingread_more
HG G 19.1
7 October 2013
16:30-18:00 		Dr. Robert Hildebrand
Institute for Operations Research at ETH Zurich, CH
Event Details

Optimization Seminar

Title Cutting Planes, Extreme functions, and the Infinite Group Problem
Speaker, Affiliation Dr. Robert Hildebrand, Institute for Operations Research at ETH Zurich, CH
Date, Time 7 October 2013, 16:30-18:00
Location HG G 19.1
Abstract In the past two decades, we have found that inequalities known as cutting planes can be enormously effective to utilize when solving mixed integer linear programs. Surprisingly, the most useful general purpose cutting planes tend to be the simplest cutting planes that were discovered in the 1970's. A recent theme for studying better cutting planes has been to understand multi-row cuts that harness more information and thus can be stronger than standard single-row cuts. With the goal of strong multi-row cuts in mind, we investigate a certain integer program relaxation called the Infinite Group Problem. We will discuss strong sufficient conditions for determining extreme inequalities for the k-dimensional infinite group problem and also surprising number theoretic dependent necessary and sufficient conditions for the 1 and 2-dimensional infinite group problems.
Cutting Planes, Extreme functions, and the Infinite Group Problemread_more
HG G 19.1
14 October 2013
16:30-18:00 		Dr. Peter Fusek
Comenius University Bratislava, Slowakia
Event Details

Optimization Seminar

Title Metric regularity in nonlinear semidefinite programming
Speaker, Affiliation Dr. Peter Fusek, Comenius University Bratislava, Slowakia
Date, Time 14 October 2013, 16:30-18:00
Location HG G 19.1
Abstract The one-to-one relation between the points fulfilling the Karush-Kuhn-Tucker conditions of an optimization problem and the zeros of the corresponding Kojima function is well-known. In the presentation we study the interplay between metric regularity and strong regularity of this a priori nonsmooth function in the context of semidefinite programming. We identify a class of locally Lipschitz functions which turn out to have coherently oriented B-subdifferentials if metric regularity is assumed. This class is general enough to contain the Kojima function corresponding to the nonlinear semidefinite programming problem. The main result is an equivalence between metric regularity and strong regularity provided that an assumption involving the topological degree is fulfilled.
Metric regularity in nonlinear semidefinite programmingread_more
HG G 19.1
21 October 2013
16:30-18:00 		Prof. Dr. Bernd Sturmfels
UC Berkeley, USA and MPI Bonn, D
Event Details

Optimization Seminar

Title The Euclidean Distance Degree
Speaker, Affiliation Prof. Dr. Bernd Sturmfels, UC Berkeley, USA and MPI Bonn, D
Date, Time 21 October 2013, 16:30-18:00
Location HG G 19.1
Abstract The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. The Euclidean distance degree is the number of critical points of this optimization problem. We focus on varieties seen in engineering applications, and we discuss exact computational methods. Our running example is the Eckart-Young Theorem which states that the nearest point map for low rank matrices is given by the singular value decomposition. This is joint work with Jan Draisma, Emil Horobet, Giorgio Ottaviani, Rekha Thomas.
The Euclidean Distance Degreeread_more
HG G 19.1
28 October 2013
16:30-18:00 		Prof. Dr. Richard Vinter
Imperial College London, UK
Event Details

Optimization Seminar

Title State Constrained Optimal Control
Speaker, Affiliation Prof. Dr. Richard Vinter, Imperial College London, UK
Date, Time 28 October 2013, 16:30-18:00
Location HG G 19.1
Abstract Estimates on the distance of a nominal state trajectory from the set of state trajectories that are confined to a closed set have an important unifying role in state constrained optimal control theory. They can be used to establish non-degeneracy of optimality conditions such as the Pontryagin Maximum Principle, to show that the value function describing the sensitivity of the minimum cost to changes of the initial condition is characterized as a unique generalized solution to the Hamilton Jacobi equation, and for numerous other purposes. We discuss the validity of various presumed distance estimates and their implications, recent counter-examples illustrating some unexpected pathologies and pose some open questions.
State Constrained Optimal Controlread_more
HG G 19.1
4 November 2013
16:30-18:00 		Dr. Vladimir Shikhman
Catholic University of Louvain, Belgien
Event Details

Optimization Seminar

Title Market Equilibrium via Convex Optimization
Speaker, Affiliation Dr. Vladimir Shikhman, Catholic University of Louvain, Belgien
Date, Time 4 November 2013, 16:30-18:00
Location HG G 19.1
Abstract We deal with mathematical modeling of economic markets towards there algorithmic nature. The focus lies on the reasonable dynamic adjustment processes converging to a market equilibrium. The behavior and price dynamics of market participants is revealed by tractable algorithmic procedures. For that, the methodology of convex optimization is used. In particular, newly established efficient numerical schemes for convex optimization problems, such as subgradient methods, induce reliable price dynamics. To guarantee their tractability, we introduce a new price adjustment principle: the equilibrium system of prices corresponds to the minimal value of the total excessive revenue of the market. In collaboration with Yurii Nesterov
Market Equilibrium via Convex Optimizationread_more
HG G 19.1
11 November 2013
16:30-18:00 		Prof. Dr. Yurii Nesterov
Catholic University of Louvain, Belgien
Event Details

Optimization Seminar

Title Universal gradient methods
Speaker, Affiliation Prof. Dr. Yurii Nesterov, Catholic University of Louvain, Belgien
Date, Time 11 November 2013, 16:30-18:00
Location HG G 19.1
Abstract In Convex Optimization, numerical schemes are always developed for some specific problem classes. One of the most important characteristics of such classes is the level of smoothness of the objective function. Methods for nonsmooth functions are different from the methods for smooth ones. However, very often the level of smoothness of the objective is difficult to estimate in advance. In this talk we present algorithms which adjust their behavior in accordance to the actual level of smoothness observed during the minimization process. Their only input parameter is the required accuracy of the solution.
Universal gradient methodsread_more
HG G 19.1
18 November 2013
16:30-18:00 		Dr. Angelos Georghiou
Automatic Control Laboratory, ETH Zurich
Event Details

Optimization Seminar

Title A stochastic capacity expansion model for the UK energy system
Speaker, Affiliation Dr. Angelos Georghiou, Automatic Control Laboratory, ETH Zurich
Date, Time 18 November 2013, 16:30-18:00
Location HG G 19.1
Abstract Energy markets are currently undergoing one of their most radical changes in history. Both market liberalization and the increasing penetration of renewable energy sources highlight the need to accommodate uncertainty in the design and management of future energy systems. This work aims to identify the most cost-efficient expansion of the UK energy grid, given a growing future demand for energy and the target to move towards a more sustainable energy system. To this end, we develop a multi-stage stochastic program where the investment decisions (generation capacity that should be built) are taken here-and-now, whereas the operating decisions are taken in hourly time stages over a horizon of 30 years. The resulting problem contains several thousand time stages and is therefore severely intractable. We develop a novel problem reformulation, based on the concept of time randomization, that allows us to equivalently reformulate the problem as a two-stage stochastic program. By taking advantage of the simple structure of the decision rule approximation scheme, we can model and solve a problem that optimizes over the whole generation capacity of the UK energy system.
A stochastic capacity expansion model for the UK energy systemread_more
HG G 19.1
25 November 2013
16:30-18:00 		Prof. Dr. Anders Rantzer
Lund University, Sweden
Event Details

Optimization Seminar

Title Scalable Control of Monotone Systems
Speaker, Affiliation Prof. Dr. Anders Rantzer, Lund University, Sweden
Date, Time 25 November 2013, 16:30-18:00
Location HG G 19.1
Abstract Classical control theory does not scale well for large systems like traffic networks, power networks and chemical reaction networks. However, many of these applications can be handled efficiently using the concept of monotone system. Monotonicity means that a given state ordering is preserved by the dynamics. For example, a system is called monotone if all step responses are monotone. Such systems are common in many branches of science and engineering. In this presentation, we will highlight several fundamental advantages of monotone control systems: Verification and performance optimization can be done in with a complexity that scales linearly with the number of states and interconnections. Distributed controllers can be designed by convex optimization. Lyapunov functions and storage functions for nonlinear monotone systems can be built from scalar functions of the states, with dramatic simplifications as a result.
Scalable Control of Monotone Systemsread_more
HG G 19.1
2 December 2013
16:30-18:00 		Prof. Dr. Benjamin Sudakov
Department of Mathematics at ETH Zurich
Event Details

Optimization Seminar

Title All pairs shortest path in quadratic time with high probability
Speaker, Affiliation Prof. Dr. Benjamin Sudakov, Department of Mathematics at ETH Zurich
Date, Time 2 December 2013, 16:30-18:00
Location HG G 19.1
Abstract All-pairs shortest path problem is one of the most important, and most studied algorithmic graph problems. For this problem many researches develop algorithms which work well on random instances, most notably complete directed graphs on n vertices with random weights on their edges. The simplest such model, on which we focus in this talk, is the one in which all edge weights are drawn independently at random from the uniform distribution on [0,1] We present an all-pairs shortest path algorithm in this setting whose running time is $O(n^2)$,in expectation and with high probability. This is clearly best possible and resolves a long standing open problem. Joint work with Y. Peres, D. Sotnikov and U. Zwick
All pairs shortest path in quadratic time with high probabilityread_more
HG G 19.1
9 December 2013
16:30-18:00 		Prof. Dr. Neil Olver
VU University Amsterdam, Netherlands
Event Details

Optimization Seminar

Title Pipage Rounding, Pessimistic Estimators and Matrix Concentration
Speaker, Affiliation Prof. Dr. Neil Olver, VU University Amsterdam, Netherlands
Date, Time 9 December 2013, 16:30-18:00
Location HG G 19.1
Abstract Negative dependence is a useful property of random variables, and one that is often exploited in algorithms based on dependent random sampling. But it does not seem to always be enough. In particular, while concentration results are known for sums of negatively dependent scalar-valued random variables, as well as sums of independent matrix-valued random variables, they are not known for sums of negatively dependent matrices. We show how this obstacle can be bypassed for pipage rounding, an important and popular dependent rounding technique. Using a method we call "concavity of pessimistic estimators", we show concentration of submodular functions and concentration of matrix sums under pipage rounding. To prove the latter result, we derive a new variant of Lieb's celebrated concavity theorem in matrix analysis. One main application of these results is to "spectrally-thin trees", a spectral analog of the thin trees that played a crucial role in the recent breakthrough on the asymmetric travelling salesman problem. (Joint work with Nick Harvey)
Pipage Rounding, Pessimistic Estimators and Matrix Concentrationread_more
HG G 19.1
16 December 2013
16:30-18:00 		Dr. Julia Pap
Eötvös University, Budapest, Hungary
Event Details

Optimization Seminar

Title Applications of a polyhedral version of Sperner's Lemma
Speaker, Affiliation Dr. Julia Pap, Eötvös University, Budapest, Hungary
Date, Time 16 December 2013, 16:30-18:00
Location HG G 19.1
Abstract Sperner's Lemma states the existence of a multicoloured triangle in certain kinds of colorings of triangulations. It's connection to topology is well-known: Brouwer's fixed-point theorem for example can be derived from it. In this talk we investigate a different kind of applications. First we state a version of Sperner's Lemma in which we color the vertices of an n-dimensional polyhedron - and we can get another version by polarizing. We show how this latter statement can lead to short proofs of a variety of results in combinatorics and game theory. For example, the theorem of Boros and Gurvich, that perfect graphs are kernel-solvable, or results about stable matchings and their generalizations. We also show that these polyhedral versions of Sperner's Lemma are PPAD-complete, and pose some open questions. Joint work with Tamás Király.
Applications of a polyhedral version of Sperner's Lemmaread_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