## Course presentation

The course gives deepened and broadened theoretical and methodological knowledge in nonlinear programming. Some subjects dealt with in the course are: Sequential-quadratic-programming methods, primal-dual interior methods, semidefinite programming, convexity, convex relaxations.

The course also gives training in modeling and solving practical problems, and to present the results in talking as well as in writing.

Headings denoted with an asterisk ( * ) is retrieved from the course syllabus version Autumn 2020

## Content and learning outcomes

### Course contents^{}

- Unconstrained optimization: optimality conditions: Newton methods, quasi-Newton methods, conjugate gradient methods.
- Constrained optimization: optimality conditions, quadratic programming, sequential quadratic programming, barrier methods, primal-dual interior methods.
- Semidefinite programming including interior methods.
- Convexity and convex relaxations.

### Intended learning outcomes^{}

To pass the course, the student should be able to do the following:

- Apply theory, concepts and methods from the parts of optimization that are given by the course contents to solve problems.
- Model, formulate and analyze simplified practical problems as optimization problems and solve by making useof given software.
- Collaborate with other students and demonstrate ability to present orally and in writing.

To receive the highest grade, the student should in addition be able to do the following:

- Combine and explain the methods in the course, and
- Apply and explain the theory and the concepts of the course in the practical problems that are included.

### Learning activities

### Course material

* Linear and Nonlinear Optimization*, second edition, by I. Griva, S. G. Nash och A. Sofer, SIAM, 2009.

(The book can be ordered from several places. Please note that you can become a SIAM member for free and obtain a discount at the SIAM bookstore.)
*Exercises in applied nonlinear optimization, 2021/2022*. Available via Canvas.
*Supplementary course material in applied nonlinear optimization, 2021/2022*. Available via Canvas.
*Lecture notes in applied nonlinear optimization, 2021/2022*. Can be downloaded from this web page, see the schedule below. Also available via Canvas.
*GAMS, A user's guide*. Available at the GAMS web site.
*GAMS*. GAMS is installed in the KTH linux computer rooms. It may also be downloaded from the GAMS web site for use on a personal computer.
- Two project assignments are handed out during the course, April 5 and April 26, respectively.

Additional notes that may be handed out during the course are also included.

### Detailed plan

Schema VT-2022-209

### Preliminary schedule

Type |
Day |
Date |
Time |
Room |
Subject |

L1. |
Tue |
Mar 22 |
13-15 |
Zoom |
Introduction. Nonlinear programming models. |

L2. |
Wed |
Mar 23 |
13-15 |
Zoom |
Optimality conditions for linearly constrained problems. |

L3. |
Thu |
Mar 24 |
13-15 |
Zoom |
Optimality conditions for nonlinearly constrained problems. |

E1. |
Tue |
Mar 29 |
13-15 |
E2 |
Optimality conditions. |

L4. |
Wed |
Mar 30 |
13-15 |
E2 |
Unconstrained optimization. |

L5. |
Fri |
Apr 1 |
15-17 |
E2 |
Unconstrained optimization, cont. |

P1. |
Tue |
Apr 5 |
13-15 |
E2 |
Introduction to GAMS. |

P2. |
Wed |
Apr 6 |
13-15 |
5O1 / 5O2 Spelhallen |
GAMS exercise session. |

E2. |
Thu |
Apr 7 |
8-10 |
E2 |
Unconstrained optimization. |

L6. |
Fri |
Apr 8 |
13-15 |
E2 |
Equality-constrained quadratic programming. |

L7. |
Mon |
Apr 11 |
10-12 |
Q21 |
Inequality-constrained quadratic programming. |

E3. |
Tue |
Apr 12 |
13-15 |
E2 |
Equality-constrained quadratic programming. |

L8. |
Wed |
Apr 13 |
13-15 |
E2 |
Inequality-constrained quadratic programming, cont. |

E4. |
Thu |
Apr 14 |
8-10 |
E2 |
Inequality-constrained quadratic programming. |

P3. |
Tue |
Apr 26 |
13-15 |
E2 |
Presentation of project assignment 1. |

L9. |
Wed |
Apr 27 |
13-15 |
E2 |
Sequential quadratic programming. |

E5. |
Fri |
Apr 29 |
8-10 |
D33 |
Sequential quadratic programming. |

L10. |
Fri |
Apr 29 |
15-17 |
D33 |
Interior methods for nonlinear programming. |

L11. |
Tue |
May 3 |
13-15 |
E2 |
Semidefinite programming. |

E6. |
Fri |
May 6 |
15-17 |
E2 |
Interior methods for nonlinear programming. |

P4. |
Tue |
May 10 |
13-15 |
E2 |
Presentation of project assignment 2. |

E7. |
Fri |
May 13 |
15-17 |
E2 |
Semidefinite programming. |

E8. |
Tue |
May 17 |
13-15 |
E2 |
Selected topics. |

Q1. |
Fri |
May 20 |
15-17 |
E2 |
Q & A Session |

### Overview of course contents

**Unconstrained optimization**

Fundamental theory, in particular optimality conditions.

Linesearch algorithms, steepest descent, Newton's method.

Conjugate directions and the conjugate gradient method.

Quasi-Newton methods.

(Chapters 11, 12.1-12.3 and 13.1-13.2 in Griva, Nash and Sofer.)
**Constrained nonlinear optimization**

Fundamental theory, optimality conditions, Lagrange multipliers and sensitivity analysis.

Quadratic programming.

Primal methods, in particular active-set methods.

Penalty and barrier methods, in particular primal-dual interior methods.

Dulal methods, local duality, separable problems.

Lagrange methods, in particular sequential quadratic programming.

(Chapters 3, 14.1-14.7, 14.8.2, 15.1-15.5, 16.1-16.3 and 16.7 in Griva, Nash and Sofer.)
**Semidefinite programming**

Fundamental theory.

(Chapter 16.8 in Griva, Nash and Sofer. Separate article in the supplementary course material. Fundamental concepts only.)

### Project assignments

The project assignments are performed in groups, where the instructor determines the division of groups. This division is changed between the two assignments. Assignment 1 is carried out using the modeling language GAMS. For project 2, there is a choice between a modeling assignment, to be carried out using GAMS, or a method assignment, to be carried out using Matlab. The project assignments *must* be carried out during the duration of the course and completed by the above mentioned presentation lectures. It is the responsibility of each student to allocate time so that the project group can meet and function. Presence at the presentation lectures is compulsory. For passing the projects, the following requirements must be fulfilled:

- No later than the night before the presentation lecture, each group must hand in a well-written report which describes the exercise and the group's suggestion for solving the exercise. Suitable word processor should be used. The report should be on a level suitable for another participant in the course who is not familiar with the group's specific problem.
- At the beginning of the presentation lecture, each student should hand in an individual sheet with a brief self-assessment of his/her contribution to the project work, quantitatively as well as qualitatively.
- At the presentation lecture, all assignments will be presented and discussed. The presentations and discussions will be made in small presentation groups, first in presentation groups where each student has worked on the same project assignment, and then in presentation groups where the students have worked on different project assignments. Each student is expected to be able to present the assignment of his/her project group, the modeling and the solution. In particular, each student is expected to take part in the discussion. The presentation and discussion should be on a level such that students having had the same assignment can discuss, and students not having had the same assignment can understand the issues that have arisen and how they have been solved. Each student should bring a copy of the project group's report to the presentation lecture, either in paper or electronically.
- Each project group should make an appointment for a discussion session with the course leaders. There is no presentation at this session, but the course leaders will ask questions and give feedback. There will be time slots available the days after the presentation session. One week prior to the presentation lecture, a list of available times for discussion sessions will be made available at Doodle, announced via Canvas. Each project group should sign up for a discussion session prior to the presentation lecture.
- Each participant in the course must contribute to the work of the group. Each group must solve their task independently. Discussion between the groups is encouraged, but each group must individually solve the assignments. It is
*not* allowed to use solutions made by others in any form. If these rules are violated, disciplinary actions in accordance with the KTH regulations will be taken.

Each project assignment is awarded a grade which is either fail or pass with grading E, D, C, B and A. Here, the mathematical treatment of the problem as well as the report and the oral presentation or discussion is taken into account. The exercises are divided into basic exercises and advanced exercises. Sufficient treatment of the basic exercises gives a passing grade. Inclusion of the advanced exercises is necessary for the higher grades (typically A-C). Normally, the same grade is given to all members of a project group. A student who has not worked on the advanced exercises says so in the self assessment form.

Each project group must solve their task independently. Discussion between the project groups concerrning interpretation of statements etc. are encouraged, but each project group must work independently without making use of solutions provided by others. All project groups will not be assigned the same exercises.

Each project assignment is awarded a grade which is either fail or pass with grading E, D, C, B and A. Here, the mathematical treatment of the problem as well as the report and the oral presentation or discussion is taken into account. Normally, the same grade is given to all members of a group.

## Preparations before course start

### Recommended prerequisites

A completed continuationcourse in numerical analysis.

### Literature

To be announced at the beginning of the course. Preliminary literature:

Linear and Nonlinear Programming by S.G.Nash och A.Sofer, McGraw-Hill, and some material from the department.

### Support for students with disabilities

Students at KTH with a permanent disability can get support during studies from Funka:

Funka - compensatory support for students with disabilities

### Course registration

Due to the project based nature of this course, students must register no later than April 4. Registration is made by the students online following KTH standard procedures.

## Examination and completion

### Grading scale^{}

A, B, C, D, E, FX, F

### Examination^{}

- PRO1 - Project, 1.5 credits, Grading scale: A, B, C, D, E, FX, F
- PRO2 - Project, 1.5 credits, Grading scale: A, B, C, D, E, FX, F
- TEN1 - Examination, 4.5 credits, Grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

#### Project ( PRO1 )

#### Project ( PRO2 )

#### Examination ( TEN1 )

### Ethical approach^{}

- All members of a group are responsible for the group's work.
- In any assessment, every student shall honestly disclose any help received and sources used.
- In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

### Final exam

2The final exam consists of five exercises and gives a maximum of 50 points. At the exam, the grades F, Fx, E, D, C, B and A are awarded. For a passing grade, normally at least 22 points are required. At the exam, in addition to writing material, no other material is allowed at the exam. Normally, the grade limits are given by E (22-24), D (25-30), C (31-36), B (37-42) and A (43-50).

The grade Fx is normally given for 20 or 21 points on the final exam. An Fx grade may be converted to an E grade by a successful completion of two supplementary exercises, that the student must complete independently. One exercise among the theory exercises handed out during the course, and one exercise which is similar to one exercise of the exam. These exercises are selected by the instructor, individually for each student. Solutions have to be handed in to the instructor and also explained orally within three weeks of the date of notification of grades.

The final exam is given Thursday June 2 2021, 8.00-13.00.

###

### Final grade

By identitying A=7, B=6, C=5, D=4, E=3, the final grade is given as

round( (grade on proj 1) + (grade on proj 2) + 2 * (grade on final exam) ) / 4),

where the rounding is made to nearest larger integer in case of a tie.

### Course Coordinator

### Teachers

### Teacher Assistants

### Examiner