MATH49111/69111 Scientific Computing Projects 2: Neural Networks, Compressed Sensing, Discontinuous Galerkin Methods, Revenue Management, and the Gillespie Algorithm
MATH49111/69111 Scientific Computing Projects 2
1 Neural Networks 1.1 Neural Networks . . . . . . . . . . . . 1.2 Evaluating the neural net output . . . 1.3 Training the neural network . . . . . . 1.3.1 Stochastic gradient . . . . . . 1.3.2 Evaluating ∇Cx{i} (p) . . . . . 1.3.3 The training algorithm . . . . 1.3.4 Exercises . . . . . . . . . . . . 1.4 The code . . . . . . . . . . . . . . . . . 1.4.1 Exercises . . . . . . . . . . . . 1.5 Training and using the neural network 1.5.1 Exercises . . . . . . . . . . . . 1.6 Report . . . . . . . . . . . . . . . . . . 2 Compressed Sensing 2.1 Iterative Hard Thresholding . . . . . . . . . 2.1.1 Gradient descent . . . . . . . . . . . 2.1.2 Iterative Thresholding . . . . . . . . 2.1.3 The Phase Transition phenomenon 2.1.4 Additional information . . . . . . . 2.2 Report . . . . . . . . . . . . . . . . . . . . . 3 Discontinuous Galerkin Methods for Convection-dominated problems 3.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Approximating the unknown, u . . . . . . . . . . . . . . . . . . 3.1.2 Formulating the problem . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Description of the algorithm . . . . . . . . . . . . . . . . . . . . 3.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Revenue Management of Carparks 4.1 Theory – The Carpark Model . . . . . . . . . . . . . . . . . . . . 4.1.1 Generating events from a Poisson Process . . . . . . . 4.1.2 Generating a Booking . . . . . . . . . . . . . . . . . . . 4.1.3 Calculated expected values of car park measures . . . 4.1.4 Optimal Revenue Management . . . . . . . . . . . . . 4.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 The Customers class . . . . . . . . . . . . . . . . . . . . 4.2.2 The Car Park Class . . . . . . . . . . . . . . . . . . . . . 4.2.3 Revenue management with a fixed allocation strategy 4.2.4 Booking rejection strategies . . . . . . . . . . . . . . . 4.3 Report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Random Numbers, Stochastic Simulation and the Gillespie Algorithm 5.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 An ODE model: chemical rate equations . . . . . . . . . . . . 5.1.2 Markov formulation . . . . . . . . . . . . . . . . . . . . . . . . 5.1.3 The Gillespie algorithm . . . . . . . . . . . . . . . . . . . . . . 5.1.4 Random numbers . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 C++ Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Reactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 The GillespieSimulation class . . . . . . . . . . . . . . 5.2.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Guidelines
Choose only one project from those in this booklet to complete and hand in. Students on the MSc in Quantitative Finance are encouraged to choose either project 1 or project 4. The projects are written to be self contained, but you may (indeed, are encouraged to) reference relevant books, papers and other resources. You can of course ask for any clarifications.
This project is worth 60% of the marks for the course, and is assessed by a written report, marked out of 60. The report will be marked in accordance with the criteria as described below under “Grading criteria”.
This is not a group work assignment and your report and all code must be written by you individually. Do not read or copy the work of other students, and do not discuss details of the projects/coursework or share your own work with others. Do not copy (or closely paraphrase) material from other sources.
- Write your report as though for a fellow student on your course: explain the project topic carefully, but there is no need to describe more basic mathematical concepts.
- Aim for precision and clarity of writing.
- The report should be well structured, containing: – an introduction and description of the problem – discussion of the problem formulation and numerical techniques used – your results, supported using figures and tables as required, and analysis of these results – a conclusion
- Ideally, reports should be typeset in LATEX and submitted in PDF format, though you may use Microsoft Word or other word-processing software if you have not used LATEXpreviously. A LATEX coursework and project template is provided on the course website, which you may use if you wish.
- The report must not exceed 15 pages in length (excluding long tables, code etc. in appendices). This should be regarded as a maximum: a concisely written project may score very high marks using somewhat fewer pages than this.
- Any books or articles referred to must be included in a references section.
- Figures and tables should be clearly labelled, and all figures and tables in the report must be referenced in the text.
- Any code used to generate results used in the report must be included in an appendix. You may be asked to provide the source code files in addition to this. Small portions of code may be included in the text, or references to the code in the appendix can be used.
- Any numerical results presented should be accompanied by a reference to the code that generated them (e.g. the name of a source code file included in the appendix). It is very important that any numerical results presented in the report are generated from the numbers produced by your own code.
- You should attempt every task set in the project, unless marked as optional, but you should not write up every task for the report. The tasks that should be written up for the report are indicated clearly in the ‘Report’ section at the end of the project. However, you are welcome to to briefly write up some of the other tasks in the report as well, if you find this useful to explain what you have done.
Presentation
The report should be well structured with an introduction of the problem being solved, a problem formulation, results, and a conclusions section. It should be clearly written and free from spelling and grammatical errors. Mathematics should be typeset carefully. The figures and tables should be clear, referenced in the text, and labelled with suitable captions.
Mathematical content
The report should be factually accurate and the mathematical language precise and clear. There should be clear descriptions of the project and the outcome to be achieved, with evidence of understanding the wider context of the problem. Any results and conclusions need to be well supported and coherent. Numerical results should be interpreted in the context of the mathematical problem, and the accuracy of the computations should be discussed in some depth. For example, numerical results should supported by validation/test cases (to demonstrate that the code has been implemented correctly), by grid or timestep convergence tests (to check that the result is accurate). Check that the results are a credible solution to the original problem! The report should provide evidence of an understanding and the competent application of the methods used in the project, as well as sufficient validation to make a convincing case that the numerical results are correct.
C++ code
Most importantly, the code must be correct and must produce the results that are claimed. The code should be robust, incorporating tests and error checking (e.g. errors from coding mistakes or invalid user input, as well as numerical error due to discretisation and roundoff ) where appropriate. The code should be well structured (e.g. using object oriented programming, where suitable or where specified in the project), and suitably commented. Credit will be given for additional effort put into the code beyond the minimum requirements of the project (for example, where code has been optimised for speed, or has been structured in a novel and suitable way, or where extensive testing has been built in).
Resources
- See the project template file on the course website for an example of LATEX syntax and for links to web resources for more information about LATEX.
- For a guide to scientific writing in general, see – Scientists Must Write (R. Barrass, Routledge, 2002) – The Elements of Style (W. Strunk & E. B. White, 1999) – What’s wrong with these equations? (N. D. Mermin, in Physics Today, October 1989), available at http://www.pamitc.org/documents/mermin.pdf
- For technical guidance on plotting figures in MATLAB/Octave and Gnuplot, see the online notes on the course website. For guidance on figure design (much of it well beyond the scope of what is required for this course) see, for example, The Visual Display of Quantitative Information (E. R. Tufte, Graphics Press, 1983) or Semiology of Graphics (J. Bertin, ESRI Press, 2010).
Grading criteria
• 30 marks (50% of the marks for the project) are for obtaining the correct numerical answers, and writing the code that does so. These marks are gained from questions in the report that ask for numerical results to be tabulated or plotted, and from the questions that ask for code to be written. These numerical answers should be incorporated into the written report (not presented as standalone answers to each question). • The remaining 50% of the marks for each project are for the understanding and analysis demonstrated in the report. These marks assess how you have chosen appropriate algorithms and program architectures in your code, how you have validated your numerical results, and presented these in the context of the mathematical problem. The levels of performance required to gain these marks are described in table 1 below.
