Skip to main content

FSF3822 Applied Nonlinear Optimization 7.5 credits

This graduate course is primarily intended for graduate students in optimization and systems theory, or other graduate students with a good background in optimization.

Choose semester and course offering

Choose semester and course offering to see information from the correct course syllabus and course offering.

Headings with content from the Course syllabus FSF3822 (Spring 2019–) are denoted with an asterisk ( )

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.

Course disposition

Lectures and project work

Literature and preparations

Specific prerequisites

A Master degree including at least 30 university credits (hp) in in Mathematics (Calculus, Linear algebra, Differential equations and transform method), and further at least  6 hp in Mathematical Statistics, 6 hp in Numerical analysis and 6 hp in Optimization.

Recommended prerequisites

No information inserted

Equipment

No information inserted

Literature

Linear and Nonlinear Optimization, second edition, by I. Griva, S. G. Nash och A. Sofer. SIAM. Additional course material from the department.

Examination and completion

If the course is discontinued, students may request to be examined during the following two academic years.

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.

Other requirements for final grade

Projects, Written examination.

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Profile picture Anders Forsgren

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

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web FSF3822

Offered by

SCI/Mathematics

Main field of study

No information inserted

Education cycle

Third cycle

Add-on studies

No information inserted

Contact

Anders Forsgren (andersf@kth.se)

Postgraduate course

Postgraduate courses at SCI/Mathematics