# TMA4180 Optimization Theory: Spring 2014

## Messages

**30.06:**Final grades for the course can be found here. A few grades have been affected by the fact that I have not received the project reports from some of you. Have a good summer!**07.06:**Hope you did well at the exam. Here is the exam text and proposed solutions. As far as the solutions are concerned: note that some small lines have not scanned properly (so some less-than-or-equal inequality signs look as less-than) and also there is an even number of sign mistakes on page 2, so they do not affect the correctness of the computation: grad(f)^T p = -16, and down the flow in the sufficient decrease test one should have used f0 + alpha c grad(f)^T p, not f0 - alpha c grad(f)^T p. Please let me know if you have any other questions or comments.**26.05:**FYI: I am out of office (conference) 03.06.14-10.06.14. I will try to answer emails during this period, but it might be sporadic. Anne Kværnø will be on call during the exam.**26.05:**Here is in my humble opinion the best project report I have received: report, code, report+a few comments.**23.05:**Two things- The grade for the course is a "portfolio grade" meaning you will obtain it on the basis of the written exam and the project combined with 80/20 weighting. Nevertheless, I would like you to get some feedback for your project reports. I marked them with some comments, and if you would like to see/discuss those, you are more then welcome to stop by my office. Send an email with TMA4180 in the subject line if you want to make sure I am at the spot. I would also like to thank the students with numbers 10006 and 10030 for their very solid report, and ask their permission to scan it and publish it here as a "reference" for everybody.
- Just an obvious hint for the exam: the questions are not sorted in the order of increasing difficulty, at least in my opinion, so do not get stuck with one question for a long time - proceed to answering the rest of them!

**15.05:**- You can bring whatever version of the book you have (printed, bound - I do not distinguish)
- Of course you can bring the errata for the book
- I am going through your project reports right now and will give you feedback very soon. So far I can tell that many of you should certainly refresh the idea of KKT conditions, especially for problems with inequality constraints; constraint qualifications, including LICQ and other CQs; and finally, their role and implications for the necessity of the KKT conditions.

**13.05:**Here is the PDF files of all the notes you can bring to the exam. These are the same notes found under Lecture notes, simply combined into one file.**08.05:**Regarding the exam: The curriculum of the course corresponds to the "reading" column in the Lecture Plan, with the exception that the calculus of variations part is found in this note and not in Troutman's book. You will be allowed to have Nocedal & Wright as well as the printed notes from the course homepage with you (in addition to the standard calculator and math formulas). Therefore I will not ask for definitions, but rather concentrate on their usage/implications for optimization problems and algorithms. Simplex algorithm is not a part of the course this year, and you may also expect that the calculus of variations part will be toned down in the exam this year compared to the previous years. Please let me know if you have any further questions. I am still available on Tuesdays 11-12, as well as during other times by appointment.**24.04:**The lecture notes on the introduction to the calculus of variations are here. Apologies for the broadest interpretation of the term "after the lecture".**01.04:**Prof. Hoemberg will upload his lecture notes on the Wiki after the lecture.**You will use these notes instead of Troutman's book.**(This is not April Fools' message.)**28.03:**If you have any further questions related to the project, I will be available at my office Monday March 31st 13:15-14:00. -Lars**27.03:**I proved the sufficiency of KKT conditions for convex problems at least a couple of times during the lectures – but since I cannot find the proof in the book, here it is.**17.03:**Mistake in the statement of the Proposition 6 in optimality conditions for constrained problems over convex sets is corrected. Of course the first order conditions are not*sufficient*for local optimality without convexity of the objective.**14.03:**During the weeks 12-13 there will be no tutorial on Fridays. Instead, I will be available for questions Thursdays 14:15-15:00 in my office. -Lars**13.03:**- Regarding the maximal possible grade for the course if one skips the project: according to this document it is "B" and not "C", as stated in the project description.
- There will be no lectures during weeks 12-13 to let you work on the project (see Lecture Plan). I am available for questions/answers both Fridays in S1, if necessary.
- Weeks 14-15 there are lectures on Thu/Fri given by Prof. Dietmar Hoemberg.

**11.03:**There will be no tutorial Friday 14th of March. Instead, I will have an office hour Thursday 13:15-14:00 if you need any guidance on the project. If this time does not fit into your schedule, please send me an e-mail. My office is in the 6th floor of Sentralbygg 2, room 644. -Lars**28.02:**I have uploaded the proof of the representation theorem used in the proof of the existence of solutions to linear programming problems here.**26.02:**The project description is here. The deadline is Apr 4 at 16:00. By now you should be able to answer most "theoretical" question about the existence of optimal solutions and optimality (KKT) conditions in the project. As far as barrier/SQP methods are concerned, more information is coming soon during the lectures, or you may read it on your own in the textbook. In any case, you may start thinking about how to represent the problem functions (objective, constraints) in a Matlab program.*Please let me know if there is something unclear in the project description as soon as possible.***26.02:**First of all, let me thank the reference group for providing feedback to me. Please do not hesitate to provide me with more feedback whenever you have questions or concerns about the course. Regarding the exam and the curriculum compared to the last year:- Simplex method is not a part of the curriculum any longer
- To the contrary, the interior point methods for linear programming and algorithms for constrained non-linear programming such as SQP, penalty, augmented Lagrangian, and barrier methods are a part of the curriculum now (you will meet some of them in the project)
- For a more precise correspondence between the course curriculum and the book please see the evolving Lecture Plan. I will summarise it before the exam
- You could
**and should**prepare for the exam by solving the old exam problems (but keep in mind that simplex algorithm is gone and there might be questions about other types of algorithms)

**31.01:**I made a mistake in the tutorials today. For exercise 4.7, I said that you only have to check that the norm of each point is greater than the previous point. This is only necessary, not sufficient. A complete solution of this exercise will be available no later than Monday, but I have included a hint in the posted solutions so that you should be able to do this by yourself. Solutions to the other exercises are now available. -Lars**29.01:**I gather that many of you are participating in the career day on Thursday 30.01. Please look through Section 5.1 of N&W. (If you know about Krylov subspace methods as a part of, e.g., Numerical Linear Algebra class, then you are in good shape.) The non-linear CG methods build upon the linear CG method, so it is important that you have at least vague ideas about those.**23.01:**Organization of the tutorials: Based on the feedback for last week's tutorial, I will continue as we did then. That is, I will demonstrate some of the exercises on the blackboard, but I still want you to actively participate. If there are particular exercises that you struggle with, I will focus on these. If you have any comments regarding the tutorials, please let me know. -Lars**15.01:**Location, location, location: I made a mistake in the previous announcement, it is VG2 on*Thursdays*and S1 on*Fridays*. I am told that VG2 is the only auditorium of a decent size available on Thursdays.**13.01:**In the tutorial on friday we will cope with both the exercises from the notes and the recommended exercises from Chapter 2, N&W, see Exercises. To profit from the tutorials you should as a mimimum have read the exercises in advance.**10.01:**As a follow-up to today's lecture on 1st/2nd order necessary/sufficient optimality conditions here is a*Science, New Series*article about the "B-2 flying wing" optimization study. "The math nerd joke" is in the right column on the first page of the article (second page of the document). Enjoy.**20.12:**Welcome to the course in Optimization Theory. The first lecture will be on Thursday January 9.

## Course information

In the course description you can find detailed information about the course, the main topics presented and the learning outcome.

**Exam**

06.06.2014, 09:00-13:00

## Teaching

**Lecturer**

Anton Evgrafov anton [dot] evgrafov [at] math [dot] ntnu [dot] no. Office hours: Tuesdays 11-12 in Sentralbygg 2, room 1038**Teaching assistant**

Lars Vingli Odsæter, Lars [dot] Odsater [at] math [dot] ntnu [dot] no (please use TMA4180 in the subject header)

## Teaching material

- J. Nocedal and S. Wright:
*Numerical Optimization*, 2nd Edition. Springer, 2006, (Errata).

This book is available in electronic form at Springerlink. From here it is also possible to order a softcover (reduced price). - J. L. Troutman: Variational Calculus and Optimal Control, 2nd Ed. Springer, 1996.

(Legal copies of relevant pages from Troutman will be sold at net cost)

## Exercises

- There will be given weekly exercises. These are not mandatory, and should not be handed in. You can solve them individually or in groups. Solutions to these exercises will be posted on the web.

The first tutorial, where you can get help with exercises, is on Friday January 17. - During the last four weeks of the course there will be one exercise counting 20% towards the total grade. This may be solved individually or in
**small**groups (2-3 people). More information with specific dates will follow.