Course syllabus adopted 2023-02-14 by Head of Programme (or corresponding).
Overview
- Swedish nameOlinjär optimering
- CodeTMA947
- Credits7.5 Credits
- OwnerMPENM
- Education cycleSecond-cycle
- Main field of studySoftware Engineering, Mathematics
- DepartmentMATHEMATICAL SCIENCES
- GradingTH - Pass with distinction (5), Pass with credit (4), Pass (3), Fail
Course round 1
- Teaching language English
- Application code 20128
- Open for exchange studentsYes
Credit distribution
Module | Sp1 | Sp2 | Sp3 | Sp4 | Summer | Not Sp | Examination dates |
|---|---|---|---|---|---|---|---|
| 0103 Laboratory 1.5 c Grading: UG | 1.5 c | ||||||
| 0203 Examination 6 c Grading: TH | 6 c |
|
In programmes
- MPCAS - COMPLEX ADAPTIVE SYSTEMS, MSC PROGR, Year 1 (compulsory elective)
- MPCAS - COMPLEX ADAPTIVE SYSTEMS, MSC PROGR, Year 2 (elective)
- MPDSC - DATA SCIENCE AND AI, MSC PROGR, Year 1 (compulsory)
- MPENM - ENGINEERING MATHEMATICS AND COMPUTATIONAL SCIENCE, MSC PROGR, Year 1 (compulsory)
- MPICT - INFORMATION AND COMMUNICATION TECHNOLOGY, MSC PROGR, Year 1 (compulsory elective)
- MPICT - INFORMATION AND COMMUNICATION TECHNOLOGY, MSC PROGR, Year 2 (elective)
- MPSYS - SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Year 1 (compulsory elective)
- MPSYS - SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Year 2 (elective)
- TKAUT - AUTOMATION AND MECHATRONICS ENGINEERING, Year 3 (elective)
- TKGBS - GLOBAL SYSTEMS ENGINEERING, Year 3 (compulsory elective)
- TKTEM - ENGINEERING MATHEMATICS, Year 3 (elective)
Examiner
Axel Ringh- Assistant Professor, Applied Mathematics and Statistics, Mathematical Sciences
Eligibility
General entry requirements for Master's level (second cycle)Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.
Specific entry requirements
English 6 (or by other approved means with the equivalent proficiency level)Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.
Course specific prerequisites
Linear algebra, analysis in one and several variables
Aim
The aim of the course is to give a good theoretical foundation for some of the most important areas of optimisation: convex optimisation, linear optimisation, and nonlinear optimisation. The course treats the basics principles for analyzing the properties of an optimisation problem, and the characterization of feasible points that are (locally) optimal. This theory is used to develop a number of examples of optimisation methods, that can be used to solve instances of practical optimisation problem. The course also aims to give some practical training in mathematical modelling and problem solving using optimisation.Learning outcomes (after completion of the course the student should be able to)
The goal is that you, after completing the course, should understand parts of the theory of optimality, duality, and convexity, and their interrelations. In this way, you will be able to analyze many types of optimization problems occurring in practice and both classify them and provide guidelines as to how they should be solved. The latter is the more practical goal of an otherwise mainly theoretical course.More precisely, after completing the course you should be able to:
- state and explain the most important concepts in convex analysis, convex optimization, and duality, and be able to apply the theory on concrete examples.
- state and explain the basics of necessary and sufficient optimality conditions, in particular the KKT conditions, and be able to utilize the theory to analyze and solve concrete examples.
- analyze linear programming problems using concepts such as duality and sensitivity; solve linear programming programs using the simplex method and explain how the method works.
- explain notions such as descent and feasible direction, and use these concepts to explain the principles behind, to analyze, and to apply classical optimization methods, e.g., steepest descent, variations of Newton's method, the Frank-Wolfe method, and penalty methods; be able to specify conditions under which these methods converge.
- formulate relevant parts of a real-world problem in terms of a mathematical optimization model, analyze the model using appropriate tools and methods, and apply appropriate solution algorithms.
Content
This basic course in optimization describes the most relevant mathematical principles that are used to analyze and solve optimization problems in continuous variables. A rough separation and overview of the content is as follows.- Convex analysis: convex set, polytope, polyhedron, cone, representation theorem, extreme point, Farkas Lemma, convex function
- Optimality conditions and duality: global/local optimum, existence and uniqueness of optimal solutions, variational inequality, Karush-Kuhn-Tucker (KKT) conditions, complementarity conditions, Lagrange multiplier, Lagrangian dual problem, global optimality conditions, weak/strong duality
- Linear programming (LP): LP models, LP algebra and geometry, basic feasible solution (BFS), the Simplex method, LP duality, optimality conditions, strong duality, complementarity, interior point methods, sensitivity analysis
- Nonlinear optimization methods: direction of descent, line search, (quasi-)Newton methods, Frank--Wolfe method, gradient projection, exterior and interior penalty methods.
Organisation
Lectures, exercises, two computer exercises, and a project assignment that comprises mathematical modelling and the solution of a concrete optimization problem med industrial relevance. Additionally, there might be voluntary elements that could give bonus points for the written final exam.Literature
"An Introduction to Continuous Optimization", by Niclas Andréasson, Anton Evgrafov, and Michael Patriksson, with Emil Gustavsson, Zuzana Nedělková, Kin Cheong Sou, and Magnus Önnheim, third edition, published by Studentlitteratur in 2016.
Examination including compulsory elements
Project assignment (laboratory), computer exercises, a written final exam. There might be voluntary elements that could give bonus points for the written final exam.
The course examiner may assess individual students in other ways than what is stated above if there are special reasons for doing so, for example if a student has a decision from Chalmers on educational support due to disability.