Un Mokameeting aura lieu le mercredi 7 juin 2023, à 14h, dans la salle A415 à l’Inria Paris. Nous aurons le plaisir d’écouter Jean-Charles Gilbert (Inria Paris) et João-Miguel Machado (Inria Paris et Ceremade, université Paris Dauphine).
Jean-Charles Gilbert : Polyhedral Newton-min algorithms for complementarity problems
Résumé : The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system.
If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-square merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent
algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-square function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a “negative kink” of the minimum function and acts accordingly.
In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global convergence to regular points is proved.
If time permits, we will also talk about a related problem, that of the computation of the B-differential of the componentwise minimum of affine functions and the link this problem has with the arrangements of hyperplanes and the bipartitions of a finite set of points.
João-Miguel Machado : Approximation 1D des mesures dans l’espace de Wasserstein
Résumé : Nous proposons une méthode variationnelle pour approcher une mesure parmi les mesures uniformément distribuées sur un ensemble de dimension 1. Le problème consiste à minimiser la distance de Wasserstein comme terme d’attache aux donnés avec une pénalisation de la longueur du support. Comme montrer l’existence de solutions est délicat, nous proposons un problème relaxé qui admet toujours des solutions. Ensuite nous montrons que si l’espace ambiant est \(\mathbb{R}^2\), sous les hypothèses techniques, n’importe quelle solution du problème relaxé est uniformément distribuée, et étant alors une solution du problème originel. Finalement nous montrons que les solutions du problème relaxé, et donc du problème originel, sont Ahlfors régulières.
