Logo

Mathematical Sciences Research Institute

Home » Algebraic, Geometric, and Combinatorial Methods for Optimization

Summer Graduate School

Algebraic, Geometric, and Combinatorial Methods for Optimization August 02, 2010 - August 13, 2010
Organizers Matthias Köppe (University of California, Davis) and Jiawang Nie (University of California, San Diego)
Lecturer(s) No Lecturers Assigned Yet.
Speaker(s)

Show List of Speakers

Description 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)

Bibliography 2 (PDF)

Funding & Logistics Show All Collapse

Show Lodging

MSRI has preferred rates at the Rose Garden Inn, depending on room availability. Reservations may be made by calling 1-800-992-9005 OR directly on their website. Click on Corporate at the bottom of the screen and when prompted enter code MATH (this code is not case sensitive). By using this code a new calendar will appear and will show the MSRI rate on all room types available.

MSRI has preferred rates at the Hotel Durant. Reservations may be made by calling 1-800-238-7268. When making reservations, guests must request the MSRI preferred rate. If you are making your reservations on line, please go to this link and enter the promo/corporate code 123MSRI. Our preferred rate is $139 per night for a Deluxe Queen/King, based on availability.

MSRI has preferred rates of $149 - $189 plus tax at the Hotel Shattuck Plaza, depending on room availability. Guests can either call the hotel's main line at 510-845-7300 and ask for the MSRI- Mathematical Science Research Inst. discount; or go to www.hotelshattuckplaza.com and click Book Now. Once on the reservation page, click “Promo/Corporate Code“ and input the code: msri.

MSRI has preferred rates of $110 - $140 at the Berkeley Lab Guest House, depending on room availability. Reservations may be made by calling 510-495-8000 or directly on their website. Select “I am an individual traveler affiliated with MSRI”.

Additional lodging options may be found on our short term housing page.

Show Directions to Venue

Show Visa/Immigration

Schedule
Show All Collapse
Aug 02, 2010
Monday
09:30 AM - 10:30 AM
  Nie Talk 1
Jiawang Nie (University of California)
11:00 AM - 12:00 PM
  Blekherman Talk 1
Grigoriy Blekherman
02:00 PM - 03:00 PM
  Nie Talk 2
Jiawang Nie (University of California)
Aug 03, 2010
Tuesday
09:30 AM - 10:30 AM
  Blekherman Talk 2
Grigoriy Blekherman
11:00 AM - 12:00 PM
  Nie Talk 3
Jiawang Nie (University of California)
02:00 PM - 03:00 PM
  Blekherman Talk 3
Grigoriy Blekherman
Aug 04, 2010
Wednesday
09:30 AM - 10:30 AM
  Nie Talk 4
Jiawang Nie (University of California)
11:00 AM - 12:00 PM
  Blekherman Talk 4
Grigoriy Blekherman
Aug 05, 2010
Thursday
09:30 AM - 10:30 AM
  Nie Talk 5
Jiawang Nie (University of California)
11:00 AM - 12:00 PM
  Blekherman Talk 5
Grigoriy Blekherman
02:00 PM - 03:00 PM
  Nie Talk 6
Jiawang Nie (University of California)
Aug 06, 2010
Friday
09:30 AM - 10:30 AM
  Blekherman Talk 6
Grigoriy Blekherman
11:00 AM - 12:00 PM
  Nie Talk 7
Jiawang Nie (University of California)
02:00 PM - 03:00 PM
  Blekherman Talk 7
Grigoriy Blekherman
Aug 09, 2010
Monday
09:30 AM - 10:00 AM
  Onn Talk 1
Shmuel Onn
11:00 AM - 12:00 PM
  Koppe Talk 1
Matthias Köppe
02:00 PM - 03:00 PM
  Onn Talk 2
Shmuel Onn
Aug 10, 2010
Tuesday
09:30 AM - 10:00 AM
  Koppe Talk 2
Matthias Köppe
11:00 AM - 12:00 PM
  Onn Talk 3
Shmuel Onn
02:00 PM - 03:00 PM
  Koppe Talk 3
Matthias Köppe
Aug 11, 2010
Wednesday
09:00 AM - 10:00 AM
  Onn Talk 4
Shmuel Onn
11:00 AM - 12:00 PM
  Koppe Talk 4
Matthias Köppe
Aug 12, 2010
Thursday
09:30 AM - 10:00 AM
  Koppe Talk 5
Matthias Köppe
11:00 AM - 12:00 PM
  Onn Talk 5
Shmuel Onn
02:00 PM - 03:00 PM
  Onn Talk 6
Shmuel Onn
Aug 13, 2010
Friday
09:30 AM - 10:00 AM
  Koppe Talk 6
Matthias Köppe
11:00 AM - 12:00 PM
  Onn Talk 7
Shmuel Onn
02:00 PM - 03:00 PM
  Koppe Talk 7
Matthias Köppe