Class lectures: Tuesdays and Thursdays 1:30PM - 2:50PM in DH A302.
Recitations: Mondays 4:30 - 6pm and Wednesdays 2 - 3:30pm see the recitation page for the location. You may attend either one.
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 optimization problems. These general concepts will also be illustrated through applications in statistics, 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 or statistics class will be helpful, since we will frequently use applications in machine learning and statistics to demonstrate the concepts we cover in class.
- We have a discussion group where we will broadcast class announcements. This is also the forum for you to post questions, discuss issues, and interact with fellow students. Please join the group and check in often:
- Textbook: Convex Optimization, Boyd and Vandenberghe, which is available online for free.
- Optional textbook: Introduction to Linear Optimization, Dimitris Bertsimas and John N. Tsitsiklis.
- Optional textbook: Convex Analysis, R. Tyrell Rockafellar
- Optional textbook: Fundamentals of Convex Analysis, Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal
- Optional textbook: Combinatorial Optimization: Algorithms and Complexity, Christos Papadimitriou and Kenneth Steiglitz.
- Optional textbook: Combinatorial Optimization, Alexander Schrijver.
- Optional textbook: Nonlinear Programming, Dimitri Bertsekas.
- Optional textbook: Approximation Algorithms, Vijay Vazirani
- Homeworks (5 assignments 50%)
- Final project (28%)
- Midterm exam (20%) - November 6 Solutions
- Scribing (2%)
ScribingScribing is compulsory for crediting students. For those auditing, scribing is not compulsory but requested. There is a minimum of two scribes per lecture, though three is the recommended number, and a fourth is optional - if all the lectures have all three scribe slots taken, then people may sign up as the fourth scribe for any lecture of their choice. Sign up for scribing lectures here. The Latex template for scribing lectures should be found here.
- Students wishing to audit must register to audit the class. This involves filling out an official audit form that must be signed by either Geoff or Ryan. Auditors may submit homework for grading, but this is not required.
- If you are not a student and want to sit in the class, please get authorization from the instructors.
Homework policyImportant 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 policyHomeworks 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.
Late homework policy
- Homeworks are due at the begining of class, unless otherwise specified.
You will be allowed 5 total late days without penalty for the entire
semester. For instance, you may be late by 1 day on five different
homeworks or late by 5 days on one homework. Each late day
corresponds to 24 hours or part thereof. These late days are in lieu
of any extensions due to sickness, travel, holidays, etc.; it is
your responsibility to plan their use appropriately. Once those
days are used, you will be penalized according to the policy below:
- Homework is worth full credit at the beginning of class on the due date.
- For the next 24 hours, it will be graded so that the highest possible score is equal to the 70th percentile of the distribution of scores of the on-time homeworks. For example, if your raw score is 80 out of 100 points, but the 70th percentile of the HW distribution is 85/100, then you will get credit for 80 * (85/100) = 68 points.
- For the following 24 hours, it will be graded out of the 40th percentile of the on-time homeworks.
- Thereafter, it will be graded out of the 10th percentile.
- You must turn in all of the homeworks, even if for reduced credit, in order to pass the course. For very-late homeworks, it is your responsibility to avoid looking at each solution set until after you have turned in the corresponding homework.
- Turn in all late homework assignments to Michelle (GHC 8001) .
Homework regrades policyIf you feel that we have made an error in grading your homework, please turn in your homework with a written explanation to Michelle, and we will consider your request. Please note that regrading of a homework may cause your grade to go up or down.
Final projectStudents will work in groups of two or three to complete a final project.
- Project proposal due date September 25 in class (10% of project grade, strict deadline, no late days allowed).
- Graded milestone due date October 30 in class (20% of project grade)
- Poster session, Wednesday December 12th at 3:30pm to 6:30pm in the NSH Atrium (35% of project grade). Please come at 3:00pm to setup your poster.
- Paper due date - December 14 at 5pm (no late days) (via electronic submission to the instructors list) (35% of project grade)