Many nonlinear integral energy functionals found in practice in continuum mechanics, such as strain energies, which we are interested in *globally* minimizing, are nonconvex, with multiple local minima and a complicated energy landscape. This makes the computation of their global minima very challenging and, except in select cases, far from guaranteed. The usual methods typically only ensure finding approximations of a local minimum through gradient descent or some version of Newton’s method on the Euler-Lagrange partial differential equations (PDEs) associated with the functional, but say nothing of whether the solution is a global minimum.

 

In this talk, for energy functionals with polynomial nonlinearity, we present an algorithm that provably converges to a global minimum and its corresponding minimizer, and can be applied to problems in nonlinear elasticity, fluid mechanics, pattern formation and PDE analysis. We do this by discretizing functions with finite element discretizations, and then leverage results from approximation theory of Sobolev spaces, calculus of variations, and most importantly, powerful representation theorems of sum-of-squares (SOS) polynomials coming from real algebraic geometry in the field of sparse polynomial optimization. More precisely, we show that as the mesh is refined and a relaxation parameter (associated to a polynomial degree) is raised, the computed results of a semidefinite program (SDP) converge to the global minimum.

 

We present numerical examples which result in excellent approximations to the global minima of different nonlinear functionals, including the pattern-forming Swift-Hohenberg free energy in two spatial dimensions, and talk about the extension to PDE-constrained minimization of such functionals, and how to use these methods in practice to produce "warm" initial guesses for Newton methods. 

Impartial selection addresses the problem of choosing one or more agents from a group based on nominations by other members of the group, in such a way that no agent can influence their own chance of being selected.

 

Deterministic mechanisms for selecting a single agent face strong impossibilities. For example, Holzman and Moulin (Econometrica, 2013) showed that when each agent nominates one other agent, no impartial mechanism can simultaneously satisfy positive unanimity—that an agent nominated by everyone else is selected—and negative unanimity—that an agent with no nominations is not selected. In response to such negative results, subsequent work has explored relaxations of this setting, either by allowing randomization or by permitting the selection of a variable number of agents. In this talk, we will further motivate these relaxations by presenting a strengthening of Holzman and Moulin’s impossibility for the case where agents may nominate any number of peers, and we will cover some recent results on both relaxations. We will also discuss how the performance of impartial mechanisms can be improved if a prediction of the optimal set of agents is available.

Backtracking line-search is an effective technique to automatically tune the step-size in smooth optimization, guaranteeing performance similar to what's achieved with the theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes, also known as diagonal preconditioners, but none of the existing methods are provably competitive with the optimal per-coordinate stepsizes.

 

In this talk, I will first give an introduction to this problem and discuss many "adaptive" methods, particularly those well-known in machine learning, that construct preconditioners during the optimization process. I will then present multidimensional backtracking, an extension of backtracking line-search to find good diagonal preconditioners for smooth convex problems. Our key insight is that the hypergradients—the gradient with respect to the step-sizes—yield separating hyperplanes that allow us to search for good preconditioners using cutting-plane methods. As black-box cutting-plane approaches like the ellipsoid method are computationally prohibitive, we develop an efficient algorithm tailored to our setting. Multidimensional backtracking is provably competitive with the best diagonal preconditioner and requires no manual tuning.

Denotemos por D la familia de conjuntos compactos y conexos en R² con área y perímetro finitos. En el contexto de diseño de mapas distritales, el índice más utilizado para medir cuan bueno es un distrito es el de Polsby-Popper: para un conjunto C ∈ D el índice se calcula como 4πA(C)/P (C)², donde A(C) es el área de C y P (C) su perímetro. Este índice isoperimétrico toma valores en [0, 1] y alcanza el valor 1 cada vez que tomamos una bola en la norma l2. A pesar de su amplio uso, “to the best of my knowledge”, no hay una caracterización axiomática de este índice que permita recuperarlo a partir de propiedades buscadas en el diseñoo del índice. Por ejemplo, el índice de Polsby-Popper satisface las siguientes propiedades:

Generating synthetic data is one of the key problems in private data analysis. In this talk, I will provide a summary of existing work, including well-established privacy attacks from the literature. After this introduction, I will present recent contributions on generating private synthetic data with relative accuracy guarantees (i.e, a mixture of additive and multiplicative error). Our main result provides (counting) error rates can be made poly-logarithmic in the sample size, data universe size, and the number of linear queries; a result which is provably unattainable in the purely-additive counterpart.

 

In this talk we present a survey of our research in the past decade on error bounds and convergence rates for deterministic as well as stochastic fixed point iterations, including the Krasnoselskii-Mann, Halpern, and similar iterative methods. 

We will emphasize the essential role played by techniques of optimal transport and Markov chains with rewards in obtaining tight error bounds. We will also discuss a few examples that illustrate how these error bounds are used to analyze the computational complexity of known algorithms in optimization and reinforcement learning for Markov decision processes, and how they can lead to design new algorithms with better complexity guarantees.

This talk outlines a novel class of high-order methods for the efficient numerical evaluation of volume potentials (VPs) defined by volume integrals over complex geometries. Inspired by the Density Interpolation Method (DIM) for boundary integral operators, the proposed methodology leverages Green’s third identity and a local polynomial interpolation of the density function to recast a given VP as a linear combination of surface-layer potentials and a volume integral with a regularized (bounded or smoother) integrand. The layer potentials can be accurately and efficiently evaluated inside and outside the integration domain using existing methods (e.g. DIM), while the regularized volume integral can be accurately evaluated by applying elementary quadrature rules to integrate over structured or unstructured domain decompositions without local numerical treatment at and around the kernel singularity. The proposed methodology is flexible, easy to implement, and fully compatible with well-established fast algorithms such as the Fast Multipole Method and H-matrices, enabling VP evaluations to achieve linearithmic computational complexity. To demonstrate the merits of the proposed methodology, we applied it to the Nyström discretization of the Lippmann-Schwinger volume integral equation for frequency-domain Helmholtz scattering problems in piecewise-smooth variable media.

 

This is joint work with Thomas G. Anderson (Rice University), Luiz Faria (ENSTA Paris), and Marc Bonnet (ENSTA Paris).

 

Optimization problems are often solved using constraint programming or mixed-integer programming techniques, using enumeration or branch-and-bound techniques. It is well known that if the problem formulation is very symmetric, there may exist many symmetrically equivalent solutions to the problem. Without handling the symmetries, traditional solving methods have to check many symmetric parts of the solution space, which comes at a high computational cost. Handling symmetries in optimization problems is thus essential for devising efficient solution methods.

The presentation will introduce and review common methods for solving mathematical programs, the concepts of symmetries in mathematical programs, and how symmetries can be handled. Then, the main results of Jasper's dissertation are presented, along with computational results. In particular, the presentation focuses on a general framework for symmetry handling that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other in the literature, the framework allows to apply different symmetry handling methods simultaneously and thus outperform their individual effects. Moreover, most existing symmetry handling methods only apply to binary variables. Our framework allows to easily generalize these methods to general variable types. Numerical experiments confirm that our novel framework is superior to the state-of-the-art methods implemented in the solver SCIP.

The Helmholtz equation for harmonic wave propagation is a widely used model for many acoustic phenomena, such as room acoustics, sonar, and biomedical ultrasound. The boundary element method (BEM) is one of the most efficient numerical methods to solve Helmholtz transmission problems and is based on boundary integral formulations that rewrite the volumetric partial differential equations into a representation of the acoustic fields in terms of surface potentials at the material interfaces. OptimUS (https://github.com/optimuslib/optimus) is a Python library centred around the BEM, which offers a user-friendly interface via Jupyter Notebooks, enabling the prediction of acoustic waves in piecewise homogeneous media in the frequency domain. 

 

This talk will provide an overview of the OptimUS interface, with a focus on case studies where objects are large relative to the wavelengths involved. This will include biomedical ultrasound, which has a growing number of therapeutic applications such as the treatment of cancers of the liver and kidney. The modelling of transcranial ultrasound neurostimulation, an emerging modality which may one day treat mental health conditions such as depression, will also be reviewed. Acoustic wave propagation into the uterus at audio range frequencies will be presented to provide awareness of the impact of everyday noise exposure on the developing fetus.

 

When studying complex systems that evolve over time, it is often not enough to just predict the future. We also want to know if equilibrium states are stable, how the system will behave on average over a long time, and how uncertainty impacts the dynamics. Techniques from polynomial optimization can be used to make these predictions when we have explicit models for the dynamics based on polynomial equations. But what if the model isn’t based on polynomial equations or, worse, we don't know the model at all?

 

In this talk, I will discuss how we can analyze dynamical systems using only data from measurements, with no need for an explicit mathematical model. The main idea is to combine polynomial optimization with a data analysis technique called extended dynamic mode decomposition, which is related to the celebrated Koopman operator. I will introduce these tools, show how they work together, and illustrate their effectiveness with examples related to stability and long-term behavior.

Fixed-point iterations provide a systematic method to approximate solutions for a wide range of problems, including operator equations, nonlinear equations, and optimization tasks. Recently, stochastic variants of these iterations have garnered attention due to their applicability in scenarios where the underlying operators are uncertain, noisy, or random. However, despite this growing interest, stochastic fixed-point iterations in non-Euclidean settings remain underexplored compared to related frameworks, such as stochastic monotone inclusions, variational inequalities, or stochastic optimization, which are predominantly studied in Euclidean spaces.

 

In this talk, we analyze the oracle complexity of stochastic Mann-type iterations designed to approximate fixed points of nonexpansive and contractive maps in a finite-dimensional space equipped with a general norm. We establish both upper and lower bounds on the convergence rate of the fixed-point residual and provide conditions for almost sure convergence of the iterates. Our findings have potential applications in reinforcement learning and bilevel optimization.

Prophet inequalities are a cornerstone in optimal stopping and online decision-making. Traditionally, they involve the sequential observation of n non-negative independent random variables and face irrevocable accept-or-reject choices. The goal is to provide policies that provide a good approximation ratio against the optimal offline solution that can access all the values upfront -- the so-called prophet value. In the prophet inequality over time problem, the decision-maker can commit to an accepted value for T units of time, during which no new values can be accepted. This creates a trade-off between the duration of commitment and the opportunity to capture potentially higher future values.

 

In this work we provide optimal approximation guarantees for the IID setting. We show a single-threshold algorithm that achieves an approximation ratio of (1+1/e^2)/2≈0.567, and we prove that no single-threshold algorithm can surpass this guarantee. Then, for each n, we prove it is possible to compute the tight worst-case approximation ratio of the optimal dynamic programming policy for instances with n values by solving a convex optimization program. A limit analysis of the first-order optimality conditions yields a nonlinear differential equation showing that the optimal dynamic programming policy's asymptotic worst-case approximation ratio is ≈0.618. Joint work with Sebastian Pérez-Salazar (Rice University, USA).

The advent of generative AI has turbocharged the development of a myriad of commercial applications, and it has slowly started to permeate into scientific computing. In this talk we discussed how recasting the formulation of old and new problems within a probabilistic approach opens the door to leverage and tailor state-of-the-art generative AI tools. As such, we review recent advancements in Probabilistic SciML – including computational fluid dynamics, inverse problems, and particularly climate sciences, with an emphasis on statistical downscaling.

 

Statistical downscaling is a crucial tool for analyzing the regional effects of climate change under different climate models: it seeks to transform low-resolution data from a (potentially biased) coarse-grained numerical scheme (which is computationally inexpensive) into high-resolution data consistent with high-fidelity models.

 

We recast this problem in a two-stage probabilistic framework using unpaired data by combining two transformations: a debiasing step performed by an optimal transport map, followed by an upsampling step achieved through a probabilistic conditional diffusion model. Our approach characterizes conditional distribution without requiring paired data and faithfully recovers relevant physical statistics, even from biased samples.

 

We will show that our method generates statistically correct high-resolution outputs from low-resolution ones, for different chaotic systems, including well known climate models and weather data. We show that the framework is able to upsample up to 300x while accurately matching the statistics of relevant physical quantities – even when the low-frequency content of the inputs and outputs differs. This is a crucial yet challenging requirement that existing state-of-the-art methods usually struggle with.