umn logo IMA home |  Contact IMA 
IMA Web

IMA Annual Program Year Workshop

Optimization and Control

January 16-20, 2007
Organizers:
Dimitris Bertsimas Sloan School of Management, Massachusetts Institute of Technology
J. William Helton Mathematics, University of California - San Diego
Jean Bernard Lasserre LAAS-CNRS
Mihai Putinar Mathematics, University of California - Santa Barbara

Schedule Participants Program Application Feedback
IMA Live Streaming and Webcasting Maps
Abstracts and Talk Materials Dining Guide
Photo Gallery

Description:

In the last decade there have been several exciting new developments in continuous, discrete, and dynamic optimization using ideas and concepts originated in algebraic geometry.

Starting in the early 1990s with the work of Conti and Traverso on toric ideals, algebraic-geometric methods have suggested intriguing new approaches to integer programming, with sustained efforts in this direction appearing every year. More recently, new relaxations have been proposed for general polynomial optimization problems over polynomial inequalities. Note that this class of problems includes 0-1 discrete optimization as a special case. Using sums of squares decompositions from real algebraic geometry and semidefinite optimization as the computational tool, several researchers (Lasserre, Parrilo and Shor) have presented strong relaxations for these problems that improve and unify earlier bounds. By their generality, these techniques have found applications in several different areas; the differential inequalities appearing in dynamical systems and control theory being a prime example. On the stochastic side, an important class of moment problems that arise in many areas of mathematics, operations research, probability theory and finance can be formulated and effectively solved using real algebraic geometry methods and semidefinite programming as the computational tool. The suitability of the algebraic geometry approach in optimization has been newly illustrated by the recent complete characterization by Helton and Vinnikov of two-dimensional semialgebraic sets representable as the feasible set of semidefinite programs, a problem with important consequences in applications such as robust control theory.

Other application areas include enumeration problems, equilibrium problems in game theory, options pricing in financial economics, and robust optimization. It is only fair to say that techniques originally thought to be of interest only for the algebraic geometry community have led to exciting new results in optimization, control theory, finance and economics and have had a decisive impact so far.

Anticipating even more progress, as evidenced by the current level of interest and activity, we are hoping that a workshop in this area bringing together both the people who develop theorems in algebraic geometry (for instance, Brion, Putinar, Schmüdgen) and the researchers who use them can facilitate progress in this interface and lead to further exciting new developments and collaborations.

Schedule
Tuesday, January 16
8:30a-9:15a Coffee and Registration   EE/CS 3-176
9:15a-9:30a Welcome and Introduction Douglas N. Arnold (University of Minnesota)  
9:30a-10:20a Complexity of multivariate optimization using exact arithmetic Marie-Francoise Roy (Université de Rennes I) EE/CS 3-180
10:20a-11:00a Coffee   EE/CS 3-176
11:00a-11:50a On the Lovasz theta-number of almost regular graphs with application to Erdos-Renyi graphs Etienne de Klerk (Katholieke Universiteit Brabant (Tilburg University)) EE/CS 3-180
11:50a-2:00p Lunch    
2:00p-2:50p Optimization of polynomials on the unit sphere Alexander Barvinok (University of Michigan) EE/CS 3-180
3:00p-3:30p Second Chances   EE/CS 3-180
3:40p-4:00p Group photos    
4:00p-6:30p IMA Reception and Poster Session
Lind Hall 400
Recent progress in applying semidefinite optimization to the satisfiability problem Miguel F. Anjos (University of Waterloo)
Solving polynomial systems via LMIs Graziano Chesi (University of Hong Kong)
Computing the best low rank approximation of a matrix Kenneth R. Driessel (Iowa State University)
Obstacle-sensitive gain scheduling using semidefinite programming Eric Feron (Georgia Institute of Technology)
Application of semidefinite programming to eigenvalue problems for elliptic linear partial differential equations Carlos R. Handy (Texas Southern University)
Experiments with linear and semidefinite relaxations for solving the minimum graph bisection problem Christoph Helmberg (Technische Universität Chemnitz-Zwickau)
Advances on the BMV trace conjecture Christopher Hillar (Texas A & M University)
Graphs of transportation polytopes Edward D. Kim (University of California)
SparsePOP and numerical results Sunyoung Kim (Ewha Womans University)
Inverse dynamical analysis of gene networks using sparsity-promoting regularization James Lu (Johann Radon Institute for Computational and Applied Mathematics )
An exact characterization of bad semidefinite programs Gabor Pataki (University of North Carolina)
Distributed optimization in an energy-constrained network Seid Alireza Razavi Majomard (University of Minnesota Twin Cities)
Semidefinite characterization and computation of real radical ideals Philipp Rostalski (Eidgenössische TH Zürich-Hönggerberg)
A PARALLEL conic interior point decomposition approach for BLOCK ANGULAR semidefinite programs Kartik K. Sivaramakrishnan (North Carolina State University)
Stability region analysis using simulations and sum-of-squares programming Ufuk Topcu (University of California)
Sensor network localization, Euclidean distance matrix completions, and graph realization Henry Wolkowicz (University of Waterloo)
SeDuMi: a package for conic optimization Yuriy Zinchenko (McMaster University)
Numerical optimization assisted by noncommutative symbolic algebra Mauricio de Oliveira (University of California, San Diego)
Wednesday, January 17
9:00a-9:30a Coffee   EE/CS 3-176
9:30a-10:20a Complexity aspects of SDP relaxations of polynomial optimization problems Markus Schweighofer (Universität Konstanz) EE/CS 3-180
10:20a-11:00a Coffee   EE/CS 3-176
11:00a-11:50a Coprime factorizations and reduction of linear parameter-varying systems Carolyn Beck (University of Illinois at Urbana-Champaign) EE/CS 3-180
11:50a-1:40p Lunch    
1:40p-2:30p Conservative structured noncommutative multidimensional linear systems: realization theory and bounded real lemma Joseph A. Ball (Virginia Polytechnic Institute and State University) EE/CS 3-180
2:30p-3:00p Coffee   EE/CS 3-176
3:00p-3:50p Matrix convexity, matrix inequalities, and beyond Scott McCullough (University of Florida) EE/CS 3-180
4:00p-4:30p Second Chances   EE/CS 3-180
6:30p-8:30p Group Dinner   Kikugawa at Riverplace (Japanese Restaurant)
43 Main Street SE Minneapolis MN 55414 612-378-3006  
Thursday, January 18
9:00a-9:30a Coffee   EE/CS 3-176
9:30a-10:30a The algebraic degree of semidefinite programming Bernd Sturmfels (University of California) EE/CS 3-180
10:20a-11:00a Coffee   EE/CS 3-176
11:00a-11:50a Sharp thresholds for sparsity recovery in the high-dimensional and noisy setting using l_1 relaxations Martin J. Wainwright (University of California) EE/CS 3-180
11:50a-1:40p Lunch    
1:40p-2:30p Sums of squares, gradient ideals, and optimization Victoria Powers (Emory University) EE/CS 3-180
2:30p-3:00p Coffee   EE/CS 3-176
3:00p-3:50p Polynomial optimal control with GloptiPoly 3.0 Didier Henrion (Centre National de la Recherche Scientifique (CNRS)) EE/CS 3-180
4:00p-4:30p Second Chances   EE/CS 3-180
5:00p-6:30p Reception   Lind Hall 400
7:00p-8:00p Math matters - IMA public lecture: Making sense of a complex world Christopher J. Budd (University of Bath) Willey Hall 125  
Friday, January 19
9:00a-9:30a Coffee   EE/CS 3-176
9:30a-10:20a Estimation of sparse graphical models Laurent El Ghaoui (University of California) EE/CS 3-180
10:20a-11:00a Coffee   EE/CS 3-176
11:00a-11:50a Discrete optimization under moment uncertainty: complexity, persistency and asymptotics Dimitris Bertsimas (Massachusetts Institute of Technology) EE/CS 3-180
11:50a-2:30p Lunch    
2:30p-3:20p LMI representation of convex sets Victor Vinnikov (Ben Gurion University of the Negev) EE/CS 3-180
3:30p-4:00p Second Chances   EE/CS 3-180
Saturday, January 20
9:00a-9:30a Coffee   EE/CS 3-176
9:30a-10:20a Sparsity in polynomial optimization Masakazu Kojima (Tokyo Institute of Technology) EE/CS 3-180
10:20a-11:00a Coffee   EE/CS 3-176
11:00a-11:50a Approximation of positive polynomials by sums of squares Salma Kuhlmann (University of Saskatchewan) EE/CS 3-180
11:50a-2:30p Lunch    
2:30p-3:20p Convex sets with lifted semidefinite representation Jean Bernard Lasserre (Centre National de la Recherche Scientifique (CNRS)) EE/CS 3-180
3:30p-4:00p Second Chances and closing remarks   EE/CS 3-180

LIST OF CONFIRMED PARTICIPANTS

Name Department Affiliation
Cheonghee Ahn Department of Mathematics Yonsei University
Suliman Al-Homidan Department of Mathmatical Sciences King Fahd University of Petroleum & Minerals
Elizabeth S. Allman Department of Mathematics and Statistics University of Alaska
Miguel F. Anjos Department of Management Sciences University of Waterloo
D. Gregory Arnold AFRL/SNAT US Air Force Research Laboratory
Douglas N. Arnold Institute for Mathematics and its Applications University of Minnesota Twin Cities
Donald G. Aronson Institute for Mathematics and its Applications University of Minnesota Twin Cities
Michel Baes ESAT/SISTA Katholieke Universiteit Leuven
Joseph A. Ball Department of Mathematics Virginia Polytechnic Institute and State University
Chunsheng Ban Department of Mathematics Ohio State University
Alexander Barvinok Department of Mathematics University of Michigan
Saugata Basu School of Mathematics Georgia Institute of Technology
Daniel J. Bates Institute for Mathematics and its Applications University of Minnesota Twin Cities
Carolyn Beck Department of General Engineering University of Illinois at Urbana-Champaign
Dimitris Bertsimas Sloan School of Management Massachusetts Institute of Technology
Yermal Sujeet Bhat Institute for Mathematics and its Applications University of Minnesota Twin Cities
Víctor Blanco Izquierdo Department of Statistics and Operational Research University of Sevilla
Cristiano Bocci Department of Mathematics Università di Milano
Tristram Bogart Department of Mathematics University of Washington
Hartwig Bosse PNA1 (Algorithms, Combinatorics and Optimization) Center for Mathematics and Computer Science (CWI)
Christopher J. Budd Department of Mathematical Sciences University of Bath
Constantine M. Caramanis Department of Electrical and Computer Engineering University of Texas
Enrico Carlini Dipartimento di Matematica Politecnico di Torino
Dong Eui Chang Department of Applied Mathematics University of Waterloo
Graziano Chesi Department of Electrical and Electronic Engineering University of Hong Kong
Hi Jun Choe Department of Mathematics Yonsei University
Ionut Ciocan-Fontanine Institute for Mathematics and its Applications University of Minnesota Twin Cities
Raul Curto Department of Mathematics University of Iowa
Etienne de Klerk Department of Econometrics and Operations Research Katholieke Universiteit Brabant (Tilburg University)
Jesus Antonio De Loera Department of Mathematics University of California
Mauricio de Oliveira Department of Mechanical and Aerospace Engineering University of California, San Diego
Xuan Vinh Doan Operations Research Center Massachusetts Institute of Technology
John C. Doyle Control and Dynamical Systems California Institute of Technology
Kenneth R. Driessel Department of Mathematics Iowa State University
Michael Dritschel Department of Mathematics University of Newcastle upon Tyne
Mathias Drton Department of Statistics University of Chicago
Laurent El Ghaoui Department of Electrical Engineering and Computer Science University of California
Lingling Fan   Midwest ISO
Makan Fardad Department of Electrical and Computer Engineering University of Minnesota Twin Cities
Maryam Fazel Control and Dynamical Systems California Institute of Technology
Eric Feron School of Aerospace Engineering Georgia Institute of Technology
Lawrence A. Fialkow Department of Computer Science SUNY at New Paltz
Stephen E. Fienberg Department of Statistics Carnegie-Mellon University
Pedro Forero Department of Electrical Engineering University of Minnesota Twin Cities
Ioannis Fotiou Automatic Control Laboratory Eidgenössische TH Zürich-Hönggerberg
Dennice Gayme Department of Control and Dynamical Systems California Institute of Technology
Tryphon T. Georgiou Department of Electrical Engineering University of Minnesota Twin Cities
Sonja Glavaski Honeywell Advanced Technology Honeywell Systems and Research Center
Jason E. Gower Institute for Mathematics and its Applications University of Minnesota Twin Cities
Carlos R. Handy Department of Physics Texas Southern University
Bernard Hanzon   National University of Ireland, University College Cork
Gloria Haro Ortega Institute for Mathematics and its Applications University of Minnesota Twin Cities
Christoph Helmberg Fakultat fur Mathematik Technische Universität Chemnitz-Zwickau
J. William Helton Department of Mathematics University of California, San Diego
Didier Henrion LAAS Centre National de la Recherche Scientifique (CNRS)
Milena Hering Institute for Mathematics and its Applications University of Minnesota Twin Cities
Christopher Hillar Department of Mathematics Texas A & M University
Jean-Baptiste Hiriart-Urruty Institute of Mathematics, MIP laboratory Université de Toulouse III (Paul Sabatier)
Sung-Pil Hong Department of Industrial Engineering Seoul National University
Serkan Hosten Department of Mathematics San Francisco State University
Benjamin J. Howard Institute for Mathematics and its Applications University of Minnesota Twin Cities
Evelyne Hubert Project CAFE Institut National de Recherche en Informatique Automatique (INRIA)
Farhad Jafari Department of Mathematics University of Wyoming
Amin Jafarian Department of Electrical and Computer Engineering University of Texas
Anders Nedergaard Jensen Institut for Matematiske Fag Aarhus University
Steve Kaliszewski Department of Mathematics and Statistics Arizona State University
Tapan Kumar Kar Faculty of Environment and Information Sciences Yokohama National University
Mordechai Katzman Department of Pure Mathematics University of Sheffield
Edward D. Kim Department of Mathematics University of California
Si-Jo Kim Department of Chemicial Engineering Andong National University
Sunyoung Kim Department of Mathematics Ewha Womans University
Henry C. King Department of Mathematics University of Maryland
Masakazu Kojima Department of Mathematical and Computing Sciences Tokyo Institute of Technology
Salma Kuhlmann Research Center for Algebra, Logic and Computation University of Saskatchewan
Nuri Kundak Department of Aerospace Engineering and Mechanics University of Minnesota Twin Cities
Song-Hwa Kwon Institute for Mathematics and its Applications University of Minnesota Twin Cities
Sanjay Lall Department of Aeronautical and Astronautical Eng. Stanford University
Andrew Lamperski Department of Control and Dynamical Systems California Institute of Technology
Jean Bernard Lasserre LAAS Centre National de la Recherche Scientifique (CNRS)
Niels Lauritzen Institut for Matematiske Fag Aarhus University
Anton Leykin Institute for Mathematics and its Applications University of Minnesota Twin Cities
Hstau Y Liao Institute for Mathematics and its Applications University of Minnesota Twin Cities
James Lu Department of Inverse Problems Johann Radon Institute for Computational and Applied Mathematics
Tom Luo Department Electrical and Computer Engineering University of Minnesota Twin Cities
Gennady Lyubeznik School of Mathematics University of Minnesota Twin Cities
Hannah Markwig Institute for Mathematics and its Applications University of Minnesota Twin Cities
Thomas Markwig Department of Mathematics Universität Kaiserslautern
Scott McCullough Department of Mathematics University of Florida
Alexandre Megretski Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology
Lisa A. Miller Department of Mechanical Engineering University of Minnesota Twin Cities
Richard B. Moeckel School of Mathematics University of Minnesota Twin Cities
Uwe Nagel Department of Mathematics University of Kentucky
Jiawang Nie Institute of Mathematics and its Application University of Minnesota Twin Cities
Antonis Papachristodoulou Department of Engineering Science University of Oxford
Pablo A. Parrilo Laboratory for Information and Decision Systems Massachusetts Institute of Technology
Gabor Pataki Department of Operations Research University of North Carolina
Helfried Peyrl   Automatic Control Laboratory
Victoria Powers Department of Mathematics and Computer Science Emory University
Mihai Putinar Department of Mathematics University of California
Jacob Quant   University of Minnesota Twin Cities
Bharath Rangarajan Department of Mechanical Engineering University of Minnesota Twin Cities
Seid Alireza Razavi Majomard Department of Electrical Engineering and Computer Science University of Minnesota Twin Cities
Ben Recht Center for the Mathematics of Information California Institute of Technology
Victor Reiner School of Mathematics University of Minnesota Twin Cities
Franz Rendl Institut für Mathematik Universität Klagenfurt
James Renegar School of Operations Research and Industrial Engineering Cornell University
John A. Rhodes Department of Mathematics and Statistics University of Alaska
Joel Roberts School of Mathematics University of Minnesota Twin Cities
Marie Rognes   University of Oslo
Philipp Rostalski Automatic Control Laboratory Eidgenössische TH Zürich-Hönggerberg
Bjarke Hammersholt Roune Department of Mathematics Aarhus University
Marie-Francoise Roy IRMAR Université de Rennes I
Christopher Ryan Sauder School of Business University of British Columbia
Arnd Scheel Institute for Mathematics and its Applications University of Minnesota Twin Cities
Markus Schweighofer Fachbereich Mathematik und Statistik Universität Konstanz
Parikshit Shah Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology
Chehrzad Shakiban Institute of Mathematics and its Application University of Minnesota Twin Cities
Kartik K. Sivaramakrishnan Department of Mathematics North Carolina State University
Steven Sperber School of Mathematics University of Minnesota Twin Cities
Dumitru Stamate School of Mathematics University of Minnesota Twin Cities
Bernd Sturmfels Department of Mathematics University of California
Jie Sun NUS Business School National University of Singapore
Bridget Eileen Tenner   Massachusetts Institute of Technology
Tamas Terlaky Department of Mathematics and Statistics McMaster University
Rekha R. Thomas Department of Mathematics University of Washington
Carl Toews Institute for Mathematics and its Applications University of Minnesota Twin Cities
Ufuk Topcu Department of Mechanical Engineering University of California
Levent Tuncel Department of Cominatorics and Optimization University of Waterloo
Victor Vinnikov Department of Mathematics Ben Gurion University of the Negev
John Voight Institute for Mathematics and its Applications University of Minnesota Twin Cities
Martin J. Wainwright Department of Electrical Engineering and Computer Science University of California
Angelika Wiegele Department of Mathematics Universität Klagenfurt
Henry Wolkowicz Department of Cominatorics and Optimization University of Waterloo
Gregory Emmanuel Yawson Department of Engineering Technology Lawrence Technological University
Josephine Yu Department of Mathematics University of California
Hongchao Zhang Institute for Mathematics and its Applications University of Minnesota Twin Cities
Lihong Zhi Mathematics Mechanization Research Center Chinese Academy of Sciences
Yuriy Zinchenko Advanced Optimization Lab, CAS McMaster University

©2006 Regents of the University of Minnesota. All rights reserved.
The University of Minnesota is an equal opportunity educator and employer.
Trouble seeing the text? | Contact U of M | Privacy
Last modified on