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

TMA947 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, professor, Matematiskt Centrum, room 2423/24; tel: 772 3529; e-mail: mipat@math.chalmers.se

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

EXERCISE ASSISTANT: Anton Evgrafov, Ph D student, Matematiskt Centrum, room 2425; 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, Lagrangian duality, iterative algorithms for optimization problems with or without constraints, relaxations, penalty functions

We may also touch upon three other important problem areas within optimization: integer programming, network optimization, and optimization under uncertainty.

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

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: at http://www.gmu.edu/departments/ore/books/naso/ns-errata.html or

at course home page

(ii) Hand-outs from books and articles

(iii) Collection of exercises [downloadable]

(iv) Lecture notes [downloadable]

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

EXAMINATION:

• Written exam (first opportunity 8/3, morning, V house, additional exams in May and August)—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 20/1 13.15–17.00; no lecture 10/2 (Charm). Lectures are given in English.

Exercises: In two parallel groups; teaching in Swedish (Niclas) normally Tuesdays 15.15– 17.00 and Thursdays 10.00–11.45 in room MD6, exercises in English (Anton) normally the same schedule but in room MD7. Exceptions: no exercise 20/1 (see above); no exercise 10/2 (Charm).

Project: Teachers are available for questions in the computer rooms, which are also booked for work on the project, on 24/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: 30/1. Hand-out of correct AMPL model: 12/2. Deadline for handing in the project report: 24/2.

Computer exercises: Each computer exercise is scheduled to take place in the computer rooms when also teachers are available, on 3/2 and 26/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 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} (20/1) Course presentation. Subject description. Course map. Applications. Modelling and classification. Modelling. Problem analysis. Classification. (i): Chapter 1 (iv): Chapter 1

\underline{Le 2} (20/1) Convexity. Convex sets and functions. Polyhedra. The Representation Theorem. (i): Chapter 2.3, 4.3–4 (iv): Chapter 3

\underline{Le 3} (22/1) Optimality. Local and global optimality. Near-optimality. Necessary and sufficient conditions for local and global optimality. Unconstrained optimization. Unconstrained optimization, introduction. (i): Chapter 2.2, 10.1–2 (iv): Chapter 3, 4, 5

\underline{Le 4} (27/1) Unconstrained optimization, continued. Descent. Search methods. Search directions. Line searches. Termination criteria. Steepest descent. (i): Chapter 10.1–5, 11.4.1, 11.5, 11.1–2 (iv): Chapter 5

\underline{Le 5} (29/1) Unconstrained optimization, continued. Newton methods. Derivative-free methods for unconstrained optimization. Constrained optimization. Introduction to constrained optimziation. Feasible directions. Primal optimality conditions. (i): Chapter 11.3, 12.2–3, 12.6, 11.4.3, 14.1 (ii): Material on derivative-free optimization (iv): Chapter 4, 5

\underline{Le 6} (3/2) Optimality conditions. Constraint qualifications. The Fritz–John conditions. The Karush–Kuhn–Tucker conditions: necessary and sufficient conditions for local or global optimality. (i): Chapter 14.2–7 (iv): Chapter 6

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

\underline{Le 8} (12/2) Linear programming. Introduction to linear programming. Modelling. Basic feasible solutions and extreme points (algebra versus geometry in linear programming). The simplex method, introduction. (i): Chapter 4, 5.1–2 (iv): Chapter 8, 9

\underline{Le 9} (17/2) Linear programming, continued. The Simplex method. Matrix and tableau forms. Phase 1 and 2. Degeneration. Termination. Revised simplex. Complexity. (i): Chapter 5.3–5.6, 9.3 (iv): Chapter 9, 10 \underline{Le 10} (19/2) Linear programming, continued. Optimality. Duality. Sensitivity analysis. (i): Chapter 6.1–4, 7.4–7.6 (iv): Chapter 11

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

\underline{Le 12} (26/2) Simply constrained optimization problems. Gradient projection. The Frank–Wolfe method. Simplicial decomposition. Lagrangian duality. Lagrangian duality for integer programs. Duality gaps and the nondifferentiability of the Lagrangian dual function. Heuristics. (i): Chapter 14.8.2–3 (iv): Chapter 12

\underline{Le 13} (2/3) Constrained optimization, continued. Penalty and barrier methods. Interior point methods for linear programming, orientation. The augmented Lagrangian. (i): Chapter 16.1–3, 17.3–4, 16.5, 15.5, 16.6 (iv): Chapter 13, 14

\underline{Le 14} (4/3) Constrained optimization, continued. Algorithms for constrained optimization, continued. An orientation on network optimization. An overview of the course. (i): Chapter 8.1–5 (ii): On applications and algorithms for network optimization. (iv): Chapter 13, 14 COURSE PLAN, EXERCISES:

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

\underline{Ex 1} (22/1) Modelling. Local and global minimum. Feasible sets. (i): 2.2.3, 4, 6, 8, 9 (iii): 2.1.1–13; 3.1.1–8

\underline{Ex 2} (27/1) Convexity. Polyhedra. Separation. Optimality. (i): 2.3.1–6, 8–17; 4.3.2; 4.4.6–8 (iii): 1.1.8, 9, 15, 16, 20, 22, 27–39

\underline{Ex 3} (29/1) Unconstrained optimization. (i): 10.2.1–7, 10–12, 17, 18; 10.5.2–6; 11.1.1, 2, 4–7; 10.3.2, 4, 6, 12 (iii): 3.3.2, 4–6, 8, 9, 15, 22

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

\underline{Ex 5} (5/2) Optimality conditions. (i): 14.2.3–6; 14.4.1, 2, 8, 9; 14.5.2, 3; 14.7.1, 8, 9 (iii): 3.5.1–8, 10–21

\underline{Ex 6} (12/2) Lagrangian duality. (i): 14.8.1, 4–8, 10 (iii): 3.4.1–3, 6, 16, 18

\underline{Ex 7} (17/2) Geometric solution of LP problems. Standard form. The geometry of the Simplex method. Basic feasible solution. (i): 4.1.1, 2; 4.2.1–6; 4.3.1, 3, 6, 10 (iii): 2.3.2, 11a, 16; 2.4.4–7, 13a, 19

\underline{Ex 8} (19/2) The Revised Simplex method. Phase I & II. (i): 5.2.2–5, 8; 5.3.4; 5.4.4; 5.5.1, 2a, 3a, 4, 10 (iii): 2.3.1, 6–10, 24, 25, 34–36; 2.4.1–3

\underline{Ex 9} (24/2) Duality in linear programming. The Dual Simplex method. Sensitivity analysis. (i): 6.1.1–7; 6.2.1–5, 7, 9, 11, 12, 15; 6.3.1, 2, 4–7; 6.4.1, 2 (iii): 2.2.1–9, 2.3.11–14, 33

\underline{Ex 10} (26/2) Sensitivity analysis, continued. Integer programming models. (iii): 5.1.4, 11, 15, 17 and hand-outs

\underline{Ex 11} (2/3) Algorithms for convexly constrained optimization. The Frank–Wolfe and simplicial decomposition algorithms. (iii): 3.6.1, 3, 8 and hand-outs

\underline{Ex 12} (4/3) Constrainted optimization methods. SQP, penalty methods. Repetition. (i): 16.2.1–6; 16.5.1, 2; 16.6.1, 5; 15.5.1, 2 (iii): 3.7.1, 4, 6 and exam questions