Department of Mathematics

Search

Optimization seminar

×

Modal title

Modal content

Spring Semester 2012

Date / Time Speaker Title Location
20 February 2012
16:30-18:00 		Dr. Caroline Uhler
Seminar of Statics of ETH Zurich
Event Details

Optimization Seminar

Title Ellipsoid Packing with Applications to Chromosome Organization
Speaker, Affiliation Dr. Caroline Uhler, Seminar of Statics of ETH Zurich
Date, Time 20 February 2012, 16:30-18:00
Location HG G 19.1
Abstract We consider the problem of packing ellipsoids of different size and shape in an ellipsoidal container so as to minimize a measure of total overlap. The motivating application is chromosome organization in the human cell nucleus. We describe a bilevel optimization formulation, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. We prove convergence to stationary points of this non-convex problem, and describe computational experience, including results from the chromosome packing application.
Ellipsoid Packing with Applications to Chromosome Organizationread_more
HG G 19.1
27 February 2012
16:30-18:00 		Dr. Robert Baier
University of Bayreuth, Germany
Event Details

Optimization Seminar

Title Approximation of Reachable Sets with Distance Fields on Grids
Speaker, Affiliation Dr. Robert Baier, University of Bayreuth, Germany
Date, Time 27 February 2012, 16:30-18:00
Location HG G 19.1
Abstract Reachable sets of nonlinear control problems at a given end time can be approximated with a set-valued version of Eulers method which demands a discretization in state space for intermediate sets by the accuracy O(h2), where h is the step-size in time. To overcome the costly approximation of these sets with an exploding number of grid points or boxes, a grid discretization of a bounding box for the reachable set of accuracy O(h) together with the calculation of distance functions via the solution of suitable optimal control problems is introduced. Distance functions offer simple formulas for the set operations applied in Eulers method as well as a representation of the reachable set via the complement of a union of open balls. The presented algorithm offers ways for a parallelized implementation and adaptivity. Numerical examples for calculated reachable sets will illustrate the method.
Approximation of Reachable Sets with Distance Fields on Gridsread_more
HG G 19.1
5 March 2012
16:30-18:00 		Stavros Gerakaris
University of Edinburgh, UK
Event Details

Optimization Seminar

Title Advances in High-Dimensional Nearest Neighbor Searching
Speaker, Affiliation Stavros Gerakaris, University of Edinburgh, UK
Date, Time 5 March 2012, 16:30-18:00
Location HG G 19.1
Abstract Over the last decades vast amount of data has become available. A fundamental computational problem for dealing with high-dimensional data is Nearest Neighbor Searching (NNS). In this talk we present several methods for NNS developed by the Database and the Computational Geometry community as well. These indexes, including FLANN, ANN, LSH and iDistance, are state-of-the-art in the field and efficiently treat high-dimensional data. We give emphasis in the theoretical aspects of the problem, in order to understand why these methods work. Finally, by comparing different approaches we witness basic tools that these communities share in common, when dealing with high-dimensional data, and we discuss the ways in which complementary approaches can learn from each other and facilitate further advances.
Advances in High-Dimensional Nearest Neighbor Searchingread_more
HG G 19.1
12 March 2012
16:30-18:00 		Prof. Dr. Volker Kaibel
Otto-von-Guericke Universität Magdeburg, Magdeburg, Germany
Event Details

Optimization Seminar

Title Extended Formulations in Combinatorial Optimization
Speaker, Affiliation Prof. Dr. Volker Kaibel, Otto-von-Guericke Universität Magdeburg, Magdeburg, Germany
Date, Time 12 March 2012, 16:30-18:00
Location HG G 19.1
Abstract The polytopes that seem to be associated naturally with combinatorial optimization problems tend to have rather complicated linear descriptions. However, in some cases there are very simple, nice, and easy to handle extended formulations for such polytopes, i.e., linear descriptions of higher dimensional polyhedra that can be projected linearly to the polytopes of interest. In this lecture, we discuss some aspects of this approach that has attracted quite some attention recently. Besides introducing the concept, we present some selected examples of extended formulations in particular meant to overview some techniques for their construction, and we discuss fundamental limitations of the approach, where we mainly concentrate on combinatorial obstructions that sometimes prevent the existance of small extended formulations. The talk is based on joint papers with Samuel Fiorini, Dirk O. Theis, and Kanstantsin Pashkovich.
Extended Formulations in Combinatorial Optimizationread_more
HG G 19.1
19 March 2012
16:30-18:00 		Dr. Paul Goulart
Automatic Control Laboratory of ETH Zurich
Event Details

Optimization Seminar

Title Performance bounds and robust control for constrained systems
Speaker, Affiliation Dr. Paul Goulart, Automatic Control Laboratory of ETH Zurich
Date, Time 19 March 2012, 16:30-18:00
Location HG G 19.1
Abstract This talk will describe robust control methods and performance bounds for uncertain linear systems with constraints. Computing optimal control policies for such systems is generally intractable, since the optimal controller is a nonlinear feedback law whose construction requires the solution of an infinite dimensional optimization problem. A tractable alternative is to instead parameterize the controller as affine in the uncertainty, which offers a number of numerical and theoretical benefits but is suboptimal in general. However, it is possible to estimate the degree of sub-optimality incurred by such an approach by similarly parameterizing a related dual problem with multipliers also affine in the uncertainty. This approach can provide a bound on the achievable performance by any controller over a finite or infinite horizon. Some numerical examples will be presented illustrating these bounds in comparison with receding horizon implementations of affine controllers.
Performance bounds and robust control for constrained systemsread_more
HG G 19.1
26 March 2012
16:30-18:00 		Prof. Dr. Stephen P. Boyd
Stanford University, Stanford, USA
Event Details

Optimization Seminar

Title Performance Bounds and Suboptimal Policies for Multi-Period Investment
Speaker, Affiliation Prof. Dr. Stephen P. Boyd, Stanford University, Stanford, USA
Date, Time 26 March 2012, 16:30-18:00
Location HG D 7.2
Abstract We consider dynamic trading of a portfolio of assets over a finite time horizon, with arbitrary time-varying distribution of asset returns. The goal is to maximize the total expected revenue from the portfolio, while respecting constraints on the portfolio such as a required terminal portfolio and leverage and risk limits. The revenue takes into account the gross cash generated in trades, transaction costs, and costs associated with the positions, such as fees for holding short positions. Our model has the form of a stochastic control problem with linear dynamics and convex cost function and constraints. We show how to use linear matrix inequality techniques and semidefinite programming to produce a quadratic bound on the value function, which in turn gives a bound on the optimal performance. This performance bound can be used to judge the performance obtained by any suboptimal policy. As a by-product of the performance bound computation, we obtain an approximate dynamic programming policy that requires the solution of a convex optimization problem, often a quadratic program, to determine the trades to carry out in each step. While we have no theoretical guarantee that the performance of our suboptimal policy is always near the performance bound (which would imply that it is nearly optimal) we observe that in numerical examples the two values are typically close. Joint work with M. Müller, B. O Donoghue and Y. Wang.
Performance Bounds and Suboptimal Policies for Multi-Period Investmentread_more
HG D 7.2
2 April 2012
16:30-18:00 		Prof. Dr. Angelia Nedich
University of Illinois at Urbana-Champaign, Urbana, USA
Event Details

Optimization Seminar

Title Distributed Optimization over a Network
Speaker, Affiliation Prof. Dr. Angelia Nedich, University of Illinois at Urbana-Champaign, Urbana, USA
Date, Time 2 April 2012, 16:30-18:00
Location HG G 19.1
Abstract Recent advances in wired and wireless technology necessitate the development of theory, models and tools to cope with new challenges posed by large-scale optimization problems over networks. In this talk, we consider distributed multi-agent network systems where each agent has its own convex objective function, which can be evaluated with stochastic errors. The problem consists of minimizing the sum of the agent functions, without a central coordinator and without agents sharing the explicit form of their objectives. However, the agents are willing to cooperate with each other locally to solve the problem, by exchanging their estimates of an optimal solution. We discuss such distributed algorithms for synchronous and asynchronous implementations. We present convergence results and convergence rate estimates, and provide some numerical results.
Distributed Optimization over a Networkread_more
HG G 19.1
23 April 2012
16:30-18:00 		Prof. Dr. Michele Conforti
Università degli Studi di Padova, Padova, Italy
Event Details

Optimization Seminar

Title Disjunctions and Mir Inequalities
Speaker, Affiliation Prof. Dr. Michele Conforti, Università degli Studi di Padova, Padova, Italy
Date, Time 23 April 2012, 16:30-18:00
Location HG G 19.1
Abstract We introduce the separation problem for disjunctive inequalities in the original space. We derive elementary proofs of the following results: - The split closure of a polyhedron is given by the Mixed Integer Rounding inequalities that have a special form. (Nemhauser and Wolsey) -The split closure is given by the intersection cuts. (Andersen, Cornuéjols and Li). -The split closure of a rational is a polyhedron, a result of (Cook, Kannan and Schrijver). -We also prove results of Balas-Jeroslow and Balas- Perregaard. This is joint work with Giacomo Zambelli.
Disjunctions and Mir Inequalitiesread_more
HG G 19.1
30 April 2012
16:30-18:00 		Prof. Dr. Sebastian Sager
Otto-von-Guericke Universität Magdeburg, Magdeburg, Germany
Event Details

Optimization Seminar

Title Mixed-Integer Optimal Control - a biased overview
Speaker, Affiliation Prof. Dr. Sebastian Sager, Otto-von-Guericke Universität Magdeburg, Magdeburg, Germany
Date, Time 30 April 2012, 16:30-18:00
Location HG G 19.1
Abstract We give an overview of the group's activities in the recent years, with a focus on mixed-integer optimal control problems (MIOCPs) in differential equations, which have gained increasing interest over the last years. This is probably due to the fact that the underlying processes have a high potential for optimization. Typical examples are the choice of gears in transport or processes in chemical engineering involving on-off valves. Although the first MIOCPs, namely the optimization of subway trains that are equipped with discrete acceleration stages, were already solved in the early eighties for the city of New York, the so-called indirect methods used there do not seem appropriate for generic large-scale optimal control problems with underlying nonlinear differential algebraic equation systems. Instead direct methods, in particular all-at-once approaches like the Direct Multiple Shooting Method, have become the methods of choice for most practical problems. In direct methods infinite-dimensional control functions are discretized by basis functions and corresponding finite-dimensional parameters that enter into the optimization problem. The drawback of direct methods with binary control functions obviously is that they lead to high-dimensional vectors of binary variables. For many practical applications a fine control discretization is required, however. Therefore, techniques from mixed-integer nonlinear programming like Branch and Bound or Outer Approximation will work only on limited and small time horizons because of the exponentially growing complexity of the problem. We propose to use an outer convexification with respect to the binary controls. The reformulated control problem has two main advantages compared to standard formulations or convexifications. First, especially for time-optimal control problems, the optimal solution of the relaxed problem will exhibit a bang-bang structure, and is thus already integer feasible. Second, theoretical results have recently been found that show that even for path-constrained and sensitivity-seeking arcs the optimal solution of the relaxed problem yields the exact lower bound on the minimum of the integer problem. This allows to calculate precise error estimates, if a coarser control discretization grid, a simplified switching structure for the optimization of switching times, or heuristics are used.
Mixed-Integer Optimal Control - a biased overviewread_more
HG G 19.1
7 May 2012
16:30-18:00 		Prof. Dr. Andrea Lodi
DEIS, Università di Bologna, Bologna, Italy
Event Details

Optimization Seminar

Title On Bilevel Programming and its Impact in Branching, Cutting and Complexity
Speaker, Affiliation Prof. Dr. Andrea Lodi, DEIS, Università di Bologna, Bologna, Italy
Date, Time 7 May 2012, 16:30-18:00
Location HG G 19.1
Abstract Bilevel programming is a rich paradigm to express a variety of real-world applications including game theoretic and pricing ones. However, what we are interested in this talk is to discuss the bilevel nature of two of the most crucial ingredients of enumerative methods for solving combinatorial optimization problems, namely branching and cutting. Specifically, we discuss a new branching method for 0-1 programs called interdiction branching [3] that exploits the intrinsic bilevel nature of the problem of selecting a branching disjunction. The method is designed to overcome the difficulties encountered in solving problems for which branching on variables is inherently weak. Unlike traditional methods, selection of the disjunction in interdiction branching takes into account the best feasible solution found so far. On the cutting plane side, we examine the nature of the so-called separation problem, which is that of generating a valid inequality violated by a given real vector, usually arising as the solution to a relaxation of the original problem. We show that the problem of generating a maximally violated valid inequality often has a natural interpretation as a bilevel program [2]. In some cases, this bilevel program can be easily re-formulated as a single-level mathematical program, yielding a standard mathematical programming formulation for the separation problem. In other cases, no reformulation exists yielding surprisingly interesting examples of problems arising in the complexity hierarchies introduced by Jeroslow [1]. [1] R. Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Mathematical Programming, 32:146-164, 1985. [2] A. Lodi, T.K. Ralphs, G. Woeginger, Bilevel Programming and Maximally Violated Valid Inequalities, Technical Report OR/11/3, DEIS - Università di Bologna. [3] A. Lodi, T.K. Ralphs, F. Rossi, S. Smriglio, Interdiction Branching, Technical Report OR/09/10, DEIS - Universita di Bologna.
On Bilevel Programming and its Impact in Branching, Cutting and Complexityread_more
HG G 19.1
14 May 2012
16:30-18:00 		Carla Michini
Università di Roma "La Sapienza", Roma, Italy
Event Details

Optimization Seminar

Title Vertex Adjacency and the Hirsch Conjecture for the Fractional Stable Set Polytope
Speaker, Affiliation Carla Michini, Università di Roma "La Sapienza", Roma, Italy
Date, Time 14 May 2012, 16:30-18:00
Location HG G 19.1
Abstract Given a graph, the edge formulation of the stable set problem is defi ned by two-variable constraints, one for each edge, expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope de fined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorithmic opportunities. Exploiting a graphic characterization of the bases, we first rede fine simplex pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. Between all possible pivots, we characterize degenerate and nondegenerate ones, and we differentiate those leading to an integer or to a fractional vertex. The graphic characterization of bases is crucial to prove another structural property of the fractional stable set polytope, concerning the adjacency of its vertices. In particular, we extend a necessary and sufficient condition due to Chvatal for adjacency of (integer) vertices of the stable set polytope to arbitrary (and possibly fractional) vertices of the fractional stable set polytope. These results lead us to prove that the Hirsch Conjecture is true for the fractional stable set polytope, i.e. the combinatorial diameter of this fractional polytope is at most equal to the number of edges of the given graph. We actually re fine this bound in the nonbipartite case by proving a tighter bound, equal to the number of nodes of the graph. We also design a simplex-like algorithm for the stable set problem that relies on the adjacency properties mentioned above. Our algorithm generates only integer solutions without using cutting plane methods. Preliminary results are encouraging but show that cycling can occur, due to the high degree of degeneracy of the polytope. Nevertheless, the perspective of an exact combinatorial method of solution for the stable set problem based on this algorithm seems intriguing, provided that an anticycling rule is embedded in its current design. Joint work with Antonio Sassano
Vertex Adjacency and the Hirsch Conjecture for the Fractional Stable Set Polytoperead_more
HG G 19.1
21 May 2012
16:30-18:00
Event Details

Optimization Seminar

Title No Seminar in favor of the Farewell Lecture of Hans-Jakob Lüthi
Speaker, Affiliation
Date, Time 21 May 2012, 16:30-18:00
Location HG G 19.1
No Seminar in favor of the Farewell Lecture of Hans-Jakob Lüthi
HG G 19.1

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

Organizers: Komei Fukuda, Bernd Gärtner, Diethard Klatte, John Lygeros, Manfred Morari, Karl Schmedders, Robert Weismantel

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