Author: "Victor MAGRON" / Language: english - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Victor MAGRON"' showing total 30 results

Start Over Author "Victor MAGRON" Language english

30 results on '"Victor MAGRON"'

1. Certifying Ground-State Properties of Many-Body Systems

Author: Jie Wang, Jacopo Surace, Irénée Frérot, Benoît Legat, Marc-Olivier Renou, Victor Magron, and Antonio Acín
Subjects: Physics, QC1-999
Abstract: A ubiquitous problem in quantum physics is to understand the ground-state properties of many-body systems. Confronted with the fact that exact diagonalization quickly becomes impossible when increasing the system size, variational approaches are typically employed as a scalable alternative: Energy is minimized over a subset of all possible states and then different physical quantities are computed over the solution state. Despite remarkable success, rigorously speaking, all that variational methods offer are upper bounds on the ground-state energy. On the other hand, so-called relaxations of the ground-state problem based on semidefinite programming represent a complementary approach, providing lower bounds to the ground-state energy. However, in their current implementation, neither variational nor relaxation methods offer provable bound on other observables in the ground state beyond the energy. In this work, we show that the combination of the two classes of approaches can be used to derive certifiable bounds on the value of any observable in the ground state, such as correlation functions of arbitrary order, structure factors, or order parameters. We illustrate the power of this approach in paradigmatic examples of 1D and 2D spin-1/2 Heisenberg models. To improve the scalability of the method, we exploit the symmetries and sparsity of the considered systems to reach sizes of hundreds of particles at much higher precision than previous works. Our analysis therefore shows how to obtain certifiable bounds on many-body ground-state properties beyond energy in a scalable way.
Published: 2024
Full Text: View/download PDF

2. Correlations constrained by composite measurements

Author: John H. Selby, Ana Belén Sainz, Victor Magron, Łukasz Czekaj, and Michał Horodecki
Subjects: Physics, QC1-999
Abstract: How to understand the set of correlations admissible in nature is one outstanding open problem in the core of the foundations of quantum theory. Here we take a complementary viewpoint to the device-independent approach, and explore the correlations that physical theories may feature when restricted by some particular constraints on their measurements. We show that demanding that a theory exhibits a composite measurement imposes a hierarchy of constraints on the structure of its sets of states and effects, which translate to a hierarchy of constraints on the allowed correlations themselves. We moreover focus on the particular case where one demands the existence of a correlated measurement that reads out the parity of local fiducial measurements. By formulating a non-linear Optimisation Problem, and semidefinite relaxations of it, we explore the consequences of the existence of such a parity reading measurement for violations of Bell inequalities. In particular, we show that in certain situations this assumption has surprisingly strong consequences, namely, that Tsirelson's bound can be recovered.
Published: 2023
Full Text: View/download PDF

3. Formal Proofs for Nonlinear Optimization

Author: Victor Magron, Xavier Allamigeon, Stéphane Gaubert, and Benjamin Werner
Subjects: Polynomial Optimization Problems, Hybrid Symbolic-numeric Certification, Semidefinite Programming, Transcendental Functions, Semialgebraic Relaxations, Flyspeck Project, Maxplus Approximation, Templates Method, Proof Assistant, Electronic computers. Computer science, QA75.5-76.95, Analytic mechanics, QA801-939
Abstract: We present a formally verified global optimization framework. Given a semialgebraic or transcendental function f and a compact semialgebraic domain K, we use the nonlinear maxplus template approximation algorithm to provide a certified lower bound of f over K.This method allows to bound in a modular way some of the constituents of f by suprema of quadratic forms with a well chosen curvature. Thus, we reduce the initial goal to a hierarchy of semialgebraic optimization problems, solved by sums of squares relaxations. Our implementation tool interleaves semialgebraic approximations with sums of squares witnesses to form certificates. It is interfaced with Coq and thus benefits from the trusted arithmetic available inside the proof assistant. This feature is used to produce, from the certificates, both valid underestimators and lower bounds for each approximated constituent.The application range for such a tool is widespread; for instance Hales' proof of Kepler's conjecture yields thousands of multivariate transcendental inequalities. We illustrate the performance of our formal framework on some of these inequalities as well as on examples from the global optimization literature.
Published: 2015
Full Text: View/download PDF

4. A FORMAL PROOF OF THE KEPLER CONJECTURE

Author: THOMAS HALES, MARK ADAMS, GERTRUD BAUER, TAT DAT DANG, JOHN HARRISON, LE TRUONG HOANG, CEZARY KALISZYK, VICTOR MAGRON, SEAN MCLAUGHLIN, TAT THANG NGUYEN, QUANG TRUONG NGUYEN, TOBIAS NIPKOW, STEVEN OBUA, JOSEPH PLESO, JASON RUTE, ALEXEY SOLOVYEV, THI HOAI AN TA, NAM TRUNG TRAN, THI DIEP TRIEU, JOSEF URBAN, KY VU, and ROLAND ZUMKELLER
Subjects: 52C17, Mathematics, QA1-939
Abstract: This article describes a formal proof of the Kepler conjecture on dense sphere packings in a combination of the HOL Light and Isabelle proof assistants. This paper constitutes the official published account of the now completed Flyspeck project.
Published: 2017
Full Text: View/download PDF

5. Sums of squares representations on singular loci

Author: Ngoc Hoang Anh Mai, Victor Magron, University of Konstanz, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), This work was supported by the FastQI grant funded by the Institut Quantique Occitan, the PHC Proteus grant 46195TA, the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: Mathematics - Algebraic Geometry, Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Algebraic Geometry (math.AG)
Abstract: The problem of characterizing a real polynomial $f$ as a sum of squares of polynomials on a real algebraic variety $V$ dates back to the pioneering work of Hilbert in [Mathematische Annalen 32.3 (1888): 342-350]. In this paper, we investigate this problem with a focus on cases where the real zeros of $f$ on $V$ are singular points of $V$. By using optimality conditions and irreducible decomposition, we provide a positive answer to the following essential question of polynomial optimization: Are there always exact semidefinite programs to compute the minimum value attained by a given polynomial over a given real algebraic variety? Our answer implies that Lasserre's hierarchy, which is known as a bridge between convex and non-convex programs with algebraic structures, has finite convergence not only in the generic case but also in the general case. As a result, we constructively prove that each hyperbolic program is equivalent to a semidefinite program., Comment: 27 pages. arXiv admin note: substantial text overlap with arXiv:2211.12440
Published: 2023

6. Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients

Author: Victor Magron, Mohab Safey El Din, Trung-Hieu Vu, Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), DesCartes funded by the CREATE Programme on AI-based Decision making in Critical Urban Systems, FastQI funded by the institute Quantum technologies in Occitanie, EPICS funded by the Gaspard Monge Program for Optimization and operationnal research, Fondation Jacques Hadamard, ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Magron, Victor, Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID, TREMPLIN-ERC - Optimisation garantie pour la vérification des systèmes cyber-physiques - - COPS2018 - ANR-18-ERC2-0004 - TERC - VALID, Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID, Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, and European Project: 813211,H2020,POEMA(2019)
Subjects: Computer Science - Symbolic Computation, FOS: Computer and information sciences, Optimization and Control (math.OC), Applied Mathematics, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Symbolic Computation (cs.SC), Mathematics - Optimization and Control, Software, Theoretical Computer Science
Abstract: Assessing non-negativity of multivariate polynomials over the reals, through the computation of {\em certificates of non-negativity}, is a topical issue in polynomial optimization. This is usually tackled through the computation of {\em sums-of-squares decompositions} which rely on efficient numerical solvers for semi-definite programming. This method faces two difficulties. The first one is that the certificates obtained this way are {\em approximate} and then non-exact. The second one is due to the fact that not all non-negative polynomials are sums-of-squares. In this paper, we build on previous works by Parrilo, Nie, Demmel and Sturmfels who introduced certificates of non-negativity modulo {\em gradient ideals}. We prove that, actually, such certificates can be obtained {\em exactly}, over the rationals if the polynomial under consideration has rational coefficients and we provide {\em exact} algorithms to compute them. We analyze the bit complexity of these algorithms and deduce bit size bounds of such certificates., Comment: 24 pages, 2 tables
Published: 2023
Full Text: View/download PDF

7. L 2+ Induced Norm Analysis of Continuous-Time LTI Systems Using Positive Filters and Copositive Programming

Author: Yoshio Ebihara, Hayato Motooka, Hayato Waki, Noboru Sebe, Victor Magron, Dimitri Peaucelle, Sophie Tarbouriech, Kyushu University, Kyushu Institute of Technology (Kyutech), Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: nonnegative signal, positive filter, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, copositive programming, L2+ induced norm
Abstract: International audience; This paper is concerned with the analysis of the L2 induced norm of continuous-time LTI systems where the input signals are restricted to be nonnegative. This induced norm is referred to as the L2+ induced norm in this paper. It has been shown very recently that the L2+ induced norm is particularly useful for the stability analysis of nonlinear feedback systems constructed from linear systems and static nonlinearities where the nonlinear elements only provide nonnegative signals. For the upper bound computation of the L2+ induced norm, an approach with copositive programming has also been proposed. It is nonetheless true that this approach becomes effective only for multi-input systems, and for single-input systems this approach does not bring any improvement over the trivial upper bound, the standard L2 norm. To overcome this difficulty, we newly introduce positive filters to increase the number of positive signals. This enables us to enlarge the size of the copositive multipliers so that we can obtain better (smaller) upper bounds with copositive programming.
Published: 2022
Full Text: View/download PDF

8. Stability of Linear Systems under Extended Weakly-Hard Constraints

Author: Victor Magron, Nils Vreman, Jie Wang, Paolo Pazzaglia, Martina Maggio, Automatic Control Group [Lund], Lund University [Lund], Saarland University [Saarbrücken], Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Equipe Polynomial OPtimization (LAAS-POP), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Magron, Victor, TREMPLIN-ERC - Optimisation garantie pour la vérification des systèmes cyber-physiques - - COPS2018 - ANR-18-ERC2-0004 - TERC - VALID, Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID
Subjects: Control and Optimization, Optimization and Control (math.OC), Control and Systems Engineering, FOS: Mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract: Control systems can show robustness to many events, like disturbances and model inaccuracies. It is natural to speculate that they are also robust to sporadic deadline misses when implemented as digital tasks on an embedded platform. This paper proposes a comprehensive stability analysis for control systems subject to deadline misses, leveraging a new formulation to describe the patterns experienced by the control task under different handling strategies. Such analysis brings the assessment of control systems robustness to computational problems one step closer to the controller implementation., 6 pages, 1 table, published in IEEE Control Systems Letters and in the proceedings of the Control and Decision Conference 2022
Published: 2022
Full Text: View/download PDF

9. A Sublevel Moment-SOS Hierarchy for Polynomial Optimization

Author: Tong Chen, Jean B. Lasserre, Victor Magron, Edouard Pauwels, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université Toulouse III - Paul Sabatier (UT3), FMJH Program PGMO (EPICS project), Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbers FA9550-19-1-7026, FA9550-18-1-0226, ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-CE23-0017,MaSDOL,Mathématiques de l'optimisation déterministe et stochastique liées à l'apprentissage profond(2019), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), and European Project: 813211,H2020,POEMA(2019)
Subjects: Discrete mathematics, 021103 operations research, Control and Optimization, Hierarchy (mathematics), Applied Mathematics, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, Lipschitz continuity, 01 natural sciences, Moment (mathematics), Computational Mathematics, Optimization and Control (math.OC), Robustness (computer science), FOS: Mathematics, Combinatorial optimization, [INFO]Computer Science [cs], Relaxation (approximation), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, Integer programming, Mathematics - Optimization and Control, Mathematics, Interpolation
Abstract: We introduce a sublevel Moment-SOS hierarchy where each SDP relaxation can be viewed as an intermediate (or interpolation) between the d-th and (d+1)-th order SDP relaxations of the Moment-SOS hierarchy (dense or sparse version). With the flexible choice of determining the size (level) and number (depth) of subsets in the SDP relaxation, one is able to obtain different improvements compared to the d-th order relaxation, based on the machine memory capacity. In particular, we provide numerical experiments for d=1 and various types of problems both in combinatorial optimization (Max-Cut, Mixed Integer Programming) and deep learning (robustness certification, Lipschitz constant of neural networks), where the standard Lasserre's relaxation (or its sparse variant) is computationally intractable. In our numerical results, the lower bounds from the sublevel relaxations improve the bound from Shor's relaxation (first order Lasserre's relaxation) and are significantly closer to the optimal value or to the best-known lower/upper bounds., 25 pages, 13 tables
Published: 2022
Full Text: View/download PDF

10. Exploiting Sparsity in Complex Polynomial Optimization

Author: Jie Wang, Victor Magron, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Equipe Polynomial OPtimization (LAAS-POP), The second author was supported by the FMJH Program PGMO (EPICS project), as well as the PEPS2 program (FastOPF project) funded by AMIES and RTE., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), and European Project: 813211,H2020,POEMA(2019)
Subjects: Correlative, Mathematical optimization, Control and Optimization, Optimization problem, media_common.quotation_subject, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, Management Science and Operations Research, 01 natural sciences, Statistics::Machine Learning, FOS: Mathematics, Quality (business), 0101 mathematics, Complex polynomial, Mathematics - Optimization and Control, Mathematics, media_common, 021103 operations research, Hierarchy (mathematics), Applied Mathematics, Explained sum of squares, Term (time), Power flow, Optimization and Control (math.OC), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: In this paper, we study the sparsity-adapted complex moment-Hermitian sum of squares (moment-HSOS) hierarchy for complex polynomial optimization problems, where the sparsity includes correlative sparsity and term sparsity. We compare the strengths of the sparsity-adapted complex moment-HSOS hierarchy with the sparsity-adapted real moment-SOS hierarchy on either randomly generated complex polynomial optimization problems or the AC optimal power flow problem. The results of numerical experiments show that the sparsity-adapted complex moment-HSOS hierarchy provides a trade-off between the computational cost and the quality of obtained bounds for large-scale complex polynomial optimization problems., 20 pages, 6 tables
Published: 2022
Full Text: View/download PDF

11. Dimension-free entanglement detection in multipartite Werner states

Author: Felix Huber, Igor Klep, Victor Magron, Jurij Volčič, Uniwersytet Jagielloński w Krakowie = Jagiellonian University (UJ), Faculty of Mathematics and Physics [Ljubljana] (FMF), University of Ljubljana, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Department of Mathematical Sciences [Copenhagen], Faculty of Science [Copenhagen], University of Copenhagen = Københavns Universitet (KU)-University of Copenhagen = Københavns Universitet (KU), PHC Proteus grant 46195TA, ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020,POEMA(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Equipe Polynomial OPtimization (LAAS-POP), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), University of Copenhagen = Københavns Universitet (UCPH)-University of Copenhagen = Københavns Universitet (UCPH), This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Magron, Victor, TREMPLIN-ERC - Optimisation garantie pour la vérification des systèmes cyber-physiques - - COPS2018 - ANR-18-ERC2-0004 - TERC - VALID, Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID
Subjects: Quantum Physics, FOS: Physical sciences, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Statistical and Nonlinear Physics, Mathematical Physics (math-ph), [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], Optimization and Control (math.OC), [MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph], FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-MP] Mathematics [math]/Mathematical Physics [math-ph], Quantum Physics (quant-ph), Mathematics - Optimization and Control, 81P42, 46N50, 20C35, 90C22, 81-08, 16R30, 13J30, [PHYS.QPHY] Physics [physics]/Quantum Physics [quant-ph], Mathematical Physics
Abstract: Werner states are multipartite quantum states that are invariant under the diagonal conjugate action of the unitary group. This paper gives a complete characterization of their entanglement that is independent of the underlying local Hilbert space: for every entangled Werner state there exists a dimension-free entanglement witness. The construction of such a witness is formulated as an optimization problem. To solve it, two semidefinite programming hierarchies are introduced. The first one is derived using real algebraic geometry applied to positive polynomials in the entries of a Gram matrix, and is complete in the sense that for every entangled Werner state it converges to a witness. The second one is based on a sum-of-squares certificate for the positivity of trace polynomials in noncommuting variables, and is a relaxation that involves smaller semidefinite constraints., Comment: updated abstract
Published: 2021
Full Text: View/download PDF

12. Minimizing rational functions: a hierarchy of approximations via pushforward measures

Author: Victor Magron, Olivier Zahm, Jean B. Lasserre, Swann Marx, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Laboratoire des Sciences du Numérique de Nantes (LS2N), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS), Mathematics and computing applied to oceanic and atmospheric flows (AIRSEA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Grenoble Alpes (UGA)-Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), FMJH Program PGMO (EPICS project) and EDF, Thales, Orange et Criteo. The research of the third author is conducted in the framework of the regional programme 'Atlanstic 2020, Research, Education and Innovation in Pays dela Loire', supported by the French Region Pays de la Loire and the European Regional Development Fund., ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020,POEMA(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: Dimension (graph theory), 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, Rational function, upper bounds hierarchy, 01 natural sciences, Theoretical Computer Science, polynomial optimization, pushforward measure, FOS: Mathematics, Pushforward (differential), 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, 021103 operations research, Hierarchy (mathematics), semidefinite programming, Pushforward measure, Numerical integration, Algebra, sums of squares, Compact space, Optimization and Control (math.OC), numerical integration, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], MSC: 90C22, 90C26, 90C30, Software
Abstract: This paper is concerned with minimizing a sum of rational functions over a compact set of high-dimension. Our approach relies on the second Lasserre's hierarchy (also known as the upper bounds hierarchy) formulated on the pushforward measure in order to work in a space of smaller dimension. We show that in the general case the minimum can be approximated as closely as desired from above with a hierarchy of semidefinite programs problems or, in the particular case of a single fraction, with a hierarchy of generalized eigenvalue problems. We numerically illustrate the potential of using the pushforward measure rather than the standard upper bounds hierarchy. In our opinion, this potential should be a strong incentive to investigate a related challenging problem interesting in its own; namely integrating an arbitrary power of a given polynomial on a simple set (e.g., unit box or unit sphere) with respect to Lebesgue or Haar measure., 24 pages, 3 tables
Published: 2021
Full Text: View/download PDF

13. Sparse Polynomial Optimization: Theory And Practice

Author: Victor Magron, Jie Wang, Victor Magron, and Jie Wang
Subjects: Sparse matrices, Polynomials, Mathematical optimization
Abstract: Many applications, including computer vision, computer arithmetic, deep learning, entanglement in quantum information, graph theory and energy networks, can be successfully tackled within the framework of polynomial optimization, an emerging field with growing research efforts in the last two decades. One key advantage of these techniques is their ability to model a wide range of problems using optimization formulations. Polynomial optimization heavily relies on the moment-sums of squares (moment-SOS) approach proposed by Lasserre, which provides certificates for positive polynomials. On the practical side, however, there is'no free lunch'and such optimization methods usually encompass severe scalability issues. Fortunately, for many applications, including the ones formerly mentioned, we can look at the problem in the eyes and exploit the inherent data structure arising from the cost and constraints describing the problem.This book presents several research efforts to resolve this scientific challenge with important computational implications. It provides the development of alternative optimization schemes that scale well in terms of computational complexity, at least in some identified class of problems. It also features a unified modeling framework to handle a wide range of applications involving both commutative and noncommutative variables, and to solve concretely large-scale instances. Readers will find a practical section dedicated to the use of available open-source software libraries.This interdisciplinary monograph is essential reading for students, researchers and professionals interested in solving optimization problems with polynomial input data.
Published: 2023

14. Sparse Noncommutative Polynomial Optimization

Author: Victor Magron, Igor Klep, Janez Povh, Department of Mathematics (University of Ljubljana), University of Ljubljana, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Faculty of Mechanical Engineering, University of Ljubljana, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
Subjects: Semialgebraic set, trace optimization, Trace (linear algebra), semialgebraic set, General Mathematics, 0211 other engineering and technologies, GNS postopek, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, eigenvalue optimization, Mathematics - Algebraic Geometry, sparsity pattern, FOS: Mathematics, GNS construction, optimizacija lastnih vrednosti, 0101 mathematics, Algebraic Geometry (math.AG), Mathematics - Optimization and Control, Eigenvalues and eigenvectors, Mathematics, Flatness (mathematics), Semidefinite programming, Discrete mathematics, noncommutative polynomial, 021103 operations research, nekomutativni polinom, optimizacija sledi, Mathematics::Operator Algebras, semidefinite programming, semidefinitno programiranje, Noncommutative geometry, semialgebraična množica, Operator algebra, Optimization and Control (math.OC), Irreducibility, 90C22, 47N10, 13J10, udc:512.622(045), [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], redki polinomi, Software
Abstract: This article focuses on optimization of polynomials in noncommuting variables, while taking into account sparsity in the input data. A converging hierarchy of semidefinite relaxations for eigenvalue and trace optimization is provided. This hierarchy is a noncommutative analogue of results due to Lasserre [SIAM J. Optim. 17(3) (2006), pp. 822--843] and Waki et al. [SIAM J. Optim. 17(1) (2006), pp. 218--242]. The Gelfand-Naimark-Segal (GNS) construction is applied to extract optimizers if flatness and irreducibility conditions are satisfied. Among the main techniques used are amalgamation results from operator algebra. The theoretical results are utilized to compute lower bounds on minimal eigenvalue and trace of noncommutative polynomials from the literature., 37 pages, 3 figures, 3 tables
Published: 2020
Full Text: View/download PDF

15. SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions

Author: Victor Magron, Martina Maggio, Jie Wang, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Lund University [Lund], Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), FMJH Program PGMO(EPICS project), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020,POEMA(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: Joint spectral radius, Iterative method, business.industry, Computer science, Computation, 010102 general mathematics, Stability (learning theory), 010103 numerical & computational mathematics, 01 natural sciences, Upper and lower bounds, Matrix decomposition, Software, Optimization and Control (math.OC), ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, business, Algorithm, Mathematics - Optimization and Control, Sparse matrix
Abstract: This paper focuses on the computation of joint spectral radii (JSR), when the involved matrices are sparse. We provide a sparse variant of the procedure proposed by Parrilo and Jadbabaie, to compute upper bounds of the JSR by means of sum-of-squares (SOS) relaxations. Our resulting iterative algorithm, called SparseJSR, is based on the term sparsity SOS (TSSOS) framework, developed by Wang, Magron and Lasserre, yielding SOS decompositions of polynomials with arbitrary sparse support. SparseJSR exploits the sparsity of the input matrices to significantly reduce the computational burden associated with the JSR computation. Our algorithmic framework is then successfully applied to compute upper bounds for JSR, on randomly generated benchmarks as well as on problems arising from stability proofs of controllers, in relation with possible hardware and software faults., 6 pages, 2 figures, 3 tables
Published: 2020
Full Text: View/download PDF

16. A second order cone characterization for sums of nonnegative circuits

Author: Victor Magron, Jie Wang, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, PNRIA, ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020,POEMA(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: MathematicsofComputing_NUMERICALANALYSIS, 010103 numerical & computational mathematics, 01 natural sciences, Computer Science::Hardware Architecture, Simple (abstract algebra), sum of nonnegative circuit polynomials, second-order cone programming, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, polynomial optimization, FOS: Mathematics, second-order cone representation, Primary, 14P10, 90C25, Secondary, 52B20, 12D15, 0101 mathematics, Representation (mathematics), Mathematics - Optimization and Control, ComputingMethodologies_COMPUTERGRAPHICS, Mathematics, Semidefinite programming, Discrete mathematics, Degree (graph theory), 010102 general mathematics, Regular polygon, Order (ring theory), 16. Peace & justice, sum of binomial squares, Cone (topology), Optimization and Control (math.OC), Second-order cone programming, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: The second-order cone is a class of simple convex cones and optimizing over them can be done more efficiently than with semidefinite programming. It is interesting both in theory and in practice to investigate which convex cones admit a representation using second-order cones, given that they have a strong expressive ability. In this paper, we prove constructively that the cone of sums of nonnegative circuits (SONC) admits a second-order cone representation. Based on this, we give a new algorithm to compute SONC decompositions for certain classes of nonnegative polynomials via second-order cone programming. Numerical experiments demonstrate the efficiency of our algorithm for polynomials with a fairly large size., 23 pages
Published: 2020
Full Text: View/download PDF

17. A sparse version of Reznick's Positivstellensatz

Author: Ngoc Hoang Anh Mai, Victor Magron, Jean Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), PNRIA, ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020,POEMA(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Equipe Polynomial OPtimization (LAAS-POP), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: Reznick's Positivstellensatz, Mathematics - Algebraic Geometry, General Mathematics, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Management Science and Operations Research, Algebraic Geometry (math.AG), Computer Science Applications
Abstract: If $f$ is a positive definite form, Reznick's Positivstellensatz [Mathematische Zeitschrift. 220 (1995), pp. 75--97] states that there exists $k\in\mathbf{N}$ such that ${\| x \|^{2k}_2}f$ is a sum of squares of polynomials. Assuming that $f$ can be written as a sum of forms $\sum_{l=1}^p f_l$, where each $f_l$ depends on a subset of the initial variables, and assuming that these subsets satisfy the so-called running intersection property, we provide a sparse version of Reznick's Positivstellensatz. Namely, there exists $k \in \mathbf{N}$ such that $f=\sum_{l = 1}^p {{\sigma_l}/{H_l^{k}}}$, where $\sigma_l$ is a sum of squares of polynomials, $H_l$ is a uniform polynomial denominator, and both polynomials $\sigma_l,H_l$ involve the same variables as $f_l$, for each $l=1,\dots,p$. In other words, the sparsity pattern of $f$ is also reflected in this sparse version of Reznick's certificate of positivity. We next use this result to also obtain positivity certificates for (i) polynomials nonnegative on the whole space and (ii) polynomials nonnegative on a (possibly non-compact) basic semialgebraic set, assuming that the input data satisfy the running intersection property. Both are sparse versions of a positivity certificate due to Putinar and Vasilescu., Comment: 19 pages, 2 tables
Published: 2020
Full Text: View/download PDF

18. Certified Roundoff Error Bounds Using Bernstein Expansions and Sparse Krivine-Stengle Representations

Author: Victor Magron, Thao Dang, Alexandre Rocca, Imperial College London, Biologie Computationnelle et Mathématique (TIMC-IMAG-BCM), Techniques de l'Ingénierie Médicale et de la Complexité - Informatique, Mathématiques et Applications, Grenoble - UMR 5525 (TIMC-IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Magron, Victor, Laboratoires d'excellence - Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique - - PERSYVAL-lab2011 - ANR-11-LABX-0025 - LABX - VALID, Polynomial Systems (PolSys), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and ANR-11-LABX-0025,PERSYVAL-lab,Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique(2011)
Subjects: FOS: Computer and information sciences, Polynomial, Floating point, Computer science, pansions, 010103 numerical & computational mathematics, 02 engineering and technology, Rational function, 01 natural sciences, Upper and lower bounds, Polynomial Optimization, Theoretical Computer Science, Krivine-Stengle Representations, Software, Bernstein Ex, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Applied mathematics, 0101 mathematics, Global optimization, Roundoff Error Bounds, ComputingMilieux_MISCELLANEOUS, Mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], business.industry, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, 010102 general mathematics, Computer Science - Numerical Analysis, 020207 software engineering, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Numerical Analysis (math.NA), Linear Programming Relaxations, Floating Point Arithmetic, Bernstein polynomial, Computational Theory and Mathematics, Rate of convergence, Hardware and Architecture, Computer Science - Mathematical Software, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Round-off error, business, Algorithm, Mathematical Software (cs.MS)
Abstract: Floating point error is a drawback of embedded systems implementation that is difficult to avoid. Computing rigorous upper bounds of roundoff errors is absolutely necessary for the validation of critical software. This problem of computing rigorous upper bounds is even more challenging when addressing non-linear programs. In this paper, we propose and compare two new algorithms based on Bernstein expansions and sparse Krivine-Stengle representations, adapted from the field of the global optimization, to compute upper bounds of roundoff errors for programs implementing polynomial and rational functions. We also provide the convergence rate of these two algorithms. We release two related software package FPBern and FPKriSten, and compare them with the state-of-the-art tools. We show that these two methods achieve competitive performance, while providing accurate upper bounds by comparison with the other tools., 14 pages, 2 figures, 2 tables. Extension of the work in arXiv:1610.07038
Published: 2019
Full Text: View/download PDF

19. Interval Enclosures of Upper Bounds of Roundoff Errors using Semidefinite Programming

Author: Victor Magron, VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Polynomial Systems (PolSys), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Polynomial, Mathematical optimization, Floating point, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, Interval (mathematics), 01 natural sciences, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], 021103 operations research, Applied Mathematics, Rounding, Computer Science - Numerical Analysis, Robust optimization, Numerical Analysis (math.NA), Monotone polygon, Optimization and Control (math.OC), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Round-off error, Software
Abstract: A longstanding problem related to floating-point implementation of numerical programs is to provide efficient yet precise analysis of output errors. We present a framework to compute lower bounds on largest absolute roundoff errors, for a particular rounding model. This method applies to numerical programs implementing polynomial functions with box constrained input variables. Our study is based on three different hierarchies, relying respectively on generalized eigenvalue problems, elementary computations and semidefinite programming (SDP) relaxations. This is complementary of over-approximation frameworks, consisting of obtaining upper bounds on the largest absolute roundoff error. Combining the results of both frameworks allows to get enclosures for upper bounds on roundoff errors. The under-approximation framework provided by the third hierarchy is based on a new sequence of convergent robust SDP approximations for certain classes of polynomial optimization problems. Each problem in this hierarchy can be solved exactly via SDP. By using this hierarchy, one can provide a monotone non-decreasing sequence of lower bounds converging to the absolute roundoff error of a program implementing a polynomial function, applying for a particular rounding model. We investigate the efficiency and precision of our method on non-trivial polynomial programs coming from space control, optimization and computational biology., 18 pages, 2 tables, 1 figure
Published: 2018
Full Text: View/download PDF

20. On Exact Polya and Putinar's Representations

Author: Victor Magron, Mohab Safey El Din, VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Polynomial Systems (PolSys), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and ANR-17-CE40-0009,GALOP,Jeux à travers la lentille de algèbre et géométrie de l'optimisation(2017)
Subjects: Computer Science - Symbolic Computation, FOS: Computer and information sciences, Semidefinite programming, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Polynomial, 010102 general mathematics, Mathematics::Optimization and Control, 0102 computer and information sciences, Positive-definite matrix, Symbolic Computation (cs.SC), Solver, 16. Peace & justice, Symbolic computation, 01 natural sciences, Cylindrical algebraic decomposition, Exponential function, Algebra, 010201 computation theory & mathematics, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Real algebraic geometry, 0101 mathematics, Mathematics
Abstract: We consider the problem of finding exact sums of squares (SOS) decompositions for certain classes of non-negative multivariate polynomials, relying on semidefinite programming (SDP) solvers. We start by providing a hybrid numeric-symbolic algorithm computing exact rational SOS decompositions for polynomials lying in the interior of the SOS cone. It computes an approximate SOS decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. An exact SOS decomposition is obtained thanks to the perturbation terms. We prove that bit complexity estimates on output size and runtime are both polynomial in the degree of the input polynomial and simply exponential in the number of variables. Next, we apply this algorithm to compute exact Polya and Putinar's representations respectively for positive definite forms and positive polynomials over basic compact semi-algebraic sets. We also compare the implementation of our algorithms with existing methods in computer algebra including cylindrical algebraic decomposition and critical point method., Comment: 19 pages, 4 algorithms, 3 tables
Published: 2018
Full Text: View/download PDF

21. Semidefinite Approximations of Invariant Measures for Polynomial Systems

Author: Victor Magron, Didier Henrion, Marcelo Forets, Polynomial Systems (PolSys), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Universidad de la República [Montevideo] (UDELAR), Czech Technical University in Prague (CTU), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, and Universidad de la República [Montevideo] (UCUR)
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Semidefinite programming, Semialgebraic set, Polynomial, Pure mathematics, Lebesgue measure, Applied Mathematics, 010102 general mathematics, Dynamical Systems (math.DS), Absolute continuity, 01 natural sciences, 010101 applied mathematics, Optimization and Control (math.OC), FOS: Mathematics, Discrete Mathematics and Combinatorics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Invariant measure, 0101 mathematics, Invariant (mathematics), Mathematics - Dynamical Systems, Mathematics - Optimization and Control, Conic optimization, Mathematics
Abstract: We consider the problem of approximating numerically the moments and the supports of measures which are invariant with respect to the dynamics of continuous- and discrete-time polynomial systems, under semialgebraic set constraints. First, we address the problem of approximating the density and hence the support of an invariant measure which is absolutely continuous with respect to the Lebesgue measure. Then, we focus on the approximation of the support of an invariant measure which is singular with respect to the Lebesgue measure. Each problem is handled through an appropriate reformulation into a linear optimization problem over measures, solved in practice with two hierarchies of finite-dimensional semidefinite moment-sum-of-square relaxations, also called Lasserre hierarchies. Under specific assumptions, the first Lasserre hierarchy allows to approximate the moments of an absolutely continuous invariant measure as close as desired and to extract a sequence of polynomials converging weakly to the density of this measure. The second Lasserre hierarchy allows to approximate as close as desired in the Hausdorff metric the support of a singular invariant measure with the level sets of the Christoffel polynomials associated to the moment matrices of this measure. We also present some application examples together with numerical results for several dynamical systems admitting either absolutely continuous or singular invariant measures., 28 pages, 14 figures
Published: 2018
Full Text: View/download PDF

22. Property-based Polynomial Invariant Generation Using Sums-of-Squares Optimization

Author: Victor Magron, Assalé Adjé, Pierre-Loïc Garoche, LAboratoire de Mathématiques et PhySique (LAMPS), Université de Perpignan Via Domitia (UPVD), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, Imperial College London, Blazy Sandrine, and Jensen Thomas
Subjects: Semidefinite programming, Invariant polynomial, Fixed point, 16. Peace & justice, Abstract interpretation, Square-free polynomial, Matrix polynomial, Algebra, Computer Science::Logic in Computer Science, Computer Science::Programming Languages, [INFO]Computer Science [cs], Invariant (mathematics), Algorithm, ComputingMilieux_MISCELLANEOUS, Mathematics, Characteristic polynomial
Abstract: While abstract interpretation is not theoretically restricted to specific kinds of properties, it is, in practice, mainly developed to compute linear over-approximations of reachable sets, aka. the collecting semantics of the program. The verification of user-provided properties is not easily compatible with the usual forward fixpoint computation using numerical abstract domains.
Published: 2015
Full Text: View/download PDF

23. Certification of real inequalities: templates and sums of squares

Author: Victor Magron, Stéphane Gaubert, Xavier Allamigeon, Benjamin Werner, Imperial College London, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Max-plus algebras and mathematics of decision (MAXPLUS), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), EEE Department, Imperial College London, Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: General Mathematics, MathematicsofComputing_NUMERICALANALYSIS, Certified global optimization, Semialgebraic relaxations, Maxplus approximation, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Applied mathematics, Inverse trigonometric functions, Semidefinite programming, Mathematics - Optimization and Control, Global optimization, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], 90C22, 90C26, 90C59, 11E25, 41A10, 41A50, Transcendental function, Numerical analysis, Abstract interpretation, Optimal control, Nonlinear system, Optimization and Control (math.OC), Polynomial optimization problems, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Nonlinear template method, Software
Abstract: We consider the problem of certifying lower bounds for real-valued multivariate transcendental functions. The functions we are dealing with are nonlinear and involve semialgebraic operations as well as some transcendental functions like $\cos$, $\arctan$, $\exp$, etc. Our general framework is to use different approximation methods to relax the original problem into polynomial optimization problems, which we solve by sparse sums of squares relaxations. In particular, we combine the ideas of the maxplus estimators (originally introduced in optimal control) and of the linear templates (originally introduced in static analysis by abstract interpretation). The nonlinear templates control the complexity of the semialgebraic relaxations at the price of coarsening the maxplus approximations. In that way, we arrive at a new - template based - certified global optimization method, which exploits both the precision of sums of squares relaxations and the scalability of abstraction methods. We analyze the performance of the method on problems from the global optimization literature, as well as medium-size inequalities issued from the Flyspeck project., Comment: 27 pages, 3 figures, 4 tables
Published: 2014
Full Text: View/download PDF

24. NLCertify: A Tool for Formal Nonlinear Optimization

Author: Victor Magron, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, ForMath European Union's 7th Framework Programme under grant agreement nr. 243847 (ForMath), Simone and Cino del Duca foundation of Institut de France., Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Multivariate statistics, Computer science, MathematicsofComputing_NUMERICALANALYSIS, Certification, Proof Assistant, Nonlinear programming, Sparse SOS, Maxplus Approximation, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Mathematics - Optimization and Control, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS], Transcendental function, Proof assistant, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Function (mathematics), Logic in Computer Science (cs.LO), Algebra, Nonlinear system, Formal Nonlinear Optimization, Optimization and Control (math.OC), Computer Science - Mathematical Software, Hybrid Symbolic-Numeric Certification, Transcendental number, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematical Software (cs.MS)
Abstract: NLCertify is a software package for handling formal certification of nonlinear inequalities involving transcendental multivariate functions. The tool exploits sparse semialgebraic optimization techniques with approximation methods for transcendental functions, as well as formal features. Given a box and a transcendental multivariate function as input, NLCertify provides OCaml libraries that produce nonnegativity certificates for the function over the box, which can be ultimately proved correct inside the Coq proof assistant., 6 pages, 2 figures
Published: 2014

25. Error Bounds for Polynomial Optimization over the Hypercube using Putinar type Representations

Author: Victor Magron, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
Subjects: Control and Optimization, Positivstellensatz, Approximations of π, Positive polynomial, Sums of squares relaxations, 010103 numerical & computational mathematics, Type (model theory), 01 natural sciences, Combinatorics, Multivariate Bernstein Approximation, Mathematics - Algebraic Geometry, Quadratic equation, FOS: Mathematics, Quadratic Module, Preordering, 0101 mathematics, Algebraic Geometry (math.AG), Mathematics - Optimization and Control, Positive Polynomial, Mathematics, Semidefinite programming, Discrete mathematics, Semidefinite Programming, Degree (graph theory), 010102 general mathematics, Optimization and Control (math.OC), Polynomial optimization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Hypercube
Abstract: Consider the optimization problem $p_{\min, Q} := \min_{\mathbf{x} \in Q} p(\mathbf{x})$, where $p$ is a degree $m$ multivariate polynomial and $Q := [0, 1]^n$ is the hypercube. We provide explicit degree and error bounds for the sums of squares approximations of $p_{\min, Q}$ corresponding to the Positivstellensatz of Putinar. Our approach uses Bernstein multivariate approximation of polynomials, following the methodology of De Klerk and Laurent to provide error bounds for Schm\"udgen type positivity certificates over the hypercube. We give new bounds for Putinar type representations by relating the quadratic module and the preordering associated with the polynomials $g_i := x_i (1 - x_i), \: i=1,\dots,n$, describing the hypercube $Q$., Comment: 7 pages, 1 table
Published: 2014
Full Text: View/download PDF

26. Approximating Pareto Curves using Semidefinite Relaxations

Author: Victor Magron, Didier Henrion, Jean B. Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
Subjects: FOS: Computer and information sciences, Polynomial, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, Management Science and Operations Research, 01 natural sciences, Multi-objective optimization, Industrial and Manufacturing Engineering, Combinatorics, symbols.namesake, Computer Science - Robotics, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Pareto distribution, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, Approximation theory, 021103 operations research, Applied Mathematics, Pareto principle, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Inverse problem, Optimization and Control (math.OC), symbols, Relaxation (approximation), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Robotics (cs.RO), Software
Abstract: International audience; We consider the problem of constructing an approximation of the Pareto curve associated with the multiobjective optimization problem $\min_{\mathbf{x} \in \mathbf{S}}\{ (f_1(\mathbf{x}), f_2(\mathbf{x})) \}$, where $f_1$ and $f_2$ are two conflicting polynomial criteria and $\mathbf{S} \subset \mathbb{R}^n$ is a compact basic semialgebraic set. We provide a systematic numerical scheme to approximate the Pareto curve. We start by reducing the initial problem into a scalarized polynomial optimization problem (POP). Three scalarization methods lead to consider different parametric POPs, namely (a) a weighted convex sum approximation, (b) a weighted Chebyshev approximation, and (c) a parametric sublevel set approximation. For each case, we have to solve a semidefinite programming (SDP) hierarchy parametrized by the number of moments or equivalently the degree of a polynomial sums of squares approximation of the Pareto curve. When the degree of the polynomial approximation tends to infinity, we provide guarantees of convergence to the Pareto curve in $L^2$-norm for methods (a) and (b), and $L^1$-norm for method (c).
Published: 2014

27. Certification of Bounds of Non-linear Functions: the Templates Method

Author: Benjamin Werner, Stéphane Gaubert, Victor Magron, Xavier Allamigeon, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Max-plus algebras and mathematics of decision (MAXPLUS), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Types, Logic and computing (TYPICAL), and Jacques Carette and David Aspinall and Christoph Lange and Petr Sojka and Wolfgang Windsteige
Subjects: Computer Science - Symbolic Computation, FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Logic in Computer Science, Optimization problem, Conjecture, Basis (linear algebra), Approximation algorithm, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Function (mathematics), Symbolic Computation (cs.SC), Optimal control, Logic in Computer Science (cs.LO), Range (mathematics), Applied mathematics, Limit (mathematics), Mathematics
Abstract: The aim of this work is to certify lower bounds for real-valued multivariate functions, defined by semialgebraic or transcendental expressions. The certificate must be, eventually, formally provable in a proof system such as Coq. The application range for such a tool is widespread; for instance Hales' proof of Kepler's conjecture yields thousands of inequalities. We introduce an approximation algorithm, which combines ideas of the max-plus basis method (in optimal control) and of the linear templates method developed by Manna et al. (in static analysis). This algorithm consists in bounding some of the constituents of the function by suprema of quadratic forms with a well chosen curvature. This leads to semialgebraic optimization problems, solved by sum-of-squares relaxations. Templates limit the blow up of these relaxations at the price of coarsening the approximation. We illustrate the efficiency of our framework with various examples from the literature and discuss the interfacing with Coq., Comment: 16 pages, 3 figures, 2 tables
Published: 2013
Full Text: View/download PDF

28. Optimisation polynomiale effective via des certificats de positivité avec ou sans dénominateurs

Author: Mai, Ngoc Hoang Anh, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Paul Sabatier - Toulouse III, Victor Magron, Jean-Bernard Lasserre, Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, UT3 : Université Toulouse 3 Paul Sabatier, Victor MAGRON, and Jean-Bernard LASSERRE (co-encadrant)
Subjects: Putinar-Vasilescu's Positivstellensatz, Hiérarchies moment/sommes-de-carrés, Taux de convergence, Polynomial optimization, Positivstellensatz de Polya, Putinar's Positivstellensatz, Programmation semidéfinie, constant trace property, Propriété de la trace constante, Positivstellensatz de Putinar, Polya's Positivstellensatz, Hiérarchie Moment-SOS, Reznick's Positivstellensatz, correlative and term sparsity, convergence rate, Positivstellensatz de Reznick, Programmation semi-définie, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, Positivstellensatz de Putinar-Vasilescu, Optimisation polynomiale, Sparsité corrélative et termique, Semidefinite programming, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Moment-SOS hierarchy, Moment/sums-of-squares hierarchy
Abstract: National audience; Positivity certificates or Positivstellens"atze provide representations of polynomials positive on basic semialgebraic sets, i.e., sets defined by finitely many polynomial inequalities. The famous Putinar's Positivstellensatz states that every positive polynomial on a basic closed semialgebraic set dollarSdollar can be written as a linear weighted combination of the polynomials describing dollarSdollar, under a certain condition on dollarSdollar slightly stronger than compactness. When written in this it becomes obvious that the polynomial is positive on dollarSdollar, and therefore this alternative description provides a certificate of positivity on dollarSdollar. Moreover, as the polynomial weights involved in Putinar's Positivstellensatz are sums of squares (SOS), such Positivity certificates enable to design convex relaxations based on semidefinite programming to solve polynomial optimization problems (POPs) that arise in various real-life applications, e.g., in management of energy networks and machine learning to cite a few. Originally developed by Lasserre, the hierarchy of semidefinite relaxations based on Putinar's Positivstellensatz is called the emph{Moment-SOS hierarchy}. In this thesis, we provide polynomial optimization methods based on positivity certificates involving specific SOS weights, without or with denominators.; Les certificats de positivité ou Positivstellens"atze fournissent des représentations de polynômes positifs sur des ensembles semialgébriques de basiques, c'est-à-dire des ensembles définis par un nombre fini d'inégalités polynomiales. Le célèbre Positivstellensatz de Putinar stipule que tout polynôme positif sur un ensemble semialgébrique basique fermé dollarSdollar peut être écrit comme une combinaison pondérée linéaire des polynômes décrivant dollarSdollar, sous une certaine condition sur dollarSdollar légèrement plus forte que la compacité. Lorsqu'il est écrit comme ceci, il devient évident que le polynôme est positif sur dollarSdollar, et donc cette description alternative fournit un certificat de positivité sur dollarSdollar. De plus, comme les poids polynomiaux impliqués dans le Positivstellensatz de Putinar sont des sommes de carrés (SOS), de tels certificats de positivité permettent de concevoir des relaxations convexes basées sur la programmation semidéfinie pour résoudre des problèmes d'optimisation polynomiale (POP) qui surviennent dans diverses applications réelles, par exemple dans la gestion des réseaux d'énergie et l'apprentissage automatique pour n'en citer que quelques unes. Développée à l'origine par Lasserre, la hiérarchie des relaxations semidéfinies basée sur le Positivstellensatz de Putinar est appelée la emph{hiérarchie Moment-SOS}. Dans cette thèse, nous proposons des méthodes d'optimisation polynomiale basées sur des certificats de positivité impliquant des poids SOS spécifiques, sans ou avec dénominateurs.
Published: 2022

29. La fonction de Christoffel: théorie et pratique

Author: Ðurašinović, Srećko, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), CNRS CREATE, This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., Toulouse School of Economics (TSE), Victor Magron, Jean-Bernard Lasserre, ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: Machine Learning, Data Analysis, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Christoffel-Darboux Kernel, Polynomial Optimization
Abstract: National audience
Published: 2022

30. Vérification de la robustesse des réseaux neuronaux à l'aide de l'optimisation polynomiale

Author: Chen, Tong, HAL-LAAS, LAAS, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Paul Sabatier - Toulouse III, Edouard Pauwels, Victor Magron, Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, and UT3 : Université Toulouse 3 Paul Sabatier
Subjects: Polynomial optimization, Hiérarchie moment-somme de carrés, neural network, correlative sparsity, optimisation polynomiale, moment-sum of squares hierarchy, hiérarchie momentsomme de carrés, robustness verification, Lipschitz constant, constante de Lipschitz, semidefinite programming, parcimonie corrélative, [SPI.AUTO]Engineering Sciences [physics]/Automatic, vérification de robustesse, [SPI.AUTO] Engineering Sciences [physics]/Automatic, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], réseau de neurones, programmation semi-définie
Abstract: Nowadays, Neural Networks (NNs) are widely and successfully used for many large-scale and complex machine learning tasks, such as image classification, voice recognition recommender system, and have attracted the attention of many community researchers. However, even though neural networks are powerful, they are generally neither robust nor reliable. This means that, for some input examples, neural network classifiers can produce unstable predictions of their labels, i.e., classifiers are sensitive to small input changes, which is problematic in some crucial areas such as auto-driving or aerospace. Therefore, the robustness of neural networks has become a critical issue in the machine learning community in recent years. Robustness for NNs has two main facets: robust trai! ning and robust verification. In this thesis, we mainly focus on verifying the robustness of pre-trained NNs. Based on semi-definite programming, we first develop a sublevel hierarchy for polynomial optimization problems and then apply it to robustness verification of NNs. Our approaches show empirical improvements over other related methods., De nos jours, les Réseaux de Neurones (RN) sont largement et avec succès utilisés pour de nombreuses tâches d’apprentissage automatique à grande échelle et complexes, telles que la classification d’images, le système de recommandation de reconnaissance vocale, et ont attiré l’attention de nombreux chercheurs de la communauté. Cependant, même si les réseaux de neurones sont puissants, ils ne sont généralement ni robustes ni fiables. Cela signifie que, pour certains exemples d’entrées, les classificateurs de réseaux de neurones peuvent produire des prédictions instables de leurs étiquettes, c’est-à-dire que les classificateurs sont sensibles aux petits changements d’entrée, ce qui est problématique dans certains domaines cruciaux comme la conduite automobile ou l’aérospatiale. Par conséquent, la robustesse des ! réseaux de neurones est devenue un problème critique dans la communauté de l’apprentissage automatique ces dernières années. La robustesse a principalement deux facettes : une formation robuste des RN et une vérification robuste des RN. Dans cette thèse, nous nous concentrons principalement sur la v! érification de la robustesse des RN pré-formés. Sur la base de la programmation semi-définie, nous développons d’abord une hiérarchie de sous-niveaux pour les problèmes d’optimisation polynomiale, puis nous l’appliquons à la vérification de robustesse des RN. Nos approches montrent des améliorations empiriques par rapport à d’autres méthodes connexes.
Published: 2022

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources

Refine your results

30 results on '"Victor MAGRON"'

1. Certifying Ground-State Properties of Many-Body Systems

2. Correlations constrained by composite measurements

3. Formal Proofs for Nonlinear Optimization

4. A FORMAL PROOF OF THE KEPLER CONJECTURE

5. Sums of squares representations on singular loci

6. Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients

7. L 2+ Induced Norm Analysis of Continuous-Time LTI Systems Using Positive Filters and Copositive Programming

8. Stability of Linear Systems under Extended Weakly-Hard Constraints

9. A Sublevel Moment-SOS Hierarchy for Polynomial Optimization

10. Exploiting Sparsity in Complex Polynomial Optimization

11. Dimension-free entanglement detection in multipartite Werner states

12. Minimizing rational functions: a hierarchy of approximations via pushforward measures

13. Sparse Polynomial Optimization: Theory And Practice

14. Sparse Noncommutative Polynomial Optimization

15. SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions

16. A second order cone characterization for sums of nonnegative circuits

17. A sparse version of Reznick's Positivstellensatz

18. Certified Roundoff Error Bounds Using Bernstein Expansions and Sparse Krivine-Stengle Representations

19. Interval Enclosures of Upper Bounds of Roundoff Errors using Semidefinite Programming

20. On Exact Polya and Putinar's Representations

21. Semidefinite Approximations of Invariant Measures for Polynomial Systems

22. Property-based Polynomial Invariant Generation Using Sums-of-Squares Optimization

23. Certification of real inequalities: templates and sums of squares

24. NLCertify: A Tool for Formal Nonlinear Optimization

25. Error Bounds for Polynomial Optimization over the Hypercube using Putinar type Representations

26. Approximating Pareto Curves using Semidefinite Relaxations

27. Certification of Bounds of Non-linear Functions: the Templates Method

28. Optimisation polynomiale effective via des certificats de positivité avec ou sans dénominateurs

29. La fonction de Christoffel: théorie et pratique

30. Vérification de la robustesse des réseaux neuronaux à l'aide de l'optimisation polynomiale

Catalog

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Category

Publication Type

Journal

Database

Publisher

30 results on '"Victor MAGRON"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources