Chalmers University of Technology/Göteborg University Optimization Mathematical Sciences Course information 2007 Michael Patriksson 8th November 2007

TMA947 Optimization, first course, 7.5 credits MMG620 Optimization, 7.5 credits

The purpose of this basic course in optimization 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 optimization model;

(III) an understanding of necessary and sufficient optimality criteria, of their consequences, and of the basic mathematical theory upon which they are built;

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

EXAMINER/LECTURER: Michael Patriksson, professor of applied mathematics, Matematiska Vetenskaper (Mathematical Sciences), room 2084; tel: 772 3529; e-mail: mipat@math.chalmers.se

LECTURER/EXERCISE ASSISTANT/PROJECT MANAGER: Peter Lindroth, Ph. D. student, Matematiska Vetenskaper, room 2086; tel: 772 5356; e-mail: peter.lindroth@math.chalmers.se

LECTURER/EXERCISE ASSISTANT: Christoffer Cromvik, Ph. D. student, Matematiska Vetenskaper, room 2079; tel: 772 3515; e-mail: christoffer.cromvik@math.chalmers.se

Course presentation

CONTENTS: The main focus of the course is on optimization problems in continuous variables. We can roughly separate the material into the following areas:

Convex analysis: convex set, polytope, polyhedron, cone, separation theorem, Farkas Lemma, convex function, Euclidean projection

Optimality conditions: local/global optimum, existence and uniqueness, constraint qualification, Karush–Kuhn–Tucker conditions, Lagrange multiplier, Lagrangian dual problem, global optimality conditions, weak/strong duality, subgradient

Linear programming: Linear optimization models, linear programming algebra and geometry, basic feasible solution, the Simplex method, termination, linear programming duality, interior point methods, sensitivity analysis, modelling languages

Nonlinear optimization methods: direction of descent, (quasi-)Newton method, conjugate direction, Frank–Wolfe method, gradient projection, exterior and interior penalty, sequential quadratic programming, closed descent maps We also touch upon other important problem areas within optimization, such as integer programming and network optimization.

PREREQUISITES: Passed courses on analysis (in one and several variables) and linear algebra; familiarity with matrix/vector notation and calculus, differential calculus.

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

COURSE LITERATURE:

(i) An Introduction to Optimization by N. Andréasson, A. Evgrafov, and M. Patriksson, published by Studentlitteratur in 2005 and found in the Cremona book store

(ii) Hand-outs from books and articles

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

EXAMINATION:

• Written exam (first opportunity 17/12, morning, V house; additional exam 25/3 2008)—gives 6 credits

• Project assignment—gives 1.5 credits

• Two correctly solved computer exercises

SCHEDULE:

Lectures: on Tuesdays and Thursdays 13.15–15.00 either in Euler (Physics building) or in HAk, where k ∈ {1, 2, 3, 4} (see the schedule below). Lecture 1 is on Tuesday 30/10 in HA2. Exception: Lecture 2 follows immediately after Lecture 1, on 30/10 15.15–17.00 in HA2. Lectures are given in English.

Exercises: on Tuesdays and Thursdays 15.15–17.00 in two parallel groups: (I) exercises in Swedish (Peter) in room MV:F21; (II) exercises in English (Christoffer) in room MV:F23. Exception both for (I) and (II): no exercise 30/10 (see above).

Project: Teachers are available for questions in the computer rooms, which are also booked for work on the project, on 29/11 (rooms: MV:F22, MV:F25) at 17.15–21.00. (Presence is not obligatory.) At other times, work is done individually. Deadline for handing in the project model: 9/11. Hand-out of correct AMPL model: 22/11. Deadline for handing in the project report: 6/12.

Computer exercises: The computer exercise are scheduled to take place when also teachers are available, on 20/11 and 11/12, respectively (rooms booked: MV:F22, MV:F25), and on both occasions at 17.15–21.00. (Presence is not obligatory.) The computer exercises can be performed individually, but preferably in groups of two. Deadline for handing in the report, unless passed through oral examination on site during the scheduled sessions: one week following each computer exercise.

Important note: The computer exercises need at least one hour of preparation each; having done that preparation, two–three hours should be enough to complete an exercise by the computer.

Information about the project and computer exercises are found on the web page

http://www.math.chalmers.se/Math/Grundutb/CTH/tma947/0708/index.html.

This course information, the course literature, project and computer exercise materials, most hand-outs and previous exams will also be found on this page.

COURSE PLAN, LECTURES:

\underline{Le 1} (30/10, HA2) Course presentation. Subject description. Course map. Applica- Week 1 tions. Optimization modelling. Modelling. Problem analysis. Classification. (i): Chapter 1, 2

\underline{Le 2} (30/10, HA2) Convexity. Convex sets and functions. Polyhedra. The Representation Theorem. Separation. Farkas Lemma. The Euclidean projection. (i): Chapter 3

\underline{Le 3} (1/11, HA3) Optimality conditions, introduction. Local and global optimality. Existence of optimal solutions. Feasible directions. Necessary and sufficient conditions for local or global optimality when the feasible set is convex. (i): Chapter 4.1–4.3

\underline{Le 4} (6/11, HA4) Unconstrained optimization methods. Search directions. Line searches. Week 2 Termination criteria. Steepest descent. Quasi-Newton and conjugate gradient methods. Derivative-free methods. (i): Chapter 11 (ii): Material on derivative-free optimization

\underline{Le 5} (8/11, HA3) Optimality conditions, continued. Necessary and sufficient conditions for local or global optimality when the feasible set is convex, continued. The normal cone. Applications to projections and fixed points. The Karush–Kuhn–Tucker conditions. Introduction to the primal–dual optimality conditions (KKT). (i): Chapter 4.4–, 5.1–5.4

\underline{Le 6} (13/11, HA4) The Karush–Kuhn–Tucker conditions, continued. Constraint qual- Week 3 ifications. The Fritz–John conditions. The Karush–Kuhn–Tucker conditions: necessary and sufficient conditions for local or global optimality. (i): Chapter 5

\underline{Le 7} (15/11, Euler) Convex duality. The Lagrangian dual problem. Weak and strong duality. Getting the primal solution. Dual algorithms. (i): Chapter 6

\underline{Le 8} (20/11, Euler) Linear programming. Introduction to linear programming. Mod- Week 4 elling. Basic feasible solutions and extreme points (algebra versus geometry in linear programming). The simplex method, introduction. (i): Chapter 7, 8 \underline{Le 9} (22/11, Euler) Linear programming, continued. The Simplex method. The revised Simplex method. Phase I and II. Degeneracy. Termination. Complexity. (i): Chapter 9

\underline{Le 10} (27/11, HA1) Linear programming, continued. Optimality. Duality. Sensitivity Week 5 analysis. (i): Chapter 10

\underline{Le 11} (29/11, Euler) Linear programming, continued. Sensitivity analysis, continued. Modelling languages and LP solvers. Integer programming. Applications. Modelling. (i): Chapter 10 (ii): On integer programming

\underline{Le 12} (6/12, HA3) Nonlinear optimization methods: convex feasible sets. The gradient Week 6 projection method. The Frank–Wolfe method. Simplicial decomposition. Applications. (i): Chapter 12, 6.3

\underline{Le 13} (11/12, Euler) Nonlinear optimization methods: general sets. Penalty and barrier Week 7 methods. Interior point methods for linear programming, orientation. (i): Chapter 13

\underline{Le 14} (13/12, Euler) Nonlinear optimization methods: general sets, continued. Sequential quadratic programming. Applications of optimization algorithms. An overview of the course. (i): Chapter 13 COURSE PLAN, EXERCISES:

\underline{Ex 1} (1/11) Modelling. Local and global minimum. Feasible sets. Week 1 (i): Chapters 1, 3, 4

\underline{Ex 2} (6/11) Convexity. Polyhedra. Separation. Optimality. Week 2 (i): Chapter 3, 4

\underline{Ex 3} (8/11) Optimality conditions. (i): Chapter 11

\underline{Ex 4} (13/11) Unconstrained optimization. Week 3

\underline{Ex 5} (15/11) The KKT conditions. (i): Chapters 4, 5

\underline{Ex 6} (20/11) Lagrangian duality. Week 4 (i): Chapter 6

\underline{Ex 7} (22/11) Geometric solution of LP problems. Standard form. The geometry of the Simplex method. Basic feasible solution. (i): Chapters 7, 8

\underline{Ex 8} (27/11) The Revised Simplex method. Phase I & II. Week 5 (i): Chapter 9

\underline{Ex 9} (29/11) Duality in linear programming. The Dual Simplex method. Sensitivity analysis. (i): Chapter 10

\underline{Ex 10} (6/12) Sensitivity analysis, continued. Integer programming models. Week 6 (i): Chapter 10 (ii): Hand-outs

\underline{Ex 11} (11/12) Algorithms for convexly constrained optimization. The Frank–Wolfe and Week 7 simplicial decomposition algorithms. (i): Chapter 12

\underline{Ex 12} (13/12) Constrained optimization methods. SQP, penalty methods. Repetition. (i): Chapter 13