KTH /
Teknikvetenskap
/
Matematik
/
Optimeringslära och systemteori
SF1811 Optimization, Oct 2017  Jan 2018
This page contains information about the course;
lectures, exercise classes, takehome assignments, etc.
It will be updated during the course.
Intro Slides
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 08790 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 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 followup 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 56 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.
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 GaussNewton.

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 2326.
Lecture 56: Chapter 6.
Lecture 7: Chapters 8, 9 and 27.
Lecture 8: Chapter 10.
Lecture 9: Chapter 11.
Lecture 10: Chapters 8 and 1215.
Lecture 11: Chapters 1618.
Lecture 12: Chapters 2021.
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 56:
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.12 in ASKS.
Lecture 12:
6.1, 6.3 and 6.8 in EXOPT.
Lecture 13:
19.619.9 and 19.11 in ASKS.
Lecture 14:
4.1, 4.2, 4.8 and 4.10 in EXOPT.
Previous exams
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
June 7, 2010:
Exam
Solutions
Mar 20, 2010:
Exam
Solutions
Aug 25, 2009:
Exam
Solutions
June 8, 2009:
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.
