Class lectures: Mondays and Wednesdays 10:30-11:50am in GHC 4307

Recitations: Thursdays 5:00 - 6:20, Hammerschlag Hall B103

Essentially, every problem in computer science and engineering can be formulated as the optimization of some function under some set of constraints. This universal reduction automatically suggests that such optimization tasks are intractable. Fortunately, most real world problems have special structure, such as convexity, locality, decomposability or submodularity. These properties allow us to formulate optimization problems that can often be solved efficiently. This course is designed to give a graduate-level student a thorough grounding in the formulation of optimization problems that exploit such structure and in efficient solution methods for these problems. The course focuses mainly on the formulation and solution of convex and combinatorial optimization problems. These general concepts will also be illustrated through applications in machine learning, AI, computer vision and robotics.

Students entering the class should have a pre-existing working knowledge of algorithms, though the class has been designed to allow students with a strong numerate background to catch up and fully participate. Though not required, having taken 10-701 or an equivalent machine learning class will be helpful, since we will use applications in machine learning and AI to demonstrate the concepts we cover in class.

Announcement Emails

Discussion Group

Textbooks

Grading

Auditing

Homework policy

Important Note: As we often reuse problem set questions from previous years, or problems covered by papers and webpages, we expect the students not to copy, refer to, or look at the solutions in preparing their answers. Since this is a graduate class, we expect students to want to learn and not google for answers. The purpose of problem sets in this class is to help you think about the material, not just give us the right answers. Therefore, please restrict attention to the books mentioned on the webpage when solving problems on the problem set. If you do happen to use other material, it must be acknowledged clearly with a citation on the submitted solution.

Collaboration policy

Homeworks will be done individually: each student must hand in their own answers. In addition, each student must write their own code in the programming part of the assignment. It is acceptable, however, for students to collaborate in figuring out answers and helping each other solve the problems. We will be assuming that, as participants in a graduate course, you will be taking the responsibility to make sure you personally understand the solution to any work arising from such collaboration. In preparing your own writeup, you should not refer to any written materials from a joint study session. You also must indicate on each homework with whom you collaborated. The final project may be completed individually or in teams of two students.

Late homework policy

Homework regrades policy

If you feel that we have made an error in grading your homework, please turn in your homework with a written explanation to Monica, and we will consider your request. Please note that regrading of a homework may cause your grade to go up or down.

Final project

For project milestone, roughly half of the project work should be completed. A short, graded write-up will be required, and we will provide feedback.

Note to people outside CMU

Feel free to use the slides and materials available online here. If you use our slides, an appropriate attribution is requested. Please email the instructors with any corrections or improvements.