Optimization 1 / MN1

Syllabus

Message board

2006-12-07: The October exam with solution is now available on the old-exams-page

2006-11-17: I have finally graded the exam. People that passed the exam and explicitly agreed on the exam cover sheet to the publishing of their name are listed here. The exams can be picked up at the IT office.

2006-11-03: I will be on travel during next week. The exam results will be posted during week 46 (starting Nov 13).

2006-10-30: Regrettfully, it will unfortunately take some time until the final exam is graded, due to serious time constraints (miscellaneous travel plus that I am immediately starting teaching again)

2006-10-24: One student has pointed out a mistake (now corrected) in the syllabus, namely in the table where the relevant sections in the book are listed. For lecture 5, the relevant sections should be 6.1-6-2, and 6.4 (covering duality and sensitivity for LP) and nothing else. Thanks for letting me know.

2006-09-10: On public demand, the last lecture, originally scheduled for the day before the exam, has been moved to Wednesday, October 18, 13.15-15.00 in room 2446.

2006-10-05: Some people have requested that the last lecture, October 24, which is given the day before the exam should be moved to some day the week before. (I will do problems from old exam during that lecture.) This is fine with me. Let us decide on this on Monday's lecture. If it is a majority for a move, we will do so.

2006-10-02: You can now view a collection of old exams (see the link on the bottom of the page).

2006-10-02: You can now pick up the graded Assignmen 1 from the IN box for Optimization I at the second floor in house 2. Some of you need to make some corrections. Please remember to attached the old report when you resubmit a corrected report. (I cannot always remember exactly what should be corrected.)

2006-09-19: Assignment number 2 will be handed out on Friday's lecture (Sept. 22) and will be uploaded here the same day, after the lecture. The due date for assignment 1 is also Sept. 22. Note that you can deliver your assignment in the IN box for Optimization I at the second floor in house 2. Since I will not check the IN box until Monday morning (Sept. 25), I will regard all reports that are in the box by that time as delivered in time. Thus, in practice, the deadline is extended until Sunday September 24.

2006-09-12: Emmet Caulfield has kindly offered to take pictures of the blackboard notes and to put jpg's online for download. You can find the pictures at http://polacksbacken.net/opt1/. You can only access the pictures from an University IP address.

I (Martin) will add messages here throughout the course

Additional Lecture Material

Here you can download pdf-files with the viewgraphs that are shown during lectures. These are either reviews from previous lecture or material complementary to the lecture notes given on the black board.

Lecture 1: Examples of Linear Programs
Lecture 2: Definition of basic solutions. The fundamental theorem of linear programming.
Lecture 3: Review: The geometry of feasible sets.
Lecture 4: Review: The simplex method.
Lecture 5: Termination and initialization of the simplex algorithm
Lecture 6: Review: Duality.
Lecture 7: Introduction to nonlinear optimization
Lecture 8: Review: Intro to nonlinear optimization
Lecture 9: Review: Newton's method for minimization. Modified Cholesky
Lecture 10: Review: Globalization/Line Search and the Steepest-Descent Method
Lecture 11: Review: Quasi-Newton/quadratic forms
Lecture 12: Review: Methods for least-squares problems
Lecture 13: Handout: Geometric motivaition of the KKT conditions
Lecture 14: Review: the KKT conditions. Handout: Quadratic Programs (QPs)
Lecture 15: Review: Optimality Conditions for NLP's. Handout: Algorithms for NLP's

Exercises

Suggested problems from the textbook.

  • p24: 2, 3
  • p52: 3
  • p69: 1 (a few at least)
  • p75: 1-3
  • p83: 1, 2
  • p105: 2 (missprint x3 >=0 in (d)), 3, 5
  • p157-159: 1, 4, 12
  • p299-302: 1, 4, 5, 7, 10
  • p306-308: 4, 6, 7, 12
  • p311-312: 4, 6
  • p323-327: 2, 3, 4, 7, 8
  • p344-347: 1, 2, 5, 11, 12
  • p356-358: 1, 2, 3, 7, 8
  • p417-418: 2, 8, 9
  • p434: 1-4
  • p437: 1, 2
  • p445-446: 1, 2, 8, 9
  • p453: 3, 4
  • p543: 1, 2
  • p518: 4

Assignments

Absolute deadline for this years assignments: November 11

You can view the status of the assignments here. You will need to supply a user name and password: First choose the login directory Anonymous from the drop-down menu (välj inloggningskatalog Anonym från rullgardinsmenyn), then use the login name opt1 plus the password that I told you in class. Email me for it if you don't remember it. Pick up corrected assignments in the outbox on the second floor in house 2.

Rules for the assignments:

  • Hand in a written report containing a short presentation of the problem, results, discussion, source code, and a print-out of the result from your Matlab sessions. A hand written report is OK for all parts except for the source code and the print-out of the runs. Answer all question and comment your results. If the report is incomplete, I will return it for completion before starting to grade it.
  • Please hand in the report in paper form (rather than by email) either to me personally or to the box marked "IN", Optimization 1. The box is located at the second floor in house 2.
  • You may work alone or in groups of two (not three). Both persons in a group should contribute to the solution and the report. Discussions between the groups are encouraged. If you receive substantial help from another group, say so in the report. You are not allowed to copy solutions or computer codes from others.
  • If an assignment is incomplete or contains serious misstakes, the report will be returned in the box marked "OUT", Optimization 1 for correction and completion. The box is located at the second floor in house 2. When you return the new or corrected report, please submit also the old one.
  • I prefer answering questions in person or by phone (instead of email). I do not wish to debug your code.
  • Use the cover page below for the report

Cover page for reports

Assignment1: Linear programming. 0.5 bonus point on final exam if correct solution handed in September 22 at the latest.

Assignment2: An Inverse Problem for Heat Conduction. 0.5 bonus point on final exam if correct solution handed in October 9 at the latest. You will need the Matlab m-files temperatures.m and param.m.

Assignment3: Portfolio optimization. 0.5 bonus point on final exam if correct solution handed in October 24 at the latest.

Old exams

You can find a collection of old exams with solutions here.

Note that the course content changed last year, compared to previous years. This and last year's syllabus does not include global optimization (typically question 6 on the old exams), nor do we now cover network problems. Instead there is now at least one problem on nonlinear optimization with constraints