The "Introduction to Optimization" lecture is accompanied by a group project in which each student contributes to the numerical benchmarking of a blackbox optimization algorithm via the COCO platform.
For further information and the results, please see the internal wiki (needs authorization that all students will get by e-mail).
Numerical blackbox optimization problems occur frequently in practice when the evaluation of the objective function(s) is not analytically describable (because it stems from an expensive numerical simulation or a real physical experiment) and in particular, gradients are not available. Due to the generality of the problem class, many algorithms are available and the main problem in practice is the question which algorithm to run on a new problem at hand. The typical path to answer this question, or at least to give some recommendations on the better algorithms, is numerical benchmarking: a set of algorithms is run on a suite of well-understood test functions and the performance behavior on those test functions is used to extrapolate performance statements for new functions outside the test suite. The open source COCO platform, developed at Inria since 2007, aims at providing several test suites for that matter and the functionalities to automatize the benchmarking up to the generation of plots and tables in HTML and LaTeX/PDF displaying algorithm performances and comparisons. For the single-objective noiseless `bbob` test suite, clearly more than 100 algorithm data sets are already freely available, for the bi-objective `bbob-biobj` suite, 16 algorithm data sets are available so far.
With this group project, students become familiar with the platform, read a research paper, implement a new algorithm ("new" in the sence of "not yet benchmarked"), and benchmark it with the platform.
The total number of groups will depend on the final number of registered students. More details therefore later at this point.
The list of algorithms will be announced in the wiki and will be adjusted to the total amount of students in the class.
The list of potential programming languages shall mainly follow the languages, provided by the COCO interfaces, i.e. python, Java, C/C++, and Matlab/Octave. Other languages are possible, but you should realize that it will potentially pose additional challenges to connect the algorithm to the COCO platform.
Each algorithm shall be covered by at most two groups with independent languages. To make sure this happens, this wiki page will be devoted to this decision making task.
This instruction is self-explanatory, the corresponding papers will be provided together with the list of algorithms. Additional information about missing details on the algorithms in the papers might be provided wherever needed.
The group's implementation of the chosen algorithm shall be connected to the COCO platform and run on the corresponding noiseless test suite.
We do not impose any minimal length of the experiment (in terms of the number of function evaluations), but recommend to run the algorithm long enough. Long enough shall mean that one starts with short and very short experiments for testing (in the range of 2-10 times dimension many function evaluations) and increases this once the algorithm is thoroughly tested. A good, and easy-to-detect reason to increase the budget of the experiment further is when the ECDF graphs still increase after the big cross (when the algorithm is stopped). Such an increase of the ECDF curve after the stop of the algorithm indicates that at least one but not all instances have been yet successful on some problems. A longer experiment will increase the chance that those unsuccessful runs become successful, resulting in more data and more accurate results in the plots.
The resulting algorithm data set (after careful testing of course), together with the source code, shall be provided online on the wiki for each group. The deadline for this is Friday, the 19th of October 2018 such that other groups, potentially implementing the same algorithm in a different language can use the data sets to produce their final paper and presentation on time.
Each group is supposed to write a final report, based on the LaTeX templates, provided by COCO. The page limitation is 10 pages. The deadline is Wednesday, the 24th of October, 2018.
The report shall cover especially the description of the algorithm implemented and a discussion of the results. Thereby, the group's own algorithm, the independent implementation by the other group, and two baseline algorithms are to be compared. As baseline algorithms, BIPOP-CMA-ES and BFGS (both covered by the lecture) shall be used in the single-objective case; NSGA-II and a random search within [-5, 5]^n shall be used in the multi-objective case. The data sets of those algorithms can be found here for BIPOP-CMA-ES and here for BFGS. The multi-objective data sets are to be found here for NSGA-II and here for the random search. The data sets can also be accessed directly via COCO's postprocessing by using the names/wildcards "BIPOP!", "BFGS!", "NSGA", and "RANDOMSEARCH-5_Auger" respectively.
Recommended content of the paper:
To this end, a single document has to be written by each group, detailing the individual contributions. Please use the provided LaTeX template for this and fill out the missing details. Note that each group member has to sign this document before submission.
In addition to the final report, an oral presentation of 15min plus around 10min of questions on the topic is to be given by each group. The presentations will take place in individual time slots (to be decided during the lecture via the wiki) on November 8 and November 9. Note that all sessions are independent and students are not expected to go to other than their own session to keep the fairness between earlier and later group presentations.
Grades for the group project are group-based in the sense that each group is judged with a baseline grade that might be (slightly) adjusted for each individual student based on the submitted document, detailing each student's contribution to the group.
The grade will mainly depend on (i) the final report and on (ii) the oral presentation (and the responses to the questions of course) with both parts contributing about 50% to the grade. Minor influence on the grades have the source code, the documentation on the wiki, the individual contribution documentation (see above), and the timely submission of all required documents.
| Mon, 17.09.2018 | First lecture. |
| Thu, 20.09.2018 | Group building phase and assignment of each group to an algorithm and programming language finished. |
| Fri, 21.09.2018, 2:00pm | Each student has COCO installed and produced an example paper by following the Getting Started section of the COCO documentation. |
| Fri, 19.10.2018 | Algorithm data sets of each group available on the wiki. |
| Wed, 24.10.2018 | Paper submission deadline. This includes sending the document which describes the individual contributions. |
| Thu, 8.11.2018 and Fri, 9.11.2018 | Individual oral group presentations (to be fixed via the wiki). |
| Fri, 16.11.2018 | Final written exam. |
All deadlines, if not mentioned otherwise, are 23:59pm Paris time.
We recall that all groups are required to provide all documents via the wiki.
In case of questions, please first consider the FAQ section of the wiki and try to help others if you find an un-answered question there. Helping yourself within each group shall be the second step. Only if this does not solve your problem, please contact the lecturers during or after the class or by e-mail. Bug reports for the COCO platform (if they come up), shall be directly documented in the platform's issue tracker.