Chalmers/Göteborg University Optimization Department of mathematics Course information 2002 Michael Patriksson 18th January 2002

TMA946 Applied optimization TM, 5 credits MAN280 Optimization, 5 credits

The course is a basic course in optimization.

The purpose of the course is to provide

(I) knowledge of some important classes of optimization problems and of application areas of optimization modelling and methods;

(II) practice in describing relevant parts of a real-world problem in a mathematical model;

(III) understanding the basic mathematical theory upon which optimality criteria are built;

(IV) examples of optimization algorithms that are naturally developed from this theory, their analysis, and their application to practical optimization problems.

LECTURER/EXAMINER: Michael Patriksson, associate professor, Matematiskt Centrum, room 5218; tel: 772 3529; e-mail: mipat@math.chalmers.se

LECTURER: Ann-Brith Strömberg, research assistant, Matematiskt Centrum, room 5266; tel: 772 5372; e-mail: anstr@math.chalmers.se

LECTURER: Tuomo Takkula, Matematiskt Centrum, room 2442; tel: 772 1052; e-mail: tuomo@cs.chalmers.se

EXERCISE ASSISTANT: Fredrik Altenstedt, Ph D student, Matematiskt Centrum, room 5267; tel: 772 5379; e-mail: alten@math.chalmers.se

EXERCISE ASSISTANT: Anton Evgrafov, Ph D student, Matematiskt Centrum, room 5217; tel: 772 5373; e-mail: toxa@math.chalmers.se

Course presentation

CONTENTS: The course is broad in its contents, but has its main focus on optimization problems in continuous variables, and can within this framework be separated into two main areas:

Linear programming: Linear optimization models, linear programming theory and geometry, the Simplex method, duality, interior point methods, sensitivity analysis, modelling languages;

Nonlinear programming: Nonlinear optimization models, convexity theory, optimality conditions, iterative algorithms for optimization problems with or without constraints, relaxations, penalty functions, Lagrangian duality.

An overview is also given of three other important problem areas within optimization: integer programming, network optimization, and optimization under uncertainty.

ORGANIZATION: Lectures, exercises, computer exercises, and a project assignment.

COURSE LITERATURE:

(i) Linear and Nonlinear Programming (book; S G Nash and A Sofer, 1996) [Cremona]

     Errata: http://www.gmu.edu/departments/ore/books/naso/ns-errata.html.

(ii) Hand-outs from books

(iii) Collection of exercises [sold by the department]

COURSE REQUIREMENTS: The course content is defined by the literature references in the plan below.

EXAMINATION:

• Written exam (first opportunity 11/3, afternoon., M house, additional exams 29/5, morning, V house, and in August)

• Project assignment

• Två correctly solved computer exercises

SCHEDULE:

Lectures: Normally on Tuesdays 13.15–15.00 and Thursdays 8.00–9.45 in the lecture hall, MD house. Exceptions: Lectures 1 and 2 are on 22/1 13.15–17.00; no lecture 12/2 (Charm). Lectures are given in English.

Exercises: In two parallel groups; teaching in Swedish (Fredrik) normally Tuesdays 15.15– 17.00 and Thursdays 10.00–11.45 in MD6, exercises in English (Anton) normally Tuesdays 15.15–17.00 and Thursdays 10.00–11.45 in MD9. Exceptions: no exercise 22/1 (see above); no exercise 12/2 (Charm).

Project: Teachers are available for questions in the computer rooms, which are also booked for work on the project, on 18/2 (rooms: B, C, H), at 17.15–21.00. (Presence is not obligatory.) At other times, work is done individually. Deadline for handing in the project model: 31/1. Hand-out of correct AMPL model: 8/2. Deadline for handing in the project report: 22/2.

Computer exercises: Each computer exercise is scheduled to take place in the computer rooms when also teachers are available, on 11/2 and 28/2, respectively (rooms booked: B, C, H), and on both occasions at 17.15–21.00 (Room H is booked from 19.00). (Presence is not obligatory.) The computer exercises can be done individually. Deadline for handing in the report: one week following each computer exercise.

Information about the project assignment and the computer exercises are found on the

web page for the course, http://www.md.chalmers.se/~mipat/TOkurs.html.

This course information and other hand-outs will also be found on this page.

COURSE PLAN, LECTURES:

\underline{Le 1} (22/1) Course presentation. Subject description. Applications. Modelling. Problem analysis. Classification. (i): Chapter 1 (ii): Course information (this document); course notes, including a document with additional applications

\underline{Le 2} (22/1) Linear programming. Solving a simple linear program with DUPLO. Fundamentals. Local and global optimality. Convex sets and functions. (i): Chapter 4.1–2, 2.2–3 (ii): “Introduction to linear programming”

\underline{Le 3} (24/1) Linear programming. Problem description. Polyhedral sets. Basic solutions and extreme points (algebra versus geometry in linear programming). Representation theorem. The Simplex method, introduction. (i): Chapter 4.3–4, 5.1–2

\underline{Le 4} (29/1) Linear programming. The Simplex method. Matrix and tableau forms. Phase 1 and 2. Degeneration. Termination. Revised simplex. Complexity. (i): Chapter 5.3–5.6, 9.3

\underline{Le 5} (31/1) Linear programming. Optimality. Duality. Sensitivity analysis. (i): Chapter 6.1–4, 7.4–7.6

\underline{Le 6} (5/2) Linear programming. Modelling languages and LP solvers. Network optimization. Graph theory. Applications. Unimodularity Bases and trees. Minimum cost network flows. The Simplex method in networks. The transportation problem. The shortest path problem. The max flow/min cut theorem. Minimum spanning trees. (i): Chapter 8.1–5 (ii): On applications and algorithms for network flow problems

\underline{Le 7} (7/2) Integer programming. Applications. Modelling. Implicit enumeration. Heuristics. (ii): On integer programming

\underline{Le 8} (14/2) Unconstrained optimization. Optimality. Search methods. Search directions. Line searches. Termination criteria. Steepest descent. (i): Chapter 10.1–5, 11.4.1, 11.5, 11.1–2

\underline{Le 9} (19/2) Unconstrained optimization. Newton methods. Derivative-free methods for unconstrained optimization. Constrained optimization. Primal optimality conditions. (i): Chapter 11.3, 12.2–3, 12.6, 11.4.3, 14.1 (ii): Material on derivative-free optimization

\underline{Le 10} (21/2) Constrained optimization. Primal algorithms. Gradient projection. Dual optimality conditions (KKT), introduction. (i): Chapter 14.2–7 (ii): On primal algorithms

\underline{Le 11} (26/2) Constrained optimization. Farkas’ Lemma. Fritz Johns’ conditions. The Karush–Kuhn–Tucker conditions. Lagrangian duality, introduction.

(i): Chapter 14.2–7, 14.8.2–3

\underline{Le 12} (28/2) Constrained optimization. Lagrangian duality. Weak and strong duality. Duality gap. Nondifferentiable optimization. (i): Chapter 14.8.2–3 (ii): On algorithms for Lagrangian dual problems

\underline{Le 13} (5/3) Constrained optimization. Penalty and barrier methods. Interior point methods for linear programming, orientation. Generalized reduced gradient (GRG), orientation. The augmented Lagrangian. (i): Chapter 16.1–3, 17.3–4, 16.5, 15.5, 16.6 (ii): On algorithms for constrained optimization

\underline{Le 14} (7/3) Optimization under uncertainty. An overview of the course. (ii): On applications and algorithms for optimization under uncertainty.

COURSE PLAN, EXERCISES:

The below list contains more exercises than will be covered during the exercises. Those that are left out are recommended home work exercises.

\underline{Ex 1} (24/1) Modelling. Geometric solution of linear optimization problems. (i): 4.1.1–2 (iii): 2.1.1–2.1.13, 2.4.5–2.4.7, 3.1.1–3.1.7

\underline{Ex 2} (29/1) Convexity. (i): 2.2.3, 4, 6, 8, 9; 2.3.1–6, 8–17 (iii): 1.1.29–1.1.41

\underline{Ex 3} (31/1) The Simplex method. Geometry, bases. (i): 4.2.1–6; 4.3.1–3, 6, 10; 4.4.6–8 (iii): 2.4.4, 2.3.1–2.3.3, 2.3.18, 2.3.24

\underline{Ex 4} (5/2) The Simplex method. Matrix form. Tableau form. Phase 1 och 2. (i): 5.2.2–6, 8; 5.3.4–5; 5.4.2, 4; 5.5.1, 2(a), 3(a), 4, 6–7, 10 (iii): 2.4.1–2.4.3, 2.3.5–2.3.9, 2.3.25, 2.4.19

\underline{Ex 5} (7/2) The Simplex method. Optimality. Duality. Sensitivity analysis. (i): 6.1.1–7; 6.2.1–5, 7, 9, 11–12, 15; 5.2.8; 6.3.1–2, 4–9; 6.4.1–3; 7.5.3–5 (iii): 2.2.1–2.2.5, 2.3.10–2.3.13, 2.2.6–2.2.9, 2.4.9, 2.3.15

\underline{Ex 6} (14/2) Network optimization. Modelling. Network flow algorithms. (i): 8.2.1–3, 6–12; 8.3.1, 3–5, 7–8 (iii): 4.2.1, 4.2.6, 4.2.21

\underline{Ex 7} (19/2) Integer programming. Modelling. Implicit enumeration. Heuristics. (ii): On integer programming

\underline{Ex 8} (21/2) Unconstrained optimization. (i): 10.2.1–7, 10–12, 17–18; 10.5.2–6, 9; 11.4.7–9; 11.1.1–2, 6–7, 10; 10.3.2–4, 6, 12 (iii): 3.3.1–3.3.11, 3.2.1

\underline{Ex 9} (26/2) Unconstrained optimization, continued.

\underline{Ex 10} (28/2) Optimality conditions. (i): 14.2.4–6; 14.4.4; 14.5.3 (iii): 3.5.1–3.5.7, 3.5.20–3.5.22, 3.5.26

\underline{Ex 11} (5/3) Lagrangian duality. (i): 14.8.4–8, 10 (iii): 3.4.1

\underline{Ex 12} (7/3) Penalty and barrier methods. Repetition. (i): 16.2.1–4; 16.5.1–2; 15.5.1–3, 5; 16.6.1, 5–6 (iii): 6.1.1–6.1.4