Optimization 1/MN 1

The course is as an introduction to computational optimization. We will cover some theory for linear and nonlinear optimization, discuss classes of important applications, and introduce computational algorithms. The text book is Linear and Nonlinear Programming, by Stephen Nash and Ariela Sofer.

The time will be divided about equally between linear programming, unconstrained nonlinear optimization, and nonlinear programming (that is, nonlinear optimization with constrains). We will define Linear Programs (LPs) and describe the simplex method for the solution of LPs. More general types of optimization problems are called Nonlinear Programs (NLPs). We will first discuss iterative methods used to find local optima for unconstrained NLPs. Finally, we will discuss nonlinear optimization problems with constraints, characterizations of solutions to such problems, and give a short orientation of numerical methods for solving NLPs.

There are 18 lectures, 3 computational assignments, and one written final examination. A passing grade in the final exam and a passing grade in each of the computational assignments are necessary to pass the course. The final exam is on Wednesday October 25, 2006. The assignments will be handed out during the course. The subjects are: linear programming, nonlinear least-squares optimization, and nonlinear programming. Detailed descriptions of the tasks will be provided later. The following applies to the assignments:

  • You shall hand in a written report for each of the assignments, which should contain a statement of the problem, presentation of the results together with a discussion. The source code should also be included in the report.
  • You can work in pairs (not 3) on the assignments and hand in a single report.
  • The grade on each assignment is pass or fail. Fail means that you have to hand in a corrected report for grading. The reports of all assignments must have been presented to the teacher no later than November 13. After this date, the next opportunity for handing in the assignments is when the course is given again next year.
  • A 0.5 bonus point will be given for correct solutions provided before the deadline for each assignment. These points are added to your result on the final exam. The deadlines for the three assignments are: September 22, October 9, and October 24. Note that the bonus deadlines are absolute.

The course will be in Swedish if no foreign students take the course, otherwise in English. A preliminary schedule of the course is found in the table below. It is likely that some delays and changes in content will occur. Lecture notes will mainly be given on the blackboard, with some additional material provided on viewgraphs. Pdf files with the viewgraph material will be put on the home page continuously throughout the course. Exercises will be taken from the book, from old exams, or from material handed out at the lectures.

Lect. Topic Sections in the book Day Time Room
1 Introduction 1 , 2 (just skim it) Aug. 29 8-10 P1111
2 Linear Programming 4 Aug. 30 10-12 P1111
3 Linear Programming 4 Sep. 4 13-15 P2247
4 Linear Programming 5.1-5.2 Sep. 6 10-12 P1111
5 Linear Programming 6.1-6.2, 6.4 Sep. 7 8-10 P1111
6 Exercises Sep. 12 13-15 P2247
7 Unconstr. nonlin. opt., intro 10.1-10.2, 2.4-2.5 Sep. 15 10-12 Häggsalen
8 Unconstr. nonlin. opt 10.3-10.5 Sep. 19 8-10 P1111
9 Unconstr. nonlin. opt 11.1-11.2 Sep. 21 10-12 P2146
10 Unconstr. nonlin. opt 11.3, 11.4 Sep. 22 13-15 P2247
11 Nonlinear Least Squares 13.1, 13.2 Sep. 25 8-10 P2247
12 Exercises Sep. 29 10-12 P1111
13 Nonlinear Programming 14.2-14.3 Oct. 2 10-12 P2347
14 Nonlinear Programming 14.4-14.6 Oct. 6 13-15 P1311
15 Nonlinear Programming 15-16 (orientation) Oct. 9 15-17 P1111
16 Exercises Oct. 10 13-15 P2247
17 Summary Oct. 12 10-12 P1311
18 Examples from old written exams old examinations Oct. 18 13-15 P2446

Lecturer is Martin Berggren. Office 2451, ph. 471 2964, .

The course homepage is at http://www.it.uu.se/edu/course/homepage/opt1