SF1811, SF1841 Optimization - Course information

Course home page adress: http://www.math.kth.se/optsyst/studinfo/kurser/SF1811/.

Instructor:

Per Enqvist,
email: penqvist@math.kth.se ,
office nr. 3705, Lindstedtsv 25,
phone nr. +46 (0)8 790 6298
The lectures will be held in english.

Teaching assistants:

Course Literature

The main literature for the course is a complete set of lecture notes that have been prepared especially for this course, namely:

      Optimization
      by Amol Sasane and Krister Svanberg.

which you can buy from the student office
("Matematiks studentexpedition", Lindstedtsvägen 25.)

These notes also contain exercises, and in the exercise classes a selected sample of these will be discussed. The solutions to all the exercises from the lecture notes are available on the homepage.

A compendium of extra exercises is also available at the student office
      Exercises in Optimization (SF1811/SF1841).

We also recommend the following book: Linear and Nonlinear Programming, second edition, by Griva, Nash och Sofer.
We encourage you to buy this book, especially if you consider taking the follow-up courses SF2812 and SF2822, since it is used as course literature in both courses. Here you find Information on the cheapest way to import it from USA that we know of.

Further material will be available on the homepage.

What is optimization?

Optimization theory deals with finding the "best" solution in a set of feasible solutions. The solutions are represented by variables and the feasible solutions are characterized by constraints on the variables. What is "best" is quantified by an objective function that for each feasible solution determines a number (ranking), e.g., the total amount of traffic that passes through a network. The problem to maximize a general objective function over a general feasible set is difficult. In this course we concentrate on optimization problems with continuous variables, where the objective function is linear, quadratic or (convex) non-linear, and the constraints are linear or (convex) non-linear. This theoretical framework has found numerous applications in many differents areas, such as crew-scheduling for airplane personel, radiation therapy planning for cancer patients, risk management for portfolios, internet traffic control and structural optimization for mechanism design.

Aim

The overall purpose of the course is that the student should get well acquainted with basic concepts, theory, models and solution methods for optimization. Furthermore, the student should get basic skills in modelling and computer based solving of various applied optimization problems. To pass the course, the student should attain most of the following aims:

• Explain basic concepts and theory for optimization, in particular the modelling concept variables-objective-constraints and some basic theoretical properties of convex optimization problems, and decide whether a given problem is convex or not.

• Apply and analyze the algorithms considered in the course. This ability can, e.g., be demonstrated by solving (small) problems with pen and paper.

• Analyze potential optimal solutions to nonlinear constrained problems.

  • State relevant optimality conditions and use these to decide whether a given feasible solution to a given convex problem with constraints is an optimal solution or not.

  • Calculate all the solutions to the Karush-Kuhn-Tucker optimality conditions of a given (not so complex but possibly nonconvex) problem with nonlinear objective- and constraint functions, and decide whether any of these is a global optimal solution.

• Explain the concept Lagrangian relaxation, and use this tool for solving separable convex optimization problems.

• Use linear algebra, in particular fundamental subspaces and factorizations, to, e.g., describe the feasible sets of linearly constrained programs.

• Formulate optimization problems on a tractable mathematical form, solve them using your own or commercial software, and then evaluate and present the result in a written or oral format.

Syllabus

Examples of applications and modelling training. Basic concepts and theory for optimization, in particular theory for convex problems. Some linear algebra in R^n, in particular bases for the four fundamental subspaces corresponding to a given matrix. Linear optimization. Simplex algorithm. Duality theory. Optimization of flows in networks, especially minimum cost network flows. Quadratic optimization with 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. Lagrangian relaxation.

Examination

Home assignments:

There will be two voluntary home assignments and a poster session. These assignments are usually appreciated by the students and the aim is to provide an opportunity for deeper understanding of the subject. The exercises will be solved using a computer and the optimization toolbox in Matlab. The results of the home assignment should be presented in a brief written report, and some randomly chosen groups will also present their work in class. The poster session will be used to present an open-ended formulation problem assignment.
All of this may grant up to a total of 5 (2+2+1) bonus points on the final exam. These bonus points will be valid for both of the exams held for this course during 2013. More information will be posted on the home page.

Written examination (TEN1, 6hp):

The examination is scheduled at March 13, 2012, at the time 08.00-13.00. You should sign up to the exam on "My Pages". The maximal number of points on the exam is 55, including the 5 bonus point that can be obtained from the home assignments. Preliminary grading:
44-55 points for an A, 38-43 points for a B, 33-37 points for a C,
28-32 points for a D, 25-27 points for an E, 23-24 points for Fx.
A short table of equations is handed out at the exam and is the only aid allowed.

An Fx grade may be converted to an E grade by a successful completion of further written and oral tests. This process has to be completed within three weeks of the date of notification of grades, so please contact the instructor asap by email.

Welcome to the course!