KTH /
Teknikvetenskap
/
Matematik
/
Optimeringslära och systemteori
SF1811 Optimization, Oct 2016  Jan 2017
This page contains information about the course;
lectures, exercise classes, takehome assignments, etc.
It will be updated during the course.
Exam, April 10, 2017.
Solutions, April 10, 2017.
Exam, Jan 11, 2017.
Solutions, Jan 11, 2017.
Some formal information about the course:
In Swedish.
In English.
Lecturer and examiner
Krister Svanberg ,
krille(a)math.kth.se
Office 3531, Lindstedtsv 25, phone 08790 7137.
Teaching assistants
Tove Odland,
odland(a)math.kth.se.
Alexander Aurell,
aaurell(a)kth.se.
Teaching assistants' page. Updated during the course.
Home assignments
Results on the home assignments, and bonus
points for the exam,
in alphabetic order.
If it is not clear who you are on the list,
send an email to the examiner.
Your home assignments 1 and 2 are available at the Student affair office.
Note 1: The points from Home assignments 1 and 2 will be added,
whereafter the sum will be rounded up to an integer. Exampel:
1.5p + 2.0p = 3.5p will give you 4 bonus point.
Note 2: These bonus points
can be used on and only on the two exams in SF1811 during 2017.
(January and April.)
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.
Preliminary schedule for the lectures 2016
(Date, time, room, subject.)
1. 
Mo 31/10 
1012 
B2 
Course intro. Linear Programming (LP). 
2. 
Tu 1/11 
0810 
B2 
The Simplex method for solving LP problems. 
3. 
We 2/11 
1517 
B2 
More on the Simplex method. 
4. 
Mo 7/11 
1012 
B2 
Network flows and linear algebra. 
5. 
We 9/11 
1416 
B2 
Duality and complementarity in LP. 
6. 
Mo 14/11 
1012 
D2 
LP duality and a game. Quadratic functions.

7. 
Tu 15/11 
0810 
D2 
QP without constraints. LDLT factorization.

8. 
Th 17/11 
1517 
B2 
QP with linear equality constraints.

9. 
Mo 21/11 
1012 
B2 
Least Squares problems and the pseudoinverse.

10. 
We 23/11 
1517 
B2 
Nonlinear Programming (NLP). Convex problems.

11. 
Mo 28/11 
1012 
B2 
NLP without constraints. Newton and GaussNewton.

12. 
We 30/11 
1517 
B2 
Inequality constraints and the KKT conditions.

13. 
Mo 5/12 
1012 
B2 
Equality constraints and the Lagrange conditions.

14. 
We 7/12 
1517 
B2 
Lagrange relaxation and dual problems.

15. 
Tu 13/12 
0810 
B2 
Summary of the course.

Preliminary schedule for the exercise classes 2016
Tove's exercise classes will be in English, in the first of the two
scheduled rooms (L51, etc.)
Alexander's exercise classes will be in Swedish, in the second of the two
scheduled rooms (L52, etc.)
1. 
Th 3/11 
1517 
L51,L52 
Linear Programming and the Simplex method 
2. 
Th 10/11 
1416 
Q33,Q34 
Network flows and some linear algebra. 
3. 
We 16/11 
1517 
L51,L52 
Duality and complementarity in LP. 
4. 
Tu 22/11 
0810 
D34,E52 
Quadratic Programming. 
5. 
Tu 29/11 
0810 
L51,L52 
Linear and nonlinear LS problems. 
6. 
Tu 6/12 
0810 
L51,L52 
Convex functions. Newtons method. 
7. 
Mo 12/12 
1012 
L51,L52 
The KKT optimality conditions. 
8. 
We 14/12 
1517 
L51,L52 
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
March 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
March 13, 2013:
Exam
Solutions
June 11, 2012:
Exam
Solutions
March 14, 2012:
Exam
Solutions
June 8, 2011:
Exam
Solutions
March 19, 2011:
Exam
Solutions
June 7, 2010:
Exam
Solutions
March 20, 2010:
Exam
Solutions
August 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
Click for new htmlstyle.
Latest update:
November 22, 2016, by Krister Svanberg.
