6.255/15.093 Optimization Methods
Fall 2011
Instructor: Pablo A Parrilo
TAs: James F Saunderson, Nathan Kallus
Lecture:
Tue-Thu 2:30-4:00
(4-370)
Recitation 1: Fri 1:00
(4-370)
Recitation 2: Wed 3:00
(34-303)
Office Hours 1: Wed 5:00-6:30
(32D-507)
Office Hours 2: Tue 4:00-5:30
(24-320)
Information:
This course introduces the principal algorithms for linear, network, discrete, nonlinear, dynamic optimization and optimal control. Emphasis is on methodology and the underlying mathematical structures. Topics include the simplex method, network flow methods, branch and bound and cutting plane methods for discrete optimization, optimality conditions for nonlinear optimization, interior point methods for convex optimization, Newton's method, heuristic methods, and dynamic programming and optimal control methods.
Announcements
Some comments on P3 and P5 of HW6
P3: many students showed (correctly) that there is no neighborhood of (0,0) for which the hessian of f_2 is psd, and then (incorrectly) asserted that (0,0) is not a local minimum for f_2. If a *sufficient* condition for a point to be a local optimum fails, that does not mean it is not a local optimum --- it just means that we don't know what it is. On the other hand, if a *necessary* condition for a point to be a local optimum fails, then that point is certainly not a local optimum.
P5: many students claimed that we need the rows of A to be linearly independent in order for the KKT conditions to be necessary in this case. It is true that if the rows of A are linearly independent then the KKT conditions are necessarily satisfied at any local optimum. But, actually, since the feasible region is a polyhedron the KKT conditions are necessarily satsified at any local optimum without any additional assumptions.
Announced on 18 December 2011 4:03 p.m. by James F Saunderson
Homework pickup
Sunday 12/18: 11am-12pm
Monday 12/19: 9am-12pm
If you can't come by at one of these times and would like to pick up your homework, let me know and we can arrange an alternative.
Announced on 17 December 2011 7:53 p.m. by James F Saunderson
Final Exam Announcement
As announced earlier, the final exam will have a duration of THREE hours, and will take place on:
Monday, December 19th, from 1:30 PM to 4:30 PM.
The exam rooms are (depending on the first letter of your last name):
A-K: E51-335
L-Z: E51-345
The exam rooms are in the Tang Center (E51):
http://whereis.mit.edu/?go=E51
Please make sure to arrive with sufficient time, particularly if you are not familiar with the location of the E51 building.
The format of the exam is open book, meaning that you are allowed
to bring and use your OWN lecture notes, formula sheets, homework
sets, or the textbook. However, no additional material (e.g., other
textbooks, assorted notes, etc). No laptops/phone/internet access
will be permitted during the exam.
The exam will cover ALL MATERIAL presented during the course, either during lectures, recitations, or homework sets.
Please let me know if you have questions/comments.
-p
Announced on 17 December 2011 6:48 p.m. by Pablo A Parrilo
Follow up on final review session
I hope you found the final review session helpful.I meant, but forgot, to remind all of you to please fill out the subject evaluations at http://web.mit.edu/subjectevaluation. The deadline is tomorrow and your input is highly valued and your sincere comments will be helpful in improving the course in the future.
Secondly, your fellow students were right in pointing out in the session that indeed unimodularity and total unimodularity were not covered in the class, at least by name, and are neither mentioned by name in the text except for a brief note. However, part (a) of the proof to theorem 7.5 (p. 289; which relies on the proof to theorem 7.3 p. 281) exactly argues the case that the constraint matrix for a network flow problem is unimodular, that is that its nonsingular square m-by-m submatrices (also known as bases) have determinant 1 or -1, and it is certainly important to know that this is the case for network flow problems and why this means that the feasible polyhedra for such problems when supplies/demands are integral have integral corners (Cramer's rule, p. 29).
Announced on 15 December 2011 11:42 a.m. by Nathan Kallus
Final review session
Next Wednesday, on the last session of the Wednesday recitation, we will hold a final review session. The review session will consist mostly of going over the solution to the Fall 2010 final exam which was just added to class materials (an electronic written-up solution is not available). As such if you plan to attend the review session it is highly recommended that you go over the questions in the exam and attempt to solve them beforehand. In addition, please prepare questions about the course material if you have any. If you have requests for particular material to be reviewed or questions about particular homework or practice final questions please email Nathan ahead of recitation so that we may be prepared to address these during the review session.In addition, to allow for more questions in a personal setting following the review session, Nathan's office hours will be moved from Tuesday to directly after the review session.
Finally, we would like to clarify problem 5 on the 2010 final. The modified IP is a relaxation where the LHS of constraints are summed only over i<j.
Announced on 10 December 2011 5:00 p.m. by Nathan Kallus
