Author: "Victor MAGRON" / Topic: mathematics - optimization and control - Searchworks@Jio Institute Digital Library Search Results

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

Start Over Author "Victor MAGRON" Topic mathematics - optimization and control

31 results on '"Victor MAGRON"'

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

Author: Ngoc Hoang Anh Mai, J. B. Lasserre, Victor Magron, Jie Wang, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Equipe Polynomial OPtimization (LAAS-POP), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), and European Project: 813211,H2020,POEMA(2019)
Subjects: Optimization and Control (math.OC), Applied Mathematics, FOS: Mathematics, MathematicsofComputing_NUMERICALANALYSIS, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Software
Abstract: We prove that every semidefinite moment relaxation of a polynomial optimization problem (POP) with a ball constraint can be reformulated as a semidefinite program involving a matrix with constant trace property (CTP). As a result such moment relaxations can be solved efficiently by first-order methods that exploit CTP, e.g., the conditional gradient-based augmented Lagrangian method. We also extend this CTP-exploiting framework to large-scale POPs with different sparsity structures. The efficiency and scalability of our framework are illustrated on second-order moment relaxations for various randomly generated quadratically constrained quadratic programs., 43 pages, 6 algorithms, 23 tables
Published: 2022
Full Text: View/download PDF

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

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

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

4. Positivity certificates and polynomial optimization on non-compact semialgebraic sets

Author: Victor Magron, Ngoc Hoang Anh Mai, Jean B. Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, and Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)
Subjects: Discrete mathematics, 021103 operations research, Optimization problem, Degree (graph theory), Hierarchy (mathematics), General Mathematics, Numerical analysis, 0211 other engineering and technologies, Value (computer science), 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Optimization and Control (math.OC), Convergence (routing), FOS: Mathematics, Strong duality, Polynomial optimization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH]Mathematics [math], 0101 mathematics, Mathematics - Optimization and Control, Software, Mathematics
Abstract: In a first contribution, we revisit two certificates of positivity on (possibly non-compact) basic semialgebraic sets due to Putinar and Vasilescu [Comptes Rendus de l'Acad\'emie des Sciences-Series I-Mathematics, 328(6) (1999) pp. 495-499]. We use Jacobi's technique from [Mathematische Zeitschrift, 237(2) (2001) pp. 259-273] to provide an alternative proof with an effective degree bound on the sums of squares multipliers in such certificates. As a consequence, it allows one to define a hierarchy of semidefinite relaxations for a general polynomial optimization problem. Convergence of this hierarchy to a neighborhood of the optimal value as well as strong duality and analysis are guaranteed. In a second contribution, we introduce a new numerical method for solving systems of polynomial inequalities and equalities with possibly uncountably many solutions. As a bonus, one may apply this method to obtain approximate global optimizers in polynomial optimization., Comment: 33 pages, 2 figures, 5 tables
Published: 2021
Full Text: View/download PDF

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

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

Author: Jie Wang, Victor Magron, Jean B. Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, and European Project: 813211,H2020,POEMA(2019)
Subjects: 0211 other engineering and technologies, 14P10, 90C25, 12D15, 12Y05, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, moment relaxation, Theoretical Computer Science, Combinatorics, chordal graph, Chordal graph, FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, 021103 operations research, Hierarchy (mathematics), Extension (predicate logic), Complement (complexity), Term (time), Moment (mathematics), Optimization and Control (math.OC), Polynomial optimization problem, term-sparsity, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Preprint, Software, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: This work is a follow-up and a complement to arXiv:1912.08899 [math.OC] for solving polynomial optimization problems (POPs). The chordal-TSSOS hierarchy that we propose is a new sparse moment-SOS framework based on term-sparsity and chordal extension. By exploiting term-sparsity of the input polynomials we obtain a two-level hierarchy of semidefinite programming relaxations. The novelty and distinguishing feature of such relaxations is to obtain quasi block-diagonal matrices obtained in an iterative procedure that performs chordal extension of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Various numerical examples demonstrate the efficiency and the scalability of this new hierarchy for both unconstrained and constrained POPs. The two hierarchies are complementary. While the former TSSOS arXiv:1912.08899 [math.OC] has a theoretical convergence guarantee, the chordal-TSSOS has superior performance but lacks this theoretical guarantee., 29 pages, 14 tables, 5 figures. arXiv admin note: text overlap with arXiv:1912.08899
Published: 2021
Full Text: View/download PDF

7. A Sublevel Moment-SOS Hierarchy for Polynomial Optimization

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

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

9. Certifying global optimality of AC-OPF solutions via sparse polynomial optimization

Author: Jie Wang, Victor Magron, and Jean B. Lasserre
Subjects: Optimization and Control (math.OC), 90C23, 14P10, 90C22, 90C26, 12D15, FOS: Mathematics, Energy Engineering and Power Technology, Electrical and Electronic Engineering, Mathematics - Optimization and Control
Abstract: We report the experimental results on certifying 1% global optimality of solutions of AC-OPF instances from PGLiB via the CS-TSSOS hierarchy -- a moment-SOS based hierarchy that exploits both correlative and term sparsity, which can provide tighter SDP relaxations than Shor's relaxation. Our numerical experiments demonstrate that the CS-TSSOS hierarchy scales well with the problem size and is indeed useful in certifying global optimality of solutions for large-scale real world problems, e.g., the AC-OPF problem. In particular, we are able to certify 1% global optimality for a challenging AC-OPF instance with 6515 buses involving 14398 real variables and 63577 constraints., Comment: 18 pages, 5 figures, 4 tables
Published: 2022
Full Text: View/download PDF

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

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

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

12. Noncommutative Christoffel-Darboux Kernels

Author: Serban Belinschi, Victor Magron, Victor Vinnikov, Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Ben-Gurion University of the Negev (BGU), Part of this work was conducted in November 2019 while STB was a visiting fellow supported by the Faculty of Natural Sciences Distinguished Scientist Visitors Program of the Ben Gurion University of the Negev, Beer-Sheva, Israel, and during the three authors’visit at the MFO workshop I.D.: 2010, 'Real Algebraic Geometry with a View Toward Hyperbolic Programming and Free Probability' (1–7 March 2020)., PHC Proteus grant 46195TA, ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020,POEMA(2019), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Department of Mathematics [Be'er Sheva], Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Belinschi, Serban, TREMPLIN-ERC - Optimisation garantie pour la vérification des systèmes cyber-physiques - - COPS2018 - ANR-18-ERC2-0004 - TERC - VALID, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID
Subjects: Mathematics - Complex Variables, Mathematics::Complex Variables, Optimization and Control (math.OC), Applied Mathematics, General Mathematics, [MATH.MATH-OA]Mathematics [math]/Operator Algebras [math.OA], Mathematics - Operator Algebras, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Complex Variables (math.CV), [MATH.MATH-OA] Mathematics [math]/Operator Algebras [math.OA], Operator Algebras (math.OA), Mathematics - Optimization and Control
Abstract: We introduce from an analytic perspective Christoffel-Darboux kernels associated to bounded, tracial noncommutative distributions. We show that properly normalized traces, respectively norms, of evaluations of such kernels on finite dimensional matrices yield classical plurisubharmonic functions as the degree tends to infinity, and show that they are comparable to certain noncommutative versions of the Siciak extremal function. We prove estimates for Siciak functions associated to free products of distributions, and use the classical theory of plurisubharmonic functions in order to propose a notion of support for noncommutative distributions. We conclude with some conjectures and numerical experiments., Comment: 48 pages, 2 figures
Published: 2021
Full Text: View/download PDF

13. The Constant Trace Property in Noncommutative Optimization

Author: Abhishek Bhardwaj, Ngoc Hoang Anh Mai, Victor Magron, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), PHC Proteus QUANTPOP, ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), European Project: 813211,H2020,POEMA(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: Semidefinite programming, 021103 operations research, Trace (linear algebra), Numerical analysis, 010102 general mathematics, 0211 other engineering and technologies, Mathematics::Optimization and Control, 02 engineering and technology, 01 natural sciences, Noncommutative geometry, Matrix (mathematics), Optimization and Control (math.OC), FOS: Mathematics, Applied mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Relaxation (approximation), 0101 mathematics, Constant (mathematics), Mathematics - Optimization and Control, Computer Science::Databases, Variable (mathematics), Mathematics
Abstract: In this article, we show that each semidefinite relaxation of a ball-constrained noncommutative polynomial optimization problem can be cast as a semidefinite program with a constant trace matrix variable. We then demonstrate how this constant trace property can be exploited via first order numerical methods to solve efficiently the semidefinite relaxations of the noncommutative problem., Comment: 8 pages, 3 tables
Published: 2021
Full Text: View/download PDF

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

Author: Didier Henrion, Felix Kirschner, Etienne De Klerk, Milan Korda, Jean-Bernard Lasserre, Victor Magron, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Department of Econometrics and Operations Research (Tilburg University), Tilburg University [Netherlands], ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), European Project: 813211,H2020,POEMA(2019), Research Group: Operations Research, Econometrics and Operations Research, Center Ph. D. Students, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Equipe Polynomial OPtimization (LAAS-POP), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: Optimization and Control (math.OC), Options pricing, General Engineering, FOS: Mathematics, Semidefinite programming, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Moment-SOS hierarchy
Abstract: In this paper we consider the problem of finding bounds on the prices of options depending on multiple assets without assuming any underlying model on the price dynamics, but only the absence of arbitrage opportunities. We formulate this as a generalized moment problem and utilize the well-known Moment-Sum-of-Squares (SOS) hierarchy of Lasserre to obtain bounds on the range of the possible prices. A complementary approach (also due to Lasserre) is employed for comparison. We present several numerical examples to demonstrate the viability of our approach. The framework we consider makes it possible to incorporate different kinds of observable data, such as moment information, as well as observable prices of options on the assets of interest., Comment: 20 pages
Published: 2021
Full Text: View/download PDF

15. Sparse Noncommutative Polynomial Optimization

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

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

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

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

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

18. Computing the Hausdorff boundary measure of semi-algebraic sets

Author: Jean B. Lasserre, Victor Magron, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, FMJH Program PGMO (EPICS project) and EDF, Thales, Orange et Criteo, 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: 666981,H2020,ERC-2014-ADG,TAMING(2015), European Project: 813211,H2020,POEMA(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
Subjects: Semidefinite programming, Semialgebraic set, Pure mathematics, Algebra and Number Theory, Applied Mathematics, 010102 general mathematics, Hausdorff space, Boundary (topology), 010103 numerical & computational mathematics, 26B15, 28A75, 97G30, 28A78, 90C22, 01 natural sciences, Measure (mathematics), Set (abstract data type), Optimization and Control (math.OC), FOS: Mathematics, Hausdorff measure, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Geometry and Topology, 0101 mathematics, Finite set, Mathematics - Optimization and Control, Mathematics
Abstract: Given a compact basic semi-algebraic set we provide a numerical scheme to approximate as closely as desired, any finite number of moments of the Hausdorff measure on the boundary of this set. This also allows one to approximate interesting quantities like length, surface, or more general integrals on the boundary, as closely as desired from above and below., Comment: 21 pages, 2 figures, 2 tables
Published: 2020
Full Text: View/download PDF

19. Exploiting term sparsity in Noncommutative Polynomial Optimization

Author: Victor Magron, Jie Wang, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse 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), FMJH Program PGMO (EPICS project) and EDF, Thales, Orange et Criteo, 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), 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: Semidefinite programming, 021103 operations research, Control and Optimization, Optimization problem, Trace (linear algebra), Hierarchy (mathematics), Applied Mathematics, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Noncommutative geometry, Term (time), Algebra, Primary, 47N10, 90C22, Secondary, 12D15, 14P10, Computational Mathematics, Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, Commutative property, Mathematics - Optimization and Control, Eigenvalues and eigenvectors, Mathematics
Abstract: We provide a new hierarchy of semidefinite programming relaxations, called NCTSSOS, to solve large-scale sparse noncommutative polynomial optimization problems. This hierarchy features the exploitation of term sparsity hidden in the input data for eigenvalue and trace optimization problems. NCTSSOS complements the recent work that exploits correlative sparsity for noncommutative optimization problems by Klep, Magron and Povh in arXiv:1909.00569, and is the noncommutative analogue of the TSSOS framework by Wang, Magron and Lasserre in arXiv:1912.08899. We also propose an extension exploiting simultaneously correlative and term sparsity, as done previously in the commutative case arXiv:2005.02828. Under certain conditions, we prove that the optimums of the NCTSSOS hierarchy converge to the optimum of the corresponding dense SDP relaxation. We illustrate the efficiency and scalability of NCTSSOS by solving eigenvalue/trace optimization problems from the literature as well as randomly generated examples involving up to several thousands of variables., Comment: 33 pages, 5 figures, 12 tables
Published: 2020
Full Text: View/download PDF

20. Optimization over trace polynomials

Author: Jurij Volčič, Victor Magron, Igor Klep, University of Ljubljana, É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), Department of Mathematics [Texas A&M University], Texas A&M University [College Station], FMJH Program PGMO (EPICS project) and EDF, Thales, Orange et Criteo, Slovenian Research Agency grants J1-8132 and P1-0222, NSF grant DMS-1954709, Proteus grant 46195TA QUANTPOP, 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), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), IMFM, Univerza v Ljubljani, 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: Nuclear and High Energy Physics, Polynomial, Optimization problem, Trace (linear algebra), FOS: Physical sciences, [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], 01 natural sciences, [MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph], 0103 physical sciences, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Real algebraic geometry, FOS: Mathematics, 0101 mathematics, Quantum information, 010306 general physics, Mathematics - Optimization and Control, Mathematical Physics, Flatness (mathematics), Mathematics, Mathematics::Operator Algebras, 010102 general mathematics, Statistical and Nonlinear Physics, Mathematical Physics (math-ph), Operator theory, Noncommutative geometry, Functional Analysis (math.FA), Mathematics - Functional Analysis, Algebra, 46N50, 90C22, 47N10, 13J30, Optimization and Control (math.OC), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: Motivated by recent progress in quantum information theory, this article aims at optimizing trace polynomials, i.e., polynomials in noncommuting variables and traces of their products. A novel Positivstellensatz certifying positivity of trace polynomials subject to trace constraints is presented, and a hierarchy of semidefinite relaxations converging monotonically to the optimum of a trace polynomial subject to tracial constraints is provided. This hierarchy can be seen as a tracial analog of the Pironio, Navascu\'es and Ac\'in scheme [New J. Phys., 2008] for optimization of noncommutative polynomials. The Gelfand-Naimark-Segal (GNS) construction is applied to extract optimizers of the trace optimization problem if flatness and extremality conditions are satisfied. These conditions are sufficient to obtain finite convergence of our hierarchy. The results obtained are applied to violations of polynomial Bell inequalities in quantum information theory. The main techniques used in this paper are inspired by real algebraic geometry, operator theory, and noncommutative algebra., Comment: 32 pages
Published: 2020
Full Text: View/download PDF

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

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

22. Semidefinite Approximations of Invariant Measures for Polynomial Systems

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

23. Optimal data fitting: a moment approach

Author: Victor Magron, Jean B. Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - 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, Polynomial Systems (PolSys), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire des signaux et systèmes (L2S), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), 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: Semidefinite programming, 0209 industrial biotechnology, Polynomial, Degree (graph theory), 020208 electrical & electronic engineering, Value (computer science), Covering problems, 02 engineering and technology, Theoretical Computer Science, Moment (mathematics), 020901 industrial engineering & automation, Optimization and Control (math.OC), ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, 0202 electrical engineering, electronic engineering, information engineering, Curve fitting, FOS: Mathematics, Applied mathematics, Relaxation (approximation), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Software, Mathematics
Abstract: We propose a moment relaxation for two problems, the separation and covering problem with semi-algebraic sets generated by a polynomial of degree d. We show that (a) the optimal value of the relaxation finitely converges to the optimal value of the original problem, when the moment order r increases and (b) after performing some small perturbation of the original problem, convergence can be achieved with r=d. We further provide a practical iterative algorithm that is computationally tractable for large datasets and present encouraging computational results., Comment: 23 pages, 5 figures
Published: 2018
Full Text: View/download PDF

24. Semidefinite Approximations of Reachable Sets for Discrete-time Polynomial Systems

Author: Pierre-Loïc Garoche, Didier Henrion, Victor Magron, Xavier Thirioux, É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, ONERA / DTIS, Université de Toulouse [Toulouse], ONERA-PRES Université de Toulouse, Czech Technical University in Prague (CTU), Assistance à la Certification d’Applications DIstribuées et Embarquées (IRIT-ACADIE), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), 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)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), and ANR-17-CE25-0018,FEANICSES,Analyses formelles et exhaustives de systèmes embarqués de contrôle à base de calculs intensifs(2017)
Subjects: Semialgebraic set, 0209 industrial biotechnology, Polynomial, Control and Optimization, convex optimization, Approximations of π, moment relaxations, Mathematics::Optimization and Control, 02 engineering and technology, Computer Science::Computational Geometry, 01 natural sciences, discrete-time polynomial systems, reachable set, Set (abstract data type), 020901 industrial engineering & automation, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, polynomial optimization, FOS: Mathematics, Computer Science::Symbolic Computation, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, Discrete mathematics, Applied Mathematics, 010102 general mathematics, semidefinite programming, sums of squares, Mathematics::Logic, Discrete time and continuous time, Optimization and Control (math.OC), Convex optimization, Polynomial optimization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: We consider the problem of approximating the reachable set of a discrete-time polynomial system from a semialgebraic set of initial conditions under general semialgebraic set constraints. Assuming inclusion in a given simple set like a box or an ellipsoid, we provide a method to compute certified outer approximations of the reachable set. The proposed method consists of building a hierarchy of relaxations for an infinite-dimensional moment problem. Under certain assumptions, the optimal value of this problem is the volume of the reachable set and the optimum solution is the restriction of the Lebesgue measure on this set. Then, one can outer approximate the reachable set as closely as desired with a hierarchy of super level sets of increasing degree polynomials. For each fixed degree, finding the coefficients of the polynomial boils down to computing the optimal solution of a convex semidefinite program. When the degree of the polynomial approximation tends to infinity, we provide strong convergence guarantees of the super level sets to the reachable set. We also present some application examples together with numerical results., Comment: 26 pages, 28 figures
Published: 2017
Full Text: View/download PDF

25. A Sums-of-Squares Extension of Policy Iterations

Author: Victor Magron, Assalé Adjé, Pierre-Loïc Garoche, Université de Perpignan Via Domitia (UPVD), ONERA - The French Aerospace Lab [Toulouse], ONERA, VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), ANR-11-LABX-0025,PERSYVAL-lab,Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique(2011), ANR-11-IDEX-0002,UNITI,Université Fédérale de Toulouse(2011), ANR-12-INSE-0007,CAFEIN,Combinaison d'approches formelles pour l'étude d'invariants numériques(2012), ANR-12-ASTR-0004,VORACE,Vérification des Optimisations Rapides Appliquées à la Commande Embarquée(2012), European Project: 306595,EC:FP7:ERC,ERC-2012-StG_20111012,STATOR(2013), Magron, Victor, Laboratoires d'excellence - Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique - - PERSYVAL-lab2011 - ANR-11-LABX-0025 - LABX - VALID, Initiative d'excellence - Université Fédérale de Toulouse - - UNITI2011 - ANR-11-IDEX-0002 - IDEX - VALID, Ingénierie Numérique et Sécurité - Combinaison d'approches formelles pour l'étude d'invariants numériques - - CAFEIN2012 - ANR-12-INSE-0007 - INS - VALID, Accompagnement spécifique des travaux de recherches et d’innovation Défense - Vérification des Optimisations Rapides Appliquées à la Commande Embarquée - - VORACE2012 - ANR-12-ASTR-0004 - ASTRID - VALID, STATic analysis with ORiginal methods - STATOR - - EC:FP7:ERC2013-01-01 - 2017-12-31 - 306595 - VALID, Imperial College London, RTRA /STAE Project BRIEFCASE, EPSRC (EP/I020457/1) Challenging Engineering Grant., ASTRID VORACE, and ANR: VORACE,Vérification des Optimisations Rapides Appliquées à la Commande Embarquée
Subjects: FOS: Computer and information sciences, 0209 industrial biotechnology, Polynomial, Mathematical optimization, Computer Science - Logic in Computer Science, Linear programming, Computer science, ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.4: Software/Program Verification, 02 engineering and technology, 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], 020901 industrial engineering & automation, Quadratic equation, ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.4: Software/Program Verification/D.2.4.3: Formal methods, FOS: Mathematics, 0101 mathematics, Invariant (mathematics), Mathematics - Optimization and Control, Semidefinite programming, ACM: D.: Software/D.3: PROGRAMMING LANGUAGES/D.3.1: Formal Definitions and Theory/D.3.1.0: Semantics, Sequence, 010102 general mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Static analysis, Computer Science Applications, Logic in Computer Science (cs.LO), Range (mathematics), Control and Systems Engineering, Optimization and Control (math.OC), ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization, Computer Science::Programming Languages, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Analysis
Abstract: In order to address the imprecision often introduced by widening operators in static analysis, policy iteration based on min-computations amounts to considering the characterization of reachable value set of a program as an iterative computation of policies, starting from a post-fixpoint. Computing each policy and the associated invariant relies on a sequence of numerical optimizations. While the early research efforts relied on linear programming (LP) to address linear properties of linear programs, the current state of the art is still limited to the analysis of linear programs with at most quadratic invariants, relying on semidefinite programming (SDP) solvers to compute policies, and LP solvers to refine invariants. We propose here to extend the class of programs considered through the use of Sums-of-Squares (SOS) based optimization. Our approach enables the precise analysis of switched systems with polynomial updates and guards. The analysis presented has been implemented in Matlab and applied on existing programs coming from the system control literature, improving both the range of analyzable systems and the precision of previously handled ones., Comment: 29 pages, 4 figures
Published: 2015
Full Text: View/download PDF

26. Semidefinite approximations of projections and polynomial images of semialgebraic sets

Author: Victor Magron, Didier Henrion, Jean B. Lasserre, Imperial College London, Czech Technical University in Prague (CTU), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
Subjects: Semidefinite programming, Semialgebraic set, Discrete mathematics, math.OC, moment relaxations, polynomial sum of squares, semidefinite programming, Semialgebraic sets, Theoretical Computer Science, Matrix polynomial, Combinatorics, Minimal polynomial (field theory), Optimization and Control (math.OC), Stable polynomial, Norm (mathematics), FOS: Mathematics, Degree of a polynomial, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Ball (mathematics), Mathematics - Optimization and Control, Software, Mathematics
Abstract: International audience; Given a compact semialgebraic set S of R^n and a polynomial map f from R^n to R^m, we consider the problem of approximating the image set F = f(S) in R^m. This includes in particular the projection of S on R^m for n greater than m. Assuming that F is included in a set B which is "simple'' (e.g. a box or a ball), we provide two methods to compute certified outer approximations of F. Method 1 exploits the fact that F can be defined with an existential quantifier, while Method 2 computes approximations of the support of image measures.The two methods output a sequence of superlevel sets defined with a single polynomial that yield explicit outer approximations of F. Finding the coefficients of this polynomial boils down to computing an optimal solution of a convex semidefinite program. We provide guarantees of strong convergence to F in L^1 norm on B, when the degree of the polynomial approximation tends to infinity. Several examples of applications are provided, together with numerical experiments.
Published: 2015

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

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

28. NLCertify: A Tool for Formal Nonlinear Optimization

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

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

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

30. Approximating Pareto Curves using Semidefinite Relaxations

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

31. Certification of inequalities involving transcendental functions: combining SDP and max-plus approximation

Author: Benjamin Werner, Stéphane Gaubert, Victor Magron, Xavier Allamigeon, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Max-plus algebras and mathematics of decision (MAXPLUS), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), and Types, Logic and computing (TYPICAL)
Subjects: Discrete mathematics, Semialgebraic set, 0209 industrial biotechnology, Approximation theory, 021103 operations research, Optimization problem, Branch and bound, Transcendental function, 0211 other engineering and technologies, 02 engineering and technology, Infimum and supremum, Combinatorics, Kepler conjecture, symbols.namesake, 020901 industrial engineering & automation, Optimization and Control (math.OC), symbols, FOS: Mathematics, Relaxation (approximation), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Mathematics
Abstract: We consider the problem of certifying an inequality of the form $f(x)\geq 0$, $\forall x\in K$, where $f$ is a multivariate transcendental function, and $K$ is a compact semialgebraic set. We introduce a certification method, combining semialgebraic optimization and max-plus approximation. We assume that $f$ is given by a syntaxic tree, the constituents of which involve semialgebraic operations as well as some transcendental functions like $\cos$, $\sin$, $\exp$, etc. We bound some of these constituents by suprema or infima of quadratic forms (max-plus approximation method, initially introduced in optimal control), leading to semialgebraic optimization problems which we solve by semidefinite relaxations. The max-plus approximation is iteratively refined and combined with branch and bound techniques to reduce the relaxation gap. Illustrative examples of application of this algorithm are provided, explaining how we solved tight inequalities issued from the Flyspeck project (one of the main purposes of which is to certify numerical inequalities used in the proof of the Kepler conjecture by Thomas Hales)., Comment: 7 pages, 3 figures, 3 tables, Appears in the Proceedings of the European Control Conference ECC'13, July 17-19, 2013, Zurich, pp. 2244--2250, copyright EUCA 2013
Published: 2013
Full Text: View/download PDF

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources

Refine your results

31 results on '"Victor MAGRON"'

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

2. Sums of squares representations on singular loci

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

4. Positivity certificates and polynomial optimization on non-compact semialgebraic sets

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

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

7. A Sublevel Moment-SOS Hierarchy for Polynomial Optimization

8. Exploiting Sparsity in Complex Polynomial Optimization

9. Certifying global optimality of AC-OPF solutions via sparse polynomial optimization

10. Dimension-free entanglement detection in multipartite Werner states

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

12. Noncommutative Christoffel-Darboux Kernels

13. The Constant Trace Property in Noncommutative Optimization

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

15. Sparse Noncommutative Polynomial Optimization

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

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

18. Computing the Hausdorff boundary measure of semi-algebraic sets

19. Exploiting term sparsity in Noncommutative Polynomial Optimization

20. Optimization over trace polynomials

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

22. Semidefinite Approximations of Invariant Measures for Polynomial Systems

23. Optimal data fitting: a moment approach

24. Semidefinite Approximations of Reachable Sets for Discrete-time Polynomial Systems

25. A Sums-of-Squares Extension of Policy Iterations

26. Semidefinite approximations of projections and polynomial images of semialgebraic sets

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

28. NLCertify: A Tool for Formal Nonlinear Optimization

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

30. Approximating Pareto Curves using Semidefinite Relaxations

31. Certification of inequalities involving transcendental functions: combining SDP and max-plus approximation

Catalog

Searchworks

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

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

31 results on '"Victor MAGRON"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources