• Svenska

# Course memo Autumn 2023

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 30 13-15 Q1 Overview of the course, introduction to linear programming (LP) (Chapter 1,2) L2 Tue Oct 31 15-17 D1 The simplex method for solving LP problems (Chapter 3, 4, 5.1, 5.2) L3 Thu Nov 2 15-17 D1 More on the simplex method (Chapter 5) E1 Fri Nov 3 8-10 U21, U31 Linear programming and the simplex method L4 Tue Nov 7 8-10 D1 Network flows and linear algebra (Chapter 7, 23-26) L5 Thu Nov 9 10-12 F1 Duality in LP,  linear algebra, Lagrangian relaxation (Chapter 6, 22-26) E2 Tue Nov 14 10-12 W42, W43 Network flows and some linear algebra L6 Tue Nov 14 13-15 E1 LP duality (Chapter 6) L7 Thu Nov 16 8-10 E1 Convexity, quadratic optimization no constraints, positive definite matrices (Chapter 8, 9, 15, 27) E3 Thu Nov 16 10-12 W37, W38 Duality and complementarity in LP L8 Tue Nov 21 15-17 Q1 Quadratic optimization no constraints and with equality constraints ( Chapter 8, 9, 10,  27) L9 Thu Nov 23 10-12 Q1 Quadratic optimization with equality constraints (Chapter 10, 27) E4 Fri Nov 24 13-15 V1, V2 Quadratic programming L10 Tue Nov 28 15-17 E1 Least-squares problems (Chapter 11) L11 Thu Nov 30 8-10 E1 Nonlinear optimization and Newton's method (Chapter 8, 16) E5 Fri Dec 1 13-15 U31, U41 Linear and nonlinear least-squares problems L12 Tue Dec 5 10-12 Q1 NLP without constraints and with equality constraints (Chapter 8, 12-15, 18, 19) L13 Wed Dec 6 10-12 D1 Equality constraints and the Lagrange conditions, Karush-Kuhn-Tucker conditions and inequality constraints (Chapter 19, 20-21) E6 Fri Dec 8 10-12 U31,U51 Convex functions. Newton's method L14 Mon Dec 11 13-15 E1 Lagrangian relaxation (Chapter 21, 22) L15 Wed Dec 13 10-12 E1 Lagrangian relaxation and summary of the course (Chapter 22) E7 Thu Dec 14 15-17 W37, W38 The KKT optimality conditions E8 Fri Dec 15 13-15 W37, W38 Lagrangian 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

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 (one bonus point): Tuesday November 14, 2023
• Homework assignment 2 (one bonus point): Monday November 27, 2023
• Homework assignment 3 (two bonus points): Monday December 11, 2023.

Irrespective of bonus point, reports for homework assignments 1, 2 and 3 must be handed in by Friday December 15, 2023, for them to be handled jointly with the January exam. In case a report handed in is not deemed acceptable, the group has the chance to hand in an updated report by the date of the January exam. It will also be possible to hand in reports for the homework assignments by the date of the re-exam. A student who has not completed all three homework assignment by the date of the re-exam is referred to the course offering of next academic year.

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.

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 understand, with purpose as explained in the previous paragraph. The particular format of the report is not important.

#### 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 Thursday January 11, 2024, 8.00-13.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

30 Oct 2023

### Course offering

• Autumn 2023-50084
• Doktorand Autumn 2023-51213

English

SCI/Mathematics