Project

Part of the grade (30%) in this course is based on a project to be handed in during the course. The project will tentatively be published in the end of February/beginning of March with a deadline on March 24.

Technically, the project is not mandatory in that you are still admitted to the exam even if you do not hand in anything. However, your best possible course result in that case is 70%, corresponding to a C.

The project will consist of both theoretical and numerical problems, and a large part will be concerned with the implementation of different optimisation algorithms. You are free to choose any programming language, although I would recommend Python or Matlab. If you sign up for the project as a group, make sure that at least one member has at least some basic experience in programming.

Project description

What to hand in and how

Your work should contain:

  1. A written report submitted electronically as a PDF file.
    • You may write either in English or in Norwegian.
    • The report should not be longer than twelve pages including all figures, tables, and possible references. I appreciate it, though, if your report is shorter than that.
    • Preferably use LaTeX, but you may use any other typesetting program you like if this causes issues.
    • Do not put your names anywhere on the report. Either use your candidate numbers for this course (if they are already available) or your student numbers (if not).
    • Make sure that you include enough details in your report that it is possible to understand how you have produced your numerical results. In particular, this includes parameter choices for your algorithms (of course, you have to state which algorithms you are actually using) and also the choice of initialisations.
    • Your report should be written as an actual scientific/mathematical report, not simply as a list of answers to the different questions posed in the project description. Roughly 25% of the grade for the project will be based on the presentation.
  2. A zip file containing all your relevant code.
    • Make sure that the code actually runs and include enough documentation for me to run it as well.
    • The quality of the code will not be included in the grade; its correctness will be, though. In particular, your implementation should actually coincide with your description of the algorithms in your report.
    • Do not put your names anywhere in the code.
    • You are free to choose any (reasonable) programming language, but Python or Matlab are recommended. Do not expect any programming help in question sessions or office hours, if you insist on a different language.

Send both files together by e-mail to me with "TMA4180 - project" in the subject heading. The deadline is Sunday, March 24, 23:59.

FAQ

  • My Quasi-Newton method does not work. Why?
    There are several possibilities, for instance:
    • If you are using the BFGS method following the notes taken in class, please note that the final formula I have derived contains an error. The correct update should be \[H_{k+1} = H_k - \rho_k(s_k(H_ky_k^T) + (H_ky_k)^T s_k) + (\rho_k^2 y_k^T H_k y_k + \rho_k) s_k s_k^T. \]
    • All the line search methods require that the search direction is actually a descent direction. In the case of the Quasi-Newton methods, this can be guaranteed if the step lengths always satisfy the Wolfe conditions.
    • Make sure that the gradient of the function you are minimising is correct. Also, do not try to solve your problem to a higher precision than its condition allows.
  • My CG method does not work. Why?
    Again, there are several possibilities, for instance:
    • If you are using the Fletcher–Reeves method, then the search direction will be a descent direction if you use the strong Wolfe conditions with parameter \(c_2 < 1/2\). Note that the bisection algorithm for finding a suitable step length has to be slightly modified for these strong Wolfe conditions.
    • If you are using the Polak–Ribière or a different method, even the strong Wolfe conditions are not necessarily enough for guaranteeing that the search directions are descent directions. You find some information about what to do in these cases in N&W, pp. 122 sqq.
    • Again, make sure that the gradient of the function you are minimising is correct and do not try to solve your problem to a higher precision than its condition allows.
  • How do I prove the concavity of the function in problem 6?
    In many cases (probably including this one), the simplest method for showing the concavity of a function is to prove that its Hessian is negative semi-definite, or, that the negative Hessian is positive semi-definite. Moreover, the positive semi-definiteness of a matrix can, for instance, be shown by proving that all minors are non-negative.

Help sessions

In addition to the exercise classes (Monday 17-18) and regular office hours (Thursday 10-11), I (Markus Grasmair) will offer additional office hours/help sessions (central building 2, 10th floor, room 1040) on:

  • Monday, March 11, 10-14.
  • Wednesday, March 13, 12-14.
  • Monday, March 18, 10-14.
  • Wednesday, March 20, 12-14.

Please reserve a time slot for those office hours by filling out the following google docs:

Moreover, Ola will have office hours on:

(All in central building 2, 10th floor, room 1056).

Registration

Please register here if you intend to do the project.

  • You may work on this project either alone or in groups of up to three students.
  • If you already have found a group, one of the group members should sign up the whole group in question 1 of the registration form.
  • If you want to be placed in a group, please sign up in question 2 of the registration form.
  • If you sign up as a group of two, an additional member might be assigned to your group.
  • Please include your full names and study programmes in your registration.
  • The deadline for the registration is Tuesday, February 26, 18:00.
2019-03-20, Markus Grasmair