Chalmers University of Technology/Göteborg University Optimization Department of mathematics Course information 2005 Michael Patriksson 13th January 2005

TMA947 Applied optimization TM, 5 credits MAN280 Optimization, 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 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, Matematiskt Centrum, room 2423/24; tel: 772 3529; e-mail: mipat@math.chalmers.se

EXERCISE ASSISTANT: Niclas Andréasson, Lic. techn., Ph. D. student, Matematiskt Centrum, room 2447; tel: 772 5378; e-mail: niclasa@math.chalmers.se

EXERCISE ASSISTANT: Anna Nyström, Ph. D. student, Matematiskt Centrum, room 2426; tel: 772 5356; e-mail: anno@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

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

(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 14/3, morning, V house, additional exams in the Easter and August periods)—gives 4 credits

• Project assignment—gives 1 credit

• 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 18/1 13.15–17.00; no lecture 8/2 (Charm 8–9/2); Lectures 4 (25/1) and 6 (1/2) are given in room VF, house V. Lectures are given in English.

Exercises: In two parallel groups: (I) Exercises in Swedish (Anna) normally Tuesdays 15.15–17.00 and Thursdays 10.00–11.45, in room VG; exception: room VF 17/2; (II) Exercises in English (Niclas) the same schedule but in room MD7 throughout. Exceptions both for (I) and (II)): no exercise 18/1 (see above); no exercise 8/2 (Charm).

Project: Teachers are available for questions in the computer rooms, which are also booked for work on the project, on 17/2 (rooms: B, C, G, H), at 17.15–21.00. (Presence is not obligatory.) At other times, work is done individually. Deadline for handing in the project model: 28/1. Hand-out of correct AMPL model: 10/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 3/2 and 24/2, respectively (rooms booked: B, C, G, H), and on both occasions at 17.15–21.00. (Presence is not obligatory.) The computer exercises can be done 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. 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/0405/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} (18/1) Course presentation. Subject description. Course map. Applications. Week 1 Optimization modelling. Modelling. Problem analysis. Classification. (i): Chapter 1, 2

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

\underline{Le 3} (20/1) 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} (25/1) 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} (27/1) 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} (1/2) The Karush–Kuhn–Tucker conditions, continued. Constraint qualifications. Week 3 The Fritz–John conditions. The Karush–Kuhn–Tucker conditions: necessary and sufficient conditions for local or global optimality. (i): Chapter 5

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

\underline{Le 8} (10/2) Linear programming. Introduction to linear programming. Modelling. Basic Week 4 feasible solutions and extreme points (algebra versus geometry in linear programming). The simplex method, introduction. (i): Chapter 7, 8 \underline{Le 9} (15/2) Linear programming, continued. The Simplex method. The revised Simplex Week 5 method. Phase I and II. Degeneracy. Termination. Complexity. (i): Chapter 9

\underline{Le 10} (17/2) Linear programming, continued. Optimality. Duality. Sensitivity analysis. (i): Chapter 10

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

\underline{Le 12} (24/2) Nonlinear optimization methods: convex feasible sets. The gradient projection method. The Frank–Wolfe method. Simplicial decomposition. Applications. Lagrangian duality. Lagrangian duality for integer programs. Duality gaps and the nondifferentiability of the Lagrangian dual function. Heuristics. Applications. (i): Chapter 12, 6.3

\underline{Le 13} (1/3) Nonlinear optimization methods: general sets. Penalty and barrier meth- Week 7 ods. Interior point methods for linear programming, orientation. Sequential quadratic programming. (i): Chapter 13

\underline{Le 14} (3/3) Nonlinear optimization methods: general sets, continued. Applications of optimization algorithms. An overview of the course. (i): Chapter 13 (ii): Hand-outs COURSE PLAN, EXERCISES:

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

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

\underline{Ex 3} (27/1) Unconstrained optimization. (i): Chapter 11

\underline{Ex 4} (1/2) Unconstrained optimization, continued. Week 3

\underline{Ex 5} (3/2) Optimality conditions. (i): Chapters 4, 5

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

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

\underline{Ex 8} (17/2) The Revised Simplex method. Phase I & II. (i): Chapter 9

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

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

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

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