This graduate course is primarily intended for graduate students in optimization and systems theory, or other graduate students with a good background in optimization.
Course memo Spring 2024
Course presentation
Headings denoted with an asterisk ( * ) is retrieved from the course syllabus version Spring 2019
Content and learning outcomes
Course contents
Theory and methods:
The simplex method and interior point methods for linear programming. Utlization of problem structure, e.g., decomposition and column generation. Stochastic programming, methods and utilization of problem structure. Branch-and-bound methods for integer programming. Lagrangian relaxation and subgradient methods for integer programming problems with special structure.
Projects:
This part of the course consists of modeling practical optimization problems and using available optimization software to solve them. The projects are carried out in small groups. An important aspect of the course is cooperation within the group as well as presentations in talking and in writing.
Intended learning outcomes
The overall goal of the course is on the one hand that the student should master models, methods and theory for different forms of nonlinear optimization, on the other hand that the student should be able to model and by a suitable modeling language solve realistic optimization problems, as well as presenting the results orally and in writing.
Upon completion of the course the student should be able to:
- Explain how the steepest-descent method, the method of conjugate gradients and quasi-Newton methods fork for minimizing a strictly convex quadratic function.
- Explain how active-set methods for convex quadratic programs work.
- Explain how sequential quadratic programming methods work.
- Explain how primal-dual interior methods for quadratic and nonlinear programming problems work.
- From a problem description formulate a nonlinear programming problem and solve it using the modeling language used in the course.
- Interpret the solutions of the solved problems by fundamental concepts such as sensitivity analysis.
- Given suitable assumptions derive optimality conditions for nonlinear programming problems.
- Make use of suitable optimality conditions to determine if a given point is a local, or even a global, minimizer for a given nonlinear programming problem.
- Explain if a solution of a real problem is a local or a global solution, given properties of the problem functions.
- Explain what relaxation is.
- Relate the modeling to the student's own field of research.
Students who have acquired deeper knowledge of the course are in addition expected to:
- In applicable cases be able to determine the quality of solutions by relating to convex relaxations of the problems.
- Explain how quasi-Newton methods for nonlinear programming problems work.
- Give examples on how sequential quadratic programming methods and interior methods may be modified to nonconvex problems and state fundamental aspects of merit functions in such methods.
- Define semidefinite programming problems and explain how primal-dual methods for semidefinite programming work.
Additional Requirements for PhD students
The course SF3822 is a PhD level version of the course SF2822.
The PhD level version of the course is primarily intended for students from PhD programs other than Applied and Computational Mathematics.
In addition to the requirements of SF2822, a passing grade in FSF3822 requires:
- Completion of advanced exercises in the two projects that are handed out during the course.
- Completion of an additional assignment. The assignment is to create a prototype of a modeling project, such as the two ones that have been given in the course. The project should be related to the field of research of the PhD student, and it should be given on a level such that it is suitable for use in the course, by modeling in GAMS, and with basic and advanced exercises.
A prototype should be derived, which means an explanation of the problem and the questions related to the problem. This need not be on such a detailed level that a GAMS model is created, but it should be on a level such that a GAMS model could be made on the basis of the description. (No GAMS model is expected.)
The description should be sent to the examiner by e-mail no later than three weeks after the exam. The PhD student will then be called to a meeting witht the examiner where the project proposal is dicussed.
The intent is to give a bridge to the PhD student's research, and see some of the motivation for taking the course.
For further information, we refer to SF2822 Applied Nonlinear Optimization.
PhD students are welcome to take the master level course SF2822 instead of SF3822.
Preparations before course start
Literature
Linear and Nonlinear Optimization, second edition, by I. Griva, S. G. Nash och A. Sofer. SIAM. Additional course material from the department.
Support for students with disabilities
Students at KTH with a permanent disability can get support during studies from Funka:
Examination and completion
Grading scale
P, F
Examination
- PRO1 - Project work, 3.0 credits, Grading scale: P, F
- TEN1 - Written exam, 4.5 credits, Grading scale: P, 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 section below is not retrieved from the course syllabus:
Project work ( PRO1 )
Written exam ( TEN1 )
Other requirements for final grade
Projects, Written examination.
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
Round Facts
Start date
18 Mar 2024
Course offering
- Spring 2024-60863
Language Of Instruction
English