Baptiste Plaquevent-Jourdain: Monday, 7th July 2025 – 10h30 to 12h00
Abstract:
The initial goal of this thesis is the resolution of complementarity problems. These problems are reformulated here by the minimum C-function, which is piecewise thus nondifferentiable and leads to nonsmooth systems. The globalization of local methods for such equations (semi smooth Newton for instance) generally faces the difficulty that the computed directions are not necessarily descent direction for the associated merit function, used in lineasearch methods (whereas for smooth equations, the opposite of the gradient always works). In the case of the minimum C-function, a recent method replaces the pseudo-linearization direction by a direction found in a suitable convex polyhedron, guaranteed to be nonempty by some stringent regularity condition. The initial objective was to remove the regularity condition, as for the smooth systems, by using a Levenberg-Marquardt approach. The piecewise smooth aspect of the merit function induced by the minimum implies to choose a certain piece, this choice being discussed towards the end of the presentation. When trying to better understand this method and the generalization of the derivative, the B(ouligand)-differential, for the minimum function, it appeared that, for the simple case of linear problems (or affine), the inherent structure of the B-differential is the one of an arrangement or hyperplanes. This problem, very classic in combinatorial geometry, that we discovered here, is actually surprisingly rich and deep. We propose improvements on a state-of-the-art algorithm identifying the chambers. In particular, « primal-dual » variants, linking the chambers of an arrangement with the circuits of the associated matroid, seem promising. This long detour is actually relevant for the nonsmooth method and the choice of the « piece ».
