Search

Your search keyword '"Equipe Polynomial OPtimization (LAAS-POP)"' showing total 43 results
Start Over Author "Equipe Polynomial OPtimization (LAAS-POP)" Language english
43 results on '"Equipe Polynomial OPtimization (LAAS-POP)"'

1. A Generalized Pell's equation for a class of multivariate orthogonal polynomials

Author

Lasserre, Jean-Bernard, Xu, Yuan, 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), Department of Mathematics, University of Oregon [Eugene], University of Oregon [Eugene], and ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)

Subjects
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Optimization and Control (math.OC), MSC: 44A60 14Q30 42C05 90C25 90C46 32U15 14P10, Probability (math.PR), FOS: Mathematics, 44A60 14Q30 42C05 90C25 90C46 32U15 14P10, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Mathematics - Probability
Abstract

We extend the polynomial Pell's equation satisfied by univariate Chebyshev polynomials on [--1, 1] from one variable to several variables, using orthogonal polynomials on regular domains that include cubes, balls, and simplexes of arbitrary dimension. Moreover, we show that such an equation is strongly connected (i) to a certificate of positivity (from real algebraic geometry) on the domain, as well as (ii) to the Christoffel functions of the equilibrium measure on the domain. In addition, the solution to Pell's equation reflects an extremal property of orthonormal polynomials associated with an entropy-like criterion.

Published
2023

2. Sums of squares certificates for polynomial moment inequalities

Author

Klep, Igor, Magron, Victor, Volčič, Jurij, Department of Mathematics (University of Ljubljana), University of Ljubljana, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Drexel University, This work was supported by the Slovenian Research Agency grants J1-2453, N1-0217, J1-3004 and P1-0222, the NSF grant DMS-1954709, the FastQI grant funded by the Institut Quantique Occitan, the PHC Proteus grant 46195TA as well as by the NationalResearch Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence andTechnological Enterprise (CREATE) programme., 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), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
Mathematics - Functional Analysis, Quantum Physics, [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], Optimization and Control (math.OC), 13J30, 44A60, 60E15, 90C22, 46G12, 47L60, 81-08, FOS: Mathematics, FOS: Physical sciences, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], Quantum Physics (quant-ph), Mathematics - Optimization and Control, Functional Analysis (math.FA)
Abstract

This paper introduces and develops the algebraic framework of moment polynomials, which are polynomial expressions in commuting variables and their formal mixed moments. Their positivity and optimization over probability measures supported on semialgebraic sets and subject to moment polynomial constraints is investigated. A positive solution to Hilbert's 17th problem for pseudo-moments is given. On the other hand, moment polynomials positive on actual measures are shown to be sums of squares and formal moments of squares up to arbitrarily small perturbation of their coefficients. When only measures supported on a bounded semialgebraic set are considered, a stronger algebraic certificate for moment polynomial positivity is derived. This result gives rise to a converging hierarchy of semidefinite programs for moment polynomial optimization. Finally, as an application, two nonlinear Bell inequalities from quantum physics are settled., 26 pages

Published
2023

3. Correlations constrained by composite measurements

Author

Selby, John H., Sainz, Ana Belén, Magron, Victor, Czekaj, Łukasz, Horodecki, Michał, University of Gdańsk (UG), Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Foundation for Polish Science (IRAP project, ICTQT, contract no.2018/MAB/5, co-financed by EU within Smart Growth Operational Programme), FastQI grant funded by the Institut Quantique Occitan, the PHC Proteus grant 46195TA, the National ResearchFoundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme, 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), 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
Quantum Physics, [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], FOS: Physical sciences, Quantum Physics (quant-ph)
Abstract

How to understand the set of correlations admissible in nature is one outstanding open problem in the core of the foundations of quantum theory. Here we take a complementary viewpoint to the device-independent approach, and explore the correlations that physical theories may feature when restricted by some particular constraints on their measurements. We show that demanding that a theory exhibits {a composite} measurement imposes a hierarchy of constraints on the structure of its sets of states and effects, which translate to a hierarchy of constraints on the allowed correlations themselves. We moreover focus on the particular case where one demands the existence of a correlated measurement that reads out the parity of local fiducial measurements. By formulating a non-linear Optimisation Problem, and semidefinite relaxations of it, we explore the consequences of the existence of such a parity reading measurement for violations of Bell inequalities. In particular, we show that in certain situations this assumption has surprisingly strong consequences, namely, that Tsirelson's bound can be recovered., Comment: 43 pages. V3 -- new numerical results

Published
2023

4. Infinite-dimensional moment-SOS hierarchy for nonlinear partial differential equations

Author

Henrion, Didier, Infusino, Maria, Kuhlmann, Salma, Vinnikov, Victor, Department of Control Engineering, Faculty of Electrical Engineering [Prague], Czech Technical University in Prague (CTU), Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Università degli Studi di Cagliari = University of Cagliari (UniCa), Universität Konstanz, and Ben-Gurion University of the Negev (BGU)

Subjects
Mathematics - Functional Analysis, Primary 90C25, Secondary 90C22, 13J30, 44A60, 46N10, 47A57, Mathematics - Analysis of PDEs, Optimization and Control (math.OC), FOS: Mathematics, [INFO]Computer Science [cs], [MATH]Mathematics [math], Mathematics - Optimization and Control, Analysis of PDEs (math.AP), Functional Analysis (math.FA)
Abstract

We formulate a class of nonlinear {evolution} partial differential equations (PDEs) as linear optimization problems on moments of positive measures supported on infinite-dimensional vector spaces. Using sums of squares (SOS) representations of polynomials in these spaces, we can prove convergence of a hierarchy of finite-dimensional semidefinite relaxations solving approximately these infinite-dimensional optimization problems. As an illustration, we report on numerical experiments for solving the heat equation subject to a nonlinear perturbation., Comment: 24 pages, 1 table, 3 figures

Published
2023

5. Controlling Microgrids Without External Data: A Benchmark of Stochastic Programming Methods

Author

Puech, Alban, Rigaut, Tristan, Franc, Adrien Le, Templier, William, Alais, Jean-Christophe, Tournoud, Maud, Bossard, Victor, Yousef, Alejandro, Stolyarova, Elena, Schneider Electric ( SE), 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), and Université de Toulouse (UT)

Subjects
microgrid, stochastic programming, Optimization and Control (math.OC), model predictive control, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], stochastic optimization, Mathematics - Optimization and Control
Abstract

Microgrids are local energy systems that integrate energy production, demand, and storage units. They are generally connected to the regional grid to import electricity when local production and storage do not meet the demand. In this context, Energy Management Systems (EMS) are used to ensure the balance between supply and demand, while minimizing the electricity bill, or an environmental criterion. The main implementation challenges for an EMS come from the uncertainties in the consumption, the local renewable energy production, and in the price and the carbon intensity of electricity. Model Predictive Control (MPC) is widely used to implement EMS but is particularly sensitive to the forecast quality, and often requires a subscription to expensive third-party forecast services. We introduce four Multistage Stochastic Control Algorithms relying only on historical data obtained from on-site measurements. We formulate them under the shared framework of Multistage Stochastic Programming and benchmark them against two baselines in 61 different microgrid setups using the EMSx dataset. Our most effective algorithm produces notable cost reductions compared to an MPC that utilizes the same uncertainty model to generate predictions, and it demonstrates similar performance levels to an ideal MPC that relies on perfect forecasts.

Published
2023

6. Sparse Polynomial Optimization: Theory and Practice

Author

Magron, Victor, Wang, Jie, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Academy of Mathematics and Systems Science [Beijing], This work was supported by the FMJH Program PGMO (EPICS project), as well as the PEPS2 Program (FastOPF project) funded by AMIES and RTE.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., World Scientific Press, ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Magron, Victor, TREMPLIN-ERC - Optimisation garantie pour la vérification des systèmes cyber-physiques - - COPS2018 - ANR-18-ERC2-0004 - TERC - VALID, Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Mathematics - Algebraic Geometry, Optimization and Control (math.OC), Mathematics - Operator Algebras, FOS: Mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Operator Algebras (math.OA), Mathematics - Optimization and Control, Algebraic Geometry (math.AG), Machine Learning (cs.LG)
Abstract

The problem of minimizing a polynomial over a set of polynomial inequalities is an NP-hard non-convex problem. Thanks to powerful results from real algebraic geometry, one can convert this problem into a nested sequence of finite-dimensional convex problems. At each step of the associated hierarchy, one needs to solve a fixed size semidefinite program, which can be in turn solved with efficient numerical tools. On the practical side however, there is no-free lunch and such optimization methods usually encompass severe scalability issues. Fortunately, for many applications, we can look at the problem in the eyes and exploit the inherent data structure arising from the cost and constraints describing the problem, for instance sparsity or symmetries. This book presents several research efforts to tackle this scientific challenge with important computational implications, and provides the development of alternative optimization schemes that scale well in terms of computational complexity, at least in some identified class of problems. The presented algorithmic framework in this book mainly exploits the sparsity structure of the input data to solve large-scale polynomial optimization problems. We present sparsity-exploiting hierarchies of relaxations, for either unconstrained or constrained problems. By contrast with the dense hierarchies, they provide faster approximation of the solution in practice but also come with the same theoretical convergence guarantees. Our framework is not restricted to static polynomial optimization, and we expose hierarchies of approximations for values of interest arising from the analysis of dynamical systems. We also present various extensions to problems involving noncommuting variables, e.g., matrices of arbitrary size or quantum physic operators., Comment: 220 pages, to appear in Series on Optimization and Its Applications, World Scientific Press

Published
2023

7. Convergence rates for sums-of-squares hierarchies with correlative sparsity

Author

Korda, Milan, Magron, Victor, Rios-Zertuche, Rodolfo, 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), Czech Technical University in Prague (CTU), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), This research was funded by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), 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), G.1.6, FOS: Mathematics, Numerical Analysis (math.NA), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Numerical Analysis, 90C23 (Primary) 13P25, 65K10 (Secondary), Mathematics - Optimization and Control
Abstract

This work derives upper bounds on the convergence rate of the moment-sum-of-squares hierarchy with correlative sparsity for global minimization of polynomials on compact basic semialgebraic sets. The main conclusion is that both sparse hierarchies based on the Schm\"udgen and Putinar Positivstellens\"atze enjoy a polynomial rate of convergence that depends on the size of the largest clique in the sparsity graph but not on the ambient dimension. Interestingly, the sparse bounds outperform the best currently available bounds for the dense hierarchy when the maximum clique size is sufficiently small compared to the ambient dimension and the performance is measured by the running time of an interior point method required to obtain a bound on the global minimum of a given accuracy., Comment: 23 pages

Published
2023

8. Peak Estimation of Time Delay Systems using Occupation Measures

Author

Miller, Jared, Korda, Milan, Magron, Victor, Sznaier, Mario, Northeastern University [Boston], Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), This work was supported by the FastQI grant funded by the Institut Quantique Occitan, the PHC Proteus grant 46195TA, as well as by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
Optimization and Control (math.OC), FOS: Mathematics, FOS: Electrical engineering, electronic engineering, information engineering, Systems and Control (eess.SY), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Electrical Engineering and Systems Science - Systems and Control
Abstract

This work proposes a method to compute the maximum value obtained by a state function along trajectories of a Delay Differential Equation (DDE). An example of this task is finding the maximum number of infected people in an epidemic model with a nonzero incubation period. The variables of this peak estimation problem include the stopping time and the original history (restricted to a class of admissible histories). The original nonconvex DDE peak estimation problem is approximated by an infinite-dimensional Linear Program (LP) in occupation measures, inspired by existing measure-based methods in peak estimation and optimal control. This LP is approximated from above by a sequence of Semidefinite Programs (SDPs) through the moment-Sum of Squares (SOS) hierarchy. Effectiveness of this scheme in providing peak estimates for DDEs is demonstrated with provided examples, Comment: 34 pages, 14 figures, 3 tables

Published
2023

9. Sums of squares representations on singular loci

Author

Ngoc Hoang Anh Mai, Victor Magron, University of Konstanz, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), This work was supported by the FastQI grant funded by the Institut Quantique Occitan, the PHC Proteus grant 46195TA, the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
Mathematics - Algebraic Geometry, Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Algebraic Geometry (math.AG)
Abstract

The problem of characterizing a real polynomial $f$ as a sum of squares of polynomials on a real algebraic variety $V$ dates back to the pioneering work of Hilbert in [Mathematische Annalen 32.3 (1888): 342-350]. In this paper, we investigate this problem with a focus on cases where the real zeros of $f$ on $V$ are singular points of $V$. By using optimality conditions and irreducible decomposition, we provide a positive answer to the following essential question of polynomial optimization: Are there always exact semidefinite programs to compute the minimum value attained by a given polynomial over a given real algebraic variety? Our answer implies that Lasserre's hierarchy, which is known as a bridge between convex and non-convex programs with algebraic structures, has finite convergence not only in the generic case but also in the general case. As a result, we constructively prove that each hyperbolic program is equivalent to a semidefinite program., Comment: 27 pages. arXiv admin note: substantial text overlap with arXiv:2211.12440

Published
2023

10. Occupation measure relaxations in variational problems: the role of convexity

Author

Henrion, Didier, Korda, Milan, Kružík, Martin, Rios-Zertuche, Rodolfo, Department of Control Engineering, Faculty of Electrical Engineering [Prague], Czech Technical University in Prague (CTU), 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), Institute of Information Theory and Automation of the Czech Academy of Sciences (UTIA / CAS), Czech Academy of Sciences [Prague] (CAS), and Faculty of Civil Engineering, Czech Technical University in Prague (FCE CTU)

Subjects
Optimization and Control (math.OC), FOS: Mathematics, [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract

This work addresses the occupation measure relaxation of calculus of variations problems, which is an infinite-dimensional linear programming relaxation amenable to numerical approximation by a hierarchy of semidefinite optimization problems. We address the problem of equivalence of this relaxation to the original problem. Our main result provides sufficient conditions for this equivalence. These conditions, revolving around the convexity of the data, are simple and apply in very general settings that may be of arbitrary dimensions and may include pointwise and integral constraints, thereby considerably strengthening the existing results. Our conditions are also extended to optimal control problems. In addition, we demonstrate how these results can be applied in non-convex settings, showing that the occupation measure relaxation is at least as strong as the convexification using the convex envelope; in doing so, we prove that a certain weakening of the occupation measure relaxation is equivalent to the convex envelope. This opens the way to application of the occupation measure relaxation in situations where the convex envelope relaxation is known to be equivalent to the original problem, which includes problems in magnetism and elasticity.

Published
2023

11. Polynomial argmin for recovery and approximation of multivariate discontinuous functions

Author

Henrion, Didier, Korda, Milan, Lasserre, Jean-Bernard, Department of Control Engineering, Faculty of Electrical Engineering [Prague], Czech Technical University in Prague (CTU), 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), Programme DesCartes supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), and ANR-19-PI3A-0004,Future - PI3A

Subjects
Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Numerical Analysis (math.NA), Mathematics - Numerical Analysis, Mathematics - Optimization and Control, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

We propose to approximate a (possibly discontinuous) multivariate function f (x) on a compact set by the partial minimizer arg miny p(x, y) of an appropriate polynomial p whose construction can be cast in a univariate sum of squares (SOS) framework, resulting in a highly structured convex semidefinite program. In a number of non-trivial cases (e.g. when f is a piecewise polynomial) we prove that the approximation is exact with a low-degree polynomial p. Our approach has three distinguishing features: (i) It is mesh-free and does not require the knowledge of the discontinuity locations. (ii) It is model-free in the sense that we only assume that the function to be approximated is available through samples (point evaluations). (iii) The size of the semidefinite program is independent of the ambient dimension and depends linearly on the number of samples. We also analyze the sample complexity of the approach, proving a generalization error bound in a probabilistic setting. This allows for a comparison with machine learning approaches.

Published
2023

12. Algebraic certificates for the truncated moment problem

Author

Henrion, Didier, Naldi, Simone, Safey El Din, Mohab, Department of Control Engineering, Faculty of Electrical Engineering [Prague], Czech Technical University in Prague (CTU), 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), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), EOARD-AFOSR grant agreement {FA8665-20-1-7029}., 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-21-CE48-0006,HYPERSPACE,Polynômes Hyperboliques : Algorithmes, Complexité, Implantations(2021), 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), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
sums of squares, Mathematics - Algebraic Geometry, semialgebraic sets, Optimization and Control (math.OC), FOS: Mathematics, moments, real algebraic geometry, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], algorithms, complexity, Algebraic Geometry (math.AG), Mathematics - Optimization and Control
Abstract

The truncated moment problem consists of determining whether a given finitedimensional vector of real numbers y is obtained by integrating a basis of the vector space of polynomials of bounded degree with respect to a non-negative measure on a given set K of a finite-dimensional Euclidean space. This problem has plenty of applications e.g. in optimization, control theory and statistics. When K is a compact semialgebraic set, the duality between the cone of moments of non-negative measures on K and the cone of non-negative polynomials on K yields an alternative: either y is a moment vector, or y is not a moment vector, in which case there exists a polynomial strictly positive on K making a linear functional depending on y vanish. Such a polynomial is an algebraic certificate of moment unrepresentability. We study the complexity of computing such a certificate using computer algebra algorithms.

Published
2023

13. Pourchet's theorem in action: decomposing univariate nonnegative polynomials as sums of five squares

Author

Magron, Victor, Koprowski, Przemysław, Vaccon, Tristan, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), University of Silesia in Katowice, XLIM UMR-CNRS 7252, Université de Limoges, Institut Quantique Occitan. PHC Proteus grant 46195TA. National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
FOS: Computer and information sciences, Computer Science - Symbolic Computation, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Symbolic Computation (cs.SC)
Abstract

Pourchet proved in 1971 that every nonnegative univariate polynomial with rational coefficients is a sum of five or fewer squares. Nonetheless, there are no known algorithms for constructing such a decomposition. The sole purpose of the present paper is to present a set of algorithms that decompose a given nonnegative polynomial into a sum of six (five under some unproven conjecture or when allowing weights) squares of polynomials. Moreover, we prove that the binary complexity can be expressed polynomially in terms of classical operations of computer algebra and algorithmic number theory., 10 pages, 9 algorithms, submitted at the ISSAC 2023 conference

Published
2023

14. A modified Christoffel function and its asymptotic properties

Author

Lasserre, Jean-Bernard, 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), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), and ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020)

Subjects
Optimization and Control (math.OC), [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Christoffel function, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract

We introduce a certain variant (or regularization) $\tilde{\Lambda}^\mu_n$ of the standard Christoffel function $\Lambda^\mu_n$ associated with a measure $\mu$ on a compact set $\Omega\subset \mathbb{R}^d$. Its reciprocal is now a sum-of-squares polynomial in the variables $(x,\varepsilon)$, $\varepsilon>0$. It shares the same dichotomy property of the standard Christoffel function, that is, the growth with $n$ of its inverse is at most polynomial inside and exponential outside the support of the measure. Its distinguishing and crucial feature states that for fixed $\varepsilon>0$, and under weak assumptions, $\lim_{n\to\infty} \varepsilon^{-d}\tilde{\Lambda}^\mu_n(\xi,\varepsilon)=f(\zeta_\varepsilon)$ where $f$ (assumed to be continuous) is the unknown density of $\mu$ w.r.t. Lebesgue measure on $\Omega$, and $\zeta_\varepsilon\in\mathbf{B}_\infty(\xi,\varepsilon)$ (and so $f(\zeta_\varepsilon)\approx f(\xi)$ when $\varepsilon>0$ is small). This is in contrast with the standard Christoffel function where if $\lim_{n\to\infty} n^d\Lambda^\mu_n(\xi)$ exists, it is of the form $f(\xi)/\omega_E(\xi)$ where $\omega_E$ is the density of the equilibrium measure of $\Omega$, usually unknown. At last but not least, the additional computational burden (when compared to computing $\Lambda^\mu_n$) is just integrating symbolically the monomial basis $(x^{\alpha})_{\alpha\in\mathbb{N}^d_n}$ on the box $\{x: \Vert x-\xi\Vert_\infty, Comment: Rapport LAAS n 23003

Published
2023

15. Polynomial Optimization, Certificates of Positivity, and Christoffel Function

Author

Lasserre, Jean-Bernard, 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), This research is also 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, Michal Kočvara, Bernard Mourrain, Cordian Riener, 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), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG]
Abstract

International audience; We briefly recall basics of the Moment-SOS hierarchy in polynomial optimization and the Christoffel-Darboux kernel (and the Christoffel function (CF)) in theory of approximation and orthogonal polynomials. We then (i) show a strong link between the CF and the SOS-based positive certificate at the core of the Moment-SOS hierarchy, and (ii) describe how the CD-kernel provides a simple interpretation of the SOS-hierarchy of lower bounds as searching for some signed polynomial density (while the SOS-hierarchy of upper bounds is searching for a positive (SOS) density). This link between the CF and positive certificates, in turn allows us (i) to establish a disintegration property of the CF much like for measures, and (ii) for certain sets, to relate the CF of their equilibrium measure with a certificate of positivity on the set, for constant polynomials.

Published
2023

16. 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 Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (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

17. A DISINTEGRATION OF THE CHRISTOFFEL FUNCTION

Author

Lasserre, Jean-Bernard, 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)-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), 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, ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), 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), and Université de Toulouse (UT)

Subjects
Optimization and Control (math.OC), General Mathematics, Christoffel function, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], disintegration of measures, Mathematics - Optimization and Control, sum of squares polynomials
Abstract

to appear in CR. Acad. Sci. Paris; We show that the Christoffel function (CF) factorizes (or can be disintegrated) as the product of two Christoffel functions, one associated with the marginal and the another related to the conditional distribution, in the spirit of "the CF of the disintegration is the disintegration of the CFs". In the proof one uses an apparently overlooked property (but interesting in its own) which states that any sum-of-squares polynomial is the Christoffel function of some linear form (with a representing measure in the univariate case). The same is true for the convex cone of polynomials that are positive on a basic semi-algebraic set. This interpretation of the CF establishes another bridge between polynomials optimization and orthogonal polynomials.

Published
2022
Full Text
View/download PDF

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

Author

Mai, Ngoc Hoang Anh, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Paul Sabatier - Toulouse III, Victor Magron, Jean-Bernard Lasserre, Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, UT3 : Université Toulouse 3 Paul Sabatier, Victor MAGRON, and Jean-Bernard LASSERRE (co-encadrant)

Subjects
Putinar-Vasilescu's Positivstellensatz, Hiérarchies moment/sommes-de-carrés, Taux de convergence, Polynomial optimization, Positivstellensatz de Polya, Putinar's Positivstellensatz, Programmation semidéfinie, constant trace property, Propriété de la trace constante, Positivstellensatz de Putinar, Polya's Positivstellensatz, Hiérarchie Moment-SOS, Reznick's Positivstellensatz, correlative and term sparsity, convergence rate, Positivstellensatz de Reznick, Programmation semi-définie, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, Positivstellensatz de Putinar-Vasilescu, Optimisation polynomiale, Sparsité corrélative et termique, Semidefinite programming, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Moment-SOS hierarchy, Moment/sums-of-squares hierarchy
Abstract

National audience; Positivity certificates or Positivstellens"atze provide representations of polynomials positive on basic semialgebraic sets, i.e., sets defined by finitely many polynomial inequalities. The famous Putinar's Positivstellensatz states that every positive polynomial on a basic closed semialgebraic set dollarSdollar can be written as a linear weighted combination of the polynomials describing dollarSdollar, under a certain condition on dollarSdollar slightly stronger than compactness. When written in this it becomes obvious that the polynomial is positive on dollarSdollar, and therefore this alternative description provides a certificate of positivity on dollarSdollar. Moreover, as the polynomial weights involved in Putinar's Positivstellensatz are sums of squares (SOS), such Positivity certificates enable to design convex relaxations based on semidefinite programming to solve polynomial optimization problems (POPs) that arise in various real-life applications, e.g., in management of energy networks and machine learning to cite a few. Originally developed by Lasserre, the hierarchy of semidefinite relaxations based on Putinar's Positivstellensatz is called the emph{Moment-SOS hierarchy}. In this thesis, we provide polynomial optimization methods based on positivity certificates involving specific SOS weights, without or with denominators.; Les certificats de positivité ou Positivstellens"atze fournissent des représentations de polynômes positifs sur des ensembles semialgébriques de basiques, c'est-à-dire des ensembles définis par un nombre fini d'inégalités polynomiales. Le célèbre Positivstellensatz de Putinar stipule que tout polynôme positif sur un ensemble semialgébrique basique fermé dollarSdollar peut être écrit comme une combinaison pondérée linéaire des polynômes décrivant dollarSdollar, sous une certaine condition sur dollarSdollar légèrement plus forte que la compacité. Lorsqu'il est écrit comme ceci, il devient évident que le polynôme est positif sur dollarSdollar, et donc cette description alternative fournit un certificat de positivité sur dollarSdollar. De plus, comme les poids polynomiaux impliqués dans le Positivstellensatz de Putinar sont des sommes de carrés (SOS), de tels certificats de positivité permettent de concevoir des relaxations convexes basées sur la programmation semidéfinie pour résoudre des problèmes d'optimisation polynomiale (POP) qui surviennent dans diverses applications réelles, par exemple dans la gestion des réseaux d'énergie et l'apprentissage automatique pour n'en citer que quelques unes. Développée à l'origine par Lasserre, la hiérarchie des relaxations semidéfinies basée sur le Positivstellensatz de Putinar est appelée la emph{hiérarchie Moment-SOS}. Dans cette thèse, nous proposons des méthodes d'optimisation polynomiale basées sur des certificats de positivité impliquant des poids SOS spécifiques, sans ou avec dénominateurs.

Published
2022

19. Optimization of Polynomials with Sparsity Encoded in a Few Linear Forms

Author

Lasserre, Jean-Bernard, 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), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), and ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020)

Subjects
Optimization and Control (math.OC), polynomials, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, sparsity, FOS: Mathematics, MathematicsofComputing_NUMERICALANALYSIS, linear forms, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, active set method
Abstract

International audience; We consider polynomials of a few linear forms and show how exploit this type of sparsity for optimization on some particular domains like the Euclidean sphere or a polytope. Moreover, a simple procedure allows to detect this form of sparsity and also allows to provide an approximation of any polynomial by such sparse polynomials.

Published
2022

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

Author

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

Subjects
Machine Learning, Data Analysis, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Christoffel-Darboux Kernel, Polynomial Optimization
Abstract

National audience

Published
2022

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

Author

Yoshio Ebihara, Hayato Motooka, Hayato Waki, Noboru Sebe, Victor Magron, Dimitri Peaucelle, Sophie Tarbouriech, Kyushu University, Kyushu Institute of Technology (Kyutech), Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
nonnegative signal, positive filter, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, copositive programming, L2+ induced norm
Abstract

International audience; This paper is concerned with the analysis of the L2 induced norm of continuous-time LTI systems where the input signals are restricted to be nonnegative. This induced norm is referred to as the L2+ induced norm in this paper. It has been shown very recently that the L2+ induced norm is particularly useful for the stability analysis of nonlinear feedback systems constructed from linear systems and static nonlinearities where the nonlinear elements only provide nonnegative signals. For the upper bound computation of the L2+ induced norm, an approach with copositive programming has also been proposed. It is nonetheless true that this approach becomes effective only for multi-input systems, and for single-input systems this approach does not bring any improvement over the trivial upper bound, the standard L2 norm. To overcome this difficulty, we newly introduce positive filters to increase the number of positive signals. This enables us to enlarge the size of the copositive multipliers so that we can obtain better (smaller) upper bounds with copositive programming.

Published
2022
Full Text
View/download PDF

22. Signed tropical halfspaces and convexity

Author

Loho, Georg, Skomra, Mateusz, Faculty of Electrical Engineering, Mathematics and Computer Science [Twente] (EEMCS), University of Twente, 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), and Université de Toulouse (UT)

Subjects
Optimization and Control (math.OC), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract

We extend the fundamentals for tropical convexity beyond the tropically positive orthant expanding the theory developed by Loho and V\'egh (ITCS 2020). We study two notions of convexity for signed tropical numbers called 'TO-convexity' (formerly 'signed tropical convexity') and the novel notion 'TC-convexity'. We derive several separation results for TO-convexity and TC-convexity. A key ingredient is a thorough understanding of TC-hemispaces - those TC-convex sets whose complement is also TC-convex. Furthermore, we use new insights in the interplay between convexity over Puiseux series and its signed valuation. Remarkably, TC-convexity can be seen as a natural convexity notion for representing oriented matroids as it is arises from a generalization of the composition operation of vectors in an oriented matroid., Comment: 48 pages, 8 figures

Published
2022

23. On the complexity of Putinar-Vasilescu's Positivstellensatz

Author

Mai, Ngoc Hoang Anh, Magron, Victor, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), 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), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
Statistics and Probability, Mathematics - Algebraic Geometry, Numerical Analysis, Control and Optimization, Algebra and Number Theory, Optimization and Control (math.OC), Applied Mathematics, General Mathematics, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Algebraic Geometry (math.AG), Mathematics - Optimization and Control
Abstract

We provide a new degree bound on the weighted sum-of-squares (SOS) polynomials for Putinar-Vasilescu's Positivstellensatz. This leads to another Positivstellensatz saying that if $f$ is a polynomial of degree at most $2 d_f$ nonnegative on a semialgebraic set having nonempty interior defined by finitely many polynomial inequalities $g_j(x)\ge 0$, $j=1,\dots,m$ with $g_1:=L-\|x\|_2^2$ for some $L>0$, then there exist positive constants $\bar c$ and $c$ depending on $f,g_j$ such that for any $\varepsilon>0$, for all $k\ge \bar c \varepsilon^{-c}$, $f$ has the decomposition \begin{equation} \begin{array}{l} (1+\|x\|_2^2)^k(f+\varepsilon)=\sigma_0+\sum_{j=1}^m \sigma_jg_j \,, \end{array} \end{equation} for some SOS polynomials $\sigma_j$ being such that the degrees of $\sigma_0,\sigma_jg_j$ are at most $2(d_f+k)$. Here $\|\cdot\|_2$ denotes the $\ell_2$ vector norm. As a consequence, we obtain a converging hierarchy of semidefinite relaxations for lower bounds in polynomial optimization on basic compact semialgebraic sets. The complexity of this hierarchy is $\mathcal{O}(\varepsilon^{-c})$ for prescribed accuracy $\varepsilon>0$. In particular, if $m=L=1$ then $c=65$, yielding the complexity $\mathcal{O}(\varepsilon^{-65})$ for the minimization of a polynomial on the unit ball. Our result improves the complexity bound $\mathcal{O}(\exp(\varepsilon^{-c}))$ due to Nie and Schweighofer in [Journal of Complexity 23.1 (2007): 135-150]., Comment: 24 pages, 1 figure

Published
2022
Full Text
View/download PDF

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

Author

Victor Magron, Nils Vreman, Jie Wang, Paolo Pazzaglia, Martina Maggio, Automatic Control Group [Lund], Lund University [Lund], Saarland University [Saarbrücken], Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Equipe Polynomial OPtimization (LAAS-POP), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Magron, Victor, TREMPLIN-ERC - Optimisation garantie pour la vérification des systèmes cyber-physiques - - COPS2018 - ANR-18-ERC2-0004 - TERC - VALID, Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID

Subjects
Control and Optimization, Optimization and Control (math.OC), Control and Systems Engineering, FOS: Mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract

Control systems can show robustness to many events, like disturbances and model inaccuracies. It is natural to speculate that they are also robust to sporadic deadline misses when implemented as digital tasks on an embedded platform. This paper proposes a comprehensive stability analysis for control systems subject to deadline misses, leveraging a new formulation to describe the patterns experienced by the control task under different handling strategies. Such analysis brings the assessment of control systems robustness to computational problems one step closer to the controller implementation., 6 pages, 1 table, published in IEEE Control Systems Letters and in the proceedings of the Control and Decision Conference 2022

Published
2022
Full Text
View/download PDF

25. Time-Varying Semidefinite Programming: Geometry of the Trajectory of Solutions

Author

Bellon, Antonio, Henrion, Didier, Kungurtsev, Vyacheslav, Mareček, Jakub, Czech Technical University in Prague (CTU), Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), 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), and Université Fédérale Toulouse Midi-Pyrénées

Subjects
Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract

In many applications, solutions of convex optimization problems must be updated on-line, as functions of time. In this paper, we consider timevarying semidefinite programs (TV-SDP), which are linear optimization problems in the semidefinite cone whose coefficients (input data) depend on time. We are interested in the geometry of the solution (output data) trajectory, defined as the set of solutions depending on time. We propose an exhaustive description of the geometry of the solution trajectory. As our main result, we show that only 6 distinct behaviors can be observed at a neighborhood of a given point along the solution trajectory. Each possible behavior is then illustrated by an example.

Published
2022

26. Converging approximations of attractors via almost Lyapunov functions and semidefinite programming

Author

Corbinian Schlosser, 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), and Université de Toulouse (UT)

Subjects
Lyapunov function, Control and Optimization, MathematicsofComputing_NUMERICALANALYSIS, Dynamical Systems (math.DS), dynamical systems, semidefinite programming, Global attractor, Optimization and Control (math.OC), Control and Systems Engineering, outer approximations, sum-of-squares, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Dynamical Systems, 37M22, 34D45, 90C22, 90C23, 93D30, Mathematics - Optimization and Control, infinite-dimensional linear programming
Abstract

In this paper we combine two existing approaches for approximating attractors. One of them approximates the attractors arbitrarily well by sublevel sets related to solutions of infinite dimensional linear programming problems. A downside there is that these sets are not necessarily positively invariant. On the contrary, the second method provides supersets of the attractor which are positively invariant. Their method on the other hand has the disadvantage that the underlying optimization problem is not computationally tractable without the use of heuristics - and incorporating them comes at the price of losing guaranteed convergence. In this paper we marry both approaches by combining their techniques and we get converging outer approximations of the attractor consisting of positively invariant sets based on convex optimization via sum-of-squares techniques. The method is easy to use and illustrated by numerical examples.

Published
2022
Full Text
View/download PDF

27. Tractable semidefinite bounds of positive maximal singular values

Author

Magron, Victor, Mai, Ngoc Hoang Anh, Ebihara, Yoshio, Waki, Hayato, 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), Graduate School of Information Science and Electrical Engineering, Kyushu University, Institute of Mathematics for Industry, Kyushu University, This research has been supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-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), 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, 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
Optimization and Control (math.OC), 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

We focus on computing certified upper bounds for the positive maximal singular value (PMSV) of a given matrix. The PMSV problem boils down to maximizing a quadratic polynomial on the intersection of the unit sphere and the nonnegative orthant. We provide a hierarchy of tractable semidefinite relaxations to approximate the value of the latter polynomial optimization problem as closely as desired. This hierarchy is based on an extension of P\'olya's representation theorem. Doing so, positive polynomials can be decomposed as weighted sums of squares of $s$-nomials, where $s$ can be a priori fixed ($s=1$ corresponds to monomials, $s=2$ corresponds to binomials, etc.). This in turn allows us to control the size of the resulting semidefinite relaxations., Comment: 4 pages, 1 table, submitted to MTNS as extended abstract

Published
2022

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

Author

Chen, Tong, HAL-LAAS, LAAS, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Paul Sabatier - Toulouse III, Edouard Pauwels, Victor Magron, Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, and UT3 : Université Toulouse 3 Paul Sabatier

Subjects
Polynomial optimization, Hiérarchie moment-somme de carrés, neural network, correlative sparsity, optimisation polynomiale, moment-sum of squares hierarchy, hiérarchie momentsomme de carrés, robustness verification, Lipschitz constant, constante de Lipschitz, semidefinite programming, parcimonie corrélative, [SPI.AUTO]Engineering Sciences [physics]/Automatic, vérification de robustesse, [SPI.AUTO] Engineering Sciences [physics]/Automatic, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], réseau de neurones, programmation semi-définie
Abstract

Nowadays, Neural Networks (NNs) are widely and successfully used for many large-scale and complex machine learning tasks, such as image classification, voice recognition recommender system, and have attracted the attention of many community researchers. However, even though neural networks are powerful, they are generally neither robust nor reliable. This means that, for some input examples, neural network classifiers can produce unstable predictions of their labels, i.e., classifiers are sensitive to small input changes, which is problematic in some crucial areas such as auto-driving or aerospace. Therefore, the robustness of neural networks has become a critical issue in the machine learning community in recent years. Robustness for NNs has two main facets: robust trai! ning and robust verification. In this thesis, we mainly focus on verifying the robustness of pre-trained NNs. Based on semi-definite programming, we first develop a sublevel hierarchy for polynomial optimization problems and then apply it to robustness verification of NNs. Our approaches show empirical improvements over other related methods., De nos jours, les Réseaux de Neurones (RN) sont largement et avec succès utilisés pour de nombreuses tâches d’apprentissage automatique à grande échelle et complexes, telles que la classification d’images, le système de recommandation de reconnaissance vocale, et ont attiré l’attention de nombreux chercheurs de la communauté. Cependant, même si les réseaux de neurones sont puissants, ils ne sont généralement ni robustes ni fiables. Cela signifie que, pour certains exemples d’entrées, les classificateurs de réseaux de neurones peuvent produire des prédictions instables de leurs étiquettes, c’est-à-dire que les classificateurs sont sensibles aux petits changements d’entrée, ce qui est problématique dans certains domaines cruciaux comme la conduite automobile ou l’aérospatiale. Par conséquent, la robustesse des ! réseaux de neurones est devenue un problème critique dans la communauté de l’apprentissage automatique ces dernières années. La robustesse a principalement deux facettes : une formation robuste des RN et une vérification robuste des RN. Dans cette thèse, nous nous concentrons principalement sur la v! érification de la robustesse des RN pré-formés. Sur la base de la programmation semi-définie, nous développons d’abord une hiérarchie de sous-niveaux pour les problèmes d’optimisation polynomiale, puis nous l’appliquons à la vérification de robustesse des RN. Nos approches montrent des améliorations empiriques par rapport à d’autres méthodes connexes.

Published
2022

29. Urysohn in action: separating semialgebraic sets by polynomials

Author

Korda, Milan, Lasserre, Jean-Bernard, Lazarev, Alexey, Magron, Victor, Naldi, Simone, Magron, Victor, Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID, Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID, 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), Czech Technical University in Prague (CTU), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Mathématiques & Sécurité de l'information (XLIM-MATHIS), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
Mathematics - Algebraic Geometry, Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Algebraic Geometry (math.AG)
Abstract

A classical result from topology called Uryshon's lemma asserts the existence of a continuous separator of two disjoint closed sets in a sufficiently regular topological space. In this work we make a search for this separator constructive and efficient in the context of real algebraic geometry. Namely, given two compact disjoint basic semialgebraic sets which are contained in an $n$-dimensional box, we provide an algorithm that computes a separating polynomial greater than or equal to 1 on the first set and less than or equal to 0 on the second one., Comment: 4 pages, 1 figure, submitted as en extended abstract for the last POEMA workshop

Published
2022

30. Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant

Author

Mai, Ngoc Hoang Anh, Magron, Victor, Lasserre, Jean-Bernard, Toh, Kim-Chuan, 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, Centre International de Mathématiques et d'Informatique (de Toulouse) - - CIMI2011 - ANR-11-LABX-0040 - LABX - VALID, Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), National University of Singapore (NUS), This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-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), 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, Computer Science - Machine Learning, Mathematics - Algebraic Geometry, Optimization and Control (math.OC), 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, Algebraic Geometry (math.AG), Machine Learning (cs.LG)
Abstract

We consider polynomial optimization problems (POP) on a semialgebraic set contained in the nonnegative orthant (every POP on a compact set can be put in this format by a simple translation of the origin). Such a POP can be converted to an equivalent POP by squaring each variable. Using even symmetry and the concept of factor width, we propose a hierarchy of semidefinite relaxations based on the extension of P\'olya's Positivstellensatz by Dickinson-Povh. As its distinguishing and crucial feature, the maximal matrix size of each resulting semidefinite relaxation can be chosen arbitrarily and in addition, we prove that the sequence of values returned by the new hierarchy converges to the optimal value of the original POP at the rate $O(\varepsilon^{-c})$ if the semialgebraic set has nonempty interior. When applied to (i) robustness certification of multi-layer neural networks and (ii) computation of positive maximal singular values, our method based on P\'olya's Positivstellensatz provides better bounds and runs several hundred times faster than the standard Moment-SOS hierarchy., Comment: 39 pages, 15 tables

Published
2022

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

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

33. Optimal bounds for bit-sizes of stationary distributions in finite Markov chains

Author

Skomra, Mateusz, 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), and Université de Toulouse (UT)

Subjects
FOS: Computer and information sciences, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Computer Science - Computer Science and Game Theory, Probability (math.PR), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Probability, Computer Science and Game Theory (cs.GT)
Abstract

An irreducible stochastic matrix with rational entries has a stationary distribution given by a vector of rational numbers. We give an upper bound on the lowest common denominator of the entries of this vector. Bounds of this kind are used to study the complexity of algorithms for solving stochastic mean payoff games. They are usually derived using the Hadamard inequality, but this leads to suboptimal results. We replace the Hadamard inequality with the Markov chain tree formula in order to obtain optimal bounds. We also adapt our approach to obtain bounds on the absorption probabilities of finite Markov chains and on the gains and bias vectors of Markov chains with rewards., 15 pages, 3 figures

Published
2021

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

35. OPTIMIZATION ON THE EUCLIDEAN UNIT SPHERE

Author

Jean B. Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, 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-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), 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), and Equipe Polynomial OPtimization (LAAS-POP)

Subjects
Polynomial optimization, Applied Mathematics, sparsity, Euclidean unit sphere, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Software, Theoretical Computer Science
Abstract

International audience; We consider the problem of minimizing a continuously differentiable function f of m linear forms in n variables on the Euclidean unit sphere. We show that this problem is equivalent to minimizing the same function of related m linear forms (but now in m variables) on the Euclidean unit ball. When the linear forms are known, this results in a drastic reduction in problem size whenever m ≪ n and allows to solve potentially large scale non-convex such problems. We also provide a test to detect when a polynomial is a polynomial in a fixed number of forms. Finally, we identify two classes of functions with no spurious local minima on the sphere: (i) quasi-convex polynomials of odd degree and (ii) nonnegative and homogeneous functions. Finally, odd degreed forms have only nonpositive local minima and at most (d − 1) m are strictly negative.

Published
2021
Full Text
View/download PDF

36. Ensemble Approximations for Constrained Dynamical Systems using Liouville Equation

Author

Souaiby, Marianne, Tanwani, Aneel, Henrion, Didier, É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-17-CE40-0019,ConVan,Contrôle des Systèmes Interconnectés sous Contraintes en Utilisant l'Analyse Variationelle(2017), 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)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), 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), and Institut National des Sciences Appliquées (INSA)-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3)

Subjects
Control and Systems Engineering, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [INFO.INFO-SY]Computer Science [cs]/Systems and Control [cs.SY], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Electrical and Electronic Engineering
Abstract

Submitted for Publication on 24-06-2021; International audience; For a class of state-constrained dynamical systems described by evolution variational inequalities, we study the time evolution of a probability measure which describes the distribution of the state over a set. In contrast to smooth ordinary differential equations, where the evolution of this probability measure is described by the Liouville equations, the flow map associated with the nonsmooth differential inclusion is not necessarily invertible and one cannot directly derive a continuity equation to describe the evolution of the distribution of states. Instead, we consider Lipschitz approximation of our original nonsmooth system and construct a sequence of measures obtained from Liouville equations corresponding to these approximations. This sequence of measures converges in weak-star topology to the measure describing the evolution of the distribution of states for the original nonsmooth system. This allows us to approximate numerically the evolution of moments (up to some finite order) for our original nonsmooth system, using a solver that uses finite order moment approximations of the Liouville equation. Our approach is illustrated with the help of an academic example.

Published
2021
Full Text
View/download PDF

37. The quest of modeling, certification and efficiency in polynomial optimization

Author

Magron, Victor, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse 3 Paul Sabatier, Salma Kuhlmann, 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), and Equipe Polynomial OPtimization (LAAS-POP)

Subjects
Polynomial optimization, schéma de parcimonie, sums of squares, hybrid numeric-symbolic algorithms, optimisation garantie, sparsity pattern, sommes de carrés, algorithmes hybrides numérique-symbolique, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, eigenvalue and trace optimization, moments, Optimisation polynomiale, trace minimale, valeur propre minimale, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], certified optimization
Abstract

National audience; Certified optimization techniques have successfully tackled challenging verification problems in various fundamental and industrial applications. The formal verification of thousands of nonlinear inequalities arising in the famous proof of Kepler conjecture was achieved in August 2014. In energy networks, it is now possible to compute the solution of large-scale power flow problems with up to thousand variables. This success follows from growing research efforts in polynomial optimization, an emerging field extensively developed in the last two decades. One key advantage of these techniques is the ability to model a wide range of problems using optimization formulations, which can be in turn solved with efficient numerical tools.My methodology heavily relies on such methods, including the moment-sums of squares (moment-SOS) hierarchy by Lasserre which provides numerical certificates for positive polynomials as well as recently developed alternative methods. However, such optimization methods still encompass many major issues on both practical and theoretical sides: scalability, unknown complexity bounds, ill-conditioning of numericalsolvers, lack of exact certification, convergence guarantees. This manuscript presents results along these research tracks with the long-term perspective of obtaining scientific breakthroughs to handlecertification of nonlinear systems arising in real-world applications. In the first part, I focus on modeling aspects. One relies on the moment-SOS hierarchy to analyze dynamical polynomial systems, either in the discrete-time or continuous-time setting, and problems involving noncommuting variables, for example matrices of finite or infinite size, to model quantum physics operators. In the second part, I describe how to design and analyze algorithms which output exact positivity certificates for either unconstrained or constrained optimization problems. In the last part, I explain how to improve the scalability of the hierarchy by exploiting the specific sparsity structure of the polynomial data coming from real-world problems. Important applications arise from various fields, including computer arithmetic (roundoff error bounds), quantum information (noncommutative optimization), and optimal power-flow.; Les techniques d'optimisation garantie ont permis de résoudre plusieurs problèmes de vérification notoirement difficiles, dans des domaines académiques et industriels. La vérification formelle des dizaines de milliers d'inégalités non-linéaires apparaissant dans la preuve célèbre de la conjecture de Kepler a été achevée en Août 2014. Il est aujourd'hui possible de calculer la solution de problèmes d'optimisation de réseaux électriques faisant intervenir plusieurs milliers de variables. Ces succès sont la conséquence d'efforts croissants de recherche en optimisation polynomiale, un domaine émergent qui s'est rapidement développé au cours des vingt dernières années. L'avantage clé de ces techniques est leur capacité de modéliser une large classe de problèmes à l'aide de reformulations dans le paradigme de l'optimisation, afin de permettre leur résolution avec des outils numériques efficaces. Ma méthodologie repose sur l'utilisation de telles méthodes, en particulier la hiérarchie moments-sommes de carrés (moment-SOS) développée par Lasserre, qui fournit des certificats numériques pour les polynômes positifs, ainsi que des méthodes alternatives récemment développées. Néanmoins, certains problèmes freinent l'utilisation de ces méthodes d'optimisation : passage à l'échelle, bornes de complexité inconnues, conditionnement des solveurs numériques, absence de certification rigoureuse, absence de garanties de convergence. Ce manuscrit présente plusieurs résultats pour pallier à certains de ces problèmes, avec la perspective à long terme d'obtenir des avancées scientifiques pour certifier des systèmes non-linéaires provenant d'applications du monde réel. Dans la première partie du manuscrit, je m'intéresse à des aspects de modélisation. La hiérarchie moment-SOS est utilisée pour analyser des systèmes à dynamique polynomiale, dans un cadre discret ou continu, ainsi que des problèmes faisant intervenir des variables non-commutatives, par exemple des matrices de taille finie ou infinie, afin de modéliser des opérateurs de physique quantique.Dans la seconde partie du manuscrit, je décris comment mettre au point et analyser des algorithmes qui calculent des certificats exacts de positivité, pour des problèmes d'optimisation avec ou sans contraintes. Dans la dernière partie du manuscrit, j'explique comment améliorer le passage à l'échelle de la hiérarchie, en exploitant la structure spécifique des données polynomiales provenant d'applications réelles, telles que l'arithmétique des ordinateurs (bornes d'erreur flottante), l'information quantique (optimisation non-commutative) et les réseaux électriques.

Published
2021

38. Moment-SOS hierarchy for large scale set approximation. Application to power systems transient stability analysis

Author

Matteo Tacchi, STAR, ABES, É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), Equipe Polynomial OPtimization (LAAS-POP), INSA de Toulouse, and Didier Henrion

Subjects
Moments, Approximations ensemblistes, Infinite dimensional optimization, Parcimonie, Power systems transient stability, Polynômes sommes de carrés, Analyse de la stabilité transitoire des systèmes électriques, Direct methods for stability analysis, [SPI.AUTO]Engineering Sciences [physics]/Automatic, Semidefinite relaxations, Polynomial sums of squares, [SPI.AUTO] Engineering Sciences [physics]/Automatic, Méthodes directes pour l’analyse de stabilité, Relaxations semidéfinie, Set approximation, Optimisation en dimension infinie, Sparsity
Abstract

This thesis deals with approximating sets using Lasserre’s moment-SOS hierarchy. The motivation is the increasing need for efficient methods to approximate sets of secure operation conditions for electrical power grids. Indeed, recent and ongoing changes in the European power network, such as the increase in renewable energy sources interfaced by power electronic devices, are bringing up new challenges in terms of power grid security assessment. The aim of the present thesis is to investig- ate the suitability of them moment-SOS hierarchy as a tool for large scale stability assessment.In this regard, the very scheme of moment-SOS hierarchies is analysed in-depth, and general results regarding the convergence and accuracy of the framework are stated, along with specific computational methods inspired from differential geo- metry and partial differential equations theory, in order to improve the convergence of the numerical scheme.From the computational viewpoint, the core of this thesis is the exploitation of problem structure to alleviate the computational burden of high dimensional, large scale industrial problems. The network structure of power grids leads us to consider general sparsity patterns and design methods which distribute our computations accordingly, drastically reducing computational costs in implementation.In addition to stability analysis, a special interest is put on the theoretical prob- lem of volume computation, whose applications rather concern the field of integral calculus and probability evaluation, as understanding this problem turns out to be a prerequisite for approximating stability regions of differential systems, such as regions of attraction or positively invariant sets, with the moment-SOS hierarchy. Indeed, the moment-SOS approach to volume computation is the core of moment- SOS stability analysis., Cette thèse a pour objet l’approximation d’ensembles au moyen de la hiérarchie moment-sommes-de-carrés (abrégée moment-SOS) de Lasserre. Elle est motivée par le besoin croissant de méthodes efficaces pour approcher des ensembles de points de fonctionnement stables dans le domaine des réseaux électriques. En effet, les récents développements et les changements en cours au sein du réseau électrique européen, comme l’augmentation de la part des énergies renouvelables dans la géné- ration d’électricité, et leur raccordement au réseau par des interfaces d’électronique de puissance, soulèvent de nouveaux défis en termes d’évaluation de la sécurité des réseaux électriques. L’objectif de cette thèse est d’étudier la pertinence de la hiérar- chie moment-SOS dans les études de stabilité à grande échelle.Dans cette optique, le schéma numérique que constituent les hiérarchies moment- SOS est étudié en détails, et des résultats généraux sur la convergence et la précision de cet outil sont formulés, et accompagnés de méthodes de calcul spécifiques, inspi- rées de notions de géométrie différentielle et de théorie des équations aux dérivées partielles, visant à améliorer la convergence du schéma numérique.Du point de vue purement calculatoire, l’élément central de cette thèse est l’ex- ploitation de la structure des problèmes, en vue d’alléger le coût des calculs liés aux problèmes industriels à grande échelle, modellisés en très grande dimension. La structure en réseau des systèmes électriques nous conduit à nous intéresser aux configurations dites parcimonieuses, et à concevoir des méthodes distribuant les cal- culs suivant ces configurations, permettant ainsi de réduire drastiquement le coût en calcul de nos implémentations.Enfin, en plus de l’analyse de stabilité, un intérêt particulier est accordé au pro- blème théorique du calcul de volumes, dont les applications se situent plutôt dans le domaine du calcul intégral et de l’évaluation probabiliste, la compréhension de ce problème étant un prérequis pour l’approximation de régions de stabilité pour les systèmes différentiels, comme par exemple les régions d’attractions ou les ensembles positivement invariants, au moyen des hiérarchies moment-SOS. En effet, l’approche du calcul de volumes par les hiérarchies moment-SOS est à l’origine de l’analyse de stabilité par ces mêmes hiérarchies.

Published
2021

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

40. Stokes, Gibbs and volume computation of semi-algebraic sets

Author

Matteo Tacchi, Jean Bernard Lasserre, Didier Henrion, É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, Réseau de Transport d'electricite (RTE), Réseau de Transport d'Electricité [Paris] (RTE), 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), Faculty of Electrical Engineering [Prague] (FEL CTU), Czech Technical University in Prague (CTU), Ecole Polytechnique Fédérale de Lausanne (EPFL), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Equipe Polynomial OPtimization (LAAS-POP), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), and Department of Control Engineering, Faculty of Electrical Engineering [Prague]

Subjects
convex optimization, multivariate integration, stokes' theorem, Theoretical Computer Science, Computational Theory and Mathematics, Optimization and Control (math.OC), FOS: Mathematics, Discrete Mathematics and Combinatorics, real algebraic geometry, Geometry and Topology, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], gibbs phenomenon, optimization, Mathematics - Optimization and Control, numerical methods for multivariate integration, attraction
Abstract

We consider the problem of computing the Lebesgue volume of compact basic semi-algebraic sets. In full generality, it can be approximated as closely as desired by a converging hierarchy of upper bounds obtained by applying the Moment-SOS (sums of squares) methodology to a certain infinite-dimensional linear program (LP). At each step one solves a semidefinite relaxation of the LP which involves pseudo-moments up to a certain degree. Its dual computes a polynomial of same degree which approximates from above the discontinuous indicator function of the set, hence with a typical Gibbs phenomenon which results in a slow convergence of the associated numerical scheme. Drastic improvements have been observed by introducing in the initial LP additional linear moment constraints obtained from a certain application of Stokes’ theorem for integration on the set. However and so far there was no rationale to explain this behavior. We provide a refined version of this extended LP formulation. When the set is the smooth super-level set of a single polynomial, we show that the dual of this refined LP has an optimal solution which is a continuous function. Therefore in this dual one now approximates a continuous function by a polynomial, hence with no Gibbs phenomenon, which explains and improves the already observed drastic acceleration of the convergence of the hierarchy. Interestingly, the technique of proof involves recent results on Poisson’s partial differential equation (PDE).

Published
2020
Full Text
View/download PDF

41. Peak Estimation and Recovery with Occupation Measures

Author

Miller, Jared, Henrion, Didier, Sznaier, Mario, Northeastern University [Boston], Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Faculty of Electrical Engineering [Prague] (FEL CTU), Czech Technical University in Prague (CTU), Equipe Polynomial OPtimization (LAAS-POP), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)

Subjects
Mathematics - Algebraic Geometry, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, 37M99, Systems and Control (eess.SY), Dynamical Systems (math.DS), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Dynamical Systems, Algebraic Geometry (math.AG), Electrical Engineering and Systems Science - Systems and Control
Abstract

Peak Estimation aims to find the maximum value of a state function achieved by a dynamical system. This problem is non-convex when considering standard Barrier and Density methods for invariant sets, and has been treated heuristically by using auxiliary functions. A convex formulation based on occupation measures is proposed in this paper to solve peak estimation. This method is dual to the auxiliary function approach. Our method will converge to the optimal solution and can recover trajectories even from approximate solutions. This framework is extended to safety analysis by maximizing the minimum of a set of costs along trajectories., 13 pages, 7 figures. Changed according to helpful comments by reviewers, focus shifted to recovery algorithm and safety margins

Published
2020

42. A hierarchy of spectral relaxations for polynomial optimization

Author

Mai, Ngoc Hoang Anh, Magron, Victor, Lasserre, Jean-Bernard, É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-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), Equipe Polynomial OPtimization (LAAS-POP), 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), 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, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID

Subjects
Optimization and Control (math.OC), 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, Software, Theoretical Computer Science
Abstract

We show that (i) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (ii) the resulting semidefinite relaxations in the moment-SOS hierarchy have the constant trace property (CTP) for the involved matrices. We then exploit the CTP to avoid solving the semidefinite relaxations via interior-point methods and rather use ad-hoc spectral methods that minimize the largest eigenvalue of a matrix pencil. Convergence to the optimal value of the semidefinite relaxation is guaranteed. As a result we obtain a hierarchy of nonsmooth "spectral relaxations" of the initial POP. Efficiency and robustness of this spectral hierarchy is tested against several equality constrained POPs on a sphere as well as on a sample of randomly generated quadratically constrained quadratic problems (QCQPs)., 38 pages, 6 figures, 11 tables

Published
2020

43. A sparse version of Reznick's Positivstellensatz

Author

Ngoc Hoang Anh Mai, Victor Magron, Jean Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), PNRIA, ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020,POEMA(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Equipe Polynomial OPtimization (LAAS-POP), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)

Subjects
Reznick's Positivstellensatz, Mathematics - Algebraic Geometry, General Mathematics, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Management Science and Operations Research, Algebraic Geometry (math.AG), Computer Science Applications
Abstract

If $f$ is a positive definite form, Reznick's Positivstellensatz [Mathematische Zeitschrift. 220 (1995), pp. 75--97] states that there exists $k\in\mathbf{N}$ such that ${\| x \|^{2k}_2}f$ is a sum of squares of polynomials. Assuming that $f$ can be written as a sum of forms $\sum_{l=1}^p f_l$, where each $f_l$ depends on a subset of the initial variables, and assuming that these subsets satisfy the so-called running intersection property, we provide a sparse version of Reznick's Positivstellensatz. Namely, there exists $k \in \mathbf{N}$ such that $f=\sum_{l = 1}^p {{\sigma_l}/{H_l^{k}}}$, where $\sigma_l$ is a sum of squares of polynomials, $H_l$ is a uniform polynomial denominator, and both polynomials $\sigma_l,H_l$ involve the same variables as $f_l$, for each $l=1,\dots,p$. In other words, the sparsity pattern of $f$ is also reflected in this sparse version of Reznick's certificate of positivity. We next use this result to also obtain positivity certificates for (i) polynomials nonnegative on the whole space and (ii) polynomials nonnegative on a (possibly non-compact) basic semialgebraic set, assuming that the input data satisfy the running intersection property. Both are sparse versions of a positivity certificate due to Putinar and Vasilescu., Comment: 19 pages, 2 tables

Published
2020
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results