Kungl Tekniska högskolan / Optimeringslära och systemteori /

« [an error occurred while processing this directive]Back
 

SF1811 Optimization for F / Optimeringslära för F 2009

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

Instructor:

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

Teaching assistants:

Study material:

• Book: Linear and Nonlinear Programming, second edition, by Griva, Nash och Sofer.
  It is encouraged to buy the new improved book, especially since the same book is also used in the continuation courses SF2812 and SF2822. Information on how to import it from USA is available on the home page. If you find it too complicated, the print-outs from the student office works too.

The following material can be bought at the student office at the math. department, Lindstedtsvägen 25.

• Print-outs from selected parts of the old book, first version of Nash and Sofer are sold.

• Compendium: Quadratic optimization.

• Compendium: Exercises in SF1841.

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.

Schedule for the classes

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.
The first written home assignment should be handed in at the beginning of the exercise class February 4, and oral presentations will also be given during this class. For the second home assignment, the deadline is March 4. The poster session will be held Febraury 18.
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 2009. More information will be posted on the home page.

Written examination (TEN1, 6hp):

The examination is scheduled at saturday March 14, 2009, at the time 08.00-13.00. The only other scheduled examination occasion this year is monday June 8, 2009, at the time 14.00-19.00.
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!