Hoppa till huvudinnehållet
Till KTH:s startsida

SF1811 Optimization 6.0 hp

Course memo Autumn 2022-50093

Version 2 – 10/30/2022, 12:42:19 PM

Course offering

Autumn 2022-1 (Start date 31/10/2022, English)

Language Of Instruction

English

Offered By

SCI/Mathematics

Course memo Autumn 2022

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.)

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

Round Facts

Start date

Missing mandatory information

Course offering

  • Autumn 2022-50093

Language Of Instruction

English

Offered By

SCI/Mathematics

Contacts