Optimization seminar

×

Modal title

Modal content

Spring Semester 2011

Date / Time Speaker Title Location
21 February 2011
16:30-18:00
Prof. Dr. Michael Hinze
University of Hamburg, Germany
Event Details

Optimization Seminar

Title Mathematics of pde constrained optimization
Speaker, Affiliation Prof. Dr. Michael Hinze, University of Hamburg, Germany
Date, Time 21 February 2011, 16:30-18:00
Location HG G 19.1
Abstract We discuss control problems with PDEs as subsidiary conditions and take special emphasis on - the proper functional analytic setting, - tailored discrete concepts in the presence of additional pointwise constraints, and on - structure exploiting solution algorithms. The theoretical results are supported by numerical experiments.
Mathematics of pde constrained optimizationread_more
HG G 19.1
7 March 2011
16:30-18:00
Prof. Dr. Yurii Nesterov
Catholic University of Louvain, Belgium
Event Details

Optimization Seminar

Title Random gradient-free minimization of convex functions
Speaker, Affiliation Prof. Dr. Yurii Nesterov, Catholic University of Louvain, Belgium
Date, Time 7 March 2011, 16:30-18:00
Location HG G 19.1
Abstract In this talk, we present the complexity bounds for methods of Convex Optimization based only on computation of the function value. The search directions of our schemes are normally distributed random Gaussian vectors. It appears that such methods usually need at most $n$ times more iterations than the standard gradient methods, where $n$ is the dimension of the space of variables. This conclusion is true both for nonsmooth and smooth problems. For the later class, we develop also an accelerated scheme with the expected rate of convergence $O({n^2 \over k^2})$, where $k$ is the iteration counter. For Stochastic Optimization, we propose a zero-order scheme and justify its expected rate of convergence $O({n\over k^{1/2}})$. We give also some bounds for the rate of convergence of the random gradient-free methods to stationary points of nonconvex functions, both for smooth and nonsmooth cases. Our theoretical results are supported by preliminary computational experiments.
Random gradient-free minimization of convex functionsread_more
HG G 19.1
14 March 2011
16:30-18:00
Prof. Dr. Martin Skutella
Technische Universität Berlin, Germany
Event Details

Optimization Seminar

Title On the periodic maintenance problem
Speaker, Affiliation Prof. Dr. Martin Skutella, Technische Universität Berlin, Germany
Date, Time 14 March 2011, 16:30-18:00
Location HG G 19.1
Abstract The periodic maintenance problem is a real-time scheduling problem that arises, for example, in the design of software-based operation control of aircraft. A set of tasks has to be distributed on a minimum number of processors and offsets of the tasks have to be computed. The tasks emit jobs periodically starting at their offset and then need to be executed on the machines without any delay. In practice, further constraints in terms of memory usage and redundancy requirements have to be met. Approaches based on standard integer programming formulations fail to solve real-world instances. By exploiting structural insights of the problem we obtain an IP-formulation and primal heuristics that together solve the real-world instances to optimality. We also give a rigorous account on the complexity and approximability landscape of the periodic maintenance problem. In particular, we present a simple variant of the well known First-Fit heuristic for the BinPacking problem which can be analyzed to be a 2-approximation algorithm for the special case of harmonic periods. This is joint work with Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier from EPF Lausanne and Jose Verschae and Andreas Wiese from TU Berlin.
On the periodic maintenance problem read_more
HG G 19.1
21 March 2011
16:30-18:00
David Adjiashvili
ETH Zurich
Event Details

Optimization Seminar

Title Dealing with Structural Uncertainty in Combinatorial Optimization
Speaker, Affiliation David Adjiashvili, ETH Zurich
Date, Time 21 March 2011, 16:30-18:00
Location HG G 19.1
Abstract Optimization under uncertainty has attracted vast attention in the last decades. The two main paradigms in the field are Stochastic Optimization and Robust Optimization. The former normally involves optimizing the expected value of the solution, hence it is meaningful in applications where the optimization needs to be performed many times. In the case that uncertainty affects the underlying structure of the problem, namely when different scenarios correspond to different feasible sets, stochastic optimization is often not applicable, since we are rarely interested in solutions which are 'feasible in expectation'. Robust optimization is often a suitable alternative in the presence of uncertainty in the underlying structure. In this talk we display a model for robust combinatorial optimization, which provides a balance between modeling power and solvability. The notion of a Robust Covering Counterpart of a combinatorial optimization problem is defined and motivated. In a nutshell, the robust covering counterpart of a combinatorial optimization problem is to find a minimum cost set of resources, which contains a feasible solution to the original problem in every scenario, while different scenarios correspond to subsets of unavailable (failed) resources. We provide a uniform hardness-of-approximation result for robust covering counterparts. On the positive side we display an approximation algorithm for the robust covering counterpart of the Matroid Optimization Problem, which essentially matches the lower bound for approximability. We briefly mention results for robust covering counterparts of other combinatorial optimization problems, as well as possible extensions of the robust covering counterpart model. Joint work with Rico Zenklusen (MIT)
Dealing with Structural Uncertainty in Combinatorial Optimizationread_more
HG G 19.1
28 March 2011
16:30-18:00
Thomas Surowiec
Humboldt-Universitaet Berlin, Germany
Event Details

Optimization Seminar

Title Mathematical Programs with Equilibrium Constraints in Function Spaces
Speaker, Affiliation Thomas Surowiec, Humboldt-Universitaet Berlin, Germany
Date, Time 28 March 2011, 16:30-18:00
Location HG G 19.1
Abstract The modeling of many real-world phenomena often leads to optimization problems formulated in function spaces. A number of these models have a bi-level structure and thus often fall into the category of non-smooth/non-convex optimization problems called mathematical programs with equilibrium constraints (MPECs). Due to an inherent lack of constraint regularity, classical results from optimization theory cannot be applied to MPECs for the derivation of KKT-type conditions. By applying and further developing certain concepts from variational analysis, we demonstrate how to derive explicit first order optimality conditions for a large class of MPECs. Afterwards, we focus on a specific MPEC inspired by the theory of elasto-plasticity. Finally, we discuss current work on the numerical realization of the derived conditions. An example illustrating the proposed algorithmic approach will be presented.
Mathematical Programs with Equilibrium Constraints in Function Spacesread_more
HG G 19.1
4 April 2011
16:30-18:00
Giuseppe Calafiore
Politecnico di Torino, Italy
Event Details

Optimization Seminar

Title Random Convex Programs
Speaker, Affiliation Giuseppe Calafiore, Politecnico di Torino, Italy
Date, Time 4 April 2011, 16:30-18:00
Location HG G 19.1
Abstract Random convex programs (RCPs) are convex optimization problems subject to a finite number N of random constraints. The optimal objective value J^* of an RCP is thus a random variable. We study the probability with which J^* is no longer optimal if a further random constraint is added to the problem (violation probability, V^*). It turns out that this probability rapidly concentrates near zero, as N increases. We first develop a theory for RCPs, leading to explicit bounds on the upper tail probability of V^*. Then, we extend the setup to the case of RCPs with r a-posteriori violated constraints (RCPVs): a paradigm that permits to improve the optimal objective value while maintaining the violation probability under control. Explicit and non-asymptotic bounds are derived also in this case: the upper tail probability of V^* is upper bounded by a multiple of a Beta distribution, irrespective of the distribution on the random constraints. Further, the relation between RCPVs and chance-constrained problems (CCP) is discussed, showing that the optimal objective J^* of an RCPV with generic constraint removal rule provides, with arbitrarily high probability, an upper bound on the optimal objective of a corresponding CCP. Moreover, whenever an optimal constraint removal rule is used in the RCPVs, then appropriate choices of N,r exist such that J^* approximates arbitrarily well the objective of the CCP.
Random Convex Programsread_more
HG G 19.1
* 18 April 2011
17:15-18:00
Event Details

Optimization Seminar

Title No Seminar in favor of the Inaugural Lecture of Robert Weismantel: Von Hilbert Basen zu Optimierungsalgorithmen
Speaker, Affiliation
Date, Time 18 April 2011, 17:15-18:00
Location HG F 30
No Seminar in favor of the Inaugural Lecture of Robert Weismantel: Von Hilbert Basen zu Optimierungsalgorithmen
HG F 30
9 May 2011
16:30-18:00
Prof. Dr. Wolfgang Marwan
Otto-von-Guericke Universität Magdeburg, Germany
Event Details

Optimization Seminar

Title A Systems Level Approach to Cellular Reprogramming
Speaker, Affiliation Prof. Dr. Wolfgang Marwan, Otto-von-Guericke Universität Magdeburg, Germany
Date, Time 9 May 2011, 16:30-18:00
Location HG G 19.1
A Systems Level Approach to Cellular Reprogramming
HG G 19.1
16 May 2011
16:30-18:00
Dr. Rico Zenklusen
Massachusetts Institute of Technology, Cambridge, USA
Event Details

Optimization Seminar

Title Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
Speaker, Affiliation Dr. Rico Zenklusen, Massachusetts Institute of Technology, Cambridge, USA
Date, Time 16 May 2011, 16:30-18:00
Location HG G 19.1
Abstract Due to the property of diminishing returns, submodular functions naturally appear in many optimization problems, and considerable interest arose in the question how to maximize them in different settings. In this talk, I will present a general framework to approximately maximize a (possibly non-monotone) submodular function f under various packing constraints. Our approach is based on approximately optimizing a natural extension F of f, known as the multilinear extension, over a polytope P which is a relaxation of the given constraints, and then effectively rounding the fractional solution. This approach has already been used in some settings, however it was limited in several important ways, mainly due to a heavy dependence of the used methods on the underlying constraints. We overcome these limitations as follows. First, I will show how F can be maximized up to a constant factor of the optimum on any down-closed polytope P over which any linear function can be optimized efficiently. Previously this was known only for monotone functions or when P was either the intersection of a constant number of knapsack constraints or a matroid polytope. Second, I will present a rather general method to effectively round the fractional solution, using contention resolution (CR) schemes. A nice property of CR schemes is that CR schemes for different down-closed polytopes can be combined to obtain a (slightly weaker) CR scheme for the intersection of those polytopes. This modularity of CR schemes allows for rounding over a wide range of polytopes P. I will discuss several CR schemes for natural constraints, and present in more detail an optimal CR scheme for matroid polytopes. Combining the obtained results, a broadly applicable framework is obtained for approximately maximizing submodular functions. This is based on joint work with Chandra Chekuri and Jan Vondrak
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemesread_more
HG G 19.1
* 20 May 2011
16:30-18:30
Prof. Dr. Ben Recht
University of Wisconsin, Madison, USA
Event Details

Optimization Seminar

Title The Convex Geometry of Inverse Problems
Speaker, Affiliation Prof. Dr. Ben Recht, University of Wisconsin, Madison, USA
Date, Time 20 May 2011, 16:30-18:30
Location HG G 19.1
Abstract Deducing the state or structure of a system from partial, noisy measurements is a fundamental task throughout the sciences and engineering. The resulting inverse problems are often ill-posed because there are fewer measurements available than the ambient dimension of the model to be estimated. In practice, however, many interesting signals or models contain few degrees of freedom relative to their ambient dimension: a small number of genes may constitute the signature of a disease, very few parameters may specify the correlation structure of a time series, or a sparse collection of geometric constraints may determine a molecular configuration. Discovering, leveraging, or recognizing such low-dimensional structure plays an important role in making inverse problems well-posed. In this talk, I will propose a unified approach to transform notions of simplicity and latent low-dimensionality into convex penalty functions. This approach builds on the success of generalizing compressed sensing to matrix completion, and greatly extends the catalog of objects and structures that can be recovered from partial information. I will focus on a suite of data analysis algorithms designed to decompose general signals into sums of atoms from a simple---but not necessarily discrete---set. These algorithms are derived in a convex optimization framework that encompasses previous methods based on l1-norm minimization and nuclear norm minimization for recovering sparse vectors and low-rank matrices. I will provide sharp estimates of the number of generic measurements required for exact and robust recovery of a variety of structured models. I will then detail several example applications and describe how to scale the corresponding inference algorithms to massive data sets.
The Convex Geometry of Inverse Problemsread_more
HG G 19.1
23 May 2011
16:30-18:00
Prof. Dr. George Constantinides
Imperial College London, UK
Event Details

Optimization Seminar

Title CANCELLED: FPGA-based acceleration of embedded numerical algorithms
Speaker, Affiliation Prof. Dr. George Constantinides, Imperial College London, UK
Date, Time 23 May 2011, 16:30-18:00
Location HG G 19.1
Abstract This talk will discuss the potential of Field-Programmable Gate Array (FPGA) architectures to accelerate numerically intensive applications, with a particular emphasis on structured quadratic programming problems arising in model predictive control. After a brief tutorial overview of FPGAs, we discuss their advantages and challenges for this application area, including a delve into some details of hardware implementations of computer arithmetic. We then provide an overview of our current implementation of FPGA-based MPC, recently presented at FPGA 2011 in Monterey, before discussing some of the open questions and challenges that remain. The work presented has been jointly developed with Eric Kerrigan and Juan Jerez.
CANCELLED: FPGA-based acceleration of embedded numerical algorithmsread_more (CANCELLED)
HG G 19.1
30 May 2011
16:30-18:00
Prof. Dr. Vladimir Veliov
Technische Universität Wien, Austria
Event Details

Optimization Seminar

Title Distributed Optimal Control in Problems of Endogenous Economic Growth
Speaker, Affiliation Prof. Dr. Vladimir Veliov, Technische Universität Wien, Austria
Date, Time 30 May 2011, 16:30-18:00
Location HG G 19.1
Abstract Distributed optimal control problems arise in economics not that much due to involvement of the physical (geographical) space, rather due to the heterogeneity of important economic factors, such as physical capital, labor, consumption goods. The heterogeneity is represented by a parameter which plays the role of spatial variable and takes values in a domain in a finite-dimensional space. In many situations the domain of heterogeneity may change with time endogenously, depending on the past controls. In our particular economic considerations the heterogeneity will be with respect to the final goods and the dynamics of the domain of heterogeneity (that is, the products available at a given time) will depend on investment in R&D. First we shall present a general equilibrium model of endogenous growth, which differs from previous considerations by other authors in that it exhibits obsolescence of old technologies. Several findings will be discussed. The physical capital stock is not involved in this model. Then we consider a model with heterogeneous technologies (or final goods) from the industry-level perspective, where the physical capital is involved in a dynamic way. Mathematically the problem is interesting due to the non-differentiability of the objective functional. Due to the same reason in the necessary optimality condition that will be presented, one of the adjoint variables satisfies a differential inclusion (instead of equation) and the maximization of the Hamiltonian takes the form of ``max-min". As a consequence, a Pontryagin-type maximum principle is obtained under certain regularity conditions for the optimal control. Finally we discuss implications of these results for the industry-level economic model mentioned above. The talk is partly based on joint works with A. Belyakov and Ts. Tsachev.
Distributed Optimal Control in Problems of Endogenous Economic Growthread_more
HG G 19.1

Notes: events marked with an asterisk (*) indicate that the time and/or location are different from the usual time and/or location and 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, Manfred Morari, Karl Schmedders, Robert Weismantel

JavaScript has been disabled in your browser