Brainstorming days on measure and polynomial optimization
Tuesday 27 Febrauary 2024, 16h30 Khashayar Neshat
Title: Exploiting symmetries for conic programmingTuesday 7 November 2023, 16h Pierre-David Letourneau
Title: An Efficient Framework for Global Non-Convex Polynomial Optimization over the Hypercubeslides
We present a novel efficient theoretical and numerical framework for solving global non-convex polynomial optimization problems. We analytically demonstrate that such problems can be efficiently reformulated using a non-linear objective over a convex set; further, these reformulated problems possess no spurious local minima (i.e., every local minimum is a global minimum). We introduce an algorithm for solving these resulting problems using the augmented Lagrangian and the method of Burer and Monteiro. We show through numerical experiments that polynomial scaling in dimension and degree is achievable for computing the optimal value and location of previously intractable global polynomial optimization problems in high dimension.
Monday 27 March 2023, 14h Carl Eggen
Title: Mixed-integer optimization methods for moment/sos hierarchies and application to energy networksslides
Abstract: In this talk, a model for decentralized energy supply network optimization is presented. This model yields a mixed-binary polynomial optimization problem (MBPOP) and thus the application of the moment/sos hierarchies to this type of optimization problems is investigated. Further, two methods from mixed-integer optimization, namely the feasibility pump and objective based bound tightening, are adapted to the moment/sos hierarchies. Finally, we show numerical results on some test instances from the MINLPLib.
Wednesday 15 February 2023, 10h Francis Bach
Title: Sums of squares: from algebra to analysisslides
Abstract: The representation of non-negative functions as sums of squares has become an important tool in many modeling and optimization tasks. Traditionally applied to polynomial functions, it requires rich tools from algebraic geometry that led to many developments in the last twenty years. In this talk, I will look at this problem from a functional analysis point of view, leading to new applications and new results on the performance of sum-of-squares optimization.
Wednesday 15 February 2023, 11h Olga Kuryatnikova
Title: Reducing non-negativity over general semialgebraic sets to non-negativity over simple setsslides
Abstract: A non-negativity certificate (NNC) is a way to write a polynomial so that its non-negativity on a semialgebraic set becomes evident. We propose a universal approach to derive NNCs that exist for positive polynomials on general semialgebraic sets from ones developed for simpler sets, such as a box, a simplex, a ball, or the non-negative orthant. The method applies to both compact and unbounded sets, and the resulting NNCs can be based not only on widely used sums-of-squares polynomials but also on other classes of polynomials, such as DSOS, SDSOS, SONC, and SAG. We present several new NNCs to illustrate the approach. The topic is based on the following working papers: arXiv:1909.06689, arXiv:2110.10079
Wednesday 16 January 2023, 14h Antonio Bellon
Title: How to solve Time-Varying Semidefinite Programs: Path Following a Burer-Monteiro Factorizationslides
Abstract: We present an online algorithm for time-varying semidefinite programs (TV-SDPs), based on the tracking of the solution trajectory of a low-rank matrix factorization, also known as the Burer-Monteiro factorization, in a path-following procedure. There, a predictor-corrector algorithm solves a sequence of linearized systems. This requires the introduction of a horizontal space constraint to ensure the local injectivity of the low-rank factorization. The method produces a sequence of approximate solutions for the original TV-SDP problem, for which we show that they stay close to the optimal solution path if properly initialized. Numerical experiments for a time-varying Max-Cut SDP relaxation demonstrate the computational advantages of the proposed method for tracking TV-SDPs in terms of runtime compared to off-the-shelf interior point methods.
Wednesday 7 December 2022, 10h Khazhgali Kozhasov
Title: Singularities of Spectrahedraslides
Abstract: Spectrahedra are feasible sets of semidefinite programs. They are convex sets with very interesting geometric properties. I will talk about the problem of counting singular points on the boundary of 3-dimensional spectrahedra. Specifically, I will discuss the case of spectrahedra defined by random matrices as well as present a classification of possible numbers of singularities of spectrahedra given by matrices of size 5 x 5. The talk is based on a joint work with Paul Breiding and Antonio Lerario and on a joint work with Taylor Brysiewicz and Mario Kummer.
Monday 26 September 2022, 10h Nando Leijenhorst
Title: Solving clustered low-rank semidefinite programs arising in polynomial optimizationslides
Abstract: Polynomial optimization problems are typically reformulated as semidefinite programs using sums-of-squares characterizations and coefficient matching. Alternatively, sampling is used instead of coefficient matching which leads to low-rank constraints. In this talk I will present a new solver we developed which uses the resulting low-rank structure. I will explain how to go from a polynomial optimization problems to a semidefinite program with low-rank constraint and how the solver exploits this, and I will briefly mention an application in discrete geometry where we combine this sampling approach with symmetry reduction. Joint work with D. de Laat.
Monday 28 March 2022, 10h Simone Naldi
Title: Spectrahedral representations of hyperbolic plane curvesslides
Abstract: A key question in the theory of hyperbolic polynomials is how to test hyperbolicity. This is classically done by computing a symmetric determinantal representation of the given polynomial. In the case of curves this is always possible, whereas in high dimension one should look at such representations for multiples of the given polynomial (according to the Generalized Lax Conjecture). In the talk I will discuss a variant of the classical Dixon method, for the computation of spectrahedral representations of curves. Then I will end with some details of a work in progress concerning polynomials that are "universal" for hyperbolicity. The talk is mostly based on a work joint with M. Kummer and D. Plaumann.
Monday 21 March 2022, 10h Nicolas Delanoue
Title: Version tropicale du théorème de Putinar. Dualité et applicationsslides
Abstract: here
Monday 28 February 2022, 10h Antonio Bellon
Title: Time-Varying Semidefinite Programming: Geometry of the Trajectory of Solutionsslides
Abstract: In many applications, solutions of convex optimization problems must be updated on-line, as functions of time. We consider time-varying semidefinite programs (TV-SDP), which are linear optimization problems in the semidefinite cone whose coefficients (input data) depend on time. We are interested in the geometry of the solution (output data) trajectory, defined as the set of solutions depending on time. An exhaustive description of the geometry of the solution trajectory is given and as our main result we show that only 6 distinct behaviors can be observed at a neighborhood of a given point along the solution trajectory. Possible behaviors are illustrated by examples.
Monday 28 February 2022, 11h Cédric Le Texier
Title: Hyperbolic plane curves near the non-singular tropical limitslides
Abstract: A plane real algebraic curve is said to be hyperbolic with respect to a real point if every real line going through that point intersect the curve in a maximal number of real points, counted with multiplicities. These curves appear in the context of semidefinite programming, as every hyperbolic plane curve admits a determinantal representation which is positive semidefinite on its points of hyperbolicity. We give a combinatorial characterisation of families of non-singular hyperbolic plane curves in terms of tropical geometry, and explore several questions around the tropical analogue of the hyperbolicity locus.
Monday 14 February 2022, 10h Alexey Lazarev
Title: Universal equivalence of symplectic groupsslides
Abstract: here
Monday 14 February 2022, 11h Adrien Le-Franc
Title: Capra-convexity in sparse optimizationslides
Abstract: here
Monday 24 January 2022, 10h Sven Polak
Title: Mutually unbiased bases: polynomial optimization and symmetryslides
Abstract: A set of k orthonormal bases of C^d is called mutually unbiased if |<e,f>|=1/sqrt(d) whenever e and f are basis vectors in distinct bases. A notorious question is for which pairs (d,k) there exist k mutually unbiased bases in dimension d. The (well-known) upper bound k<=d+1 is attained when d is a power of a prime. For all other dimensions it is an open problem whether the bound can be attained. Navascués, Pironio, and Acín showed how to reformulate the existence question in terms of the existence of a certain C*-algebra. This naturally leads to a noncommutative polynomial optimization problem and an associated hierarchy of semidefinite programs. The problem has a symmetry coming from the wreath product of S_d and S_k. We exploit this symmetry (analytically) to reduce the size of the semidefinite programs making them (numerically) tractable. Along the way we provide a novel explicit decomposition of a certain "L-shaped" permutation module into irreducible modules. We present numerical results for small d,k and low levels of the hierarchy. This is based on joint work with Sander Gribling, see arXiv:2111.05698
Monday 24 January 2022, 11h Andries Steenkamp
Title: An application of polynomial optimization to high order portfolio optimizationslides
Abstract: Portfolio optimization is the practice of buying/selling assets such that the collective pool of assets has maximized the expected return on investment and minimized the risk of losing money. Since the 1950's the Markowitz model was used to describe the risk and returns of a given portfolio. The model has since been extended to contain the higher-order terms: skewness and kurtosis. We attack this extended problem with POP alongside other optimization techniques in this talk.
Monday 10 January 2022, 9h30 Benoît Bonnet
Title: A Mean-Field Optimal Control Approach to the Training of NeurODEsslides
Abstract: In this talk, I will discuss some recent results that I obtained in collaboration with C. Cipriani, M. Fornasier and H. Huang on the topic of control-theoretic modelling for neural network. More specifically, we build on the continuous-time formulation of residual block networks - colloquially referred to as NeurODEs in the litterature - to propose a mean-field optimal control framework for the training of a class of neural networks. After discussing the underlying model, I will present two familes of first-order optimality conditions for these problems, as well as numerical simulations for simple classification problems in low dimension.
Tuesday 30 November 2021, 10h Zheng Qu
Title: On the exactness of Lasserre's relaxation for polynomial optimization with equality constraintsslides
Abstract: We study exactness condition for Lasserre's relaxation for polynomial optimization with n polynomial equality constraints, where n is the number of variables. Under the assumption that the quotient ring has dimension equal to the product of the degrees of the polynomials defining the feasible set, we show that Lasserre's relaxation is exact for degree larger than or equal to d, where d is the sum of the degrees of the defining polynomials minus the number of variables n. For relaxation of order smaller than d, we describe the exact region as the convex hull of the moment map image of a linear subspace. The convex hull lies in a tubular neighborhood of the moment map image with respect to the relative entropy distance for some universal constant. For relaxation of order equal to d-1, the convex hull coincides with the moment map image of the complexification of a hyperplane, and is diffeomorphic to its amoeba. Based on results from the theory of amoeba, we obtain an explicit description of the exact region for degree d-1 relaxation and its geometric properties, from which we further derive estimation of the degree (d-1)-relaxation error. As an application of our general theory we obtain various results about the exact region of the binary problem.
Tuesday 30 November 2021, 11h Lucas Slot
Title: Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernelslides
Abstract: We consider Lasserre's approximation hierarchies for the problem of minimizing a polynomial f over a compact semialgebraic set X in R^n. When X is the unit ball or the standard simplex, we show that the hierarchies based on Schmüdgen-type positivity certificates of degree r converge to the global minimum of f at a rate in O(1/r^2), matching recently obtained convergence rates for the hypersphere and hypercube [−1,1]^n. For our proof, we establish a connection between Lasserre's hierarchies and the Christoffel-Darboux kernel, and make use of closed form expressions for this kernel derived by Xu.
Monday 22 November 2021, 15h Mauricio Velasco
Title: Harmonic hierarchies for polynomial optimizationslides
Abstract: The cone of nonnegative forms of a given degree is a convex set of remarkable beauty and usefulness. In this talk we will discuss some recent ideas for approximating this set through polyhedra and spectrahedra. We call the resulting approximations harmonic hierarchies since they arise naturally from harmonic analysis on spheres (or equivalently from the representation theory of SO(n)). We will describe theoretical results leading to sharp estimates for the quality of these approximations and will also show a brief demo of our Julia implementation of harmonic hierarchies. These results are joint work with Sergio Cristancho (UniAndes).
Tuesday 9 November 2021, 14h Matias Bender
Title: Polynomial systems, sparsity, and applicationsslides
Abstract: Polynomial systems are ubiquitous in computational mathematics and have several applications in science and engineering. In this talk, I will present some linear-algebra-based strategies to compute with them. First, I will focus on solving, symbolically and numerically, structured systems such as sparse and multi-homogeneous. For that, I will merge classical tools, like Gröbner bases and resultants, with Toric geometry. Later, I will present some applications of these techniques in different domains such as differential equations and topological data analysis, among others.
Monday 8 November 2021, 10h Tong Chen
Title: Effective certification of monotone deep equilibrium modelsslides
Abstract: A presentation of the paper https://arxiv.org/pdf/2110.08260.pdf, about certification of monotone deep equilibrium models by using zonotopes.
Monday 18 October 2021, 15h Philipp di Dio
Title: Time-dependent moments from the heat equationslides
Abstract: We present a new connection between the classical theory of moments and the theory of partial differential equations (arXiv:2108.03505). For the classical heat equation we compute the moments of the unique solution. These moments are polynomials in the time variable, of degree comparable to the degree of the moment, and with coefficients satisfying a recursive relation. This allows us to define the polynomials for any sequence. In the case of moment sequences, the polynomials trace a curve (the heat curve) which remains in the moment cone for positive time, but may wander outside for negative times. We also study how the determinacy of a moment sequence behaves along the heat curve. We show that for several other partial differential equations we have access to the time-dependent moments without calculating the solution of the partial differential equation.
Monday 11 October 2021, 16h Julia Lindberg
Title: Polynomial system solving in applicationsslides
Abstract: Polynomial systems arise naturally in many applications in engineering and the sciences. This talk will outline classes of homotopy continuation algorithms used to solve them. I will then describe ways in which structures such as irreducibility, symmetry and sparsity can be used to improve computational speed. The efficacy of these algorithms will be demonstrated on systems in power systems engineering, statistics and optimization.
Monday 4 October 2021, 16h Mareike Dressler
Title: Signomial Moment Theory and Upper Bounds for Signomial Optimizationslides
Abstract: Signomials are obtained by generalizing polynomials to allow for arbitrary real exponents. This generalization offers great expressive power, but has historically sacrificed the organizing principle of "degree" that is central to polynomial optimization theory. In this talk, I introduce the concept of signomial rings that allows to reclaim that principle. Then I provide a language for and basic results in signomial moment theory that are analogous to those in the rich moment-SOS literature for polynomial optimization. That theory is used to turn (hierarchical) inner-approximations of signomial nonnegativity cones into (hierarchical) outer-approximations of the same. Finally, I explain how any such construction leads to highly structured convex programs which produce bounds that approach the minimum of a signomial from above. This is joint work with Riley Murray.
Monday 4 October 2021, 17h Riley Murray
Title: Theoretical and practical applications of signomial rings to polynomial optimizationslides
Abstract: Signomials generalize polynomials by allowing arbitrary real exponents, at the expense of restricting the resulting function to the positive orthant. This talk concerns a recently proven signomial Positivstellensatz based on "sums of arithmetic-geometric exponentials" (SAGE). The Positivstellensatz applies to compact sets which need not be convex or even basic semi-algebraic. In the first part of the talk, I explain how this result is derived through the newly-defined concept of signomial rings. Then I explain how the same concept leads to a new convex relaxation hierarchy for signomial optimization. These relaxations (which are based on relative entropy programming) can be solved more reliably than those arising from earlier SAGE-based Positivstellensatz. Moreover, this increase in reliability comes at no apparent cost of longer solver runtimes or worse bounds. Numerical examples are provided to illustrate the performance of the hierarchy on problems in chemical engineering and reaction networks. (Joint work with Mareike Dressler.)
Monday 20 September 2021, 15h Andreas Bluhm
Title: Free spectrahedra and quantum information theoryslides
Abstract: In this talk, I will explain how some problems in quantum information theory can be rephrased as inclusion problems of certain free spectrahedra. Free spectrahedra typically arise as matricial relaxations of linear matrix inequalities. A well-known example is the matrix cube. On the quantum side, I will focus on measurement incompatibility: Two quantum measurements are compatible if there exists a third one which implements both measurements at the same time. The best known example of incompatible measurements are the position and the momentum of a particle. Using the connection to free spectrahedra, we can show that inclusion constants correspond to the robustness of measurement incompatibility to white noise.
Monday 28 June 2021, 15h Jared Miller
Title: Bounding distances to unsafe setsslides
Abstract: We propose an algorithm to bound the minimum distance between points on trajectories of a dynamical system and points on an unsafe set. Prior work on certifying safety of trajectories includes barrier and density methods, which do not provide a margin of proximity to the unsafe set in terms of distance. The distance problem is relaxed to a Monge-Kantorovich type optimal transport problem based on existing occupation-measure methods of peak estimation. Specialized programs may be developed for polyhedral norm distances (e.g. L1 and Linfinity) and for scenarios where a shape is traveling along trajectories (e.g. rigid body motion).
Monday 28 June 2021, 16h Edgar Fuentes Figueroa
Title: Polynomial Optimization Techniques for Energy Network Operation and Designslides
Abstract: Global solution of the Optimal Power Flow (OPF) problem remains an active research topic. In particular, convex relaxations of the OPF problem based on semidefinite programming have been shown to deliver tight lower bounds and are an important tool for proving global optimality. In this category, Lasserre's hierarchy of moment relaxations has been useful to globally solve challenging instances. According to experiments, the second- and third-order moment relaxations are exact for many practical cases. However, realistic networks contain thousands of variables and exploiting the sparsity of the network becomes crucial for solving large-scale instances. Even for moderate-size instances, implementing a full second-order moment relaxation could become intractable. In this talk, we focus on introducing the OPF problem remarking the term sparsity structure of the quadratic constraints of the problem. To continue, we discuss some ideas found in the literature that allow to apply moment-like relaxations to OPF instances with up to 4000 variables.
Monday 14 June 2021, 15h Nicolas Augier
Title: On the ensemble controllability of quantum systemsslides
Abstract: The principal issue that will be developed in this talk is how to control a parameter-dependent family of quantum systems with a common control input, namely, the ensemble controllability problem. Thanks to the study of one-parameter families of Hamiltonians driven by two real controls and their generic spectrum singularities, we will give an explicit adiabatic control strategy when geometric conditions on the spectrum of the Hamiltonian are satisfied, i.e. when the Hamiltonian admits conical or semi-conical intersections of eigenvalues. Then, in order to understand which ensemble controllability properties can be extended to the case where the system is driven by a single real input, we will study the compatibility of the adiabatic with the rotating wave approximations.
Monday 14 June 2021, 16h Pierre-Emmanuel Emeriau
Title: Witnessing Wigner Negativityslides
Abstract: Quantum Information describes the behavior of information when encoded in degrees of freedoms of particles governed by the laws of quantum physics. It is important to study and better understand non-classical features allowed by the quantum theory. Negativity of the Wigner function is arguably one of the most striking non-classical features of quantum states. Beyond its fundamental relevance, it is also a necessary resource for quantum speedup with continuous variables. As quantum technologies emerge, the need to identify and characterize the resources which provide an advantage over existing classical technologies becomes more pressing. Yet it is quite challenging to detect Wigner negativity experimentally. Here we derive witnesses for Wigner negativity of single mode and multimode quantum states, based on fidelities with Fock states, which can be reliably measured and efficiently estimated using standard detection setups. These witnesses possess a threshold expectation value indicating whether the measured state has a negative Wigner function. Moreover, the amount of violation provides an operational quantification of Wigner negativity. We phrase the problem of finding the threshold values for our witnesses as an infinite-dimensional linear optimisation. By relaxing and restricting the corresponding linear programs, we derive two hierarchies of semidefinite programs, which provide numerical sequences of increasingly tighter upper and lower bounds for the threshold values. We further show that both sequences converge to the threshold value. Moreover, our witnesses form a complete family - each Wigner negative state is detected by at least one witness - thus providing a reliable method for experimentally witnessing Wigner negativity of quantum states from few measurements. From a foundational perspective, our findings provide insights on the set of positive Wigner functions which still lacks a proper characterisation.
Monday 31 May 2021, 15h Victor Magron
Title: Optimizing over trace polynomialsslides
Abstract: Motivated by recent progress in quantum information theory, this article aims at optimizing trace polynomials, i.e., polynomials in noncommuting variables and traces of their products. A novel Positivstellensatz certifying positivity of trace polynomials subject to trace constraints is presented, and a hierarchy of semidefinite relaxations converging monotonically to the optimum of a trace polynomial subject to tracial constraints is provided. This hierarchy can be seen as a tracial analog of the Pironio, Navascués and Acín scheme [New J. Phys., 2008] for optimization of noncommutative polynomials. The results obtained are applied to violations of polynomial Bell inequalities in quantum information theory.
Monday 17 May 2021, 15h Corbinian Schlosser
Title: An explicit proof of Vinter's theoremslides
Abstract: We provide a more elementary proof of Vinter's Theorem which states that optimal control problems with additional convexity properties can be reformulated as linear programs on the space of continuously differentiable functions. The constraints in this linear program are of Hamilton-Jacobi-Bellman (HJB) PDE type and the linear program gives the correct solution even if the optimal cost function is not smooth. We show that the optimal cost function can be approximated by a sequence of smooth functions, arising from relaxed optimal control problems (OCP), such that the HJB inequality that appears in Vinter's Theorem satisfied. Those relaxed OCPs treat the state constraints by penalty functions. This has the advantage that Lipschitz regularity of the optimal cost can be guaranteed and it overcomes the need to take the state constraints into account explicitly.
Monday 3 May 2021, 15h Jared Miller
Title: Analysis and Control of Time-Delay Systems with Occupation Measuresslides
Abstract: The evolution of time delay systems (delay differential equations) depends on present and past values of the state. This dependence on state histories can lead to instabilities, bifurcations, and nonintuitive behaviors which are not found in analogous ODE systems. Some instances of time delay systems with their associated delays include epidemic models (incubation period), population dynamics (gestation time), and fluid modeling (transport time of fluid moving in a pipe). This work presents an occupation measure framework to develop weak solutions over a finite time interval of nonlinear time-delay systems with a finite number of bounded discrete delays. A Liouville equation is formulated with respect to a joint occupation measure supported in delay coordinates. Data consistency in delayed coordinates is enforced by constraining marginals of the joint occupation measure with respect to shifted copies of component measures. Applications of this weak solution include optimal control (including dead-time), peak estimation, and reachable set estimation of time delay systems. This is joint work in collaboration with Milan Korda, Victor Magron, Alexandre Seuret and Mario Sznaier.
Tuesday 6 April 2021, 15h Felix Kirschner
Title: Convergence rates of RLT and Lasserre-type hierarchies of the generalized moment problem on the simplex and the sphereslides
Abstract: The talk is based on the following joint work with Etienne de Klerk arXiv:2103.02924. We consider the generalized moment problem (GMP) over the simplex and the sphere. This is a rich setting and it contains NP-hard problems as special cases, like constructing optimal cubature schemes and rational optimization. Using the Reformulation-Linearization Technique (RLT) and Lasserre-type hierarchies, relaxations of the problem are introduced and analyzed. For our analysis we assume throughout the existence of a dual optimal solution as well as strong duality. For the GMP over the simplex we prove a convergence rate of O(1/r) for a linear programming, RLT-type hierarchy, where r is the level of the hierarchy, using a quantitative version of Polya's Positivstellensatz. As an extension of a recent result by Fang and Fawzi arXiv:1908.05155 we prove the Lasserre hierarchy of the GMP over the sphere has a convergence rate of O(1/r^2).
Monday 29 March 2021, 15h Mateusz Skomra
Title: A machine learning framework for solving high-dimensional mean field gamesslides
Abstract: I will present a paper by Ruthotto, Osher, Li, Nurbekyan, and Fung, published in PNAS 2020 117 (17), about solving high-dimensional mean field games (MFG) using an approach based on machine learning. The results of the paper apply to potential MFGs, which can be formulated as infinite-dimensional optimal control problems. In order to solve these problems numerically, the authors propose a framework that consists of two steps. First, they show how to solve the continuity equation using the computation of characteristic curves. This reduces MFG to an unconstrained optimization problem that involves only the potential function. Second, they parametrize the potential using a neural network and transform MFG into a machine learning problem. In particular, this method does not use spatial discretization and is capable of solving problems in high dimensions. In the talk, I will introduce the notion of mean field games, present the framework from the paper, and discuss its applications to optimal transport and crowd motion problems.
Monday 22 March 2021, 15h Enrico Facca
Title: The Dynamical Monge-Kantorovich model. An Optimal Transport Problem tool for applied sciencesslides
Abstract: In this talk we present the Dynamical Monge-Kantorovich (DMK) model, a recent reformulation of the Optimal Transport Problem (OTP). This research field deals with the problem of finding the best strategy of moving resources from one place to another. The DMK model has been successfully applied in the numerical solution of the OTP on 2d, 3d, and surface domains. More recently, the model was applied also on graphs, where the combination of implicit time-stepping scheme with the Newton method resulted in an efficient numerical scheme able to tackle large scale OTP. In this presentation, we give an overview of the OTP and DMK models, with a particular focus on application of OT tools to applied problems.
Monday 8 March 2021, 15h Rodolfo Rios-Zertuche
Title: Long term dynamics of small step algorithmsslides
Abstract: We introduce "closed measures," a statistical method that is helpful in connecting the discrete and the continuous dynamics and revealing the quasi-periodicity of a range of algorithms that share the property that the distance between successive iterations vanishes asymptotically. The area of application includes many of the optimization algorithms used today for training large-scale neural networks, such as the small-step (stochastic) subgradient method, the heavyball algorithm, and Lyapunov function methods, and extends also to subdifferential inclusions and games.
Tuesday 16 February 2021, 15h Ulysse Marteau Ferret
Title: Finding Global Minima via Kernel Approximationsslides
Abstract: We consider the global minimization of smooth functions based solely on function evaluations. Algorithms that achieve the optimal number of function evaluations for a given precision level typically rely on explicitly constructing an approximation of the function which is then minimized with algorithms that have exponential running-time complexity. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum. This is done by using infinite sums of square smooth functions and has strong links with polynomial sum-of-squares hierarchies. Leveraging recent representation properties of reproducing kernel Hilbert spaces, the infinite-dimensional optimization problem can be solved by subsampling in time polynomial in the number of function evaluations, and with theoretical guarantees on the obtained minimum. The rate is nearly optimal in the case of Sobolev functions and more generally makes the proposed method particularly suitable for functions that have a large number of derivatives. Indeed, when m is in the order of d, the convergence rate to the global optimum does not suffer from the curse of dimensionality, which affects only the worst-case constants (that we track explicitly through the paper).
Tuesday 2 February 2021, 15h Didier Henrion
Title: Moment-SOS hierarchy and exit time of stochastic processesslides
Abstract: The moment sum of squares (moment-SOS) hierarchy produces sequences of upper and lower bounds on functionals of the exit time solution of a polynomial stochastic differential equation with polynomial constraints, at the price of solving semidefiniteoptimization problems of increasing size. In this talk we use standard results from elliptic partial differential equation analysis to prove convergence of the bounds produced by the hierarchy. We also use elementary convex analysis to describe a super-and sub-solution interpretation dual to a linear formulation on occupation measures. The practical relevance of the hierarchy is illustrated with numerical examples.
Tuesday 19 January 2021, 15h Corbinian Schlosser
Title: Theoretical Foundations for Higher Order Dynamic Mode Decompositionsslides
Abstract: I will talk about Liouville and Koopman operators, as well as reproducing kernel Hilbert spaces for dynamical systems, based on articles by J. Rosenfeld et al: arXiv:1909.11792, arXiv:1910.03977 and arXiv:2101.02646.
First Brainstorming day on measure and polynomial optimization
Friday 11 September 2020, 10h-12h 14h-16h, Salle du Conseil LAAS-CNRS
10h-10h10 Intro
10h10-10h40 Tong Chen
Title: Polynomial optimization for estimating the Lipschitz constant of neural networksslides
Abstract: The Lipschitz constant of neural networks is useful for several applications in deep learning, such as robustness certification. We first show the semi-algebraic description of the well-known ReLU function and its generalized derivative. Then we introduce a heuristic SDP relaxation to give an upper bound of the Lipschitz constant of multi-layer fully-connected neural networks. This approach can also be applied to give upper bounds of general nearly-dense POPs.
10h40-11h20 Hoang Ngoc Anh Mai
Title: A hierarchy of spectral relaxations for polynomial optimizationslides
Abstract: We show that (i) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (ii) the resulting semidefinite relaxations in the moment-SOS hierarchy have the constant trace property (CTP) for the involved matrices. We then exploit the CTP to avoid solving the semidefinite relaxations via interior-point methods and rather use ad-hoc spectral methods that minimize the largest eigenvalue of a matrix pencil. Efficiency and robustness of this spectral hierarchy is tested against on a sample of randomly generated quadratically constrained quadratic problems.
11h20-11h50 Corbinian Schlosser
Title: Sparse moment-sum-of-squares relaxations for nonlinear dynamical systems with guaranteed convergenceslides
Abstract: This talk will present sparse moment-sum-of-squares relaxations for various problems from nonlinear dynamical systems including maximum positively invariant set, region of attaction or global attractor. We show that these problems admit a sparse relaxation with guaranteed convergence such that the number of variables in the largest sum-of-squares multiplier is given by the longest weighted path of the vector field's sparsity graph. This allows for a significant reduction of the size of the SDP relaxations, thereby allowing to address far larger systems without compromising convergence guarantees. Numerical examples demonstrate the approach.
11h50-14h Lunch break
14h-14h30 Matteo Tacchi
Title: Approximating the region of attraction of a sparse dynamical systemslides
Abstract: Moment-SOS hierarchies are a powerful tool to analyse the stability of nonlinear differential systems by reducing complex problems into semidefinite programs. However, this method is very sensitive to dimensionality and becomes quickly intractable when addressing real life systems. A general solution to use Moment-SOS hierarchies in high dimension consists of exploiting the structure of the problem, e.g. sparsity in its description, as already done for optimization and volume computation. This talk intends to make a first step in the direction of sparse approximation of regions of attraction, with a first encouraging published result and a variety of open questions.
14h30-15h Jie Wang
Title: Exploiting term sparsity in large-scale polynomial optimizationslides
Abstract: Over the past twenty years, the moment-SOS hierarchy has become a powerful tool to tackle polynomial optimization. For large-scale problems, the cost and constraints typically involve only a few amount of terms. It is known that one can exploit correlative sparsity for moment-SOS hierarchies. However, this only takes into account correlations between variables and hence plenty of information hidden in the term level is lost. We show how to exploit the few correlations between terms and propose a novel term sparsity adapted moment-SOS hierarchy. In addition, correlative and term sparsity can be exploited simultaneously. By virtue of these results, we are able to solve polynomial optimization problems, e.g., AC-OPF or noncommutative eigenvalue/trace problems, involving up to several thousand of variables and constraints.