MAGDEBURG LECTURES

ON OPTIMIZATION AND CONTROL

Recent Advances in Mixed-Integer Nonlinear Optimization

Prof. Sven Leyffer
Mathematics and Computer Science Division
Argonne National Laboratory
Argonne, Il, USA

Abstract
Scientists are increasingly moving from the simulation of complex processes to the optimization, control, and design of complex systems. Many important design problems involve not only continuous variables with nonlinear constraints but also discrete decisions, giving rise to mixed-integer nonlinear programming problems (MINLPs). MINLPs combine the combinatorial complexity of the discrete decisions with the numerical challenges of the nonlinear functions. The last decade has seen a rise in new ideas, algorithmic approaches, and software packages for solving MINLPs. We will review the underlying theory of these algorithms and discuss their practical performance. We will describe extensions to other classes of MINLP such as conic-constrained MINLPs and special classes of nonlinear functions, emphasizing how to exploit their structure within a solution process. Finally, we will present a new package for solving mixed-integer nonlinear optimization problems, MINOTAUR. The MINOTAUR toolkit is designed to provide a flexible and efficient framework for solving MINLPs. The code is developed in a modular way to enable developers and users to efficiently combine the knowledge of problem structure with algorithmic insights.

Short CV
Sven obtained his Ph.D. in 1994 from the University of Dundee, working on mixed-integer nonlinear programming problems with Roger Fletcher. He has held postdoc positions at Dundee, Northwestern, and Argonne, where he now works as a computational mathematician in the Mathematics and Computer Science Division. Sven is a Senior Fellow of the Computation Institute at the University of Chicago.
Sven is the current SIAM Vice President for Programs, a co-editor of Mathematical Programming and an editor-in-chief of Mathematical Methods of Operations Research. He serves on the editorial board of Computational Optimization and Applications. In addition, Sven edits the SIAG/OPT Views-and-News. He has served as the INFORMS Optimization Vice-Chair for nonlinear programming and as the Program Director of the SIAM activity group on optimization. For other appointments, see this list of other appointments.

Diameter of polyhedra: Abstractions, upper bounds and open problems

Prof. Friedrich Eisenbrand
Chair of Discrete Optimization
Ecole Polytechnique Federale de Lausanne (EPFL)
Switzerland

Time & Place
The presentation on July 11, 2013 will be given in the Lukas Klause (Schleinufer 1, 39104 Magdeburg) and starts at 5.30 p.m.

Abstract
One of the most prominent mysteries in convex geometry is the question whether the diameter of a polyhedron is bounded by a polynomial in the number of facets. After Francisco Santos refuted the classical Hirsch conjecture in 2010, the polynomial Hirsch conjecture, stating that the answer to the question above is "Yes", has received considerable attention. The gap between the best known lower bound (linear) and the best known upper bound (n^{log d} by Kalai and Kleitman) is large.

In this talk I present the best known bounds mentioned above in a very simple abstract setting that does not involve any geometry. The polynomial Hirsch conjecture is also open in this abstract setting. I furthermore show polynomial upper bounds on the diameter of polyhedra that are defined by matrices with small sub-determinants and close with open problems.

Information about the Speaker
Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems.

Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001.

Autogeneration of Nonlinear Optimal Control Algorithms for Embedded Hardware and Application to Tethered Airplane Control

Prof. Moritz Diehl
Optimization in Engineering Center (OPTEC) and
Electrical Engineering Department ESAT
KU Leuven

Abstract
Nonlinear Model Predictive Control (NMPC) is a feedback control technique that uses the most current state estimate of a nonlinear system to compute an optimal plan for the future system behaviour. This plan is recomputed in every sampling time, creating feedback. Thus, NMPC needs to repeatedly solve a nonlinear optimal control problem. Recent algorithmic progress makes the solution of NMPC optimization problems possible at sampling times in the milli and microsecond range.

This talk describes some of the recent algorithmic developments that made it possible to solve classical NMPC benchmark problems with computation times below even one microsecond. We also present experimental results where the algorithms are used for state estimation and feedback control of tethered airplanes that are intended for airborne wind power generation.

Information about the Speaker
since 2006: Associate professor (with tenure), ESAT-SCD, K.U. Leuven,and PI of OPTEC
2001-2006: Scientific assistant (C1) at IWR, Heidelberg University
spring 2005: research stay at Univ. Paul Sabatier, Toulouse
spring 2003: Long term fellow at IMA, University of Minnesota, USA
spring 2002: research stay at INRIA Rocquencourt
1999-2001: PhD at IWR, Heidelberg University (summa cum laude)
1993-99: Diploma of Physics at Heidelberg University (with distinction)

Polynomial Optimization via Semidefinite Programming

Prof. Markus Schweighofer
Fachbereich Mathematik und Statistik
Universität Konstanz

Abstract
Polynomial optimization is concerned with minimizing or maximizing a polynomial objective function subject to a finite number of polynomial constraints. The constraints are non-strict real polynomial inequalities in several variables. A very successful technique to solve these problems has emerged since the turn of the millennium: The basic idea is to relax the problem by replacing all nonlinear monomials by new variables. As a matter of course, the resulting linear program would in general carry little information about the original problem. To delimit the loss of information during the linearization procedure, one adds infinite families of polynomial inequalities which are redundant in the original polynomial optimization problem but carry important information after being linearized. Each such family is chosen in a way such that it becomes a single linear matrix inequality when linearized. The linearized problem is no longer a linear program but still a semidefinite program and can therefore be solved efficiently. But what exactly do the optimal solutions of the original problem have to do with the original problem?

Short CV
since 09/2009 Universität Konstanz, full professor
09/07--08/09 Université de Rennes 1, maître de conférences
09/03--08/07 Universität Konstanz, scientific employee
09/02--08/03 Université de Rennes 1, post-doc
2002 Ph.D. Universität Konstanz
1999 Diplom Passau

Modelling, Simulation and Optimal Control of Descriptor Systems

Prof. Volker Mehrmann
Institute for Mathematics
Technische Universität Berlin
DFG Research Center Matheon

Abstract
Automated modeling of dynamical systems has reached a very high level of maturity. Unfortunately the resulting models are not always well suited for numerical simulation, control or optimization. As a consequence typically a remodeling has to be carried out to use classical simulation, optimization and control tools in a reliable and satisfactory way. We present a remodeling concept that creates, from a given automatically generated model (including over- and under-determined systems), a new system which is provably well suited for simulation, control and optimization, but has the same solution set. In particular all the variables keep their physical meaning. We demonstrate the advantages of the new approach and also present some of the current challenges.

Short CV
Volker Mehrmann received his Diploma in mathematics in 1979, his Ph.D. in 1982, and his habilitation in 1987 from the University of Bielefeld, Germany. He spent research years at Kent State University in 1979-1980, at the University of Wisconsin in 1984-1985, and at IBM Research Center in Heidelberg in 1988-1989. After spending the years 1990-1992 as a visiting full professor at the RWTH Aachen, he was a full professor at Chemnitz University of Technology from 1993 to 2000. Since then he has been a full professor for Mathematics at TU Berlin.
He is a member of acatech (the German academy of engineering) and president of GAMM (International Association of Applied Mathematics and Mechanics). His research interests are in the areas of numerical mathematics/scientific computing, applied and numerical linear algebra, control theory, and the theory and numerical solution of differential-algebraic equations. He is editor-in-chief of Linear Algebra and its Applications and he is Chairman of MATHEON, the DFG Research Center "Mathematics for key technologies" in Berlin as the GAMM, the "Gesellschaft für Angewandte Mathematik und Mechanik. He is the author and co-author of 5 monographs and textbooks, has (co-)edited 5 books and (co-)authored more than 160 articles in peer-reviewd scientific journals.

Convex Computation of the Region of Attraction of Polynomial Control Systems

Prof. Didier Henrion
Laboratory for Analysis and Architecture of Systems
Methods and Algorythems in Control (MAC)
CNRS-French National Center for Scientific Research
France

Department of Automatic Control
Faculty of Electrical Engineering
Czech Technical University Prag
Czech Republic

Abstract
We address the problem of computing the region of attraction (ROA) of a target set (typically a neighborhood of an equilibrium point) of a controlled nonlinear system with polynomial dynamics and semialgebraic state and input constraints. We show that the ROA can be computed by solving a convex linear programming (LP) problem over the cone of nonnegative measures. In turn, this problem can be solved approximately via a converging hierarchy of convex finite-dimensional linear matrix inequalities (LMIs). The dual LP on nonnegative continuous functions (approximated by polynomial sum-of-squares) allows us to generate a hierarchy of guaranteed semialgebraic outer approximations converging almost uniformly to the ROA. This is joint work with Milan Korda and Colin N. Jones, Ecole Polytechnique Federale de Lausanne, Switzerland.

Short CV
Currently he is a CNRS "Directeur de Recherche" (senior researcher) at LAAS in the research group MAC. He is also holding a secondary appointment as an associate professor at the Department of Automatic Control of the Faculty of Electrical Engineering of the Czech Technical University in Prague.

He received the "Diplôme d'Ingénieur" (Engineer's Degree) and the "Diplôme d'Etudes Approfondies" (Masters' Degree) with specialization in control from Institut National des Sciences Appliquées (INSA, National Institute for Applied Sciences), Toulouse, Southwestern France, in September 1994. From October 1994 to December 1995 he was a research assistant at Universidad Simón Bolívar, Caracas, Venezuela. From February 1996 to December 1998 he was a Ph.D. student at Ustav Teorie Informace a Automatizace (UTIA, Institute of Information Theory and Automation), Prague, Czech Republic. From October 1996 to August 1999 he was a Ph.D. student at Laboratoire d'Analyse et d'Architecture des Systèmes (LAAS, Laboratory of Analysis and Architecture of Systems) of Centre National de la Recherche Scientifique (CNRS, National Center for Scientific Research) in Toulouse, France. He received the "Candidate of Sciences" (Ph.D.) degree from Akademie Ved Ceske Republiky (Academy of Sciences of the Czech Republic) in December 1998, the "Diplôme de Doctorat" (Ph.D. degree) from INSA Toulouse in October 1999, the "Diplôme d'Habilitation à Diriger des Recherches" (French Habilitation) degree from Université Paul Sabatier de Toulouse in December 2007, and the "Docent" (Czech Habilitation) degree from Ceske Vysoke Uceni Technicke v Praze (CVUT, Czech Technical University in Prague) in June 2008. In 2004 he was awarded the Bronze Medal from CNRS, for his achievements in systems control theory. In 2005 he was awarded, jointly with Fredrik Kahl, the David Marr Prize for the best paper at the International Conference on Computer Vision. In 2011, upon recommendation by a committee of the French Acadèmie des Sciences, he was awarded a scientific grant by the Simone and Cino del Duca Foundation of the Institut de France, on the topic of applied mathematics. In 2012 he was awarded, jointly with Jérôme Malick, the Charles Broyden prize for the best paper in the journal Optimization Methods and Sofware.

Global Optimization with Differential Equations Embedded

Prof. Paul I. Barton
Department of Chemical Engineering
Massachusetts Institute of Technology
USA

Abstract
Optimization problems with ordinary differential equations (ODEs) or differential-algebraic equations (DAEs) embedded are ubiquitous in many science and engineering disciplines. These optimization problems are usually nonconvex and often exhibit multiple local minima, some of which are suboptimal. This talk will discuss the theory and implementation of algorithms that can guarantee locating a global optimal solution of nonconvex optimization problems with ODEs and DAEs embedded. In particular, we will discuss the theory required to construct bounds and convex relaxations for nonconvex functionals with ODEs and DAEs embedded, and how the estimates generated by these relaxations can be computed practically. We also demonstrate the use of these bounds and relaxations in deterministic global optimization algorithms for continuous and mixed-integer problems.

Short CV
Paul Barton is the Lammot du Pont Professor of Chemical Engineering and Director of the Process Systems Engineering Laboratory at MIT, where he has been since 1992. He received his Ph.D. from the Centre for Process Systems Engineering at Imperial College, London University in 1992. He has held Visiting Professor appointments at CNRS-ENSIC, Nancy, France and EPFL, Lausanne, Switzerland. He has industrial experience with BP and Air Products, and has consulted for major corporations including Dow Chemical, Alstom Power and Aspen Technology. He has received a number of awards, including the Outstanding Young Researcher Award in 2004 and the Computing in Chemical Engineering Award in 2011, both from AIChE's CAST Division. Barton's research interests include hybrid discrete/continuous dynamic systems; numerical analysis of ordinary differential, differential-algebraic and partial differential-algebraic equations; sensitivity analysis and automatic differentiation; global, mixed-integer and dynamic optimization theory and algorithms; and open process modeling software. Some of the applications his group is currently focusing on include energy systems engineering, continuous pharmaceutical manufacturing and nano-scale systems engineering. He served as Director for AIChE's CAST Division from 2001-2004 and is currently a subject editor for Optimal Control Applications and Methods and associate editor for Journal of Global Optimization and Journal of Optimization Theory and Applications. He is author or co-author of over 120 articles in refereed journals. He has been very active in the design and the development of process modeling software, having been the original author of gPROMS, and having led the development of ABACUSS/JACOBIAN and DAEPACK at MIT, all of which are now commercial products widely used in industry.