慶應義塾大学
2017年度 春学期

Optimization Theory

Note: To read the HTML files below properly, you will need a MathML-capable web browser. In my experience, only Firefox handles this well. If you are using another browser, please use the PDF versions of the lecture notes.

2017年度春学期　水曜日１時限
2017 Spring Term, Class is Wednesdays 1st period.
担当: Rodney Van Meter
E-mail: rdv@sfc.keio.ac.jp
Masashi Aono

Concepts 概要

Some people view daily life itself as an optimization problem: how do you get the most out of a set of limited resources, including time, space, food, fuel, materials, or money? How do you find the best path to a destination, or maximize the profit for your company? Some such problems sound gauzy and vague. How can we turn those problems into concrete formulations so that we can quantify success or failure? Are there simple methods for finding optimal solutions, and how can we prove that our solution is optimal? This class introduces the topics in a form friendly those interested in everything from business to computer networking to mathematics.

Objectives & Teaching method:

This class is a gentle introduction to optimization. Indeed, "A Gentle Introduction to Optimization" is the title of the textbook. This class will be a basic lecture format with regular homeworks. Each homework set will be a few easily solved mathematical problems.

The students will select their own final project, which will form a significant fraction of the grade.

Advice:

Students are *strongly* encouraged to get, read and make use of the textbook. Students are also strongly encouraged to take this class *after* taking a basic class in linear algebra. The level of math expected is uniform use of vectors and matrices; the concepts taught build a strong theoretical and practical foundation, but the math itself does not get harder over the course of the semester.

(Update: okay, so that proved to not be entirely true; once we get to the last three weeks of the semester, we use derivatives and partial derivatives when talking about gradient descent and related topics. I do pause to explain the basic idea, but it's more of a "refresher" than actual introduction, so if you don't know what a derivative is, the last three lectures are likely to be opaque. However, there are no required homeworks that depend on you understanding derivatives.

SFC-SFS page for this class.

Course Outline

教科書 Primary Textbook

(See a more complete list of resources below.)

B. Guenin, J. Könemann, L. Tunçel,
A Gentle Introduction to Optimization Theory

ISBN-13: 978-1107658790 ISBN-10: 1107658799

Lecture by Lecture

宿題とノート
Homeworks and Additional Notes

These files are for your reference. In case of any differences, the exact problems and due dates on SFS should be considered definitive.

Requirements

The course consists of fourteen ninety-minute classes. Students are expected to read the material, contribute to classroom discussions, and complete regular homework. A large-scale project will contribute a big chunk of the grade.

成績の仕方
Grading

Your grade will be determined as follows:

宿題の提出
Submitting Homework

This year, we will be managing homework through the SFC-SFS system.

Term Project

You will complete a moderately large project during the term.

Learning Resources (Textbooks and More)

  1. I use this book for simplex and background math in the first few weeks of the semester, and the Hungarian algorithm when we talk about minimum weight perfect matching on a bipartite graph:
    B. Guenin, J. Könemann, L. Tunçel,
    A Gentle Introduction to Optimization Theory
    Links to: Publisher, Amazon
  2. And of course this book (the standard text on algorithms) for some of the graph algorithms:
    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein,
    Introduction to Algorithms, Third Edition
    Links to: Publisher, Amazon
  3. And Russell and Norvig on AI, for the A* algorithm:
    Stuart Russell and Peter Norvig,
    Artificial Intelligence: A Modern Approach, 3e
    Links to: the authors' site, publisher, Amazon
    (n.b.: There are several versions of this edition floating around, one purporting to be the international edition, but it seems the U.S. edition is the best.)
  4. This book is a good reference I’ve used while preparing some material, but a little too heavy for an SFC class. I highly recommend it for further study for those interested in the topic, though (and it's cheap!):
    Christos H. Papadimitriou and Kenneth Steiglitz,
    Combinatorial Optimization: Algorithms and Complexity
    Links to: Amazon
  5. One of these next two is the book that the prior instructor used when teaching this in Japanese.
  6. Wikipedia has been helpful, but the quality is very uneven.
  7. For gradient descent, these sites have been helpful: Also, there is an ad hoc list of test functions for global optimizers:
  8. If you generalize from least squares and linear programming (including simplex), but stop before you go all the way to non-linear optimization techniques such as gradient descent, you get to convex optimization. This online course and book comes recommended:
    Stephen Boyd and Lieven Vandenbeghe,
    Convex Optimization (700 pages!)

Contacting Me/Office Hours/Class Notes
連絡先/オフィスアワー

If you need to contact me, email is the preferred method. Please put "OPT:" in the Subject field of the email. If I do not respond to a query within 24 hours, please resend. For more urgent matters, junsec should know how to get ahold of me.

Office Hours, Spring 2017春のオフィスアウアー：TBD, Delta N211. You may come to my office during this time without an appointment. If you wish to see me otherwise, you can attempt to find me directly, or send me email to arrange an appointment.

The lecture notes for each week are posted in SFC-SFS shortly before the lecture.

その他 Additional Information