SITE MAP

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

SEARCH

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

SHORTCUT:


WARNING: You are currently visiting an archive of MSRI's website, information on this page is not maintained. Please go to http://www.msri.org for current information.
Any form submissions you make here will not be retained or sent to MSRI staff. This site is to be used for reference only.
 

Algebraic, Geometric, and Combinatorial Methods for Optimization

August 02, 2010 to August 13, 2010
 
Organized By: Matthias Köppe (University of California, Davis) and Jiawang Nie (University of California, San Diego)
 

This workshop is intended to introduce to graduate students the main ideas of algebraic, geometric and combinatorial methods in global optimization. We emphasize the major developments in the past few years from two viewpoints. The first one is that of the interaction of semidefinite programming and real algebraic geometry and includes topics such as linear matrix inequalities, positive polynomials, and sums of squares. The second viewpoint is that of primal methods and generating function methods in integer linear and nonlinear optimization.

The workshop consists of four parts of lectures and corresponding tutorials and computer experimentation with computer software in the area.


Week 1 -- Schedule Week 1 (PDF)

The first part (Jiawang Nie, University of California, San Diego) introduces the basic theory of semidefinite programming, which includes convex sets and linear matrix inequalities, duality theory, optimality conditions, and applications such as in control and optimization. We will also introduce how to use the existing software for solving semidefinite programming problems.
Lecture Notes Week 1 Nie (PDF), Homework Assigments Week 1 (PDF)

The second part (Greg Blekherman, Virginia Tech) introduces positive polynomials, sum of squares, basic real algebraic geometry, and its connections to semidefinite programming. The applications will also be covered. Existing software will be introduced.
Lecture Notes Week 1 Blekherman (PDF)


Week 2 -- Schedule Week 2 (PDF)

The third part (Shmuel Onn, Technion - Israel Institute of Technology) concentrates on primal methods of integer linear and nonlinear optimization, such as the theory of test sets, in particular the recent advances in Graver basis methods.

The fourth part (Matthias Köppe, University of California, Davis) is on tools from the geometry of numbers, with a focus on rational generating function techniques for integer programming. We introduce lattices, the LLL algorithm, Lenstra's algorithm for integer programming in fixed dimension, Barvinok's theory of short rational generating functions, and the summation method for polynomial integer programming.
Lecture Notes Week 2 Koeppe (PDF)

Teaching assistants: Cynthia Vinzant, University of California, Berkeley and Amitabh Basu, University of California, Davis

Bibliography (PDF)
 

Currently Available Videos

  • Matthias Köppe, Koppe Talk 2 August 10,2010, 09:30 AM to 10:00 AM
  • Shmuel Onn, Onn Talk 3 August 10,2010, 11:00 AM to 12:00 PM
  • Matthias Köppe, Koppe Talk 3 August 10,2010, 02:00 PM to 03:00 PM
  • Shmuel Onn, Onn Talk 4 August 11,2010, 09:00 AM to 10:00 AM
  • Matthias Köppe, Koppe Talk 4 August 11,2010, 11:00 AM to 12:00 PM
  • Matthias Köppe, Koppe Talk 5 August 12,2010, 09:30 AM to 10:00 AM
  • Shmuel Onn, Onn Talk 5 August 12,2010, 11:00 AM to 12:00 PM
  • Shmuel Onn, Onn Talk 6 August 12,2010, 02:00 PM to 03:00 PM
  • Matthias Köppe, Koppe Talk 6 August 13,2010, 09:30 AM to 10:00 AM
  • Shmuel Onn, Onn Talk 7 August 13,2010, 11:00 AM to 12:00 PM
  • Matthias Köppe, Koppe Talk 7 August 13,2010, 02:00 PM to 03:00 PM
  • Jiawang Nie, Nie Talk 1 August 2,2010, 09:30 AM to 10:30 AM
  • Grigoriy Blekherman, Blekherman Talk 1 August 2,2010, 11:00 AM to 12:00 PM
  • Jiawang Nie, Nie Talk 2 August 2,2010, 02:00 PM to 03:00 PM
  • Grigoriy Blekherman, Blekherman Talk 2 August 3,2010, 09:30 AM to 10:30 AM
  • Jiawang Nie, Nie Talk 3 August 3,2010, 11:00 AM to 12:00 PM
  • Grigoriy Blekherman, Blekherman Talk 3 August 3,2010, 02:00 PM to 03:00 PM
  • Jiawang Nie, Nie Talk 4 August 4,2010, 09:30 AM to 10:30 AM
  • Grigoriy Blekherman, Blekherman Talk 4 August 4,2010, 11:00 AM to 12:00 PM
  • Jiawang Nie, Nie Talk 5 August 5,2010, 09:30 AM to 10:30 AM
  • Grigoriy Blekherman, Blekherman Talk 5 August 5,2010, 11:00 AM to 12:00 PM
  • Jiawang Nie, Nie Talk 6 August 5,2010, 02:00 PM to 03:00 PM
  • Grigoriy Blekherman, Blekherman Talk 6 August 6,2010, 09:30 AM to 10:30 AM
  • Jiawang Nie, Nie Talk 7 August 6,2010, 11:00 AM to 12:00 PM
  • Grigoriy Blekherman, Blekherman Talk 7 August 6,2010, 02:00 PM to 03:00 PM
  • Shmuel Onn, Onn Talk 1 August 9,2010, 09:30 AM to 10:00 AM
  • Matthias Köppe, Koppe Talk 1 August 9,2010, 11:00 AM to 12:00 PM
  • Shmuel Onn, Onn Talk 2 August 9,2010, 02:00 PM to 03:00 PM
You can find videos of other workshops and events on our VMath - Streaming Video page.
 
 
Back to Summer Graduate Workshop Listing
 
Want to be kept updated on upcoming events? Then Click Here to Subscribe to Our Newsletters!
 
WARNING: You are currently visiting an archive of MSRI's website.
Any form submissions you make here will not be retained or sent to MSRI staff. This site is to be used for reference only.