[an error occurred while processing this directive]


Kungl Tekniska högskolan / Optimeringslära och systemteori /

[an error occurred while processing this directive]This is a printer-friendly version of https://www.math.kth.se/optsyst/grundutbildning/kurser/SF1811

« [an error occurred while processing this directive]Back
 



SF1811 Optimization, Oct 2017 - Jan 2018

This page contains information about the course; lectures, exercise classes, take-home assignments, etc.
It will be updated during the course.

Exam and partial solutions Apr 05, 2018
Exam and Solutions Jan 10, 2018

Intro Slides
First set of slides from lecture 13
Second set of slides from lecture 13
Summary slides of important concepts


Some formal information about the course: In Swedish. In English.
Lecturer and examiner
Johan Karlsson, johan.karlsson(a)math.kth.se
Office 3550, Lindstedtsv 25, phone 08-790 8440.

Teaching assistants
Tove Odland, odland(a)math.kth.se.
David Ek, daviek(a)kth.se.

Teaching assistants' page. Updated during the course.

Home assignment 2.
This home assignment is on Quadratic optimization.
The deadline is 17:00, December 15, 2017. Only hand in one solution for each group. Each solution should consist of one report (pdf/doc) and a separate file for the code (m-file).
Matlab script for the covariance matrix.

Home assignment 1.
This home assignment is on Linear optimization.
The deadline is 15:00 on Wednesday, November 22, 2017.
The matrices Redarc and Bluearc.

The home assignments should be carried out either alone or together with one other student. A possible way to find another student to work with might be to write a post in the "News feed" ("Nyhetsflödet") on the course web.

Course literature
The main literature for the course is the compendium "Optimization" by Amol Sasane and Krister Svanberg (ASKS), which you can buy at the KTH bookstore. ASKS contains some exercises, for which solutions are available below. Additional exercises:
"Exercises in Optimization" (EXOPT).
We also recommend the book Linear and Nonlinear Optimization, second edition, by Griva, Nash and Sofer. We encourage you to buy this book, especially if you consider taking the follow-up courses SF2812 and SF2822, since it is used as course literature in both these courses. Here you find some information about the book.

Information about the exam

  • The only allowed equipment at the exam is: Pen, eraser and ruler. (Penna, suddgummi och linjal.) In addition, a formula sheet will be handed out in the beginning of the exam. Preliminary version of this formula sheet.
  • Calculator is not allowed at the exam!
  • Dictionary is not allowed at the exam!
  • In order to participate in the exam, you must register for the exam at the KTH "My pages" ("Mina sidor") between certain dates, see
    Studentexpedition matematik or
    Student affairs office for these dates and additional information.
    If you are a PhD student then you cannot use "Mina sidor" to register for the exam. Instead, you should fill in a form and send this by email, between certain dates, to elevexp(a)math.kth.se. Again see
    Studentexpedition matematik or
    Student affairs office for these dates and additional information.
  • The exam consists of 5-6 tasks (exercises) which together can give you 50 credits. Added to these credits are your X bonus credits from this year's home assignments, so your maximal result on the exam is 50+X credit. You are guaranteed to pass if you get 25 credits (including bonus credits).
  • The tasks are written in English, but you may write your answers in either English or Swedish.

    Typical point limits for grades:
    A: 45-54, B: 39-44, C: 34-38, D: 29-33, E: 25-28, Fx: 23-24, F: 0-22.
    Actual point limits may differ with a few points depending on the difficulty of the actual exam (but only to your benefit).

    Schedule: Times and locations
    Detailed schedule

    Preliminary schedule for the lectures 2017

    1. Course intro. Linear Programming (LP).
    2. The Simplex method for solving LP problems.
    3. More on the Simplex method.
    4. Network flows and linear algebra.
    5. Duality and complementarity in LP.
    6. LP duality and a game. Quadratic functions.
    7. QP without constraints. LDLT factorization.
    8. QP with linear equality constraints.
    9. Least Squares problems and the pseudoinverse.
    10. Nonlinear Programming (NLP). Convex problems.
    11. NLP without constraints. Newton and Gauss-Newton.
    12. Inequality constraints and the KKT conditions.
    13. Equality constraints and the Lagrange conditions.
    14. Lagrange relaxation and dual problems.
    15. Summary of the course.

    Preliminary schedule for the exercise classes 2017
    Tove's exercise classes will be in English, in the first of the two scheduled rooms (L51, etc.)
    David's exercise classes will be in Swedish, in the second of the two scheduled rooms (L52, etc.)
    1. Linear Programming and the Simplex method
    2. Network flows and some linear algebra.
    3. Duality and complementarity in LP.
    4. Quadratic Programming.
    5. Linear and nonlinear LS problems.
    6. Convex functions. Newtons method.
    7. The KKT optimality conditions.
    8. Lagrange relaxation and dual problems.

    Recommended reading in the course compendium
    before and after each lecture.

  • Lecture 1: Chapters 1 and 2.
  • Lecture 2: Chapters 3 and 4. Sections 5.1 and 5.2.
  • Lecture 3: The rest of Chapter 5.
  • Lecture 4: Section 7.2. Chapters 23-26.
  • Lecture 5-6: Chapter 6.
  • Lecture 7: Chapters 8, 9 and 27.
  • Lecture 8: Chapter 10.
  • Lecture 9: Chapter 11.
  • Lecture 10: Chapters 8 and 12-15.
  • Lecture 11: Chapters 16-18.
  • Lecture 12: Chapters 20-21.
  • Lecture 13: Chapter 19.
  • Lecture 14: Chapter 22.

    Recommended exercises in ASKS and EXOPT after each lecture.

  • Lecture 1: 2.2, 2.3, 3.3 in ASKS. 1.1, 1.3 in EXOPT.
  • Lecture 2: 4.7 in ASKS. 1.2(a+b), 1.5(a+b), 1.6(a), 1.11(a+b) in EXOPT.
  • Lecture 3: 1.4, 1.8(a+b), 1.13(a+b) in EXOPT.
  • Lecture 4: All exercises i chapter 26 in ASKS. 2.2, 2.5(a) in EXOPT.
  • Lecture 5-6: 1.2(c+d), 1.5(c), 1.6(b), 1.8(c), 1.11(c), 1.13(c) in EXOPT.
  • Lecture 7: 27.22 in ASKS. 5.8 in EXOPT.
  • Lecture 8: 5.1, 5.2, 5.5, 5.9 in EXOPT.
  • Lecture 9: 5.7, 5.4 and 5.6 in EXOPT.
  • Lecture 10: 3.9 (a)-(d) and 6.4 (a)-(c) in EXOPT.
  • Lecture 11: 3.6 and 6.2 in EXOPT. The solved Example 17.1-2 in ASKS.
  • Lecture 12: 6.1, 6.3 and 6.8 in EXOPT.
  • Lecture 13: 19.6-19.9 and 19.11 in ASKS.
  • Lecture 14: 4.1, 4.2, 4.8 and 4.10 in EXOPT.

    Previous exams

  • Jan 10, 2018:     Exam and Solutions
  • Apr 10, 2017:     Exam   Solutions
  • Jan 11, 2017:     Exam   Solutions
  • Mar 14, 2016:     Exam   Solutions
  • Jan 13, 2016:     Exam   Solutions
  • Apr 7, 2015:     Exam   Solutions
  • Jan 14, 2015:     Exam   Solutions
  • Aug 18, 2014:     Exam   Solutions
  • June 3, 2014:     Exam   Solutions
  • Mar 14, 2014:     Exam   Solutions
  • Jan 18, 2014:     Exam   Solutions
  • May 29, 2013:     Exam   Solutions
  • Mar 13, 2013:     Exam   Solutions
  • June 11, 2012:     Exam   Solutions
  • Mar 14, 2012:     Exam   Solutions
  • June 8, 2011:     Exam   Solutions
  • Mar 19, 2011:     Exam   Solutions

    Solutions to the exercises from the lecture notes:

  • Chapter 1 pdf file
  • Chapter 2 pdf file
  • Chapter 3 pdf file
  • Chapter 4 pdf file
  • Chapter 5 pdf file
  • Chapter 6 pdf file
  • Chapter 7 pdf file
  • Chapter 8 pdf file
  • Chapter 9 pdf file
  • Chapter 10 pdf file
  • Chapter 11 pdf file
  • Chapter 13 pdf file
  • Chapter 14 pdf file
  • Chapter 15 pdf file
  • Chapter 16 pdf file
  • Chapter 17 pdf file
  • Chapter 19 pdf file
  • Chapter 20 pdf file
  • Chapter 21 pdf file
  • Chapter 22 pdf file
  • Chapter 23 pdf file
  • Chapter 24 pdf file
  • Chapter 25 pdf file
  • Chapter 26 pdf file

    • Latest update: October 22, 2017, by Johan Karlsson.