Publications

2022

• Global Solution of Quadratic Problems by Interval Methods and Convex Reformulation
  
  • Elloumi Sourour
  • Lambert Amélie
  • Neveu Bertrand
  • Trombettoni Gilles
  , 2022.
• An accelerated level-set method for inverse scattering problems
  
  • Audibert Lorenzo
  • Haddar Houssem
  • Liu Xiaoli
  SIAM Journal on Imaging Sciences, Society for Industrial and Applied Mathematics, 2022, 15 (3), pp.1576-1600. We propose a rapid and robust iterative algorithm to solve inverse acoustic scattering problems formulated as a PDE constrained shape optimization problem. We use a level-set method to represent the obstacle geometry and propose a new scheme for updating the geometry based on an adaptation of accelerated gradient descent methods. The resulting algorithm aims at reducing the number of iterations and improving the accuracy of reconstructions. To cope with regularization issues, we propose a smoothing to the shape gradient using a single layer potential associated with ik where k is the wave number. Numerical experiments are given for several data types (full aperture, backscattering, phaseless, multiple frequencies) and show that our method outperforms a non accelerated approach in terms of convergence speed, accuracy and sensitivity to initial guesses. (10.1137/21M1457783)
  DOI : 10.1137/21M1457783
• The stochastic Auxiliary Problem Principle in Banach spaces: measurability and convergence
  
  • Bittar Thomas
  • Carpentier Pierre
  • Chancelier Jean-Philippe
  • Lonchampt Jéro͂me
  SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2022, 32 (3), pp.1871-1900. The stochastic Auxiliary Problem Principle (APP) algorithm is a general Stochastic Approximation (SA) scheme that turns the resolution of an original optimization problem into the iterative resolution of a sequence of auxiliary problems. This framework has been introduced to design decomposition-coordination schemes but also encompasses many well-known SA algorithms such as stochastic gradient descent or stochastic mirror descent. We study the stochastic APP in the case where the iterates lie in a Banach space and we consider an additive error on the computation of the subgradient of the objective. In order to derive convergence results or efficiency estimates for a SA scheme, the iterates must be random variables. This is why we prove the measurability of the iterates of the stochastic APP algorithm. Then, we extend convergence results from the Hilbert space case to the Banach space case. Finally, we derive efficiency estimates for the function values taken at the averaged sequence of iterates or at the last iterate, the latter being obtained by adapting the concept of modified Fejér monotonicity to our framework. (10.1137/21M1402467)
  DOI : 10.1137/21M1402467
• Minimizing recovery cost of network optimization problems
  
  • Alès Zacharie
  • Elloumi Sourour
  Networks, Wiley, 2022. We propose a two-stage recoverable robustness approach that minimizes the recovery cost. In many applications, once the uncertainty ξ is revealed, it can be more important to recover a solution x ξ which is as similar as possible to the nominal solution x nom than to minimize the nominal objective value of x ξ. This for example occurs when the nominal solution is implemented on a regular basis or when the uncertainty is revealed late. We define the proactive problem which minimizes the weighted recovery costs over a discrete set of scenarios while ensuring optimality of the nominal objective value of x nom. We model the recovery cost of a scenario by a distance between the first-stage nominal solution and the second-stage solution recovered for this scenario. We show for two different solution distances d val and dstruct that the proactive problem is N P-hard for both the integer min-cost flow problem with uncertain arc demands and for the integer max-flow problem with uncertain arc capacities. For these two problems, we prove that once uncertainty is revealed, even identifying a reactive solution x r with a minimal distance to a given solution x nom is N P-hard for dstruct, and is polynomial for d val. We highlight the benefits of the proactive approach in a case study on a railroad planning problem. First, we compare it to the anchored and the k-distance approaches. Then, we show the efficiency of the proactive solution over reactive solutions. Finally, we illustrate the recovery cost reduction when relaxing the optimality constraint on the nominal objective of the proactive solution x nom. We also consider the min-max version of the proactive problem where we minimize the maximal recovery cost over all scenarios. We show that the same complexity results hold for this version. We also exhibit a class of problems for which the set of extreme points of the convex hull of a discrete uncertainty set always contain a worst-case scenario. We show that this result does not hold for three distinct classes deduced from the first one. (10.1002/net.22121)
  DOI : 10.1002/net.22121
• Relaxed-inertial proximal point algorithms for problems involving strongly quasiconvex functions
  
  • Grad Sorin-Mihai
  • Lara Felipe
  • Marcavillaca Raul Tintaya
  , 2022. Introduced in the 1970's by Martinet for minimizing convex functions and extended shortly afterward by Rockafellar towards monotone inclusion problems, the proximal point algorithm turned out to be a viable computational method for solving various classes of optimization problems, in particular with nonconvex objective functions. We propose first a relaxed-inertial proximal point type algorithm for solving optimization problems consisting in minimizing strongly quasiconvex functions whose variables lie in finitely dimensional linear subspaces. The method is then extended to equilibrium problems where the involved bifunction is strongly quasiconvex in the second variable. Possible modifications of the hypotheses that would allow the algorithms to solve similar problems involving quasiconvex functions are discussed, too. Numerical experiments confirming the theoretical results, in particular that the relaxed-inertial algorithms outperform their ``pure'' proximal point counterparts, are provided, too.
• Achievement and Fragility of Long-term Equitability
  
  • Simonetto Andrea
  • Notarnicola Ivano
  , 2022. Equipping current decision-making tools with notions of fairness, equitability, or other ethically motivated outcomes, is one of the top priorities in recent research efforts in machine learning, AI, and optimization. In this paper, we investigate how to allocate limited resources to {locally interacting} communities in a way to maximize a pertinent notion of equitability. In particular, we look at the dynamic setting where the allocation is repeated across multiple periods (e.g., yearly), the local communities evolve in the meantime (driven by the provided allocation), and the allocations are modulated by feedback coming from the communities themselves. We employ recent mathematical tools stemming from data-driven feedback online optimization, by which communities can learn their (possibly unknown) evolution, satisfaction, as well as they can share information with the deciding bodies. We design dynamic policies that converge to an allocation that maximize equitability in the long term. We further demonstrate our model and methodology with realistic examples of healthcare and education subsidies design in Sub-Saharian countries. One of the key empirical takeaways from our setting is that long-term equitability is fragile, in the sense that it can be easily lost when deciding bodies weigh in other factors (e.g., equality in allocation) in the allocation strategy. Moreover, a naive compromise, while not providing significant advantage to the communities, can promote inequality in social outcomes. (10.1145/3514094.3534132)
  DOI : 10.1145/3514094.3534132
• Long time behaviour for electromagnetic waves in dissipative Lorentz media
  
  • Cassier Maxence
  • Joly Patrick
  • Rosas Martinez Luis Alejandro
  , 2022. A very general class of models for describing the propagation of waves in dispersive electromagnetic media is provided by generalized Lorentz models. In this work, we study the long time behaviour of the solutions of the dissipative version of these models.
• Inverse problem for the Helmholtz equation and singular sources in the divergence form
  
  • Baratchart Laurent
  • Haddar Houssem
  • Villalobos Guillén Cristóbal
  , 2022. We shall discuss an inverse problem where the underlying model is related to sources generated by currents on an anisotropic layer. This problem is a generalization of another motivated by the recovering of magnetization distribution in a rock sample from outer measurements of the generated static magnetic field. The original problem can be formulated as inverse source problem for the Laplace equation [1,2] with sources being the divergence of the magnetization whereas the generalization comes from taking the Helmholtz equation. Either inverse problem is non uniquely solvable with a kernel of infinite dimension. We shall present a decomposition of the space of sources that will allow us to discuss constraints that may restore uniqueness and propose regularization schemes adapted to these assumptions. We then present some validating experiments and some related open questions.
• Scattering in a partially open waveguide: the inverse problem
  
  • Bourgeois Laurent
  • Fritsch Jean-François
  • Recoquillay Arnaud
  , 2022.
• One-Way methods for wave propagation in complex flows
  
  • Ruello Maëlys
  • Rudel Clément
  • Pernet Sébastien
  • Brazier Jean-Philippe
  , 2022.
• Learning equilibria with personalized incentives in a class of nonmonotone games
  
  • Fabiani Filippo
  • Simonetto Andrea
  • Goulart Paul J.
  , 2022. We consider quadratic, nonmonotone generalized Nash equilibrium problems with symmetric interactions among the agents, which are known to be potential. As may happen in practical cases, we envision a scenario in which an explicit expression of the underlying potential function is not available, and we design a two-layer Nash equilibrium seeking algorithm. In the proposed scheme, a coordinator iteratively integrates the noisy agents' feedback to learn the pseudo-gradients of the agents, and then design personalized incentives for them. On their side, the agents receive those personalized incentives, compute a solution to an extended game, and then return feedback measures to the coordinator. We show that our algorithm returns an equilibrium in case the coordinator is endowed with standard learning policies, and corroborate our results on a numerical instance of a hypomonotone game.
• Optimization of a domestic microgrid equipped with solar panel and battery: Model Predictive Control and Stochastic Dual Dynamic Programming approaches
  
  • Pacaud François
  • Carpentier Pierre
  • Chancelier Jean-Philippe
  • de Lara Michel
  Energy Systems, Springer, 2022, 15 (1), pp.115-139. In this study, a microgrid with storage (battery, hot water tank) and solar panel is considered. We benchmark two algorithms, MPC and SDDP, that yield online policies to manage the microgrid, and compare them with a rule based policy. Model Predictive Control (MPC) is a well-known algorithm which models the future uncertainties with a deterministic forecast. By contrast, Stochastic Dual Dynamic Programming (SDDP) models the future uncertainties as stagewise independent random variables with known probability distributions. We present a scheme, based on out-of-sample validation, to fairly compare the two online policies yielded by MPC and SDDP. Our numerical studies put to light that MPC and SDDP achieve significant gains compared to the rule based policy, and that SDDP overperforms MPC not only on average but on most of the out-of-sample assessment scenarios. (10.1007/s12667-022-00522-7)
  DOI : 10.1007/s12667-022-00522-7
• New optimization models for optimal classification trees
  
  • Alès Zacharie
  • Huré Valentine
  • Lambert Amélie
  , 2022.
• Convergence analysis of multi-step one-shot methods for linear inverse problems
  
  • Bonazzoli Marcella
  • Haddar Houssem
  • Vu Tuan Anh
  , 2022. In this work we are interested in general linear inverse problems where the corresponding forward problem is solved iteratively using fixed point methods. Then one-shot methods, which iterate at the same time on the forward problem solution and on the inverse problem unknown, can be applied. We analyze two variants of the so-called multi-step one-shot methods and establish sufficient conditions on the descent step for their convergence, by studying the eigenvalues of the block matrix of the coupled iterations. Several numerical experiments are provided to illustrate the convergence of these methods in comparison with the classical usual and shifted gradient descent. In particular, we observe that very few inner iterations on the forward problem are enough to guarantee good convergence of the inversion algorithm.
• OpReg-Boost: Learning to Accelerate Online Algorithms with Operator Regression
  
  • Bastianello Nicola
  • Simonetto Andrea
  • Dall'Anese Emiliano
  , 2022. This paper presents a new regularization approach -- termed OpReg-Boost -- to boost the convergence and lessen the asymptotic error of online optimization and learning algorithms. In particular, the paper considers online algorithms for optimization problems with a time-varying (weakly) convex composite cost. For a given online algorithm, OpReg-Boost learns the closest algorithmic map that yields linear convergence; to this end, the learning procedure hinges on the concept of operator regression. We show how to formalize the operator regression problem and propose a computationally-efficient Peaceman-Rachford solver that exploits a closed-form solution of simple quadratically-constrained quadratic programs (QCQPs). Simulation results showcase the superior properties of OpReg-Boost w.r.t. the more classical forward-backward algorithm, FISTA, and Anderson acceleration.
• A high-order discontinuous Galerkin Method using a mixture of Gauss-Legendre and Gauss-Lobatto quadratures for improved efficiency
  
  • Chaillat Stéphanie
  • Cottereau Régis
  • Sevilla Ruben
  , 2022. In discontinuous Galerkin spectral element methods (DGSEM), the two most common approaches to numerically integrate the terms of the weak form are either using Gauss-Legendre or Gauss-Lobatto quadratures. The former yields more accurate results but at a higher computational cost, so that a priori it is not clear whether one approach is more efficient that the other. In this paper, it is shown (theoretically for a particular case and numerically for the general case) that using Gauss-Lobatto quadrature for the convection matrix actually introduces a negligible error. In contrast, using Gauss-Lobatto quadratures for the evaluation of the jump term in the element faces introduces a sizeable error. This leads to the proposal of a new DG approach, where the convection matrix is evaluated using Gauss-Lobatto quadratures, whereas the face mass matrices are integrated using Gauss-Legendre quadratures. For elements with constant Jacobian and constant coefficients, a formal proof shows that no numerical integration error is actually introduced in the evaluation of the residual, even though both the mass and the convection matrices are not computed exactly with Gauss-Lobatto quadratures. For elements with non-constant Jacobian and/or non-constant coefficients, the impact of numerical integration error on the overall error is evaluated through a series of numerical tests, showing that this is also negligible. In addition, the computational cost associated to the matrix-vector products required to evaluate the residual is evaluated precisely for the different cases considered. The proposed approach is particularly attractive in the most general case, since the use of Gauss-Lobatto quadratures significantly speeds-up the evaluation of the residual.
• An efficient numerical method for time domain electromagnetic wave propagation in co-axial cables
  
  • Beni Hamad Akram
  • Beck Geoffrey
  • Imperiale Sébastien
  • Joly Patrick
  Computational Methods in Applied Mathematics, De Gruyter, 2022. In this work we construct an efficient numerical method to solve 3D Maxwell's equations in coaxial cables. Our strategy is based upon an hybrid explicit-implicit time discretization combined with edge elements on prisms and numerical quadrature. One of the objective is to validate numerically generalized Telegrapher's models that are used to simplify the 3D Maxwell equations into a 1D problem. This is the object of the second part of the article. (10.1515/cmam-2021-0195)
  DOI : 10.1515/cmam-2021-0195
• Stochastic incremental mirror descent algorithms with Nesterov smoothing
  
  • Grad Sorin-Mihai
  • Bitterlich Sandy
  , 2022. We propose a stochastic incremental mirror descent method constructed by means of the Nesterov smoothing for minimizing a sum of finitely many proper, convex and lower semicontinuous functions over a nonempty closed convex set in a Euclidean space. The algorithm can be adapted in order to minimize (in the same setting) a sum of finitely many proper, convex and lower semicontinuous functions composed with linear operators. Another modification of the scheme leads to a stochastic incremental mirror descent Bregman-proximal scheme with Nesterov smoothing for minimizing the sum of finitely many proper, convex and lower semicontinuous functions with a prox-friendly proper, convex and lower semicontinuous function in the same framework. Different to the previous contributions from the literature on mirror descent methods for minimizing sums of functions, we do not require these to be (Lipschitz) continuous or differentiable. Applications in Logistics, Tomography and Machine Learning modeled as optimization problems illustrate the theoretical achievements.
• Acoustic passive cloaking using thin outer resonators
  
  • Chesnel Lucas
  • Heleine Jérémy
  • Nazarov Sergei A
  Zeitschrift für Angewandte Mathematik und Physik = Journal of Applied mathematics and physics = Journal de mathématiques et de physique appliquées, Springer Verlag, 2022, 73 (3). We consider the propagation of acoustic waves in a 2D waveguide unbounded in one direction and containing a compact obstacle. The wavenumber is fixed so that only one mode can propagate. The goal of this work is to propose a method to cloak the obstacle. More precisely, we add to the geometry thin outer resonators of width ε and we explain how to choose their positions as well as their lengths to get a transmission coefficient approximately equal to one as if there were no obstacle. In the process we also investigate several related problems. In particular, we explain how to get zero transmission and how to design phase shifters. The approach is based on asymptotic analysis in presence of thin resonators. An essential point is that we work around resonance lengths of the resonators. This allows us to obtain effects of order one with geometrical perturbations of width ε. Various numerical experiments illustrate the theory. (10.1007/s00033-022-01736-6)
  DOI : 10.1007/s00033-022-01736-6
• Robust treatment of cross points in Optimized Schwarz Methods
  
  • Claeys Xavier
  • Parolin Emile
  Numerische Mathematik, Springer Verlag, 2022, 151 (2), pp.405-442. In the field of Domain Decomposition (DD), Optimized Schwarz Method (OSM) appears to be one of the prominent techniques to solve large scale time-harmonic wave propagation problems. It is based on appropriate transmission conditions using carefully designed impedance operators to exchange information between sub-domains. The efficiency of such methods is however hindered by the presence of cross-points, where more than two sub-domains abut, if no appropriate treatment is provided. In this work, we propose a new treatment of the cross-point issue for the Helmholtz equation that remains valid in any geometrical interface configuration. We exploit the multi-trace formalism to define a new exchange operator with suitable continuity and isometry properties. We then develop a complete theoretical framework that generalizes classical OSM to partitions with cross points and contains a rigorous proof of geometric convergence, uniform with respect to the mesh discretization, for appropriate positive impedance operators. Extensive numerical results in 2D and 3D are provided as an illustration of the performance of the proposed method. (10.1007/s00211-022-01288-x)
  DOI : 10.1007/s00211-022-01288-x
• Convergence d'un couplage élastique-acoustique FEM-BEM itératif, global en temps
  
  • Nassor Alice
  • Chaillat Stéphanie
  • Bonnet Marc
  • Leblé Bruno
  • Barras Guillaume
  , 2022. Une méthode itérative convergente pour le couplage FEM-BEM élastodynamique-acoustique global en temps, permettant de traiter un problème d’interaction fluide-structure est proposée. Les équations structures sont résolues en éléments finis (FEM), tandis que la partie fluide est traitée par éléments de frontière (BEM), formulée en temps discrets par Convolution Quadrature method (CQM). Le couplage présenté se base sur la formulation de conditions de transmission de Robin. La convergence est démontrée et illustrée. Un deuxième couplage itératif en temps à convergence garantie est proposé.
• Méthode des éléments de frontière pour la mécanique des failles et le contrôle sismique
  
  • Bagur Laura
  • Chaillat Stéphanie
  • Semblat Jean-François
  • Stefanou Ioannis
  , 2022. Ce travail consiste à vérifier numériquement des stratégies de contrôle de séismes par injection de fluide dans le sol. Nous étudions les capacités des méthodes d’éléments de frontière (BEMs) à simuler des séquences de glissements sismiques et asismiques en géomécanique. Un algorithme basé sur les BEMs accélérées par FFT est considéré, validé, et des résultats sont présentés pour un problème simple de mécanique des failles. Les challenges en lien avec l’extension des BEMs accélérées pour incorporer les couplages multi-physiques en jeu sont discutés.
• A non-overlapping domain decomposition method with perfectly matched layer transmission conditions for the Helmholtz equation
  
  • Royer Anthony
  • Geuzaine Christophe
  • Béchet Eric
  • Modave Axel
  Computer Methods in Applied Mechanics and Engineering, Elsevier, 2022, 395, pp.115006. It is well-known that the convergence rate of non-overlapping domain decomposition methods (DDMs) applied to the parallel finite-element solution of large-scale time-harmonic wave problems strongly depends on the transmission condition enforced at the interfaces between the subdomains. Transmission operators based on perfectly matched layers (PMLs) have proved to be well-suited for configurations with layered domain partitions. They are shown to be a good compromise between basic impedance conditions, which lead to suboptimal convergence, and computational expensive conditions based on the exact Dirichlet-to-Neumann (DtN) map related to the complementary of the subdomain. Unfortunately, the extension of the PML-based DDM for more general partitions with cross-points (where more than two subdomains meet) is rather tricky and requires some care. In this work, we present a non-overlapping substructured DDM with PML transmission conditions for checkerboard (Cartesian) decompositions that takes cross-points into account. In such decompositions, each subdomain is surrounded by PMLs associated to edges and corners. The continuity of Dirichlet traces at the interfaces between a subdomain and PMLs is enforced with Lagrange multipliers. This coupling strategy offers the benefit of naturally computing Neumann traces, which allows to use the PMLs as discrete operators approximating the exact Dirichlet-to-Neumann maps. Two possible Lagrange multiplier finite element spaces are presented, and the behavior of the corresponding DDM is analyzed on several numerical examples. (10.1016/j.cma.2022.115006)
  DOI : 10.1016/j.cma.2022.115006
• Spectral theory for Maxwell's equations at the interface of a metamaterial. Part II: Limiting absorption, limiting amplitude principles and interface resonance
  
  • Cassier Maxence
  • Hazard Christophe
  • Joly Patrick
  Communications in Partial Differential Equations, Taylor & Francis, 2022, 47 (6), pp.1217-1295. This paper is concerned with the time-dependent Maxwell's equations for a plane interface between a negative material described by the Drude model and the vacuum, which fill, respectively, two complementary half-spaces. In a first paper, we have constructed a generalized Fourier transform which diagonalizes the Hamiltonian that represents the propagation of transverse electric waves. In this second paper, we use this transform to prove the limiting absorption and limiting amplitude principles, which concern, respectively, the behavior of the resolvent near the continuous spectrum and the long time response of the medium to a time-harmonic source of prescribed frequency. This paper also underlines the existence of an interface resonance which occurs when there exists a particular frequency characterized by a ratio of permittivities and permeabilities equal to −1 across the interface. At this frequency, the response of the system to a harmonic forcing term blows up linearly in time. Such a resonance is unusual for wave problem in unbounded domains and corresponds to a non-zero embedded eigenvalue of infinite multiplicity of the underlying operator. This is the time counterpart of the ill-posdness of the corresponding harmonic problem. (10.1080/03605302.2022.2051188)
  DOI : 10.1080/03605302.2022.2051188
• Robust MILP formulations for the two-stage weighted vertex p-center problem
  
  • Durán Mateluna Cristian
  • Alès Zacharie
  • Jorquera-Bravo Natalia
  • Elloumi Sourour
  , 2022. The weighted vertex p-center problem (PCP) consists of locating p facilities among a set of potential sites such that the maximum weighted distance from any client to its closest open facility is minimized. This paper studies the exact resolution of the two-stage robust weighted vertex p-center problem (RPCP2). In this problem, the opening of the centers is fixed in the first stage while the client allocations are recourse decisions fixed once the uncertainty is revealed. The problem uncertainty comes from both the nodal demands and the edge lengths. It is modeled by box uncertainty sets. We introduce three different robust reformulations based on MILPs from the literature. We prove that considering a finite subset of scenarios is sufficient to obtain an optimal solution of (RPCP2). We leverage this result to introduce a column-and-constraint generation algorithm and a branch-and-cut algorithm to efficiently solve this problem optimally. We highlight how these algorithms can be adapted to solve, for the first time to optimality, the single-stage problem (RPCP1) which is obtained when no recourse is considered. We present a numerical study to compare the performance of these formulations on randomly generated instances and a case study from the literature.