Mini-project of Numerical Optimization course
General rules of the mini-project
The mini-project contributes to the final evaluation of Graduate School (GS) students only. Therefore, only GS students are required to participate. Other students can participate but they are not allowed to team up with GS students and their projects will not be supervised or evaluated. They can consult advices from the teaching teams though.
GS students form groups of 4 students (or fewer if we cannot form all 4-member groups). They will have to choose and explore one of the following projects. You can propose your own project but please consult the teaching teams (either me or Thomas).
In the end, each group is expected to prepare:
GS students form groups of 4 students (or fewer if we cannot form all 4-member groups). They will have to choose and explore one of the following projects. You can propose your own project but please consult the teaching teams (either me or Thomas).
In the end, each group is expected to prepare:
- An implementation in Python for your project
- A short report to summarize your project: the report should be around 3-5 pages (there is no strict page limit though). If your reports have many images/figures/graphs, you can have more pages, but please try to be as concise as possible. Lengthy report badly affects your note.
- A presentation: you will prepare a presentation of 15 minutes to present to the teaching teams. You do not need to send your presentation.
- Duration: 6 weeks
- Deadline for code and report: 23h59 (Paris time), 18 April 2026
- Project presentation date: During the week 20-24 April 2026
Evaluation of the mini-project
All projects will be evaluated based on their respective levels. More specifically, we categorize each project into 4 levels:
- Level 0: The project fails the objectives. Either the implementation or the report fails to prove that the students understand the core ideas of the paper and use it for specific applications.
- Level 1: The project successfully accomplishes the initial objectives given in its description. The code and report clearly show the understanding of the topics, techniques and related applications. You should get 65-80% (depending on the difficulties of the project) of the maximum note at this point.
- Level 2: Surpassing the initial objectives, students consider, implement and compare related models/algorithms/methods of the original project. This can be accomplished by reading and investigating researches citing/improving the original paper. You can also search for a review paper that summarizes the litterature of the original paper. Attaining this level, you will get 90-95% maximum note.
- Level 3: The students now have a very good understanding of the field and can either: identify fundamental challenges of the methods/techniques and/or propose new approach. Note that you need to reach level 2 before getting level 3: simply proposing (dump or supposedly new) ideas (without knowing existing works) does not get you to level 3. At this level, you typically get 100% (or more, there is no limit after) the maximum note.
Project proposals for the course: Numerical Optimization, M1 Applied Mathematics
Project 1: Nonnegative matrix factorization (NMF) and applications
This project introduces the nonnegative factoziation modelisation and its applications. Students are required to understand and implement the well-known multiplicative update rule and apply it to certain applications.
Main references
- The multiplicative update rule: Link to paper
- Applications: Several applications of NMF are introduced in Section 1.3 of the NMF book by Nicolas Gillis. You can find the datasets for these applications there-in.
Project 2: A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
This project investigate a fast proximal algorithm to minimize a composite function of the form f = g + h where h can be a non-convex function. We then use this algorithm to perform image denoising task.
Main references
Our main reference is the seminal paper by Amir Beck and Marc Teboulle, which provides a counterpart for Nesterov optimal algorithm in non-convex case. Students are expected to understand this paper, implement the methods and re-implement experiments (notably image denoising) in Section 5 of this paper.
Project 3: Sparse matrix factorization and applications
This project focus on sparse matrix factorization, a generalized version of the well-known linear inverse problems. We investigate how to approximate a matrix by the product of sparse factors, which can reduce the memory footage and accelerate the matrix-vector product operation. Students are expected to read and re-implement existing algorithms, then use their own implemented algorithms to factorize real-world matrices.
Main references
- Problem formulation and algorithms: Link to the paper. Note that the main algorithms in the previous paper is called Proximal Alternating Linearized Minimization (PALM), which is originally proposed and analysed in PALM paper. It is noteworthy that the latter is more difficult to understand.
- Sample codes: Several applications are discussed in Sections V-VI of Sparse Matrix Factorization paper. Some tutorials are available here.
Project 4: Robust Principal Component Analysis
This project is about Robust Principal Component Analysis (RPCA), a generalization of the well-known Principal Component Analysis (PCA). Students are expected to understand the modeling of RPCA, its corresponding optimization problem and implement an algorithm to solve it. Applications of RPCA are also expected from the project.
Main references
Our main reference is the seminal paper by Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright, which provides the theoretical framework for RPCA. An algorithm for RPCA is presented in Section 5. Applications can be found in Section 4. Re-implementing that algorithm and trying it with applications in this paper can be a good start.
Project 5: Black box variational inference
This project aims at performing variational inference, that is approximate a Bayesian posterior distribution by a simpler distribution, in a black box way, that is without using model-specific computations. Students are expected to implement the basic BBVI algorithm, use it to approximate simple Bayesian posteriors, and investigate variance reduction techniques and alternative algorithms.
Main references
Black-box variational inference (BBVI), was introduced in the eponymous paper from Rajesh Ranganath, Sean Gerrish, and David M. Blei, which proposed a stochastic gradient descent algorithm to solve the problem in Section 2. Strategies to reduce the variance are discussed in Section 3, and other algorithmic strategies in Section 4. Experiments are provided in Section 5.
Project 6: Expectation-maximization
Expectation-maximization (EM) is a classic algorithm for maximum likelihood estimation, in cases where the likelihood depends on unobserved latent variables.For this project, students are expected to implement the EM algorithm in the case of finite mixtures.
Main references
The EM algorithm was formalized by Arthur P. Dempster, Ann Laird, and Donald B. Rubin in 1977. The algorithms is defined in Section 2, and theoretical properties are provided in Section 3. Note that Section 3 also introduces a generalized EM algorithm. Section 4 is devoted to examples of applications. The EM algorithm is also introduced in a more modern format in the book Pattern Recognition and Machine Learning by Christopher M. Bishop (Chatper 9).
Project 7: Sinkhorn’s algorithm in optimal transport
Computing the optimal transport between two discrete measures can be formalized as a linear optimization problem, whose reoslution can be slow.Sinkhorn's algorithm has been proposed to solve an entropic regularization of the original optimal transport problem, and has been shown to converge much faster. The goal of this project is to implement Sinkhorn's algorithm, compare it to linear solvers, and apply it on optimal transport problems, possibly originating from machine learning.
Main references
The use of Sinkhorn's algorithm has been proposed in the context of regularized optimal transport by Marco Cuturi in 2013. This algorithm is also detailed in the book Computational Optimal Transport by Gabriel Peyré and Marco Cuturi (Chapter 4).
Project 8: Semi-smooth Newton methods for non-linear complementarity problems
Newton's method can be extended from the resolution of root-finding problems for smoth function to the resolution of so-called non-linear complementarity problems, which are non-smooth. These problems encompass in particular the resolution of constrained optimization problems and of game theory equilibriums. The students are expected to implement a semi-smooth version of the Newton's method and use it to solve problems from constrained optimization and game theory.
Main references
We consider the semi-smooth Newton's method proposed by Tecla De Luca, Francisco Facchinei, and Christian Kanzow. In this paper, Section 2 introduces some definitions associated with semi-smooth functions, Section 3 presents the algorithm, Section 4 and 5 presents some sufficient conditions for the well-posedness of the problem and the algorithm, the convergence proof is given in Section 6, and Section 7 gives some details about the implementation of the algorithm with some numerical results. Numerical experiments are performed on problems taken from the extensive numerical experiments in the earlier paper by Jong-Shi Pang and Steven A. Gabriel.