SF1811 is a basic course on optimization.
Course memo Autumn 2022
Course presentation
Headings denoted with an asterisk ( * ) is retrieved from the course syllabus version Autumn 2019
Content and learning outcomes
Course contents
- Examples of applications of optimization and modelling training.
- Basic concepts and theory for optimization, in particular theory for convex problems.
- Linear algebra in Rn, in particular bases for the four fundamental subspaces corresponding to a given matrix, and LDLT-factorization of a symmetric positive semidefinite matrix.
- Linear optimization, including duality theory.
- Optimization of flows in networks.
- Quadratic optimization with linear equality constraints.
- Linear least squares problems, in particular minimum norm solutions.
- Unconstrained nonlinear optimization, in particular nonlinear least squares problems.
- Optimality conditions for constrained nonlinear optimization, in particular for convex problems.
- Lagrangian relaxation.
Intended learning outcomes
After completing the course students should for a passing grade be able to
- Apply basic theory, concepts and methods, within the parts of optimization theory described by the course content, to solve problems
- Formulate simplified application problems as optimization problems and solve using software.
- Read and understand mathematical texts about for example, linear algebra, calculus and optimization and their applications, communicate mathematical reasoning and calculations in this area, orally and in writing in such a way that they are easy to follow.
For higher grades the student should also be able to
- Explain, combine and analyze basic theory, concepts and methods within the parts of optimization theory described by the course content.
Preliminary schedule
Type | Day | Date | Time | Room | Subject |
L1 | Mon | Oct 31 | 8-10 | D1 | Overview of the course, introduction to linear programming (LP) (Chapter 1,2) |
L2 | Wed | Nov 2 | 10-12 | M1 | The simplex method for solving LP problems (Chapter 3, 4, 5.1, 5.2) |
L3 | Thu | Nov 3 | 8-10 | D1 | More on the simplex method (Chapter 5) |
E1 | Fri | Nov 4 | 8-10 | U31, U41 | Linear programming and the simplex method |
L4 | Wed | Nov 9 | 8-10 | D1 | Network flows and linear algebra (Chapter 7, 23-26) |
L5 | Fri | Nov 11 | 8-10 | D1 | Duality in LP, linear algebra, Lagrange relaxation (Chapter 6, 22-26) |
E2 | Mon | Nov 14 | 8-10 | U21, U31 | Network flows and some linear algebra |
L6 | Wed | Nov 16 | 10-12 | M1 | LP duality (Chapter 6) |
L7 | Thu | Nov 17 | 8-10 | F2 | Convexity, quadratic optimization no constraints, positive definite matrices (Chapter 8, 9, 15, 27) |
E3 | Fri | Nov 18 | 8-10 | W42, W43 | Duality and complementarity in LP |
L8 | Mon | Nov 21 | 8-10 | M1 | Quadratic optimization no constraints and with equality constraints ( Chapter 8, 9, 10, 27) |
L9 | Wed | Nov 23 | 10-12 | F2 | Quadratic optimization with equality constraints (Chapter 10, 27) |
E4 | Thu | Nov 24 | 15-17 | U21, U31 | Quadratic programming |
L10 | Wed | Nov 30 | 10-12 | M1 | Least-squares problems (Chapter 11) |
L11 | Thu | Dec 1 | 8-10 | D1 | Nonlinear optimization and Newton's method (Chapter 8, 16) |
E5 | Fri | Dec 2 | 8-10 | U41, U51 | Linear and nonlinear least-squares problems |
L12 | Mon | Dec 5 | 8-10 | E1 | NLP without constraints and with equality constraints (Chapter 8, 12-15, 18, 19) |
L13 | Wed | Dec 7 | 10-12 | F2 | Equality constraints and the Lagrange conditions, Karush-Kuhn-Tucker conditions and inequality constraints (Chapter 19, 20-21) |
E6 | Fri | Dec 9 | 8-10 | W37, W38 | Convex functions. Newton's method |
L14 | Mon | Dec 12 | 8-10 | M1 | Lagrange relaxation (Chapter 21, 22) |
L15 | Wed | Dec 14 | 10-12 | D1 | Lagrange relaxation and summary of the course (Chapter 22) |
E7 | Thu | Dec 15 | 8-10 | W42, W43 | The KKT optimality conditions |
E8 | Fri | Dec 16 | 8-10 | W42, W43 | Lagrange relaxation and dual problems |
Chapter references refer to the compendium by Svanberg and Sasane.
Information on exercise sessions is given in Canvas.
Preparations before course start
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 here. Additional exercises are provided in "Exercises in Optimization" (EXOPT), which is available in Canvas.
We also recommend the book Linear and Nonlinear Optimization, second edition, by I. Griva, S. G. Nash och A. Sofer, SIAM, 2009. We encourage you to buy this book, especially if you consider taking the follow-up courses SF2812 and/or SF2822, since it is used as course literature in both these courses.
(The book can be ordered from several places. Please note that you can become a SIAM member for free and obtain a discount at the SIAM bookstore.)
Support for students with disabilities
Students at KTH with a permanent disability can get support during studies from Funka:
Examination and completion
Grading scale
A, B, C, D, E, FX, F
Examination
- INL1 - Home assignment, 2.0 credits, Grading scale: P, F
- TEN2 - Exam, 4.0 credits, Grading scale: A, B, C, D, E, FX, F
Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.
The examiner may apply another examination format when re-examining individual students.
The examiner decides, in consultation with KTHs Coordinator of students with disabilities (Funka), about any customized examination for students with documented,lastingdisability. The examiner may allow another form of examination for reexamination of individual students.
The section below is not retrieved from the course syllabus:
INL1 - Home assignment, 2.0 credits
There are three compulsory homework assignments. A homework assignment is carried out in a group of one or two students, where the students select the groups. For each homework assignment, a group should hand in a written report in Canvas. A report which is handed in by the following due dates makes the group's members eligible for bonus points for the final exams of this academic year:
- Homework assignment 1: Tuesday November 15, 2022
- Homework assignment 2: Monday November 28, 2022
- Homework assignment 3: Monday December 12, 2022.
Homework assignments 1 and 2 give 1 credit each and assignment three gives 2 bonus credits. To pass the 2.0 hp homework assignments examination for this academic year, the reports need to be handed in no later than by the date for the reexam.
The aim of the homework assignments is to practice using mathematical concepts and methods and to practice report writing. The purpose of the report is to explain the problem, give theoretical background and present results on a level which is suitable for a master student who has taken the course SF1811 but not done this particular homework assignment. The presentation should be similar to the presentation of examples in the course literature. Write using your own words and include additional explanations for the steps. This means that a solution with only formulas is not acceptable.
The report does not have to be long, probably less than five pages. If applicable, Matlab code should be included, e.g in an appendix. The most important aspects are that the report is correct and that a reader is able to learn something. The form of the report is not important, e.g. it does not matter if the there is table of contents or a section "conclusion". In the grading, it is taken into account how well the report explains the problem, describes the theoretical background, and presents the results.
TEN2 - Exam, 4.0 credits
The final exam will consist of five problems that all together give a maximal score of 50 credits plus bonus credits. You are guaranteed to pass with 25 credits, including bonus credits. The questions in the exam will be in English and you may write your answers in English or Swedish. Typically the grades will be: E at least 25, D 29, C 34, B 39, and A at least 45 credits, including bonus credits.The exam will include an alternative question taken from a list of theory questions, available in Canvas. For one of the questions, there will be two alternatives: one standard question and one specific theory question from the list. It is the student's choice which of the alternatives to this question that is handed in.
The grade Fx is normally given for 23 or 24 points on the final exam. An Fx grade may be converted to an E grade by a successful completion of two supplementary exercises, that the student must complete independently. One exercise among the theory exercises handed out during the course, and one exercise which is similar to one exercise of the exam. These exercises are selected by the instructor, individually for each student. It is the responsitibility of the student to contact the instructor to initiate such a process. Solutions have to be handed in to the instructor and also explained orally within three weeks of the date of notification of grades.
No aids, except of course pen, pencil, eraser and ruler, are allowed in the exam. E.g. calculators or dictionaries are not allowed. A formula sheet, which is available in Canvas, will be included in the exam.
The final exam is given Wednesday January 11, 2023, 14.00-19.00. Registration for the exam has to be made in advance according to KTH rules.
Ethical approach
- All members of a group are responsible for the group's work.
- In any assessment, every student shall honestly disclose any help received and sources used.
- In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.
Further information
No information inserted
Contacts
Course Coordinator
Teachers
Teacher Assistants
Examiner
Round Facts
Start date
31 Oct 2022
Course offering
- Autumn 2022-50093
Language Of Instruction
English