Author: "European Project: 813211,H2020,POEMA(2019)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"European Project: 813211,H2020,POEMA(2019)"' showing total 71 results

Start Over Author "European Project: 813211,H2020,POEMA(2019)"

71 results on '"European Project: 813211,H2020,POEMA(2019)"'

1. SONC optimization and exact nonnegativity certificates via second-order cone programming

Author: Magron, Victor, Wang, Jie, 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), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), 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), 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), 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 - 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: FOS: Computer and information sciences, Computer Science - Symbolic Computation, Algebra and Number Theory, MathematicsofComputing_NUMERICALANALYSIS, Symbolic Computation (cs.SC), sum of binomial squares, exact nonnegativity certificate, Mathematics - Algebraic Geometry, Computational Mathematics, rounding-projection algorithm, Optimization and Control (math.OC), sum of nonnegative circuit polynomials, second-order cone programming, polynomial optimization, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, second-order conerepresentation, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Algebraic Geometry (math.AG), Mathematics - Optimization and Control
Abstract: The second-order cone (SOC) 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 SOCs, 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 SOC representation. Based on this, we give a new algorithm for unconstrained polynomial optimization via SOC programming. We also provide a hybrid numeric-symbolic scheme which combines the numerical procedure with a rounding-projection algorithm to obtain exact nonnegativity certificates. Numerical experiments demonstrate the efficiency of our algorithm for polynomials with fairly large degree and number of variables., 29 pages, 7 tables, 6 figures, extended version of the article published in the proceedings of ISSAC 2020. arXiv admin note: text overlap with arXiv:1906.06179
Published: 2023
Full Text: View/download PDF

2. Exploiting Constant Trace Property in Large-scale Polynomial Optimization

Author: Ngoc Hoang Anh Mai, J. B. Lasserre, 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 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-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), 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: Optimization and Control (math.OC), Applied Mathematics, FOS: Mathematics, MathematicsofComputing_NUMERICALANALYSIS, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Software
Abstract: We prove that every semidefinite moment relaxation of a polynomial optimization problem (POP) with a ball constraint can be reformulated as a semidefinite program involving a matrix with constant trace property (CTP). As a result such moment relaxations can be solved efficiently by first-order methods that exploit CTP, e.g., the conditional gradient-based augmented Lagrangian method. We also extend this CTP-exploiting framework to large-scale POPs with different sparsity structures. The efficiency and scalability of our framework are illustrated on second-order moment relaxations for various randomly generated quadratically constrained quadratic programs., 43 pages, 6 algorithms, 23 tables
Published: 2022
Full Text: View/download PDF

3. 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

4. On the Effective Putinar’s Positivstellensatz and Moment Approximation

Author: Lorenzo Baldi, Bernard Mourrain, AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), This work has been supported by European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Actions, grant agreement 813211 (POEMA), 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), and European Project: 813211,H2020,POEMA(2019)
Subjects: Mathematics - Algebraic Geometry, Optimization and Control (math.OC), General Mathematics, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], FOS: Mathematics, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Commutative Algebra, Commutative Algebra (math.AC), Mathematics - Optimization and Control, Algebraic Geometry (math.AG), Software
Abstract: We analyse the representation of positive polynomials in terms of Sums of Squares. We provide a quantitative version of Putinar's Positivstellensatz over a compact basic semialgebraic set S, with a new polynomial bound on the degree of the positivity certificates. This bound involves a Lojasiewicz exponent associated to the description of S. We show that if the gradients of the active constraints are linearly independent on S (Constraint Qualification condition),this Lojasiewicz exponent is equal to 1. We deduce the first general polynomial bound on the convergence rate of the optima in Lasserre's Sum-of-Squares hierarchy to the global optimum of a polynomial function on S, and the first general bound on the Hausdorff distance between the cone of truncated (probability) measures supported on S and the cone of truncated pseudo-moment sequences, which are positive on the quadratic module of S., Comment: Mathematical Programming, Series A, 2022
Published: 2022
Full Text: View/download PDF

5. Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems

Author: Jérémy Berthomieu, Alin Bostan, Andrew Ferguson, Mohab Safey El Din, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Symbolic Special Functions : Fast and Certified (SPECFUN), 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), Calcul formel, mathématiques expérimentales et interactions (MATHEXP), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(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), and European Project: 813211,H2020,POEMA(2019)
Subjects: Computer Science - Symbolic Computation, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Algebra and Number Theory, Mathematics::Commutative Algebra, Hilbert series, combinatorics, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Gröbner bases, determinantal ideals, Groebner bases, Mathematics - Commutative Algebra
Abstract: International audience; Determinantal polynomial systems are those involving maximal minors of some given matrix. An important situation where these arise is the computation of the critical values of a polynomial map restricted to an algebraic set. This leads directly to a strategy for, among other problems, polynomial optimisation. Computing Gröbner bases is a classical method for solving polynomial systems in general. For practical computations, this consists of two main stages. First, a Gröbner basis is computedwith respect to a DRL (degree reverse lexicographic) ordering. Then, a change of ordering algorithm, such as \textsf{Sparse-FGLM}, designed by Faug\`ere and Mou, is used to find a Gröbner basis of the same system but with respect to a lexicographic ordering. The complexity of this latter step, in terms of the number of arithmetic operations in the ground field, is $O(mD^2)$, where $D$ is the degree of the ideal generated by the input and $m$ is the number of non-trivial columns of a certain $D \times D$ matrix. While asymptotic estimates are known for $m$ in the case of \textit{generic} polynomial systems, thus far, the complexity of \textsf{Sparse-FGLM} was unknown for the class of determinantal systems. By assuming Fröberg's conjecture, thus ensuring that the Hilbert series of generic determinantal ideals have the necessary structure, we expand the work of Moreno-Soc\'ias by detailing the structure of the DRL staircase in the determinantal setting. Then we study the asymptotics of the quantity $m$ by relating it to the coefficients of these Hilbert series. Consequently, we arrive at a new bound on the complexity of the \textsf{Sparse-FGLM} algorithm for generic determinantal systems and, in particular, for generic critical point systems. We consider the ideal inside the polynomial ring $\mathbb{K}[x_1, \dots, x_n]$, where $\mathbb{K}$ is some infinite field, generated by $p$ generic polynomials of degree $d$ and the maximal minors of a $p \times (n-1)$ polynomial matrix with generic entries of degree $d-1$. Then, in this setting, for the case $d=2$ and for $n \gg p$ we establish an exact formula for $m$ in terms of $n$ and $p$. Moreover, for $d \geq 3$, we give a tight asymptotic formula, as $n \to \infty$, for $m$ in terms of $n,p$ and $d$.
Published: 2022
Full Text: View/download PDF

6. Finer Complexity Estimates for the Change of Ordering of Gröbner Bases for Generic Symmetric Determinantal Ideals

Author: Andrew Ferguson, Huu Phuoc Le, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), European Project: 813211,H2020,POEMA(2019), European Project, 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: Symmetric matrices, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Mathematics::Commutative Algebra, Determinantal ideals, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Gröbner bases, FGLM
Abstract: International audience; Polynomial matrices and ideals generated by their minors appear in various domains such as cryptography, polynomial optimization and effective algebraic geometry. When the given matrix is symmetric, this additional structure on top of the determinantal structure, affects computations on the derived ideals. Thus, understanding the complexity of these computations is important. Moreover, this study serves as a stepping stone towards further understanding the effects of structure in determinantal systems, such as those coming from moment matrices. In this paper, we focus on the Sparse-FGLM algorithm, the state-of-the-art for changing ordering of Gröbner bases of zero-dimensional ideals. Under a variant of Fröberg’s conjecture, we study its complexity for symmetric determinantal ideals and identify the gain of exploiting sparsity in the Sparse-FGLM algorithm compared with the classical FGLM algorithm. For an $n \times n$ symmetric matrix with polynomial entries of degree $d$, we show that the complexity of Sparse-FGLM for zero-dimensional determinantal ideals obtained from this matrix over that of the FGLM algorithm is at least $O(1/d)$. Moreover, for some specific sizes of minors, we prove finer results of at least $O(1/nd)$ and $O(1/n^3d)$.
Published: 2022
Full Text: View/download PDF

7. Deciding Cuspidality of Manipulators through Computer Algebra and Algorithms in Real Algebraic Geometry

Author: Damien Chablat, Rémi Prébet, Mohab Safey El Din, Durgesh H. Salunkhe, Philippe Wenger, Laboratoire des Sciences du Numérique de Nantes (LS2N), Institut National de Recherche en Informatique et en Automatique (Inria)-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)-École Centrale de Nantes (Nantes Univ - ECN), Nantes Université (Nantes Univ)-Nantes Université (Nantes Univ)-Nantes université - UFR des Sciences et des Techniques (Nantes univ - UFR ST), Nantes Université - pôle Sciences et technologie, Nantes Université (Nantes Univ)-Nantes Université (Nantes Univ)-Nantes Université - pôle Sciences et technologie, Nantes Université (Nantes Univ), Robotique Et Vivant (LS2N - équipe ReV), Nantes Université (Nantes Univ)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Grant FA8665-20-1-7029 of the EOARD-AFOSR, ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(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), European Project: ECARP, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Nantes Université - École Centrale de Nantes (Nantes Univ - ECN), Robotique Et Vivant (ReV), Nantes Université (Nantes Univ)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), and European Project: 813211,H2020,POEMA(2019)
Subjects: Computer Science - Symbolic Computation, FOS: Computer and information sciences, robotics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], I.1.4, critical points, cuspidality, computational real algebraic geometry, Symbolic Computation (cs.SC), I.1.2, symbolic computation, Computer Science::Robotics, Computer Science - Robotics, Mathematics - Algebraic Geometry, 68W30, 14Q30, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Robotics (cs.RO), Algebraic Geometry (math.AG)
Abstract: Cuspidal robots are robots with at least two inverse kinematic solutions that can be connected by a singularity-free path. Deciding the cuspidality of generic 3R robots has been studied in the past, but extending the study to six-degree-of-freedom robots can be a challenging problem. Many robots can be modeled as a polynomial map together with a real algebraic set so that the notion of cuspidality can be extended to these data. In this paper we design an algorithm that, on input a polynomial map in $n$ indeterminates, and $s$ polynomials in the same indeterminates describing a real algebraic set of dimension $d$, decides the cuspidality of the restriction of the map to the real algebraic set under consideration. Moreover, if $D$ and $\tau$ are, respectively the maximum degree and the bound on the bit size of the coefficients of the input polynomials, this algorithm runs in time log-linear in $\tau$ and polynomial in $((s+d)D)^{O(n^2)}$. It relies on many high-level algorithms in computer algebra which use advanced methods on real algebraic sets and critical loci of polynomial maps. As far as we know, this is the first algorithm that tackles the cuspidality problem from a general point of view., Comment: 10 pages, 4 figures, published in the Proceedings of ISSAC2022
Published: 2022
Full Text: View/download PDF

8. Globally Optimal Solution to Inverse Kinematics of 7DOF Serial Manipulator

Author: Pavel Trutman, Mohab Safey El Din, Didier Henrion, Tomas Pajdla, Czech Institute of Informatics, Robotics and Cybernetics [Prague] (CIIRC), Czech Technical University in Prague (CTU), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-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 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), P. Trutman was supported by the EU Structural and Investment Funds, Operational Programe Research, Development and Education under the project IMPACT (reg. no. CZ.02.1.01/0.0/0.0/15_003/0000468) and Grant Agency of the CTU Prague project SGS19/173/OHK3/3T/13. T. Pajdla was supported by EU Structural and Investment Funds, Operational Programe Research, Development and Education under the project The Robotics for Industry 4.0 project (reg. no. CZ.02.1.01/0.0/0.0/15_003/0000470, the EUH2020 ARtwin No. 856994, and EU H2020 SPRING No. 871245 Projects.Didier Henrion and Mohab Safey El Din are supported by the European Union’s Horizon2020 research and innovation programme under the MarieSkłodowska-Curie grant agreement N°813211 (POEMA). Mohab Safey ElDin is supported by the ANR grants ANR-18-CE33-0011 Sesame, ANR-19-CE40-0018 De Rerum Natura, ANR-19-CE48-0015 ECARP and the CAMiSAdo PGMO project, ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(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, European Project: 813211,H2020,POEMA(2019), Faculty of Electrical Engineering [Prague] (FEL CTU), Institut National Polytechnique (Toulouse) (Toulouse INP), 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)-Institut National des Sciences Appliquées (INSA)-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-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), and Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)
Subjects: FOS: Computer and information sciences, Computer Science - Symbolic Computation, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Control and Optimization, Mechanical Engineering, Biomedical Engineering, Symbolic Computation (cs.SC), Computer Science Applications, Human-Computer Interaction, Computer Science::Robotics, Computer Science - Robotics, Optimization and Control (math.OC), Artificial Intelligence, Control and Systems Engineering, FOS: Mathematics, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], Computer Vision and Pattern Recognition, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Robotics (cs.RO), Mathematics - Optimization and Control
Abstract: International audience; The Inverse Kinematics (IK) problem is concerned with finding robot control parameters to bring the robot into a desired position under the kinematics and collision constraints. We present a global solution to the optimal IK problem for a general serial 7DOF manipulator with revolute joints and a quadratic polynomial objective function. We show that the kinematic constraints due to rotations can be all generated by the second-degree polynomials. This is an important result since it significantly simplifies the further step where we find the optimal solution by Lasserre relaxations of nonconvex polynomial systems. We demonstrate that the second relaxation is sufficient to solve a general 7DOF IK problem. Our approach is certifiably globally optimal. We demonstrate the method on the 7DOF KUKA LBR IIWA manipulator and show that we are in practice able to compute the optimal IK or certify infeasibility in 99.9 % tested poses. We also demonstrate that by the same approach, we are able to solve the IK problem for a random generic manipulator with seven revolute joints.
Published: 2022
Full Text: View/download PDF

9. Guessing Gröbner Bases of Structured Ideals of Relations of Sequences

Author: Mohab Safey El Din, Jérémy Berthomieu, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), PGMO grant P-2019-0018 CAMiSAdoEOARD-AFOSR grant FA8665-20-1-7029, ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(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), and European Project: 813211,H2020,POEMA(2019)
Subjects: Computer Science - Symbolic Computation, Discrete mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Ring (mathematics), Finite group, Algebra and Number Theory, Ideal (set theory), Recurrence relation, 010102 general mathematics, Linear recurrence relations, Structure (category theory), Change of orderings, Field (mathematics), 010103 numerical & computational mathematics, 16. Peace & justice, 01 natural sciences, Computational Mathematics, Gröbner basis, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Gröbner bases, 0101 mathematics, Invariant (mathematics), Mathematics, Symmetries
Abstract: Assuming sufficiently many terms of a n-dimensional table defined over a field are given, we aim at guessing the linear recurrence relations with either constant or polynomial coefficients they satisfy. In many applications, the table terms come along with a structure: for instance, they may be zero outside of a cone, they may be built from a Gr{\"o}bner basis of an ideal invariant under the action of a finite group. Thus, we show how to take advantage of this structure to both reduce the number of table queries and the number of operations in the base field to recover the ideal of relations of the table. In applications like in combinatorics, where all these zero terms make us guess many fake relations, this allows us to drastically reduce these wrong guesses. These algorithms have been implemented and, experimentally, they let us handle examples that we could not manage otherwise. Furthermore, we show which kind of cone and lattice structures are preserved by skew polynomial multiplication. This allows us to speed up the guessing of linear recurrence relations with polynomial coefficients by computing sparse Gr{\"o}bner bases or Gr{\"o}bner bases of an ideal invariant under the action of a finite group in a ring of skew polynomials., Comment: Journal of Symbolic Computation, Elsevier, In press
Published: 2022
Full Text: View/download PDF

10. Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension

Author: Jie Wang, Victor Magron, Jean B. Lasserre, É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), 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), 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 European Project: 813211,H2020,POEMA(2019)
Subjects: 0211 other engineering and technologies, 14P10, 90C25, 12D15, 12Y05, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, moment relaxation, Theoretical Computer Science, Combinatorics, chordal graph, Chordal graph, FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, 021103 operations research, Hierarchy (mathematics), Extension (predicate logic), Complement (complexity), Term (time), Moment (mathematics), Optimization and Control (math.OC), Polynomial optimization problem, term-sparsity, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Preprint, Software, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: This work is a follow-up and a complement to arXiv:1912.08899 [math.OC] for solving polynomial optimization problems (POPs). The chordal-TSSOS hierarchy that we propose is a new sparse moment-SOS framework based on term-sparsity and chordal extension. By exploiting term-sparsity of the input polynomials we obtain a two-level hierarchy of semidefinite programming relaxations. The novelty and distinguishing feature of such relaxations is to obtain quasi block-diagonal matrices obtained in an iterative procedure that performs chordal extension of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Various numerical examples demonstrate the efficiency and the scalability of this new hierarchy for both unconstrained and constrained POPs. The two hierarchies are complementary. While the former TSSOS arXiv:1912.08899 [math.OC] has a theoretical convergence guarantee, the chordal-TSSOS has superior performance but lacks this theoretical guarantee., 29 pages, 14 tables, 5 figures. arXiv admin note: text overlap with arXiv:1912.08899
Published: 2021
Full Text: View/download PDF

11. Computing real radicals and S-radicals of polynomial systems

Author: Mohab Safey El Din, Zhi-Hong Yang, Lihong Zhi, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Key Laboratory of Mathematics Mechanization (KLMM), Chinese Academy of Sciences [Changchun Branch] (CAS)-Institute of Systems Science (ISS), China-Academy of Mathematics and Systems Science [Beijing], North Carolina State University [Raleigh] (NC State), University of North Carolina System (UNC), European Project: 813211,H2020,POEMA(2019), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(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: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Sequence, Polynomial, Algebra and Number Theory, Degree (graph theory), S-radical ideal, 010102 general mathematics, Closure (topology), Real radical, 010103 numerical & computational mathematics, 01 natural sciences, Combinatorics, Computational Mathematics, Semi-algebraic set, Real algebraic geometry, Bounded function, Ideal (ring theory), 0101 mathematics, Finite set, ComputingMilieux_MISCELLANEOUS, Polynomial system, Mathematics
Abstract: Let f = ( f 1 , … , f s ) be a sequence of polynomials in Q [ X 1 , … , X n ] of maximal degree D and V ⊂ C n be the algebraic set defined by f and r be its dimension. The real radical 〈 f 〉 r e associated to f is the largest ideal which defines the real trace of V. When V is smooth, we show that 〈 f 〉 r e , has a finite set of generators with degrees bounded by deg ⁡ V . Moreover, we present a probabilistic algorithm of complexity ( s n D n ) O ( 1 ) to compute the minimal primes of 〈 f 〉 r e . When V is not smooth, we give a probabilistic algorithm of complexity s O ( 1 ) ( n D ) O ( n r 2 r ) to compute rational parametrizations for all irreducible components of the real algebraic set V ∩ R n . Let ( g 1 , … , g p ) in Q [ X 1 , … , X n ] and S be the basic closed semi-algebraic set defined by g 1 ≥ 0 , … , g p ≥ 0 . The S-radical of 〈 f 〉 , which is denoted by 〈 f 〉 S , is the ideal associated to the Zariski closure of V ∩ S . We give a probabilistic algorithm to compute rational parametrizations of all irreducible components of that Zariski closure, hence encoding 〈 f 〉 S . Assuming now that D is the maximum of the degrees of the f i 's and the g i 's, this algorithm runs in time 2 p ( s + p ) O ( 1 ) ( n D ) O ( r n 2 r ) . Experiments are performed to illustrate and show the efficiency of our approaches on computing real radicals.
Published: 2021
Full Text: View/download PDF

12. A Signature-based Algorithm for Computing the Nondegenerate Locus of a Polynomial System

Author: Eder, Christian, Lairez, Pierre, Mohr, Rafael, Din, Mohab Safey El, Fachbereich Mathematik [Kaiserslautern], Technische Universität Kaiserslautern (TU Kaiserslautern), Calcul formel, mathématiques expérimentales et interactions (MATHEXP), 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), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), DFG Sonderforschungsbereich TRR 195, Forschungsinitiative Rheinland-Pfalz, ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(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), European Project: 101040794,10000 DIGITS, and European Project: 813211,H2020,POEMA(2019)
Subjects: FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Symbolic Computation, G.4, Algebra and Number Theory, Mathematics::Commutative Algebra, 13P10, 13P05, Symbolic Computation (cs.SC), I.1.2, Algorithm, Computational Mathematics, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Gröbner Basis, Ideal Decomposition
Abstract: Polynomial system solving arises in many application areas to model non-linear geometric properties. In such settings, polynomial systems may come with degeneration which the end-user wants to exclude from the solution set. The nondegenerate locus of a polynomial system is the set of points where the codimension of the solution set matches the number of equations. Computing the nondegenerate locus is classically done through ideal-theoretic operations in commutative algebra such as saturation ideals or equidimensional decompositions to extract the component of maximal codimension. By exploiting the algebraic features of signature-based Gr\"obner basis algorithms we design an algorithm which computes a Gr\"obner basis of the equations describing the closure of the nondegenerate locus of a polynomial system, without computing first a Gr\"obner basis for the whole polynomial system., Comment: 22 pages, 2 figures. Substantial rewrite of content of the parts of the paper involving signature-based Gr\"obner basis algorithms, both the exposition and the description of the core algorithm of the paper changed
Published: 2022
Full Text: View/download PDF

13. Polynomial description for the T-Orbit Spaces of Multiplicative Actions

Author: Hubert, Evelyne, Metzlaff, Tobias, Riener, Cordian, AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), The Arctic University of Norway (UiT), European Project: 813211,H2020,POEMA(2019), The Arctic University of Norway [Tromsø, Norway] (UiT), 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), Metzlaff, Tobias, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID
Subjects: Multiplicative Invariant Theory, Weyl Groups, Chebyshev Polynomials, Semi-Algebraic Sets, [MATH.MATH-AG] Mathematics [math]/Algebraic Geometry [math.AG], Orbit Spaces, [MATH] Mathematics [math], Polynomial Matrix Inequalities, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH]Mathematics [math], [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR], [MATH.MATH-GR] Mathematics [math]/Group Theory [math.GR]
Abstract: International audience; A finite group with an integer representation has a multiplicative action on the ring of Laurent polynomials, which is induced by a nonlinear action on the complex torus. We study the structure of the associated orbit space as the image of the fundamental invariants. For the Weyl groups of types A, B, C and D, this image is a compact basic semi-algebraic set and we present the defining polynomial inequalities explicitly. We show how orbits correspond to solutions in the complex torus of symmetric polynomial systems and give a characterization of the orbit space as the positivity-locus of a symmetric real matrix polynomial. The resulting domain is the region of orthogonality for a family of generalized Chebyshev polynomials, which have connections to topics such as Fourier analysis and representations of Lie algebras.
Published: 2022

14. Optimization of trigonometric polynomials with crystallographic symmetry and applications

Author: Metzlaff, Tobias, Moustrou, Philippe, Riener, Cordian, Hubert, Evelyne, Metzlaff, Tobias, Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID, Université Côte d'Azur (UCA), AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), Université Toulouse - Jean Jaurès (UT2J), The Arctic University of Norway [Tromsø, Norway] (UiT), and European Project: 813211,H2020,POEMA(2019)
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Chebyshev Polynomials, Polynomial optimization, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Trigonometric polynomials, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Root systems, [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR], Chromatic number bounds, [MATH.MATH-GR] Mathematics [math]/Group Theory [math.GR]
Abstract: The Weyl group of a crystallographic root system has a multiplicative action on the ring of multivariate trigonometric polynomials. We study the problem of minimizing an invariant trigonometric polynomial. This problem can be written as a polynomial optimization problem on a compact basic semi-algebraic set. Lasserre's moment-SOS hierarchy is formulated in the basis of generalized Chebyshev polynomials, leading to a different notion of the polynomial degree and smaller matrices in the arising semi-definite program. Bilevel optimization techniques are applied to solve max-min problems. Optimal values of trigonometric polynomials appear in spectral bounds for chromatic numbers and independence numbers of geometric distance graphs. We study the quality of these bounds for polytope norms and prove sharpness in several cases.
Published: 2022

15. 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

16. 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

17. Solving parametric systems of polynomial equations over the reals through Hermite matrices

Author: Le, Huu Phuoc, Safey El Din, Mohab, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Mohab Safey El Din and Huu Phuoc Le are supported by the ANR grants ANR-18-CE33-0011 SESAME, and ANR-19-CE40-0018 DERERUMNATURA, the joint ANR-FWF ANR-19-CE40-0018 ECARP project, the PGMO grant CAMISADO and the European Union’s Horizon 2020 research and innovative training network program under the Marie Skłodowska-Curie grant agreement N° 813211 (POEMA) and the Grant FA8665-20-1-7029 of the EOARD-AFOSR., ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(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), European Project, European Project: 813211,H2020,POEMA(2019), and Mohab Safey El Din and Huu Phuoc Le are supported by the ANR grants ANR-18-CE33-0011 SESAME, and ANR-19-CE40-0018 DERERUMNATURA, the joint ANR-FWF ANR-19-CE40-0018 ECARP project, the PGMO grant CAMISADO and the European Union’s Horizon 2020 research and innovative training network program under the Marie Skłodowska-Curie grant agreement N° 813211 (POEMA)
Subjects: Computer Science - Symbolic Computation, Computational Geometry (cs.CG), FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Algebra and Number Theory, Mathematics::Commutative Algebra, 010102 general mathematics, 0102 computer and information sciences, Symbolic Computation (cs.SC), 16. Peace & justice, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Polynomial system solving, I.1.2, Real root classification, Computational Mathematics, 010201 computation theory & mathematics, Real algebraic geometry, Computer Science - Computational Geometry, Groebner bases, 0101 mathematics, Hermite quadratic forms
Abstract: International audience; We design a new algorithm for solving parametric systems of equations having finitely many complex solutions for generic values of theparameters. More precisely, let $\mathbf{f} = (f_1, \ldots, f_m)\subset \mathbb{Q}[\mathbf{y}][\mathbf{x}]$ with $\mathbf{y} = (y_1, \ldots, y_{t})$ and $\mathbf{x} = (x_1, \ldots, x_{n})$, $\mathcal{V}\subset \mathbb{C}^t \times \mathbb{C}^n$ be the algebraic set defined by the simultaneous vanishing of the $f_i$'s and $\pi$ be the projection $(\mathbf{y}, \mathbf{x}) \to \mathbf{y}$. Under the assumptions that $\mathbf{f}$ admits finitely many complex solutions when specializing $\mathbf{y}$ to generic values and that the ideal generated by $\mathbf{f}$ is radical, we solve the following algorithmic problem. On input $\mathbf{f}$, we compute {\em semi-algebraic formulas} defining open semi-algebraic sets$\mathcal{S}_1, \ldots, \mathcal{S}_{\ell}$ in the parameters' space $\mathbb{R}^t$ such that $\cup_{i=1}^{\ell} \mathcal{S}_i$ is dense in$\mathbb{R}^t$ and, for $1\leq i \leq \ell$, the number of real points in $\mathcal{V}\cap \pi^{-1}(\eta)$ is invariant when $\eta$ rangesover $\mathcal{S}_i$.This algorithm exploits special properties of some well chosen monomial bases in the quotient algebra $\mathbb{Q}(\mathbf{y})[\mathbf{x}] / I$ where $I\subset \mathbb{Q}(\mathbf{y})[\mathbf{x}]$ is the ideal generated by $\mathbf{f}$ in $\mathbb{Q}(\mathbf{y})[\mathbf{x}]$ as well as thespecialization property of the so-called Hermite matrices which represent Hermite's quadratic forms. This allows us to obtain``compact'' representations of the semi-algebraic sets $\mathcal{S}_i$ by means of semi-algebraic formulas encoding the signature of a givensymmetric matrix. When $\mathbf{f}$ satisfies extra genericity assumptions (such as regularity), we use the theory of Gr\"obner bases to derive complexitybounds both on the number of arithmetic operations in $\mathbb{Q}$ and the degree of the output polynomials. More precisely, letting $d$ bethe maximal degrees of the $f_i$'s and $\mathfrak{D} = n(d-1)d^n$, we prove that, on a generic input $\mathbf{f}=(f_1,\ldots,f_n)$, one cancompute those semi-algebraic formulas with $O\ {\widetilde{~}}\left (\binom{t+\mathfrak{D}}{t}\ 2^{3t}\ n^{2t+1} d^{3nt+2(n+t)+1} \right )$arithmetic operations in $\mathbb{Q}$ and that the polynomials involved in these formulas have degree bounded by $\mathfrak{D}$.We report on practical experiments which illustrate the efficiency of this algorithm, both on generic parametric systems and parametricsystems coming from applications since it allows us to solve systems which are out of reach on the current state-of-the-art.
Published: 2022
Full Text: View/download PDF

18. Converging outer approximations to global attractors using semidefinite programming

Author: Milan Korda, Corbinian Schlosser, É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), 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, and European Project: 813211,H2020,POEMA(2019)
Subjects: 0209 industrial biotechnology, Polynomial, Linear programming, Dynamical systems theory, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], MathematicsofComputing_NUMERICALANALYSIS, Outer approximations, Dynamical Systems (math.DS), 34D45 (primary), 90C22 (secondary), 02 engineering and technology, Occupation measures, 01 natural sciences, 020901 industrial engineering & automation, Attractor, Dynamical systems, FOS: Mathematics, Applied mathematics, Infinite-dimensional linear programming, Semidefinite programming, Mathematics - Dynamical Systems, 0101 mathematics, Electrical and Electronic Engineering, Mathematics - Optimization and Control, Mathematics, Sequence, 010102 general mathematics, Sum-of-squares, Global attractor, Discrete time and continuous time, Optimization and Control (math.OC), Control and Systems Engineering, Convex optimization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: International audience; This paper develops a method for obtaining guaranteed outer approximations for global attractors of continuous and discrete time nonlinear dynamical systems. The method is based on a hierarchy of semidefinite programming problems of increasing size with guaranteed convergence to the global attractor. The approach taken follows an established line of reasoning, where we first characterize the global attractor via an infinite dimensional linear programming problem (LP) in the space of Borel measures. The dual to this LP is in the space of continuous functions and its feasible solutions provide guaranteed outer approximations to the global attractor. For systems with polynomial dynamics, a hierarchy of finite-dimensional sum-of-squares tightenings of the dual LP provides a sequence of outer approximations to the global attractor with guaranteed convergence in the sense of volume discrepancy tending to zero. The method is very simple to use and based purely on convex optimization. Numerical examples with the code available online demonstrate the method.
Published: 2021
Full Text: View/download PDF

19. On Moment Approximation and the Effective Putinar's Positivstellensatz

Author: Baldi, Lorenzo, Mourrain, Bernard, AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), This work has been supported by European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Actions, grant agreement 813211 (POEMA), and European Project: 813211,H2020,POEMA(2019)
Subjects: [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], Mathematics::Optimization and Control, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: We analyse the representation of positive polynomials in terms of Sums of Squares. We provide a quantitative version of Putinar Positivstellensatz over a compact basic closed semialgebraic set S, with new polynomial bounds on the degree of the positivity certificates. These bounds involve a Łojasiewicz exponent associated to the description of S. We show that under Constraint Qualification Conditions, this Łojasiewicz exponent is equal to 1. We deduce new bounds on the convergence rate of the optima in Lasserre Sum-of-Squares hierarchy to the global optimum of a polynomial function on S and new bounds on the Hausdorff distance between the cone of truncated (probability) measures supported on S and the cone of truncated moment sequences, which are positive on the quadratic module of S.
Published: 2021

20. Exploiting Term Sparsity in Moment-SOS hierarchy for Dynamical Systems

Author: Magron, Victor, Wang, Jie, Schlosser, Corbinian, Korda, Milan, 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), Academy of Mathematics and Systems Science (AMSS), Chinese Academy of Sciences [Beijing] (CAS), 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), 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, Centre International de Mathématiques et d'Informatique (de Toulouse) - - CIMI2011 - ANR-11-LABX-0040 - LABX - 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: Optimization and Control (math.OC), FOS: Mathematics, 93C10, 93C15, 93C20, 90C22, 90C23, 34C11, 37C10, [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: In this paper we present term sparsity sum-of-squares (TSSOS) methods applied to several problems from dynamical systems, such as region of attraction, maximum positively invariant sets and global attractors. We combine the TSSOS algorithm of Wang, Magron and Lasserre [SIAM J. Optim., 31(1):30-58, 2021] with existing infinite dimensional linear program representations of those sets. This leads to iterative schemes in the moment-sum-of-squares hierarchy which allows less expensive computations while keeping convergence guarantees. Finally this procedure is closely related to sign symmetries of the dynamical system as was already revealed for polynomial optimization. Numerical examples demonstrate the efficiency of the approach in the presence of appropriate sparsity., 16 pages
Published: 2021

21. Certifying Global Optimality of AC-OPF Solutions via the CS-TSSOS Hierarchy

Author: Wang, Jie, Magron, Victor, Chinese Academy of Sciences [Beijing] (CAS), 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, FMJH Program PGMO (EPICS project), 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), and European Project: 813211,H2020,POEMA(2019)
Subjects: [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: 13 pages, 1 figure, 4 tables; In this paper, we report the experimental results on certifying 1% global optimality of solutions of AC-OPF instances from PGLiB with up to 24464 buses via the CS-TSSOS hierarchy - a moment-SOS based hierarchy that exploits both correlative and term sparsity, which can provide tighter SDP relaxations than Shor's relaxation. Our numerical experiments demonstrate that the CS-TSSOS hierarchy scales well with the problem size and is indeed useful in certifying 1% global optimality of solutions for large-scale real world problem; e.g., the AC-OPF problem. In particular, we are able to certify 1% global optimality for an AC-OPF instance with 6515 buses involving 14398 real variables and 63577 constraints.
Published: 2021

22. Noncommutative Polynomial Optimization

Author: Bhardwaj, Abhishek, Klep, Igor, Magron, Victor, Australian National University (ANU), Department of Mathematics (University of Ljubljana), University of Ljubljana, 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), QUANTPOP funded by PHC Proteus, EPICS funded by the Gaspard Monge Program for Optimization and operationnal research, Fondation Jacques Hadamard, FastQI funded by Institute Quantum technologies in Occitanie., 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), 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, European Project: 813211,H2020,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: Optimization and Control (math.OC), ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, 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: In this chapter we present the sums of Hermitian squares approach to noncommutative polynomial optimization problems. This is an extension of the sums of squares approach for polynomial optimization arising from real algebraic geometry. We provide a gentle introduction to the underlying theory of this methodology and highlight its importance., Comment: 10 pages
Published: 2021

23. 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

24. On the solution existence and stability of polynomial optimization problems

Author: Vu Trung Hieu, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), European Project: 813211,H2020,POEMA(2019), 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: Normalization (statistics), Asymptotic analysis, Polynomial, Control and Optimization, Optimization problem, Eaves, 0211 other engineering and technologies, Stability (learning theory), Computational intelligence, 010103 numerical & computational mathematics, 02 engineering and technology, Type (model theory), 01 natural sciences, Local upper-Hölder stability, Genericity, FOS: Mathematics, Applied mathematics, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Frank–Wolfe type theorem, 021103 operations research, Polynomial optimization, Asymptotic cone, Regularity condition, Mathematics Subject Classification (2000) 90C30·14P10, Eaves type theorem, Optimization and Control (math.OC), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Upper semicontinuity
Abstract: This paper introduces and investigates a regularity condition in the asymptotic sense for optimization problems whose objective functions are polynomial. Under this regularity condition, the normalization argument in asymptotic analysis enables us to see the solution existence as well as the solution stability of these problems. We prove a Frank-Wolfe type theorem for regular optimization problems and an Eaves type theorem for non-regular pseudoconvex optimization problems. Moreover, we show results on the stability such as upper semicontinuity and local upper-H\"{o}lder stability of the solution map of polynomial optimization problems. At the end of the paper, we discuss the genericity of the regularity condition., Comment: The old title: A regularity condition in polynomial optimization
Published: 2021
Full Text: View/download PDF

25. Computing the dimension of a real algebraic set

Author: Lairez, Pierre, Safey El Din, Mohab, Symbolic Special Functions : Fast and Certified (SPECFUN), 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), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), This work is supported by ANR under grants ANR-19-CE48-0015 (ECARP), ANR-18-CE33-0011 (Sesame) and ANR-19-CE40-0018 (DeRerumNatura), and the EU H2020 research and innovation programme under grant 813211 (POEMA)., ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), and European Project: 813211,H2020,POEMA(2019)
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Algebraic algorithms, ComputingMilieux_MISCELLANEOUS, Computing methodologies
Abstract: International audience
Published: 2021

26. Polynomial-Division-Based Algorithms for Computing Linear Recurrence Relations

Author: Jérémy Berthomieu, Jean-Charles Faugère, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), CryptoNext Security, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), PGMO grant P-2019-0018 CAMiSAdo, ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), European Project: 813211,H2020,POEMA(2019), 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: Computer Science - Symbolic Computation, Polynomial, Monomial, 010103 numerical & computational mathematics, 0102 computer and information sciences, 01 natural sciences, Polynomial long division, Gröbner basis, Padé approximants, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Computer Science::Symbolic Computation, 0101 mathematics, Mathematics, Extended Euclidean algorithm, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Algebra and Number Theory, Polynomial arithmetic, Monomial ideal, Computational Mathematics, 010201 computation theory & mathematics, Linear algebra, Gröbner bases, linear recursive sequences, Algorithm, Berlekamp-Massey-Sakata
Abstract: International audience; Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear recurrence relations of a sequence with the Berlekamp-Massey algorithm. Likewise, sparse multivariate polynomial interpolation and multidimensional cyclic code decoding require guessing linear recurrence relations of a multivariate sequence.Several algorithms solve this problem. The so-called Berlekamp-Massey-Sakata algorithm (1988) uses polynomial additions and shifts by a monomial. The Scalar-FGLM algorithm (2015) relies on linear algebra operations on a multi-Hankel matrix, a multivariate generalization of a Hankel matrix. The Artinian Gorenstein border basis algorithm (2017) uses a Gram-Schmidt process.We propose a new algorithm for computing the Gröbner basis of the ideal of relations of a sequence based solely on multivariate polynomial arithmetic. This algorithm allows us to both revisit the Berlekamp-Massey-Sakata algorithm through the use of polynomial divisions and to completely revise the Scalar-FGLM algorithm without linear algebra operations.A key observation in the design of this algorithm is to work on the mirror of the truncated generating series allowing us to use polynomial arithmetic modulo a monomial ideal. It appears to have some similarities with Padé approximants of this mirror polynomial.As an addition from the paper published at the ISSAC conferance, we give an adaptive variant of this algorithm taking into account the shape of the final Gröbner basis gradually as it is discovered. The main advantage of this algorithm is that its complexity in terms of operations and sequence queries only depends on the output Gröbner basis.All these algorithms have been implemented in Maple and we report on our comparisons.
Published: 2021
Full Text: View/download PDF

27. 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

28. msolve: A Library for Solving Polynomial Systems

Author: Christian Eder, Mohab Safey El Din, Jérémy Berthomieu, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Fachbereich Mathematik [Kaiserslautern], Technische Universität Kaiserslautern (TU Kaiserslautern), PGMO grant P-2019-0018 CAMiSAdo, Forschungsinitiative Rheinland-Pfalz, ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), European Project: 813211,H2020,POEMA(2019), Grant FA8665-20-1-7029 of the EOARD-AFOSR, 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: Computer Science - Symbolic Computation, FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Polynomial, 010102 general mathematics, Univariate, 010103 numerical & computational mathematics, Symbolic Computation (cs.SC), Lexicographical order, Symbolic computation, 01 natural sciences, Magma (computer algebra system), Algebra, Range (mathematics), Gröbner basis, Linear algebra, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Computer Science::Symbolic Computation, 0101 mathematics, computer, computer.programming_language, Mathematics
Abstract: We present a new open source C library \texttt{msolve} dedicated to solving multivariate polynomial systems of dimension zero through computer algebra methods. The core algorithmic framework of \texttt{msolve} relies on Gr\''obner bases and linear algebra based algorithms for polynomial system solving. It relies on Gr\''obner basis computation w.r.t.\ the degree reverse lexicographical order, Gr\''obner conversion to a lexicographical Gr\''obner basis and real solving of univariate polynomials. We explain in detail how these three main steps of the solving process are implemented, how we exploit \texttt{AVX2} instruction processors and the more general implementation ideas we put into practice to better exploit the computational capabilities of this algorithmic framework. We compare the practical performances of \texttt{msolve} with leading computer algebra systems such as \textsc{Magma}, \textsc{Maple}, \textsc{Singular} on a wide range of systems with finitely many complex solutions, showing that \texttt{msolve} can tackle systems which were out of reach by the computer algebra software state-of-the-art., Comment: 2021 International Symposium on Symbolic and Algebraic Computation, Jul 2021, Saint-P{\'e}tersbourg, Russia
Published: 2021
Full Text: View/download PDF

29. On the computation of asymptotic critical values of polynomial maps and applications

Author: Jérémy Berthomieu, Andrew Ferguson, Mohab Safey El Din, Ferguson, Andrew, Décider l'irrationalité et la transcendance - - DeRerumNatura2019 - ANR-19-CE40-0018 - AAPG2019 - VALID, Algorithmes efficaces et exacts pour la planification de trajectoire en robotique - - ECARP2019 - ANR-19-CE48-0015 - AAPG2019 - VALID, APPEL À PROJETS GÉNÉRIQUE 2018 - Singularités Et Stabilité des AsservisseMEnts référencés capteurs - - SESAME2018 - ANR-18-CE33-0011 - AAPG2018 - VALID, Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), European Project: 813211,H2020,POEMA(2019), 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: FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Symbolic Computation, [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], Polynomial optimisation, Gröbner bases, Symbolic Computation (cs.SC), Asymptotic critical values
Abstract: Let $\mathbf{f} = \left( f_1, \dots, f_p\right) $ be a polynomial tuple in $\mathbb{Q}[z_1, \dots, z_n]$ and let $d = \max_{1 \leq i \leq p} \deg f_i$. We consider the problem of computing the set of asymptotic critical values of the polynomial mapping, with the assumption that this mapping is dominant, $\mathbf{f}: z \in \mathbb{K}^n \to (f_1(z), \dots, f_p(z)) \in \mathbb{K}^p$ where $\mathbb{K}$ is either $\mathbb{R}$ or $\mathbb{C}$. This is the set of values $c$ in the target space of $\mathbf{f}$ such that there exists a sequence of points $(\mathbf{x}_i)_{i\in \mathbb{N}}$ for which $\mathbf{f}(\mathbf{x}_i)$ tends to $c$ and $\|\mathbf{x}_i\| \kappa(\mathrm{d} \mathbf{f}(\mathbf{x}_i))$ tends to $0$ when $i$ tends to infinity where $\mathrm{d} \mathbf{f}$ is the differential of $\mathbf{f}$ and $\kappa$ is a function measuring the distance of a linear operator to the set of singular linear operators from $\mathbb{K}^n$ to $\mathbb{K}^p$. Computing the union of the classical and asymptotic critical values allows one to put into practice generalisations of Ehresmann's fibration theorem. This leads to natural and efficient applications in polynomial optimisation and computational real algebraic geometry. Going back to previous works by Kurdyka, Orro and Simon, we design new algorithms to compute asymptotic critical values. Through randomisation, we introduce new geometric characterisations of asymptotic critical values. This allows us to dramatically reduce the complexity of computing such values to a cost that is essentially $O(d^{2n(p+1)})$ arithmetic operations in $\mathbb{Q}$. We also obtain tighter degree bounds on a hypersurface containing the asymptotic critical values, showing that the degree is at most $p^{n-p+1}(d-1)^{n-p}(d+1)^{p}$. Next, we show how to apply these algorithms to unconstrained polynomial optimisation problems and the problem of computing sample points per connected component of a semi-algebraic set defined by a single inequality/inequation. We report on the practical capabilities of our implementation of this algorithm. It shows how the practical efficiency surpasses the current state-of-the-art algorithms for computing asymptotic critical values by tackling examples that were previously out of reach.
Published: 2021

30. Finite convergence of sum-of-squares hierarchies for the stability number of a graph

Author: Monique Laurent, Luis Felipe Vargas, Centrum voor Wiskunde en Informatica (CWI), Centrum Wiskunde & Informatica (CWI)-Netherlands Organisation for Scientific Research, European Project: 813211,H2020,POEMA(2019), Research Group: Operations Research, Econometrics and Operations Research, Center Ph. D. Students, 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: Stable set problem, Polynomial optimization, Applied Mathematics, Sum-of-squares polynomial, Standard quadratic programming, Laserre hierarchy, Copositive programming, Theoretical Computer Science, Optimization and Control (math.OC), FOS: Mathematics, Motzkin--Straus formulation, $\alpha$-critical graph, Finite convergence, Semidefinite programming, [MATH]Mathematics [math], Mathematics - Optimization and Control, Software
Abstract: We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $\alpha(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [SIAM J. Optim. 12 (2002), pp.875--892], who conjectured convergence to $\alpha(G)$ in $r=\alpha(G)-1$ steps. Even the weaker conjecture claiming finite convergence is still open. We establish links between this hierarchy and sum-of-squares hierarchies based on the Motzkin-Straus formulation of $\alpha(G)$, which we use to show finite convergence when $G$ is acritical, i.e., when $\alpha(G\setminus e)=\alpha(G)$ for all edges $e$ of $G$. This relies, in particular, on understanding the structure of the minimizers of Motzkin-Straus formulation and showing that their number is finite precisely when $G$ is acritical. As a byproduct we show that deciding whether a standard quadratic program has finitely many minimizers does not admit a polynomial-time algorithm unless P=NP., Comment: We removed the material from section 7 about rank 0 graphs which will be included in separate forthcoming work
Published: 2021

31. CONVERGENCE RATES OF RLT AND LASSERRE-TYPE HIERARCHIES FOR THE GENERALIZED MOMENT PROBLEM OVER THE SIMPLEX AND THE SPHERE

Author: Etienne De Klerk, Felix Kirschner, Tilburg University [Netherlands], 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), Research Group: Operations Research, Econometrics and Operations Research, Center Ph. D. Students, and European Project: 813211,H2020,POEMA(2019)
Subjects: Control and Optimization, Optimization and Control (math.OC), Generalized moment problem with polynomials, FOS: Mathematics, Business, Management and Accounting (miscellaneous), [MATH]Mathematics [math], 16. Peace & justice, Linear programming hierarchies, Mathematics - Optimization and Control, Semidefinite programming hierarchies
Abstract: We consider the generalized moment problem (GMP) over the simplex and the sphere. This is a rich setting and it contains NP-hard problems as special cases, like constructing optimal cubature schemes and rational optimization. Using the Reformulation-Linearization Technique (RLT) and Lasserre-type hierarchies, relaxations of the problem are introduced and analyzed. For our analysis we assume throughout the existence of a dual optimal solution as well as strong duality. For the GMP over the simplex we prove a convergence rate of $O(1/r)$ for a linear programming, RLT-type hierarchy, where $r$ is the level of the hierarchy, using a quantitative version of P\'olya's Positivstellensatz. As an extension of a recent result by Fang and Fawzi [Math. Program., 2020, https://doi.org/10.1007/s10107-020-01537-7] we prove the Lasserre hierarchy of the GMP [Math. Program., Vol. 112, 65-92, 2008] over the sphere has a convergence rate of $O(1/r^2)$. Moreover, we show the introduced linear RLT-relaxation is a generalization of a hierarchy for minimizing forms of degree $d$ over the simplex, introduced by de Klerk, Laurent and Parrilo [J. Theoretical Computer Science, Vol. 361, 210-225, 2006]., Comment: 13 pages
Published: 2021

32. Stability of Control Systems under Extended Weakly-Hard Constraints

Author: Vreman, Nils, Pazzaglia, Paolo, Wang, Jie, Magron, Victor, Maggio, Martina, 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 - 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), 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), and European Project: 813211,H2020,POEMA(2019)
Subjects: [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: 14 pages, 2 figures, 2 tables; Control systems can show robustness to many events, like disturbances and model inaccuracies. It is natural to speculate that they are also robust to alterations of the control signal pattern, due to sporadic late completions (called deadline misses) when implemented as a digital task on an embedded platform. Recent research analysed stability when imposing constraints on the maximum number of consecutive deadlines that can be missed. This is only one type of characterization, and results in a pessimistic analysis when applied to more general cases. To overcome this limitation, this paper proposes a comprehensive stability analysis for control systems subject to a set of generic constraints, describing the possible sequences of correct completions and deadline misses. The proposed analysis brings the assessment of control systems robustness to computational problems one step closer to the controller implementation.
Published: 2021

33. Noncommutative Christoffel-Darboux Kernels

Author: Serban Belinschi, Victor Magron, Victor Vinnikov, Institut de Mathématiques de Toulouse UMR5219 (IMT), 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)-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), Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), 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, Ben-Gurion University of the Negev (BGU), Part of this work was conducted in November 2019 while STB was a visiting fellow supported by the Faculty of Natural Sciences Distinguished Scientist Visitors Program of the Ben Gurion University of the Negev, Beer-Sheva, Israel, and during the three authors’visit at the MFO workshop I.D.: 2010, 'Real Algebraic Geometry with a View Toward Hyperbolic Programming and Free Probability' (1–7 March 2020)., 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), 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), É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), Department of Mathematics [Be'er Sheva], 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), 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), Belinschi, Serban, TREMPLIN-ERC - Optimisation garantie pour la vérification des systèmes cyber-physiques - - COPS2018 - ANR-18-ERC2-0004 - TERC - VALID, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID
Subjects: Mathematics - Complex Variables, Mathematics::Complex Variables, Optimization and Control (math.OC), Applied Mathematics, General Mathematics, [MATH.MATH-OA]Mathematics [math]/Operator Algebras [math.OA], Mathematics - Operator Algebras, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Complex Variables (math.CV), [MATH.MATH-OA] Mathematics [math]/Operator Algebras [math.OA], Operator Algebras (math.OA), Mathematics - Optimization and Control
Abstract: We introduce from an analytic perspective Christoffel-Darboux kernels associated to bounded, tracial noncommutative distributions. We show that properly normalized traces, respectively norms, of evaluations of such kernels on finite dimensional matrices yield classical plurisubharmonic functions as the degree tends to infinity, and show that they are comparable to certain noncommutative versions of the Siciak extremal function. We prove estimates for Siciak functions associated to free products of distributions, and use the classical theory of plurisubharmonic functions in order to propose a notion of support for noncommutative distributions. We conclude with some conjectures and numerical experiments., Comment: 48 pages, 2 figures
Published: 2021
Full Text: View/download PDF

34. The Constant Trace Property in Noncommutative Optimization

Author: Abhishek Bhardwaj, Ngoc Hoang Anh Mai, 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, 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), PHC Proteus QUANTPOP, 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,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: Semidefinite programming, 021103 operations research, Trace (linear algebra), Numerical analysis, 010102 general mathematics, 0211 other engineering and technologies, Mathematics::Optimization and Control, 02 engineering and technology, 01 natural sciences, Noncommutative geometry, Matrix (mathematics), Optimization and Control (math.OC), FOS: Mathematics, Applied mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Relaxation (approximation), 0101 mathematics, Constant (mathematics), Mathematics - Optimization and Control, Computer Science::Databases, Variable (mathematics), Mathematics
Abstract: In this article, we show that each semidefinite relaxation of a ball-constrained noncommutative polynomial optimization problem can be cast as a semidefinite program with a constant trace matrix variable. We then demonstrate how this constant trace property can be exploited via first order numerical methods to solve efficiently the semidefinite relaxations of the noncommutative problem., Comment: 8 pages, 3 tables
Published: 2021
Full Text: View/download PDF

35. Barrier and penalty methods for low-rank semidefinite programming with application to truss topology design

Author: Habibi, Soodeh, Kavand, Arefeh, Kocvara, Michal, Stingl, Michael, Kocvara, Michal, Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID, School of Mathematics, University of Birmingham, Department Mathematik [Erlangen], Friedrich-Alexander Universität Erlangen-Nürnberg (FAU), European Project: 813211,H2020,POEMA(2019), 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: Optimization and Control (math.OC), 90C22, 90C51, 65F08, 74P05, MathematicsofComputing_NUMERICALANALYSIS, FOS: Mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Numerical Analysis, Numerical Analysis (math.NA), [MATH.MATH-NA] Mathematics [math]/Numerical Analysis [math.NA], Mathematics - Optimization and Control, Computer Science::Numerical Analysis, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: The aim of this paper is to solve large-and-sparse linear Semidefinite Programs (SDPs) with low-rank solutions. We propose to use a preconditioned conjugate gradient method within second-order SDP algorithms and introduce a new efficient preconditioner fully utilizing the low-rank information. We demonstrate that the preconditioner is universal, in the sense that it can be efficiently used within a standard interior-point algorithm, as well as a newly developed primal-dual penalty method. The efficiency is demonstrated by numerical experiments using the truss topology optimization problems of growing dimension.
Published: 2021
Full Text: View/download PDF

36. Revisiting semidefinite programming approaches to options pricing: complexity and computational perspectives

Author: Didier Henrion, Felix Kirschner, Etienne De Klerk, Milan Korda, Jean-Bernard Lasserre, 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, Department of Econometrics and Operations Research (Tilburg University), Tilburg University [Netherlands], 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,POEMA(2019), Research Group: Operations Research, Econometrics and Operations Research, Center Ph. D. Students, 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), 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: Optimization and Control (math.OC), Options pricing, General Engineering, FOS: Mathematics, Semidefinite programming, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Moment-SOS hierarchy
Abstract: In this paper we consider the problem of finding bounds on the prices of options depending on multiple assets without assuming any underlying model on the price dynamics, but only the absence of arbitrage opportunities. We formulate this as a generalized moment problem and utilize the well-known Moment-Sum-of-Squares (SOS) hierarchy of Lasserre to obtain bounds on the range of the possible prices. A complementary approach (also due to Lasserre) is employed for comparison. We present several numerical examples to demonstrate the viability of our approach. The framework we consider makes it possible to incorporate different kinds of observable data, such as moment information, as well as observable prices of options on the assets of interest., Comment: 20 pages
Published: 2021
Full Text: View/download PDF

37. TSSOS: a Julia library to exploit sparsity for large-scale polynomial optimization

Author: Magron, Victor, Wang, Jie, 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 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, 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,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), 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: FOS: Computer and information sciences, Optimization and Control (math.OC), ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Computer Science - Mathematical Software, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematical Software (cs.MS), Mathematics - Optimization and Control
Abstract: The Julia library TSSOS aims at helping polynomial optimizers to solve large-scale problems with sparse input data. The underlying algorithmic framework is based on exploiting correlative and term sparsity to obtain a new moment-SOS hierarchy involving potentially much smaller positive semidefinite matrices. TSSOS can be applied to numerous problems ranging from power networks to eigenvalue and trace optimization of noncommutative polynomials, involving up to tens of thousands of variables and constraints., 10 pages, 2 figures, 2 tables
Published: 2021

38. Homotopy techniques for solving sparse column support determinantal polynomial systems

Author: Thi Xuan Vu, George Labahn, Mohab Safey El Din, Éric Schost, Symbolic Computation Group (SCG), University of Waterloo [Waterloo]-David R. Cheriton School of Computer Science, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), European Project: 813211,H2020,POEMA(2019), 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: Computer Science - Symbolic Computation, Statistics and Probability, FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Numerical Analysis, Polynomial, Control and Optimization, Algebra and Number Theory, Applied Mathematics, General Mathematics, Homotopy, 010102 general mathematics, Zero (complex analysis), Field (mathematics), 010103 numerical & computational mathematics, Symbolic Computation (cs.SC), 01 natural sciences, Algebraic closure, Polynomial matrix, Combinatorics, Symmetric group, 0101 mathematics, Algebraic number, Mathematics
Abstract: Let $\mathbf{K}$ be a field of characteristic zero with $\overline{\mathbf{K}}$ its algebraic closure. Given a sequence of polynomials $\mathbf{g} = (g_1, \ldots, g_s) \in \mathbf{K}[x_1, \ldots , x_n]^s$ and a polynomial matrix $\mathbf{F} = [f_{i,j}] \in \mathbf{K}[x_1, \ldots, x_n]^{p \times q}$, with $p \leq q$, we are interested in determining the isolated points of $V_p(\mathbf{F},\mathbf{g})$, the algebraic set of points in $\overline{\mathbf{K}}$ at which all polynomials in $\mathbf{g}$ and all $p$-minors of $\mathbf{F}$ vanish, under the assumption $n = q - p + s + 1$. Such polynomial systems arise in a variety of applications including for example polynomial optimization and computational geometry. We design a randomized sparse homotopy algorithm for computing the isolated points in $V_p(\mathbf{F},\mathbf{g})$ which takes advantage of the determinantal structure of the system defining $V_p(\mathbf{F}, \mathbf{g})$. Its complexity is polynomial in the maximum number of isolated solutions to such systems sharing the same sparsity pattern and in some combinatorial quantities attached to the structure of such systems. It is the first algorithm which takes advantage both on the determinantal structure and sparsity of input polynomials. We also derive complexity bounds for the particular but important case where $\mathbf{g}$ and the columns of $\mathbf{F}$ satisfy weighted degree constraints. Such systems arise naturally in the computation of critical points of maps restricted to algebraic sets when both are invariant by the action of the symmetric group.
Published: 2021
Full Text: View/download PDF

39. Exact Moment Representation in Polynomial Optimization

Author: Lorenzo Baldi, Bernard Mourrain, AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), European Project: 813211,H2020,POEMA(2019), 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: Moments, Duality, High Energy Physics::Lattice, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], Flat Truncation, Sums of Squares, Commutative Algebra (math.AC), Measures, Mathematics - Commutative Algebra, Polynomial Optimization, 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], Algebraic Geometry (math.AG), Mathematics - Optimization and Control
Abstract: We investigate the problem of representing moment sequences by measures in the context ofPolynomial Optimization Problems. This consists in finding the infimum of a real polynomial ona real semialgebraic set defined by polynomial inequalities. We analyze the exactness of MomentMatrix (MoM) relaxations, dual to the Sum of Squares (SoS) relaxations, which are hierarchiesof convex cones introduced by Lasserre to approximate measures and positive polynomials. Weinvestigate in particular flat truncation properties, which allow testing effectively when MoMexactness holds.We consider the quadratic module Q generated by the inequalities. We show that the dualof the MoM relaxation coincides with the SoS relaxation extended with the real radical ofthe support of Q, and focus on the zero-dimensional case, generalizing results for equationsdefining a finite real variety. We deduce sufficient and necessary conditions for flat truncation,under the finite convergence assumption: flat truncation happens if and only if the support ofthe quadratic module associated with the minimizers is of dimension zero. We also bound theorder of the relaxation at which flat truncation holds.As corollaries, we conclude that flat truncation holds:$\bullet$ when regularity conditions, known as Boundary Hessian Conditions, hold: this resultimplies that flat truncation and MoM exactness holds generically;$\bullet$ when the support of the quadratic module Q is zero-dimensional;$\bullet$ in singular cases, flat truncation holds for the MoM relaxation extended with the polarconstraints when the real variety of polar points is finite.Effective numerical computations illustrate these flat truncation properties.
Published: 2020

40. A certified iterative method for isolated singular roots

Author: Mantzaflaris, Angelos, Mourrain, Bernard, Szanto, Agnes, AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), Dept. of Mathematics, North Carolina State University, European Project: 813211,H2020,POEMA(2019), 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: Computational Mathematics, Algebra and Number Theory, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG]
Abstract: International audience; In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root and we compute its multiplicity structure. More precisely, given a polynomial system f = (f1 ,. .. , fN) ∈ C[x1 ,. .. , xn ]^N , we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of f such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so-called inverse system that describes the multiplicity structure at the root. We use α-theory test to certify the quadratic convergence, and to give bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria.
Published: 2020

41. Computing Free Non-commutative Groebner Bases over Z with Singular:Letterplace

Author: Levandovskyy, Viktor, Metzlaff, Tobias, Zeid, Karim, Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH), AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), 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), Rheinisch-Westfälische Technische Hochschule Aachen (RWTH), and European Project: 813211,H2020,POEMA(2019)
Subjects: Non-commutative algebra, Mathematics::Commutative Algebra, Rings and Algebras (math.RA), [MATH.MATH-RA]Mathematics [math]/Rings and Algebras [math.RA], FOS: Mathematics, Coefficients in rings, Mathematics - Rings and Algebras, Groebner bases, [MATH]Mathematics [math], Algorithms
Abstract: With this paper we present an extension of our recent ISSAC paper about computations of Groebner(-Shirshov) bases over free associative algebras Z. We present all the needed proofs in details, add a part on the direct treatment of the ring Z/mZ as well as new examples and applications to e.g. Iwahori-Hecke algebras.The extension of Groebner bases concept from polynomial algebras over fields to polynomial rings over rings allows to tackle numerous applications, both of theoretical and of practical importance.Groebner and Groebner-Shirshov bases can be defined for various non-commutative and even non-associative algebraic structures. We study the case of associative rings and aim at free algebras over principal ideal rings. We concentrate ourselves on the case of commutative coefficient rings without zero divisors (i.e. a domain). Even working over Z allows one to do computations, which can be treated as universal for fields of arbitrary characteristic. By using the systematic approach, we revisit the theory and present the algorithms in the implementable form. We show drastic differences in the behavior of Groebner bases between free algebras and algebras, close to commutative.Even the process of the formation of critical pairs has to be reengineered, together with the implementing the criteria for their quick discarding.We present an implementation of algorithms in the Singular subsystem called Letterplace, which internally uses Letterplace techniques (and Letterplace Groebner bases), due to La Scala and Levandovskyy. Interesting examples and applications accompany our presentation.
Published: 2020

42. Sparse moment-sum-of-squares relaxations for nonlinear dynamical systems with guaranteed convergence

Author: Schlosser, Corbinian, Korda, Milan, 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), 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), É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, European Project: 813211,H2020,POEMA(2019), Korda, Milan, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID
Subjects: Optimization and Control (math.OC), [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], FOS: Mathematics, [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 90C22, 37M22, Mathematics - Optimization and Control
Abstract: In this paper we prove general sparse decomposition of dynamical systems provided that the vector field and constraint set possess certain structures, which we call subsystems. This notion is based on causal dependence in the dynamics between the different states. This results in sparse descriptions for three problems from nonlinear dynamical systems: region of attraction, maximum positively invariant set and (global) attractor. The decompositions can be paired with any method for computing (outer) approximations of these sets in order to reduce the computation to lower dimensional systems. We illustrate this by the methods from previous works based on infinite-dimensional linear programming, as one example where the curse of dimensionality is present and hence dimension reduction is crucial. For polynomial dynamics, we show that these problems admit a sparse sum-of-squares (SOS) approximation with guaranteed convergence such that the number of variables in the largest SOS multiplier is given by the dimension of the largest subsystem appearing in the decomposition. The dimension of such subsystems depends on the sparse structure of the vector field and the constraint set and can allow for a significant reduction of the size of the semidefinite program (SDP) relaxations. The method is simple to use and based solely on convex optimization. Numerical examples demonstrate the approach.
Published: 2020

43. Reflection groups and cones of sums of squares

Author: Sebastian Debus, Cordian Riener, The Arctic University of Norway (UiT), European Project: 813211,H2020,POEMA(2019), Debus, Sebastian, Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID, The Arctic University of Norway [Tromsø, Norway] (UiT), 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: Computational Mathematics, Mathematics - Algebraic Geometry, Algebra and Number Theory, Rings and Algebras (math.RA), FOS: Mathematics, [MATH] Mathematics [math], Mathematics - Rings and Algebras, [MATH]Mathematics [math], Mathematics - Commutative Algebra, Commutative Algebra (math.AC), Algebraic Geometry (math.AG)
Abstract: We consider cones of real forms which are sums of squares forms and invariant by a (finite) reflection group. We show how the representation theory of these groups allows to use the symmetry inherent in these cones to give more efficient descriptions. We focus especially on the $A_{n}$, $B_n$, and $D_n$ case where we use so called higher Specht polynomials to give a uniform description of these cones. These descriptions allow us, for example, to study the connection of these cones to non-negative forms. In particular, we give a new proof of a result by Harris who showed that every non-negative ternary even symmetric octic form is a sum of squares.
Published: 2020

44. Semialgebraic Optimization for Lipschitz Constants of ReLU Networks

Author: Chen, Tong, Lasserre, Jean-Bernard, Magron, Victor, Pauwels, Edouard, É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), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), 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), 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,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), 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), 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), Pauwels, Edouard, 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, Centre International de Mathématiques et d'Informatique (de Toulouse) - - CIMI2011 - ANR-11-LABX-0040 - LABX - VALID, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: The Lipschitz constant of a network plays an important role in many applications of deep learning, such as robustness certification and Wasserstein Generative Adversarial Network. We introduce a semidefinite programming hierarchy to estimate the global and local Lipschitz constant of a multiple layer deep neural network. The novelty is to combine a polynomial lifting for ReLU functions derivatives with a weak generalization of Putinar's positivity certificate. This idea could also apply to other, nearly sparse, polynomial optimization problems in machine learning. We empirically demonstrate that our method provides a trade-off with respect to state of the art linear programming approach, and in some cases we obtain better bounds in less time., NeurIPS 2020
Published: 2020

45. Computing critical points for invariant algebraic systems

Author: Faugère, Jean-Charles, Labahn, George, Safey El Din, Mohab, Schost, Éric, Vu, Thi Xuan, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Symbolic Computation Group (SCG), University of Waterloo [Waterloo]-David R. Cheriton School of Computer Science, ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), European Project: 813211,H2020,POEMA(2019), 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: FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Symbolic Computation, Computational Mathematics, Algebra and Number Theory, Symbolic Computation (cs.SC)
Abstract: Let $\mathbf{K}$ be a field and $\phi$, $\mathbf{f} = (f_1, \ldots, f_s)$ in $\mathbf{K}[x_1, \dots, x_n]$ be multivariate polynomials (with $s < n$) invariant under the action of $\mathcal{S}_n$, the group of permutations of $\{1, \dots, n\}$. We consider the problem of computing the points at which $\mathbf{f}$ vanish and the Jacobian matrix associated to $\mathbf{f}, \phi$ is rank deficient provided that this set is finite. We exploit the invariance properties of the input to split the solution space according to the orbits of $\mathcal{S}_n$. This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in $d^s$, ${{n+d}\choose{d}}$ and $\binom{n}{s+1}$ where $d$ is the maximum degree of the input polynomials. When $d,s$ are fixed, this is polynomial in $n$ while when $s$ is fixed and $d \simeq n$ this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.
Published: 2020
Full Text: View/download PDF

46. Computing controlled invariant sets from data using convex optimization

Author: Milan Korda, É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), 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, and European Project: 813211,H2020,POEMA(2019)
Subjects: 0209 industrial biotechnology, Control and Optimization, Linear programming, Computer science, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], 02 engineering and technology, Maximum controlled invariant set, 01 natural sciences, [SPI.AUTO]Engineering Sciences [physics]/Automatic, 020901 industrial engineering & automation, FOS: Mathematics, Applied mathematics, Infinite-dimensional linear programming, 0101 mathematics, Invariant (mathematics), Sampling, Mathematics - Optimization and Control, Invariant set, Data, Continuous function, Applied Mathematics, 010102 general mathematics, Probabilistic logic, Lipschitz continuity, Convex optimization, Rate of convergence, Optimization and Control (math.OC), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Subspace topology
Abstract: International audience; This work presents a data-driven method for approximation of the maximum positively invariant (MPI) set and the maximum controlled invariant (MCI) set for nonlinear dynamical systems. The method only requires the knowledge of a finite collection of one-step transitions of the discrete-time dynamics, without the requirement of segments of trajectories or the control inputs that effected the transitions to be available. The approach uses a novel characterization of the MPI and MCI sets as the solution to an infinite-dimensional linear programming (LP) problem in the space of continuous functions, with the optimum being attained by a (Lipschitz) continuous function under mild assumptions. The infinite-dimensional LP is then approximated by restricting the decision variable to a finite-dimensional subspace and by imposing the non-negativity constraint of this LP only on the available data samples. This leads to a single finite-dimensional LP that can be easily solved using off-the-shelf solvers. We analyze the convergence rate and sample complexity, proving probabilistic as well as hard guarantees on the volume error of the approximations. The approach is very general, requiring minimal underlying assumptions. In particular, the dynamics is not required to be polynomial or even continuous (forgoing some of the theoretical results). Detailed numerical examples up to state-space dimension ten with code available online demonstrate the method.
Published: 2020
Full Text: View/download PDF

47. Robots, computer algebra and eight connected components

Author: Mohab Safey El Din, Josef Schicho, Jose Capco, Johannes Kepler Universität Linz - Johannes Kepler University Linz [Autriche] (JKU), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Research Institute for Symbolic Computation (RISC), Johannes Kepler Universität Linz (JKU), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(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), Johannes Kepler University Linz [Linz] (JKU), and European Project: 813211,H2020,POEMA(2019)
Subjects: Connected component, FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Symbolic Computation, Polynomial, business.industry, Robotics, 010103 numerical & computational mathematics, 02 engineering and technology, Kinematics, Symbolic Computation (cs.SC), Symbolic computation, 01 natural sciences, Algebra, Computer Science::Robotics, Path (graph theory), 0202 electrical engineering, electronic engineering, information engineering, Robot, 020201 artificial intelligence & image processing, Artificial intelligence, 0101 mathematics, Invariant (mathematics), business, Mathematics
Abstract: International audience; Answering connectivity queries in semi-algebraic sets is a long-standing and challenging computational issue with applications in robotics, in particular for the analysis of kinematic singularities. One task there is to compute the number of connected components of the complementary of the singularities of the kinematic map. Another task is to design a continuous path joining two given points lying in the same connected component of such a set. In this paper, we push forward the current capabilities of computer algebra to obtain computer-aided proofs of the analysis of the kinematic singularities of various robots used in industry. We first show how to combine mathematical reasoning with easy symbolic computations to study the kinematic singularities of an infinite family (depending on paramaters) modelled by the UR-series produced by the company ``Universal Robots''. Next, we compute roadmaps (which are curves used to answer connectivity queries) for this family of robots. We design an algorithm for ``solving'' positive dimensional polynomial system depending on parameters. The meaning of solving here means partitioning the parameter's space into semi-algebraic components over which the number of connected components of the semi-algebraic set defined by the input system is invariant. Practical experiments confirm our computer-aided proof and show that such an algorithm can already be used to analyze the kinematic singularities of the UR-series family. The number of connected components of the complementary of the kinematic singularities of generic robots in this family is $8$.
Published: 2020
Full Text: View/download PDF

48. 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

49. Computing the real isolated points of an algebraic hypersurface

Author: Timo de Wolff, Mohab Safey El Din, Huu Phuoc Le, Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Institut for Analysis and Algebra (IAA), Technische Universität Braunschweig = Technical University of Braunschweig [Braunschweig], ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(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), and European Project: 813211,H2020,POEMA(2019)
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Computer Science - Symbolic Computation, Computation, Rigidity (psychology), 010103 numerical & computational mathematics, 02 engineering and technology, Symbolic Computation (cs.SC), [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Semi-algebraic sets, Auxetics, Real algebraic geometry, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], 0101 mathematics, Algebraic number, Mathematics, Real number, Algebraic set, Discrete mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Critical point method, Randomized algorithm, Hypersurface, Rigidity, Computer Science - Computational Geometry, 020201 artificial intelligence & image processing
Abstract: Let $\mathbb{R}$ be the field of real numbers. We consider the problem of computing the real isolated points of a real algebraic set in $\mathbb{R}^n$ given as the vanishing set of a polynomial system. This problem plays an important role for studying rigidity properties of mechanism in material designs. In this paper, we design an algorithm which solves this problem. It is based on the computations of critical points as well as roadmaps for answering connectivity queries in real algebraic sets. This leads to a probabilistic algorithm of complexity $(nd)^{O(n\log(n))}$ for computing the real isolated points of real algebraic hypersurfaces of degree $d$. It allows us to solve in practice instances which are out of reach of the state-of-the-art., Conference paper ISSAC 2020
Published: 2020
Full Text: View/download PDF

50. Punctual Hilbert Schemes and Certified Approximate Singularities

Author: Agnes Szanto, Bernard Mourrain, Angelos Mantzaflaris, AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), Department of mathematics [North Carolina], North Carolina State University [Raleigh] (NC State), University of North Carolina System (UNC)-University of North Carolina System (UNC), European Project: 813211,H2020,POEMA(2019), 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: certification, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], inverse system, 010103 numerical & computational mathematics, Commutative Algebra (math.AC), 01 natural sciences, multiplication matrix, Mathematics - Algebraic Geometry, symbols.namesake, Singularity, Approximation error, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Applied mathematics, 0101 mathematics, Newton's method, Algebraic Geometry (math.AG), Mathematics, Inverse system, 010102 general mathematics, multiplicity structure, Multiplicity (mathematics), Mathematics - Commutative Algebra, singularity, Rate of convergence, Hilbert scheme, symbols, Gravitational singularity, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root with a prescribed multiplicity structure. More precisely, given a polynomial system f $=(f\_1, \ldots, f\_N)\in C[x\_1, \ldots, x\_n]^N$, we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of $f$ such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so called inverse system that describes the multiplicity structure at the root. We use $$\alpha$$-theory test to certify the quadratic convergence, and togive bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria., Comment: International Symposium on Symbolic and Algebraic Computation, Jul 2020, Kalamata, France
Published: 2020
Full Text: View/download PDF

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

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

71 results on '"European Project: 813211,H2020,POEMA(2019)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources