Author: "European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015)"' showing total 59 results

Start Over Author "European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015)"

59 results on '"European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015)"'

1. VOLUME OF SUBLEVEL SETS OF HOMOGENEOUS POLYNOMIALS

Author: Lasserre, Jean B., É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, European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] (LAAS), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), 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)-Institut National Polytechnique [Toulouse] (INP)-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique [Toulouse] (INP), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Équipe Méthodes et Algorithmes en Commande ( LAAS-MAC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Toulouse III - Paul Sabatier ( UPS ), 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 ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), 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 ), and European Project : 666981,H2020,ERC-2014-ADG,TAMING ( 2015 )
Subjects: [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, Lebesgue integration, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Combinatorics, symbols.namesake, FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, Eigenvalues and eigenvectors, Mathematics, Semidefinite programming, Sequence, Level set (data structures), 021103 operations research, Algebra and Number Theory, Applied Mathematics, Computational geometry, Optimization and Control (math.OC), Homogeneous polynomial, [ INFO.INFO-CG ] Computer Science [cs]/Computational Geometry [cs.CG], symbols, Geometry and Topology, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Volume (compression)
Abstract: International audience; Consider the sub level set K := {x : g(x) ≤ 1} where g is a positive and homogeneous polynomial. We show that its Lebesgue volume can be approximated as closely as desired by solving a sequence of generalized eigenvalue problems with respect to a pair of Hankel matrices of increasing size, and whose entries are obtained in closed form.
Published: 2019
Full Text: View/download PDF

2. Optimal control problems with oscillations, concentrations and discontinuities

Author: Tillmann Weisser, Didier Henrion, Martin Kružík, É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), Institute of Information Theory and Automation of the Czech Academy of Sciences (UTIA / CAS), Czech Academy of Sciences [Prague] (CAS), 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, Équipe Méthodes et Algorithmes en Commande ( LAAS-MAC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Toulouse III - Paul Sabatier ( UPS ), 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 ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), 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 ), Institute of Information Theory and Automation, Academy of Sciences of the Czech Republic, and European Project : 666981,H2020,ERC-2014-ADG,TAMING ( 2015 )
Subjects: [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], Semidefinite programming, 0209 industrial biotechnology, Hierarchy (mathematics), Numerical analysis, 020208 electrical & electronic engineering, 02 engineering and technology, State (functional analysis), Classification of discontinuities, Optimal control, Signal, functional analysis, Discontinuity (linguistics), optimal control, 020901 industrial engineering & automation, Optimization and Control (math.OC), Control and Systems Engineering, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Applied mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Electrical and Electronic Engineering, optimization, Mathematics - Optimization and Control, Mathematics
Abstract: International audience; Optimal control problems with oscillations (chattering controls) and concentrations (impulsive controls) can have integral performance criteria such that concentration of the control signal occurs at a discontinuity of the state signal. Techniques from functional analysis (anisotropic parametrized measures) are applied to give a precise meaning of the integral cost and to allow for the sound application of numerical methods. We show how this can be combined with the Lasserre hierarchy of semidefinite programming relaxations.
Published: 2018
Full Text: View/download PDF

3. Positive functionals and Hessenberg matrices

Author: Mihai Putinar, 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), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), University of California [Santa Barbara] (UC Santa Barbara), University of California (UC), 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, 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), University of California [Santa Barbara] (UCSB), University of California, Équipe Méthodes et Algorithmes en Commande ( LAAS-MAC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Mathématiques de Toulouse UMR5219 ( IMT ), Centre National de la Recherche Scientifique ( CNRS ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -PRES Université de Toulouse-Université Paul Sabatier - Toulouse 3 ( UPS ) -Université Toulouse - Jean Jaurès ( UT2J ) -Université Toulouse 1 Capitole ( UT1 ), University of California [Santa Barbara], and European Project : 666981,H2020,ERC-2014-ADG,TAMING ( 2015 )
Subjects: [ MATH.MATH-CV ] Mathematics [math]/Complex Variables [math.CV], Pure mathematics, Cubature formula, Normal matrices, Analyse Fonctionnelle, General Mathematics, [ MATH.MATH-FA ] Mathematics [math]/Functional Analysis [math.FA], Harmonic polynomial, [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], 01 natural sciences, Measure (mathematics), Normal matrix, Dilation (operator theory), Matrix (mathematics), 0103 physical sciences, FOS: Mathematics, Matrix analysis, Complex Variables (math.CV), 0101 mathematics, Mathematics, Variable (mathematics), Mathematics - Complex Variables, Applied Mathematics, 010102 general mathematics, [MATH.MATH-CV]Mathematics [math]/Complex Variables [math.CV], Functional Analysis (math.FA), Hessenberg matrix, Hessenberg matrices, Mathematics - Functional Analysis, 47B20 65D32, 010307 mathematical physics
Abstract: Not every positive functional defined on bi-variate polynomials of a prescribed degree bound is represented by the integration against a positive measure. We isolate a couple of conditions filling this gap, either by restricting the class of polynomials to harmonic ones, or imposing the vanishing of a defect indicator. Both criteria offer constructive cubature formulas and they are obtained via well known matrix analysis techniques involving either the dilation of a contractive matrix to a unitary one or the specific structure of the Hessenberg matrix associated to the multiplier by the underlying complex variable., To appear in Proc. Amer. Math. Soc
Published: 2018
Full Text: View/download PDF

4. Linear conic optimization for inverse optimal control

Author: Jean B. Lasserre, Edouard Pauwels, Didier Henrion, Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-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)-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é de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), 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)-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), Czech Technical University in Prague (CTU), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), 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), 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-Centre National de la Recherche Scientifique (CNRS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), 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)-Institut National Polytechnique (Toulouse) (Toulouse INP), Centre National de la Recherche Scientifique (CNRS)-PRES Université de Toulouse-Université Toulouse III - Paul Sabatier (UT3), 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 1 Capitole (UT1), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Institut de recherche en informatique de Toulouse ( IRIT ), Institut National Polytechnique [Toulouse] ( INP ) -Université Toulouse 1 Capitole ( UT1 ) -Université Toulouse - Jean Jaurès ( UT2J ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Mathématiques de Toulouse UMR5219 ( IMT ), Centre National de la Recherche Scientifique ( CNRS ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -PRES Université de Toulouse-Université Paul Sabatier - Toulouse 3 ( UPS ) -Université Toulouse - Jean Jaurès ( UT2J ) -Université Toulouse 1 Capitole ( UT1 ), Équipe Méthodes et Algorithmes en Commande ( LAAS-MAC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Czech Technical University in Prague ( CTU ), and European Project : 666981,H2020,ERC-2014-ADG,TAMING ( 2015 )
Subjects: [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], 0209 industrial biotechnology, Mathematical optimization, Control and Optimization, Linear programming, Context (language use), 02 engineering and technology, 01 natural sciences, 020901 industrial engineering & automation, conic duality, polynomial optimization, FOS: Mathematics, Relevance (information retrieval), 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, Applied Mathematics, 010102 general mathematics, Inverse problem, semidefinite programming, inverse optimal control, 16. Peace & justice, Identification (information), Optimization and Control (math.OC), Complementarity (molecular biology), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Conic optimization
Abstract: International audience; We address the inverse problem of Lagrangian identification based on trajecto-ries in the context of nonlinear optimal control. We propose a general formulation of the inverse problem based on occupation measures and complementarity in linear programming. The use of occupation measures in this context offers several advan-tages from the theoretical, numerical and statistical points of view. We propose an approximation procedure for which strong theoretical guarantees are available. Finally, the relevance of the method is illustrated on academic examples.
Published: 2016
Full Text: View/download PDF

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

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. Moments and convex optimization for analysis and control of nonlinear partial differential equations

Author: Korda, Milan, Henrion, Didier, Lasserre, Jean-Bernard, UCSB (UCSB), University of California [Santa Barbara] (UC Santa Barbara), University of California (UC)-University of California (UC), É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), České Vysoké Učení Technické (CVUT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Elsevier, and European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015)
Subjects: MathematicsofComputing_NUMERICALANALYSIS, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Semidefinite programming, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Partial differential equations, Optimal control, Convex optimization, Occupation measure
Abstract: This work presents a convex-optimization-based framework for analysis and control of nonlinear partial differential equations. The approach uses a particular weak embedding of the nonlinear PDE, resulting in a linear equation in the space of Borel measures. This equation is then used as a constraint of an infinite-dimensional linear programming problem (LP). This LP is then approximated by a hierarchy of convex, finite-dimensional, semidefinite programming problems (SDPs). In the case of analysis of uncontrolled PDEs, the solutions to these SDPs provide bounds on a specified, possibly nonlinear, functional of the solutions to the PDE; in the case of PDE control, the solutions to these SDPs provide bounds on the optimal value of a given optimal control problem as well as suboptimal feedback controllers. The entire approach is based purely on convex optimization and does not rely on spatio-temporal gridding, even though the PDE addressed can be fully nonlinear. The approach is applicable to a very broad class nonlinear PDEs with polynomial data. Computational complexity is analyzed and several complexity reduction procedures are described. Numerical examples demonstrate the approach.
Published: 2022

8. Semi-algebraic approximation using Christoffel-Darboux kernel

Author: Didier Henrion, Edouard Pauwels, Swann Marx, Tillmann Weisser, Jean B. Lasserre, Laboratoire des Sciences du Numérique de Nantes (LS2N), 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), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-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)-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é de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), 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), Atlanstic 2020, Research, Education and Innovation in Pays de la Loire, supported by the French Region Pays de la Loire and the European Regional Development Fund, 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: 666981,H2020,ERC-2014-ADG,TAMING(2015), Université Toulouse 1 Capitole (UT1)-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-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)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), 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), 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), and Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1)
Subjects: Polynomial, or- thogonal polynomials, convex optimization, General Mathematics, 010103 numerical & computational mathematics, Lebesgue integration, 01 natural sciences, Gibbs phenomenon, orthogonal polynomials 42C05, symbols.namesake, FOS: Mathematics, Applied mathematics, Almost everywhere, 0101 mathematics, approximation theory, Mathematics - Optimization and Control, orthogonal polynomials, Mathematics, Pointwise convergence, Approximation theory, 010102 general mathematics, Function (mathematics), 16. Peace & justice, Computational Mathematics, 47B32, positive polynomials, Optimization and Control (math.OC), symbols, Piecewise, 41A30 Contents, moments, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Analysis
Abstract: International audience; We provide a new method to approximate a (possibly discontinuous) function using Christoffel-Darboux kernels. Our knowledge about the unknown multivariate function is in terms of finitely many moments of the Young measure supported on the graph of the function. Such an input is available when approximating weak (or measure-valued) solution of optimal control problems, entropy solutions to non-linear hyperbolic PDEs, or using numerical integration from finitely many evaluations of the function. While most of the existing methods construct a piecewise polynomial approximation, we construct a semi-algebraic approximation whose estimation and evaluation can be performed efficiently. An appealing feature of this method is that it deals with non-smoothness implicitly so that a single scheme can be used to treat smooth or non-smooth functions without any prior knowledge. On the theoretical side, we prove pointwise convergence almost everywhere as well as convergence in the Lebesgue one norm under broad assumptions. Using more restrictive assumptions, we obtain explicit convergence rates. We illustrate our approach on various examples from control and approximation. In particular we observe empirically that our method does not suffer from the the Gibbs phenomenon when approximating discontinuous functions.
Published: 2021
Full Text: View/download PDF

9. Distributionally robust polynomial chance-constraints under mixture ambiguity sets

Author: Tillmann Weisser, 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), 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), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: Polynomial (hyperelastic model), 021103 operations research, Degree (graph theory), Lebesgue measure, General Mathematics, chance-constraints, Dimension (graph theory), 0211 other engineering and technologies, distributionally robust, probabilistic constraints, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Omega, Combinatorics, Compact space, Optimization and Control (math.OC), FOS: Mathematics, Probability distribution, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, Mathematics - Optimization and Control, semidefinite relaxations, Software, Mathematics
Abstract: Given $${\mathbf {X}}\subset {\mathbb {R}}^n$$ , $$\varepsilon \in (0,1)$$ , a parametrized family of probability distributions $$(\mu _{{\mathbf {a}}})_{{\mathbf {a}}\in {\mathbf {A}}}$$ on $${\varvec{\Omega }}\subset {\mathbb {R}}^p$$ , we consider the feasible set $${\mathbf {X}}^*_\varepsilon \subset {\mathbf {X}}$$ associated with the distributionally robust chance-constraint $$\begin{aligned} {\mathbf {X}}^*_\varepsilon \,=\,\{{\mathbf {x}}\in {\mathbf {X}}:\,\mathrm{Prob}_\mu [f({\mathbf {x}},{\omega })\,>\,0]> 1-\varepsilon ,\,\forall \mu \in {\mathscr {M}}_{\mathbf {a}}\}, \end{aligned}$$ where $${\mathscr {M}}_{\mathbf {a}}$$ is the set of all possibles mixtures of distributions $$\mu _{\mathbf {a}}$$ , $${\mathbf {a}}\in {\mathbf {A}}$$ . For instance and typically, the family $${\mathscr {M}}_{\mathbf {a}}$$ is the set of all mixtures of Gaussian distributions on $${\mathbb {R}}$$ with mean and standard deviation $${\mathbf {a}}=(a,\sigma )$$ in some compact set $${\mathbf {A}}\subset {\mathbb {R}}^2$$ . We provide a sequence of inner approximations $${\mathbf {X}}^d_\varepsilon =\{{\mathbf {x}}\in {\mathbf {X}}:w_d({\mathbf {x}})
Published: 2019
Full Text: View/download PDF

10. Exploiting Sparsity for Semi-Algebraic Set Volume Computation

Author: Didier Henrion, Tillmann Weisser, Matteo Tacchi, 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), Réseau de Transport d'Electricité [Paris] (RTE), Los Alamos National Laboratory (LANL), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Faculty of Electrical Engineering [Prague] (FEL CTU), Czech Technical University in Prague (CTU), Doctorate fellowship of M. Tacchi was supported by RTE Company, 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, 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), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), 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), Czech Technical University in Prague, Faculty of Electrical Engineering, and Department of Control Engineering
Subjects: 021103 operations research, Hierarchy (mathematics), Lebesgue measure, Linear programming, Applied Mathematics, Numerical analysis, Computation, 0211 other engineering and technologies, Volume (computing), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Moment problem, Set (abstract data type), Computational Mathematics, Computational Theory and Mathematics, 010201 computation theory & mathematics, Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Algorithm, Mathematics - Optimization and Control, Analysis, Mathematics
Abstract: International audience; We provide a systematic deterministic numerical scheme to approximate the volume (i.e. the Lebesgue measure) of a basic semi-algebraic set whose description follows a sparsity pattern. As in previous works (without sparsity), the underlying strategy is to consider an infinite-dimensional linear program on measures whose optimal value is the volume of the set. This is a particular instance of a generalized moment problem which in turn can be approximated as closely as desired by solving a hierarchy of semidefinite relaxations of increasing size. The novelty with respect to previous work is that by exploiting the sparsity pattern we can provide a sparse formulation for which the associated semidefinite relaxations are of much smaller size. In addition, we can decompose the sparse relaxations into completely decoupled subproblems of smaller size, and in some cases computations can be done in parallel. To the best of our knowledge, it is the first contribution that exploits sparsity for volume computation of semi-algebraic sets which are possibly high-dimensional and/or non-convex and/or non-connected.
Published: 2021
Full Text: View/download PDF

11. Convex computation of extremal invariant measures of nonlinear dynamical systems and Markov processes

Author: Milan Korda, Didier Henrion, Igor Mezic, É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), Faculty of Electrical Engineering [Prague] (FEL CTU), Czech Technical University in Prague (CTU), Department of Mechanical Engineering [Santa Barbara], University of California [Santa Barbara] (UC Santa Barbara), University of California (UC)-University of California (UC), TAM, European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), University of California [Santa Barbara] (UCSB), University of California-University of California, Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Czech Technical University in Prague, Faculty of Electrical Engineering, Department of Control Engineering, Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: convex optimization, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], Markov process, Dynamical Systems (math.DS), 01 natural sciences, Measure (mathematics), 010305 fluids & plasmas, Invariant measure, physical measure, symbols.namesake, 0103 physical sciences, FOS: Mathematics, Applied mathematics, Ergodic theory, 0101 mathematics, Invariant (mathematics), Mathematics - Dynamical Systems, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, Applied Mathematics, Feasible region, General Engineering, ergodic optimization, 010101 applied mathematics, Optimization and Control (math.OC), Modeling and Simulation, Convex optimization, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: We propose a convex-optimization-based framework for computation of invariant measures of polynomial dynamical systems and Markov processes, in discrete and continuous time. The set of all invariant measures is characterized as the feasible set of an infinite-dimensional linear program (LP). The objective functional of this LP is then used to single out a specific measure (or a class of measures) extremal with respect to the selected functional such as physical measures, ergodic measures, atomic measures (corresponding to, e.g., periodic orbits) or measures absolutely continuous w.r.t. to a given measure. The infinite-dimensional LP is then approximated using a standard hierarchy of finite-dimensional semidefinite programming problems, the solutions of which are truncated moment sequences, which are then used to reconstruct the measure. In particular, we show how to approximate the support of the measure as well as how to construct a sequence of weakly converging absolutely continuous approximations. As a by-product, we present a simple method to certify the nonexistence of an invariant measure, which is an important question in the theory of Markov processes. The presented framework, where a convex functional is minimized or maximized among all invariant measures, can be seen as a generalization of and a computational method to carry out the so-called ergodic optimization, where linear functionals are optimized over the set of invariant measures. Finally, we also describe how the presented framework can be adapted to compute eigenmeasures of the Perron–Frobenius operator.
Published: 2021
Full Text: View/download PDF

12. The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs

Author: Henrion, Didier, Korda, Milan, Lasserre, Jean-Bernard, 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 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), World Scientific, ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(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, 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), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)
Subjects: Positive Polynomials, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Moment problems, Statistics, Control, Non Linear PDEs, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [STAT.CO]Statistics [stat]/Computation [stat.CO], Computational geometry, Probability
Abstract: International audience; The moment-SOS hierarchy is a powerful methodology that is used to solve the Generalized Moment Problem (GMP) where the list of applications in various areas of Science and Engineering is almost endless. Initially designed for solving polynomial optimization problems (the simplest example of the GMP), it applies to solving any instance of the GMP whose description only involves semi-algebraic functions and sets. It consists of solving a sequence (a hierarchy) of convex relaxations of the initial problem, and each convex relaxation is a semidefinite program whose size increases in the hierarchy. The goal of this book is to describe in a unified and detailed manner how this methodology applies to solving various problems in different areas ranging from Optimization, Probability, Statistics, Signal Processing, Computational Geometry, Control, Optimal Control and Analysis of a certain class of nonlinear PDEs. For each application, this unconventional methodology differs from traditional approaches and provides an unusual viewpoint. Each chapter is devoted to a particular application, where the methodology is thoroughly described and illustrated on some appropriate examples. The exposition is kept at an appropriate level of detail to aid the different levels of readers not necessarily familiar with these tools, to better know and understand this methodology
Published: 2020
Full Text: View/download PDF

13. Determining projection constants of univariate polynomial spaces

Author: Simon Foucart, Jean B. Lasserre, Department of Mathematics [Texas A&M University], Texas A&M University [College Station], É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, NSF Grant DMS 1622134, 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: AMS classification: 41A44, Polynomial, Pure mathematics, projection constant, General Mathematics, 65K05, 010103 numerical & computational mathematics, 90C22, [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], programming, 01 natural sciences, Upper and lower bounds, 90C47, Projection (mathematics), Quartic function, FOS: Mathematics, Mathematics - Numerical Analysis, Uniqueness, 0101 mathematics, 41A44 65K05 90C22 90C47, Mathematics - Optimization and Control, Mathematics, Numerical Analysis, method of moments, semidefinite, Applied Mathematics, 010102 general mathematics, Univariate, linear programming, Numerical Analysis (math.NA), Functional Analysis (math.FA), Quintic function, Mathematics - Functional Analysis, Minimal projection, Optimization and Control (math.OC), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Constant (mathematics), [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Analysis
Abstract: International audience; The long-standing problem of minimal projections is addressed from a computational point of view. Techniques to determine bounds on the projection constants of univariate polynomial spaces are presented. The upper bound, produced by a linear program, and the lower bound, produced by a semidefinite program exploiting the method of moments, are often close enough to deduce the projection constant with reasonable accuracy. The implementation of these programs makes it possible to find the projection constant of several three-dimensional spaces with five digits of accuracy, as well as the projection constants of the spaces of cubic, quartic, and quintic polynomials with four digits of accuracy. Beliefs about uniqueness and shape-preservation of minimal projections are contested along the way.
Published: 2018
Full Text: View/download PDF

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

15. NONNEGATIVE FORMS WITH SUBLEVEL SETS OF MINIMAL VOLUME

Author: Jean B. Lasserre, Khazhgali Kozhasov, Technische Universität Braunschweig = Technical University of Braunschweig [Braunschweig], Institut für Analysis und Algebra (IAA), É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), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Technische Universität Braunschweig [Braunschweig], Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), 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), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)
Subjects: General Mathematics, 010103 numerical & computational mathematics, 01 natural sciences, Combinatorics, Mathematics - Algebraic Geometry, FOS: Mathematics, 49Q10, 65K10, 90C25, 26B15, 28A75, 97G30, 0101 mathematics, Algebraic Geometry (math.AG), Mathematics - Optimization and Control, Gramian matrix, Mathematics, Bombieri norm, Numerical analysis, 010102 general mathematics, Probabilistic logic, Explained sum of squares, Functional Analysis (math.FA), Mathematics - Functional Analysis, sublevel sets, orthogonally invariant norms, Optimization and Control (math.OC), Bounded function, Norm (mathematics), Nonnegative homogeneous polynomials, Minimal volume, Lebesgue volume, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], extremal properties, Software
Abstract: We show that the Euclidean ball has the smallest volume among sublevel sets of nonnegative forms of bounded Bombieri norm as well as among sublevel sets of sum of squares forms whose Gram matrix has bounded Frobenius or nuclear (or, more generally, p-Schatten) norm. These volume-minimizing properties of the Euclidean ball with respect to its representation (as a sublevel set of a form of fixed even degree) complement its numerous intrinsic geometric properties. We also provide a probabilistic interpretation of the results.
Published: 2020
Full Text: View/download PDF

16. Data analysis from empirical moments and the Christoffel function

Author: Mihai Putinar, Edouard Pauwels, Jean B. Lasserre, Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), 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)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, University of California [Santa Barbara] (UCSB), University of California, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), 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), 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), 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-Centre National de la Recherche Scientifique (CNRS), PNRIA, ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-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)-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é de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), University of California [Santa Barbara] (UC Santa Barbara), University of California (UC), 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)-Centre National de la Recherche Scientifique (CNRS), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UPS)
Subjects: FOS: Computer and information sciences, data analysis, 62G05 62G07 68T05 58C35 46E22 42C05 47B32, Numerical & Computational Mathematics, Machine Learning (stat.ML), Moment matrix, 010103 numerical & computational mathematics, 01 natural sciences, Measure (mathematics), Mathematical Sciences, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Simple (abstract algebra), Information and Computing Sciences, Christoffel-Darboux kernel, Real algebraic geometry, 0101 mathematics, Empirical measure, Reproducing kernel Hilbert spaces, orthogonal polynomials, Mathematics, Approximation theory, Christoffel symbols, Applied Mathematics, Function (mathematics), Manifold, stat.ML, Algebra, Computational Mathematics, Density estimation, Computational Theory and Mathematics, Support inference, Orthogonal polynomials, Christoffel function, Analysis
Abstract: International audience; Spectral features of the empirical moment matrix constitute a resourceful tool for unveiling properties of a cloud of points, among which, density, support and latent structures. It is already well known that the empirical moment matrix encodes a great deal of subtle attributes of the underlying measure. Starting from this object as base of observations we combine ideas from statistics, real algebraic geometry, orthogonal polynomials and approximation theory for opening new insights relevant for Machine Learning (ML) problems with data supported on singular sets. Refined concepts and results from real algebraic geometry and approximation theory are empowering a simple tool (the empirical moment matrix) for the task of solving non-trivial questions in data analysis. We provide (1) theoretical support, (2) numerical experiments and, (3) connections to real world data as a validation of the stamina of the empirical moment matrix approach.
Published: 2020
Full Text: View/download PDF

17. CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization

Author: Wang, Jie, Magron, Victor, Lasserre, Jean, Mai, Ngoc Hoang Anh, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Equipe Polynomial OPtimization (LAAS-POP), PNRIA, 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), 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, European Project: 813211,H2020,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, and Taming non convexity? - TAMING - - H20202015-09-01 - 2019-09-01 - 666981 - VALID
Subjects: FOS: Computer and information sciences, [INFO.INFO-MS] Computer Science [cs]/Mathematical Software [cs.MS], Optimization and Control (math.OC), Applied Mathematics, FOS: Mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Computer Science - Mathematical Software, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Mathematical Software (cs.MS), Software, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract: This work proposes a new moment-SOS hierarchy, called CS-TSSOS, for solving large-scale sparse polynomial optimization problems. Its novelty is to exploit simultaneously correlative sparsity and term sparsity by combining advantages of two existing frameworks for sparse polynomial optimization. The former is due to Waki et al. while the latter was initially proposed by Wang et al. and later exploited in the TSSOS hierarchy. In doing so we obtain CS-TSSOS -- a two-level hierarchy of semidefinite programming relaxations with (i), the crucial property to involve blocks of SDP matrices and (ii), the guarantee of convergence to the global optimum under certain conditions. We demonstrate its efficiency and scalability on several large-scale instances of the celebrated Max-Cut problem and the important industrial optimal power flow problem, involving up to six thousand variables and tens of thousands of constraints., Comment: 28 pages, 8 figures, 8 tables
Published: 2020
Full Text: View/download PDF

18. Connecting optimization with spectral analysis of tri-diagonal matrices

Author: Jean B. Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse 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), PNRIA, ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(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, 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), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), and ANR-19-PI3A-0004,ANITI,'Investing for the Future – PIA3'
Subjects: General Mathematics, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Combinatorics, Diagonal matrix, FOS: Mathematics, Symmetric matrix, Mathematics - Numerical Analysis, 0101 mathematics, Global optimization, Mathematics - Optimization and Control, orthogonal polynomials, Eigenvalues and eigenvectors, Mathematics, 021103 operations research, tri-diagonal matrices, Continuous function, global optimization, 90C22 65F15 42C05 58C40, Numerical Analysis (math.NA), Compact space, Optimization and Control (math.OC), Linear algebra, Orthogonal polynomials, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], hierarchy of upper bounds, Software, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: International audience; We show that the global minimum (resp. maximum) of a continuous function on a compact set can be approximated from above (resp. from below) by computing the smallest (rest. largest) eigenvalue of a hierarchy of (r × r) tri-diagonal univariate moment matrices of increasing size. Equivalently it reduces to computing the smallest (resp. largest) root of a certain univariate degree-r orthonormal polynomial. This provides a strong connection between the fields of optimization, orthogonal polynomials, numerical analysis and linear algebra, via asymptotic spectral analysis of tri-diagonal symmetric matrices.
Published: 2020
Full Text: View/download PDF

19. Maximal Positively Invariant Set Determination for Transient Stability Assessment in Power Systems

Author: Carmen Cardozo, Didier Henrion, Patrick Pantiatici, Antoine Oustry, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Réseau de Transport d'Electricité [Paris] (RTE), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Faculty of Electrical Engineering [Prague] (FEL CTU), Czech Technical University in Prague (CTU), 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: 0209 industrial biotechnology, transient stability, convex optimization, Computer science, Lasserre's relaxation, 02 engineering and technology, [SPI.AUTO]Engineering Sciences [physics]/Automatic, symbols.namesake, Electric power system, power systems, 020901 industrial engineering & automation, moment-sum-of-squares hierarchy, 0202 electrical engineering, electronic engineering, information engineering, Taylor series, Applied mathematics, Time domain, Invariant (mathematics), Transient stability assessment, 020208 electrical & electronic engineering, [SPI.NRJ]Engineering Sciences [physics]/Electric power, invariant sets, Invariant (physics), Convex optimization, symbols, occupation measures, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Synchronous motor
Abstract: International audience; This paper assesses the transient stability of a synchronous machine connected to an infinite bus through the notion of invariant sets. The problem of computing a conservative approximation of the maximal positive invariant set is formulated as a semi-definitive program based on occupation measures and Lasserre's relaxation. An extension of the proposed method into a robust formulation allows us to handle Taylor approximation errors for non-polynomial systems. Results show the potential of this approach to limit the use of extensive time domain simulations provided that scalability issues are addressed.
Published: 2019
Full Text: View/download PDF

20. Simple Formula for Integration of Polynomials on a Simplex

Author: Jean B. Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse 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), 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, 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), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)
Subjects: Polynomial, Pure mathematics, Computer Networks and Communications, Laplace transform, Homogeneous function, 010103 numerical & computational mathematics, 01 natural sciences, symbols.namesake, Simple (abstract algebra), Convex polytope, Classical Analysis and ODEs (math.CA), FOS: Mathematics, Mathematics - Numerical Analysis, 0101 mathematics, Mathematics, Simplex, Degree (graph theory), Lebesgue measure, Applied Mathematics, Numerical Analysis (math.NA), [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], 010101 applied mathematics, Computational Mathematics, Mathematics - Classical Analysis and ODEs, Numerical integration, symbols, convex polytope, 65D30 78M12 44A10, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], simplex, Software, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: We show that integrating a polynomial of degree t on an arbitrary simplex (with respect to Lebesgue measure) reduces to evaluating t homogeneous polynomials of degree j = 1, 2,. .. , t, each at a unique point $\xi$ j of the simplex. This new and very simple formula can be exploited in finite (and extended finite) element methods, as well as in other applications where such integrals are needed., Comment: To appear in BIT Numerical Mathematics
Published: 2019
Full Text: View/download PDF

21. Connecting optimization with spectral analysis of tri-diagonal (univariate) moment matrices

Author: Lasserre, Jean-Bernard, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), and European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015)
Subjects: tri-diagonal matrices, global optimization, 90C22 65F15 42C05 58C40, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], orthogonal polynomials, hierarchy of upper bounds
Abstract: We show that the global minimum (resp. maximum) of a continuous function on a compact set can be approximated from above (resp. from below) by computing the smallest (rest. largest) eigenvalue of a hierarchy of (r × r) tri-diagonal univariate moment matrix of increasing size. Equivalently it reduces to computing the smallest (resp. largest) root of a certain univariate degree-r orthonormal polynomial. This provides a strong connection between the fields of optimization, orthogonal poly-nomials, numerical analysis and linear algebra, via asymptotic spectral analysis of tri-diagonal symmetric matrices.
Published: 2019

22. Connecting optimization with spectral analysis of tri-diagonal Hankel matrices

Author: Lasserre, Jean-Bernard, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] (LAAS), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), 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)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), Université Fédérale Toulouse Midi-Pyrénées, European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Institut National Polytechnique (Toulouse) (Toulouse INP), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UPS), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)
Subjects: tri-diagonal Hankel matrices, global optimization, 90C22 65F15 42C05 58C40, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], hierarchy of upper bounds, orthogonal polynomials
Abstract: We show that the global minimum (resp. maximum) of a continuous function on a compact set can be approximated from above (resp. from below) by computing the smallest (rest. largest) eigenvalue of a hierarchy of (r × r) tri-diagonal Hankel matrix of increasing size. Equivalently it reduces to computing the smallest (resp. largest) root of a certain univariate degree-r orthonormal polynomial. This provides a strong connection between the fields of optimization, orthogonal poly-nomials, numerical analysis and linear algebra, via asymptotic spectral analysis of tri-diagonal Hankel matrices.
Published: 2019

23. Volume of sub-level sets of polynomials

Author: Jean B. Lasserre, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse 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: 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), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: 0209 industrial biotechnology, Sequence, 020208 electrical & electronic engineering, 02 engineering and technology, Extension (predicate logic), 16. Peace & justice, Lebesgue integration, Combinatorics, Set (abstract data type), symbols.namesake, 020901 industrial engineering & automation, Homogeneous polynomial, 0202 electrical engineering, electronic engineering, information engineering, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Eigenvalues and eigenvectors, Mathematics, Volume (compression)
Abstract: Consider the sub-level set $\mathbf{K}:=\{\mathrm{x}:g(\mathrm{x})\leq 1\}$ of a nonnegative homogeneous polynomial $g$ . We show that its Lebesgue volume vol(K) can be approximated as closely as desired by solving a sequence of generalized eigenvalue problems with respect to a pair of Hankel matrices of increasing size, whose entries are obtained in closed form. An extension to the non-homogeneous case is also briefly described.
Published: 2019
Full Text: View/download PDF

24. The empirical Christoffel function with applications in data analysis

Author: Edouard Pauwels, Jean B. Lasserre, Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), 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), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, 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), and Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Christoffel symbols, education.field_of_study, Applied Mathematics, 010102 general mathematics, Population, Support, 01 natural sciences, Novelty detection, Machine Learning (cs.LG), 010104 statistics & probability, Computational Mathematics, Counting measure, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Outlier, Applied mathematics, Affine transformation, 0101 mathematics, education, Finite set, Mathematics
Abstract: International audience; We illustrate the potential applications in machine learning of theChristoffel function, or more precisely, its empirical counterpart associatedwith a counting measure uniformly supported on a finite set of points.Firstly, we provide a thresholding scheme which allows to approximatethe support of a measure from a finite subset of its moments with strongasymptotic guaranties. Secondly, we provide a consistency result whichrelates the empirical Christoffel function and its population counterpartin the limit of large samples. Finally, we illustrate the relevance of ourresults on simulated and real world datasets for several applications instatistics and machine learning: (a) density and support estimation fromfinite samples, (b) outlier and novelty detection and (c) affine matching
Published: 2019
Full Text: View/download PDF

25. Tractable semi-algebraic approximation using Christoffel-Darboux kernel

Author: Marx, Swann, Pauwels, Edouard, Weisser, Tillmann, Henrion, Didier, Lasserre, Jean, Laboratoire d'analyse et d'architecture des systèmes (LAAS), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), 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)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), and European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015)
Subjects: convex optimization, positive polynomials, moments, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], approximation theory, orthogonal polynomials
Abstract: We provide a new method to approximate a (possibly discontinuous) function using Christoffel-Darboux kernels. Our knowledge about the unknown multivariate function is in terms of finitely many moments of the Young measure supported on the graph of the function. Such an input is available when approximating weak (or measure-valued) solution of optimal control problems, entropy solutions to non-linear hyperbolic PDEs, or using numerical integration from finitely many evaluations of the function. While most of the existing methods construct a piecewise polynomial approximation, we construct a semi-algebraic approximation whose estimation and evaluation can be performed efficiently. An appealing feature of this method is that it deals with non-smoothness implicitly so that a single scheme can be used to treat smooth or non-smooth functions without any prior knowledge. On the theoretical side, we prove pointwise convergence almost everywhere as well as convergence in the Lebesgue one norm under broad assumptions. Using more restrictive assumptions, we obtain explicit convergence rates. We illustrate our approach on various examples from control and approximation. In particular we observe empirically that our method does not suffer from the the Gibbs phenomenon when approximating discontinuous functions.
Published: 2019

26. SPECTRA – a Maple library for solving linear matrix inequalities in exact arithmetic

Author: Din, Mohab Safey El, Henrion, Didier, Naldi, Simone, Safey, Mohab, Din, El, É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), Czech Technical University in Prague (CTU), Technische Universität Dortmund [Dortmund] (TU), 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), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: FOS: Computer and information sciences, Computer Science - Symbolic Computation, Control and Optimization, MathematicsofComputing_NUMERICALANALYSIS, Linear matrix inequalities, 010103 numerical & computational mathematics, Symbolic Computation (cs.SC), Linear matrix, engineering.material, 01 natural sciences, Mathematics - Algebraic Geometry, Polynomial sums of squares, Symbolic computation, Real algebraic geometry, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Computer Science::Symbolic Computation, Semidefinite programming, 0101 mathematics, Algebra over a field, Arithmetic, Algebraic Geometry (math.AG), Mathematics - Optimization and Control, Mathematics, Discrete mathematics, Maple, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Applied Mathematics, 010102 general mathematics, Degenerate energy levels, Algebra, Optimization and Control (math.OC), engineering, Computer algebra, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Software, Low rank matrices
Abstract: This document describes our freely distributed Maple library {\sc spectra}, for Semidefinite Programming solved Exactly with Computational Tools of Real Algebra. It solves linear matrix inequalities with symbolic computation in exact arithmetic and it is targeted to small-size, possibly degenerate problems for which symbolic infeasibility or feasibility certificates are required., Significantly extended version
Published: 2019
Full Text: View/download PDF

27. Semidefinite Relaxations for Lebesgue and Gaussian Measures of Unions of Basic Semialgebraic Sets

Author: Youssouf Emin, 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), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), École polytechnique (X), 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, 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), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)
Subjects: Semidefinite programming, Discrete mathematics, convex optimization, General Mathematics, Gaussian, Management Science and Operations Research, semidefinite programming, 44A60 28A75 90C05 90C22, 16. Peace & justice, Lebesgue integration, Lebesgue and Gaussian measure, Computer Science Applications, symbols.namesake, semi-algebraic sets, Scheme (mathematics), moment problem and sums of squares, Convex optimization, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Borel measure, Mathematics
Abstract: Given a finite Borel measure [Formula: see text] on [Formula: see text] and basic semialgebraic sets [Formula: see text], [Formula: see text], we provide a systematic numerical scheme to approximate as closely as desired [Formula: see text], when all moments of [Formula: see text] are available (and finite). More precisely, we provide a hierarchy of semidefinite programs whose associated sequence of optimal values is monotone and converges to the desired value from above. The same methodology applied to the complement [Formula: see text] provides a monotone sequence that converges to the desired value from below. When [Formula: see text] is the Lebesgue measure, we assume that [Formula: see text] is compact and contained in a known box [Formula: see text], and in this case the complement is taken to be [Formula: see text]. In fact, not only [Formula: see text] but also every finite vector of moments of [Formula: see text] (the restriction of [Formula: see text] on [Formula: see text]) can be approximated as closely as desired and so permits to approximate the integral on [Formula: see text] of any given polynomial.
Published: 2019
Full Text: View/download PDF

28. Inner approximations of the maximal positively invariant set for polynomial dynamical systems

Author: Antoine Oustry, Matteo Tacchi, Didier Henrion, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Réseau de Transport d'electricite (RTE), Réseau de Transport d'Electricité [Paris] (RTE), Faculty of Electrical Engineering [Prague] (FEL CTU), 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, Laboratoire d'analyse et d'architecture des systèmes [Toulouse] (LAAS), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), 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)-Institut National Polytechnique [Toulouse] (INP)-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique [Toulouse] (INP), Réseau de Transport d'Electricité-RTE, Czech Technical University in Prague, Faculty of Electrical Engineering, Department of Control Engineering, Laboratoire d'informatique de l'École polytechnique [Palaiseau] ( LIX ), Centre National de la Recherche Scientifique ( CNRS ) -École polytechnique ( X ), Équipe Méthodes et Algorithmes en Commande ( LAAS-MAC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), 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 ) -Institut National Polytechnique [Toulouse] ( INP ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Institut National Polytechnique [Toulouse] ( INP ), and Réseau de Transport d'electricite ( RTE )
Subjects: [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], 0209 industrial biotechnology, Control and Optimization, Dynamical systems theory, Approximations of π, 0211 other engineering and technologies, 02 engineering and technology, Systems and Control (eess.SY), Electrical Engineering and Systems Science - Systems and Control, 020901 industrial engineering & automation, [INFO.INFO-SY]Computer Science [cs]/Systems and Control [cs.SY], FOS: Mathematics, FOS: Electrical engineering, electronic engineering, information engineering, Mathematics - Optimization and Control, Mathematics, 021103 operations research, Polynomial vector fields, Mathematical analysis, Linear matrix inequality, Invariant (physics), Control and Systems Engineering, Optimization and Control (math.OC), [ INFO.INFO-SY ] Computer Science [cs]/Systems and Control [cs.SY], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Finite time, Polynomial dynamical systems
Abstract: International audience; The Lasserre or moment-sum-of-square hierarchy of linear matrix inequality relaxations is used to compute inner approximations of the maximal positively invariant set for continuous-time dynamical systems with polynomial vector fields. Convergence in volume of the hierarchy is proved under a technical growth condition on the average exit time of trajectories. Our contribution is to deal with inner approximations in infinite time, while former work with volume convergence guarantees proposed either outer approximations of the maximal positively invariant set or inner approximations of the region of attraction in finite time.
Published: 2019
Full Text: View/download PDF

29. Computation of Chebyshev Polynomials for Union of Intervals

Author: Jean B. Lasserre, Simon Foucart, Department of Mathematics [Texas] (TAMU), Texas A&M University [College Station], É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, NSF grants DMS-1622134 and DMS-1664803, 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: Chebyshev polynomials, Polynomial, Computation, 010103 numerical & computational mathematics, Method of moments (probability theory), Characterization (mathematics), 90C22, [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], 01 natural sciences, Set (abstract data type), FOS: Mathematics, Mathematics - Numerical Analysis, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Discrete mathematics, Semidefinite programming, Applied Mathematics, 010102 general mathematics, Numerical Analysis (math.NA), 16. Peace & justice, Functional Analysis (math.FA), Mathematics - Functional Analysis, AMS classification: 31A15, Computational Theory and Mathematics, Optimization and Control (math.OC), 41A50, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Analysis, Monic polynomial, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: International audience; Chebyshev polynomials of the first and second kind for a set K are monic polynomials with minimal L ∞-and L 1-norm on K, respectively. This articles presents numerical procedures based on semidefinite programming to compute these polynomials in case K is a finite union of compact intervals. For Chebyshev polynomials of the first kind, the procedure makes use of a characterization of polynomial nonnegativity. It can incorporate additional constraints, e.g. that all the roots of the polynomial lie in K. For Chebyshev polynomials of the second kind, the procedure exploits the method of moments. Key words and phrases: Chebyshev polynomials of the first kind, Chebyshev polynomials of the second kind, nonnegative polynomials, method of moments, semidefinite programming.
Published: 2019
Full Text: View/download PDF

30. A moment approach for entropy solutions to nonlinear hyperbolic PDEs

Author: Jean B. Lasserre, Tillmann Weisser, Swann Marx, Didier Henrion, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, 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), 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), and Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0209 industrial biotechnology, convex optimization, Control and Optimization, MathematicsofComputing_NUMERICALANALYSIS, 02 engineering and technology, 01 natural sciences, 020901 industrial engineering & automation, Mathematics - Analysis of PDEs, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Applied mathematics, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, Conservation law, Partial differential equation, Applied Mathematics, 010102 general mathematics, Godunov's scheme, 16. Peace & justice, Burgers' equation, Nonlinear system, Optimization and Control (math.OC), Convex optimization, moments and positive polynomials, nonlinear partial differential equation, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Linear equation, Analysis of PDEs (math.AP)
Abstract: International audience; We propose to solve polynomial hyperbolic partial differential equations (PDEs) with convex optimization. This approach is based on a very weak notion of solution of the nonlinear equation, namely the measure-valued (mv) solution, satisfying a linear equation in the space of Borel measures. The aim of this paper is, first, to provide the conditions that ensure the equivalence between the two formulations and, second, to introduce a method which approximates the infinite-dimensional linear problem by a hierarchy of convex, finite-dimensional, semidefinite programming problems. This result is then illustrated on the celebrated Burgers equation. We also compare our results with an existing numerical scheme, namely the Godunov scheme.
Published: 2018
Full Text: View/download PDF

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

32. Stability results for infinite-dimensional linear control systems subject to saturations

Author: Swann Marx, Yacine Chitour, Christophe Prieur, Équipe Méthodes et Algorithmes en Commande ( LAAS-MAC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), 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 ) -Institut National Polytechnique [Toulouse] ( INP ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Institut National Polytechnique [Toulouse] ( INP ), Laboratoire des signaux et systèmes ( L2S ), Université Paris-Sud - Paris 11 ( UP11 ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ), SYSCO ( GIPSA-SYSCO ), Département Automatique ( GIPSA-DA ), Grenoble Images Parole Signal Automatique ( GIPSA-lab ), Université Pierre Mendès France - Grenoble 2 ( UPMF ) -Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ) -Université Pierre Mendès France - Grenoble 2 ( UPMF ) -Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ) -Grenoble Images Parole Signal Automatique ( GIPSA-lab ), Université Pierre Mendès France - Grenoble 2 ( UPMF ) -Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ) -Université Pierre Mendès France - Grenoble 2 ( UPMF ) -Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Toulouse III - Paul Sabatier ( UPS ), 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 ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), 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 ), iCODE Institute, research project of the IDEX Paris-Saclay, ANR-11-IDEX-0003-02/11-LABX-0056,LMH,LabEx Mathématique Hadamard ( 2011 ), European Project : 666981,H2020,ERC-2014-ADG,TAMING ( 2015 ), É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 signaux et systèmes (L2S), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), GIPSA - Systèmes non linéaires et complexité (GIPSA-SYSCO), Département Automatique (GIPSA-DA), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-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), and Université de Toulouse (UT)
Subjects: 0209 industrial biotechnology, Mathematical analysis, Linear system, Linear control systems, Control space, Banach space, Hilbert space, 010103 numerical & computational mathematics, 02 engineering and technology, Stability result, 16. Peace & justice, 01 natural sciences, symbols.namesake, 020901 industrial engineering & automation, [ MATH.MATH-AP ] Mathematics [math]/Analysis of PDEs [math.AP], Exponential stability, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, [ SPI.AUTO ] Engineering Sciences [physics]/Automatic, [ INFO.INFO-AU ] Computer Science [cs]/Automatic Control Engineering, symbols, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], 0101 mathematics, Saturation (chemistry), Mathematics
Abstract: International audience; This article deals with the stability analysis and the derivation of ISS-Lyapunov functions for infinitedimensional linear systems subject to saturations. Two cases are considered: 1) the saturation acts in the same space as the control space; 2) the saturation acts in another space, especially a Banach space. For the first case, an explicit ISS-Lyapunov function can be derived. For the second case, we prove the global asymptotic stability of the origin when considering all weak solutions.
Published: 2018
Full Text: View/download PDF

33. Chance-Constrained Optimization for Non-Linear Network Flow Problems

Author: Weisser, Tillmann, Roald, Line, Misra, Sidhant, É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, Los Alamos National Laboratory (LANL), 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: Optimization, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Optimization and Control (math.OC), Algebraic/Geometric Methods, Probability (math.PR), FOS: Mathematics, Stochastic/Uncertain Systems, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Transportation Networks, Mathematics - Optimization and Control, Mathematics - Probability, Nonlinear Systems
Abstract: Many engineered systems, such as energy and transportation infrastructures, are networks governed by non-linear physical laws. A primary challenge for operators of these networks is to achieve optimal utilization while maintaining safety and feasibility, especially in the face of uncertainty regarding the system model. To address this problem, we formulate a Chance Constrained Optimal Physical Network Flow (CC-OPNF) problem that attempts to optimize the system while satisfying safety limits with a high probability. However, the non-linear equality constraints representing the network physics introduce modelling and optimization challenges which make the chance constraints numerically intractable in their original form. The main contribution of the paper is to present a method to obtain tractable polynomial approximations to the chance constraints using Semidefinite Programming (SDP). The method uses a combination of existing semi-algebraic techniques for projection and volume computation in combination with novel set manipulations to provide conservative inner approximations to the chance constraints. In addition, we develop a new two-step procedure to improve computational speed. While the method is applicable to general physical network flow problems with polynomial constraints, we use the AC optimal power flow problem for electric grids as an example to demonstrate the method numerically.
Published: 2018

34. Representation of distributionally robust chance-constraints

Author: Lasserre , Jean, Weisser , Tillmann, Équipe Méthodes et Algorithmes en Commande ( LAAS-MAC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), 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 ) -Institut National Polytechnique [Toulouse] ( INP ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Institut National Polytechnique [Toulouse] ( INP ), and European Project : 666981,H2020,ERC-2014-ADG,TAMING ( 2015 )
Subjects: [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], chance-constraints, distributionally robust, probabilistic constraints, semidefinite relaxations
Abstract: Given $X \subset R^n$, $\varepsilon \in (0,1)$, a parametrized family of probability distributions $(\mu_{a})_{a\in A}$ on $\Omega\subset R^p$, we consider the feasible set $X^*_\varepsilon\subset X$ associated with the {\em distributionally robust} chance-constraint \[X^*_\varepsilon\,=\,\{x \in X :\:{\rm Prob}_\mu[f(x,\omega)\,>\,0]> 1-\varepsilon,\,\forall\mu\in M_a\},\]where $M_a$ is the set of all possibles mixtures of distributions $\mu_a$, $a\in A$.For instance and typically, the family$M_a$ is the set of all mixtures ofGaussian distributions on $R$ with mean and standard deviation $a=(a,\sigma)$ in some compact set $A\subset R^2$.We provide a sequence of inner approximations $X^d_\varepsilon=\{x\in X: w_d(x)
Published: 2018

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

36. The Moment-SOS hierarchy

Author: Lasserre, Jean, É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, 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: Optimization and Control (math.OC), FOS: Mathematics, 90C26 90C22 90C27 65K05 14P10 44A60, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract: The Moment-SOS hierarchy initially introduced in optimization in 2000, is based on the theory of the K-moment problem and its dual counterpart, polynomials that are positive on K. It turns out that this methodology can be also applied to solve problems with positivity constraints " f (x) $\ge$ 0 for all x $\in$ K " and/or linear constraints on Borel measures. Such problems can be viewed as specific instances of the " Generalized Problem of Moments " (GPM) whose list of important applications in various domains is endless. We describe this methodology and outline some of its applications in various domains., Comment: To appear in Proceedings of ICM-2018, Rio de Janeiro
Published: 2018
Full Text: View/download PDF

37. Moments and convex optimization for analysis and control of nonlinear partial differential equations

Author: Korda, Milan, Henrion, Didier, Lasserre, Jean-Bernard, UCSB (UCSB), University of California [Santa Barbara] (UCSB), University of California-University of California, É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, České Vysoké Učení Technické (CVUT), 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), and European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015)
Subjects: Mathematics - Analysis of PDEs, Optimization and Control (math.OC), MathematicsofComputing_NUMERICALANALYSIS, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Semidefinite programming, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Partial differential equations, Mathematics - Optimization and Control, Convex optimization, Occupation measure, Optimal control, Analysis of PDEs (math.AP)
Abstract: This work presents a convex-optimization-based framework for analysis and control of nonlinear partial differential equations. The approach uses a particular weak embedding of the nonlinear PDE, resulting in a linear equation in the space of Borel measures. This equation is then used as a constraint of an infinite-dimensional linear programming problem (LP). This LP is then approximated by a hierarchy of convex, finite-dimensional, semidefinite programming problems (SDPs). In the case of analysis of uncontrolled PDEs, the solutions to these SDPs provide bounds on a specified, possibly nonlinear, functional of the solutions to the PDE; in the case of PDE control, the solutions to these SDPs provide bounds on the optimal value of a given optimal control problem as well as suboptimal feedback controllers. The entire approach is based purely on convex optimization and does not rely on spatio-temporal gridding, even though the PDE addressed can be fully nonlinear. The approach is applicable to a very broad class nonlinear PDEs with polynomial data. Computational complexity is analyzed and several complexity reduction procedures are described. Numerical examples demonstrate the approach.
Published: 2018
Full Text: View/download PDF

38. On inverse optimal control via polynomial optimization

Author: Jean B. Lasserre, Jérémy Rouot, É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), 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, 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), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0209 industrial biotechnology, Mathematical optimization, Class (set theory), Differential equation, MathematicsofComputing_NUMERICALANALYSIS, 02 engineering and technology, State (functional analysis), Inverse problem, Optimal control, Set (abstract data type), 020901 industrial engineering & automation, Control system, 0202 electrical engineering, electronic engineering, information engineering, Trajectory, Applied mathematics, 020201 artificial intelligence & image processing, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Mathematics
Abstract: International audience; We consider the class of control systems where the differential equation, state and control system are described by polynomials. Given a set of trajectories and a class of Lagrangians, we are interested to find a Lagrangian in this class for which these trajectories are optimal. To model this inverse problem we use a relaxed version of Hamilton-Jacobi-Bellman optimality conditions, in the continuity of previous work in this vein. Then we provide a general numerical scheme based on polynomial optimization and positivity certificates, and illustrate the concepts on a few academic examples.
Published: 2017
Full Text: View/download PDF

39. Computing gaussian & exponential measures of semi-algebraic sets

Author: Lasserre, Jean-Bernard, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, 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: Gaussian measure, Statistics, computational geometry, 28A75 49Q15 13P25 90C22 90C05 65C60 65K05, moments, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, semidefinite relaxations, pobability
Abstract: We provide a numerical scheme to approximate as closely as desired the Gaussian or exponential measure $\mu(\om)$ of (not necessarily compact) basic semi-algebraic sets$\om\subset\R^n$. We obtain two monotone (non increasing and non decreasing) sequences of upper and lower bounds $(\overline{\omega}\_d)$, $(\underline{\omega}\_d)$, $d\in\N$, each converging to $\mu(\om)$ as $d\to\infty$. For each $d$, computing $\overline{\omega}\_d$ or $\underline{\omega}\_d$reduces to solving a semidefinite program whose size increases with $d$. Some preliminary (small dimension) computational experiments are encouraging and illustrate thepotential of the method. The method also works for any measure whose moments are known and which satisfies Carleman's condition., Comment: To appear in Advances in Applied Mathematics
Published: 2017

40. Algorithm for Optimization and Interpolation based on Hyponormality

Author: Josz, Cédric, É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, 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: Autonne-Takagi factorization, Optimization and Control (math.OC), 49M20 65F99 47N10, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Toeplitz matrix, Hankel matrix, moment problem, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, hyponormality, Cholesky factorization
Abstract: On one hand, consider the problem of finding global solutions to a polynomial optimization problem and, on the other hand, consider the problem of interpolating a set of points with a complex exponential function. This paper proposes a single algorithm to address both problems. It draws on the notion of hyponormality in operator theory. Concerning optimization, it seems to be the first algorithm that is capable of extracting global solutions from a polynomial optimization problem where the variables and data are complex numbers. It also applies to real polynomial optimization, a special case of complex polynomial optimization, and thus extends the work of Henrion and Lasserre implemented in GloptiPoly. Concerning interpolation, the algorithm provides an alternative to Prony's method based on the Autonne-Takagi factorization and it avoids solving a Vandermonde system. The algorithm and its proof are based exclusively on linear algebra. They are devoid of notions from algebraic geometry, contrary to existing methods for interpolation. The algorithm is tested on a series of examples, each illustrating a different facet of the approach. One of the examples demonstrates that hyponormality can be enforced numerically to strenghten a convex relaxation and to force its solution to have rank one., Comment: 32 page, 7 figures
Published: 2017

41. Lasserre hierarchy for large scale polynomial optimization in real and complex variables

Author: Daniel K. Molzahn, Cédric Josz, É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), Argonne National Laboratory [Lemont] (ANL), 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), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: Mathematical optimization, 020209 energy, Physical system, Multi-ordered Lasserre hierarchy, Scale (descriptive set theory), 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, optimal power flow, Convergence (routing), 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Hermitian sum-of-squares, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Semidefinite programming, Hierarchy (mathematics), 010102 general mathematics, Operator theory, semidefinite programming, Optimization and Control (math.OC), chordal sparsity, Key (cryptography), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 90C22, 90C06, 90C26, 28A99, 14Q99, 47N10, Complex number, Software
Abstract: We propose general notions to deal with large scale polynomial optimization problems and demonstrate their efficiency on a key industrial problem of the twenty first century, namely the optimal power flow problem. These notions enable us to find global minimizers on instances with up to 4,500 variables and 14,500 constraints. First, we generalize the Lasserre hierarchy from real to complex to numbers in order to enhance its tractability when dealing with complex polynomial optimization. Complex numbers are typically used to represent oscillatory phenomena, which are omnipresent in physical systems. Using the notion of hyponormality in operator theory, we provide a finite convergence criterion which generalizes the Curto-Fialkow conditions of the real Lasserre hierarchy. Second, we introduce the multi-ordered Lasserre hierarchy in order to exploit sparsity in polynomial optimization problems (in real or complex variables) while preserving global convergence. It is based on two ideas: 1) to use a different relaxation order for each constraint, and 2) to iteratively seek a closest measure to the truncated moment data until a measure matches the truncated data. Third and last, we exhibit a block diagonal structure of the Lasserre hierarchy in the presence of commonly encountered symmetries. To the best of our knowledge, the Lasserre hierarchy was previously limited to small scale problems, while we solve a large scale industrial problem with thousands of variables and constraints to global optimality., 30 pages, 6 figures
Published: 2017

42. Sparse polynomial interpolation: compressed sensing, super resolution, or Prony?

Author: Josz , Cédric, Lasserre , Jean-Bernard, Mourrain , Bernard, Équipe Méthodes et Algorithmes en Commande ( LAAS-MAC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Toulouse III - Paul Sabatier ( UPS ), 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 ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), 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 ), AlgebRe, geOmetrie, Modelisation et AlgoriTHmes ( AROMATH ), Inria Sophia Antipolis - Méditerranée ( CRISAM ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -National and Kapodistrian University of Athens, and European Project : 666981,H2020,ERC-2014-ADG,TAMING ( 2015 )
Subjects: [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], Linear programming, Prony’s method, super-resolution, Semidefinite programming
Abstract: We show that the sparse polynomial interpolation problem reduces to a discrete super-resolution problem on the n-dimensional torus. Therefore the semidefinite programming approach initiated by Candès & Fernandez-Granda [7] in the univariate case (and later extended to the multi-variate setting) can be applied. In particular, exact recovery is guaranteed provided that a geometric spacing condition on the " supports " holds and the number of evaluations are sufficiently many (but not many). It also turns out that the (compressed sensing) LP-formulation of ℓ 1-norm minimization is also guaranteed to provide exact recovery provided that the evaluations are made in a certain manner and even though the Restricted Isometry Property for exact recovery is not satisfied. (A naive compressed sensing LP-approach does not offer such a guarantee.) Finally we also describe the algebraic Prony method for sparse interpolation, which also recovers the exact decomposition but from less point evaluations and with no geometric spacing condition. We provide two sets of numerical experiments , one in which the super-resolution technique and Prony's method seem to cope equally well with noise, and another in which the super-resolution technique seems to cope with noise better than Prony's method, at the cost of an extra computational burden (i.e. a semidefinite optimization).
Published: 2017

43. On the Relationship Between Real and Complex Linear Systems

Author: Josz, Cédric, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), European Project: 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), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: Orthogonal projection, Rings and Algebras (math.RA), Cholesky factorization, FOS: Mathematics, MathematicsofComputing_NUMERICALANALYSIS, Numerical Analysis (math.NA), Linear algebra, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Rings and Algebras, Mathematics - Numerical Analysis, Schur’s complement
Abstract: We consider the problem of solving a linear system of equations which involves complex variables and their conjugates. We characterize when it reduces to a complex linear system, that is, a system involving only complex variables (and not their conjugates). In that case, we show how to construct the complex linear system. Interestingly, this provides a new insight on the relationship between real and complex linear systems. In particular, any real symmetric linear system of equations can be solved via a complex linear system of equations. Numerical illustrations are provided. The mathematics in this manuscript constitute an exciting interplay between Schur's complement, Cholesky's factorization, and Cauchy's interlace theorem.
Published: 2017

44. Convergence rates of moment-sum-of-squares hierarchies for optimal control problems

Author: Didier Henrion, Milan Korda, Colin N. Jones, Ecole Polytechnique Fédérale de Lausanne (EPFL), 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, 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: 0209 industrial biotechnology, Polynomial, General Computer Science, moment relaxations, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, optimal control, 020901 industrial engineering & automation, Bellman equation, Convergence (routing), FOS: Mathematics, 0101 mathematics, Electrical and Electronic Engineering, approximation theory, Mathematics - Optimization and Control, Mathematics, polynomial sums of squares, Discrete mathematics, Semidefinite programming, Mechanical Engineering, Explained sum of squares, semidefinite programming, Optimal control, Moment (mathematics), Rate of convergence, Optimization and Control (math.OC), Control and Systems Engineering, Convergence rate, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: We study the convergence rate of the moment-sum-of-squares hierarchy of semidefinite programs for optimal control problems with polynomial data. It is known that this hierarchy generates polynomial under-approximations to the value function of the optimal control problem and that these under approximations converge in the L-1 norm to the value function as their degree d tends to infinity. We show that the rate of this convergence is 0(1/log log d). We treat in detail the continuous-time infinite-horizon-discounted problem and describe in brief how the same rate can be obtained for the finite-horizon continuous-time problem and for the discrete-time counterparts of both problems. (C) 2016 Elsevier B.V. All rights reserved.
Published: 2017

45. Approximate Optimal Designs for Multivariate Polynomial Regression

Author: Didier Henrion, Yohann De Castro, Jean B. Lasserre, Roxana Hess, Fabrice Gamboa, Probabilités et Statistique, Laboratoire de Mathématiques d'Orsay (LM-Orsay), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Méthodes d'Analyse Stochastique des Codes et Traitements Numériques (GdR MASCOT-NUM), 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 [Toulouse] (LAAS), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), 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)-Institut National Polytechnique [Toulouse] (INP)-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique [Toulouse] (INP), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), 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), 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), Czech Technical University in Prague (CTU), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: Statistics and Probability, Optimal design, FOS: Computer and information sciences, Polynomial, Christoffel Polynomial, Computer Science - Information Theory, Mathematics - Statistics Theory, 010103 numerical & computational mathematics, Statistics Theory (math.ST), Statistics - Computation, 01 natural sciences, 90C25, Methodology (stat.ME), 010104 statistics & probability, 90C90, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], 62K05, Equivalence Theorem, FOS: Mathematics, Applied mathematics, Semidefinite programming, Mathematics - Numerical Analysis, 0101 mathematics, Equivalence (measure theory), Statistics - Methodology, MSC 2010 subject classifications: Primary 62K05, 90C25, secondary 41A10, 49M29, 90C90, 15A15, Computation (stat.CO), Mathematics, 49M29, 15A15, Christoffel symbols, Hierarchy, Information Theory (cs.IT), Linear model, Numerical Analysis (math.NA), 16. Peace & justice, Experimental design, 62K05, 90C25 (Primary) 41A10, 49M29, 90C90, 15A15 (secondary), Designtheory, 41A10, Linear Model, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Statistics, Probability and Uncertainty
Abstract: We introduce a new approach aiming at computing approximate optimal designs for multivariate polynomial regressions on compact (semi-algebraic) design spaces. We use the moment-sum-of-squares hierarchy of semidefinite programming problems to solve numerically the approximate optimal design problem. The geometry of the design is recovered via semidefinite programming duality theory. This article shows that the hierarchy converges to the approximate optimal design as the order of the hierarchy increases. Furthermore, we provide a dual certificate ensuring finite convergence of the hierarchy and showing that the approximate optimal design can be computed numerically with our method. As a byproduct, we revisit the equivalence theorem of the experimental design theory: it is linked to the Christoffel polynomial and it characterizes finite convergence of the moment-sum-of-square hierarchies., Comment: 30 Pages, 8 Figures. arXiv admin note: substantial text overlap with arXiv:1703.01777
Published: 2017
Full Text: View/download PDF

46. Geometric and Numerical Foundations of Movements

Author: Nicolas Mansard, Jean-Paul Laumond, Jean B. Lasserre, Équipe Mouvement des Systèmes Anthropomorphes (LAAS-GEPETTO), 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), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Springer, Bruno Siciliano, Oussama Khatib, European Project: 340050,EC:FP7:ERC,ERC-2013-ADG,ACTANTHROPE(2014), 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, 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), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)
Subjects: business.industry, Management science, Computer science, Robotics, Motion (physics), Movement analysis, [SCCO]Cognitive science, [SPI]Engineering Sciences [physics], Multidisciplinary approach, Real algebraic geometry, Artificial intelligence, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], business, ComputingMilieux_MISCELLANEOUS
Abstract: This book aims at gathering roboticists, control theorists, neuroscientists, and mathematicians, in order to promote a multidisciplinary research on movement analysis. It follows the workshop Geometric and Numerical Foundations of Movements held at LAAS-CNRS in Toulouse in November 2015[1]. Its objective is to lay the foundations for a mutual understanding that is essential for synergetic development in motion research. In particular, the book promotes applications to robotics --and control in general-- of new optimization techniques based on recent results from real algebraic geometry.
Published: 2017
Full Text: View/download PDF

47. A bounded degree SOS hierarchy for polynomial optimization

Author: Jean B. Lasserre, Shouguang Yang, Kim-Chuan Toh, 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, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), National University of Singapore (NUS), PGMO grant of the ``Fondation Mathématique Jacques Hadamard', 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), and Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole)
Subjects: Polynomial, Control and Optimization, Optimization problem, 90C22, Management Science and Operations Research, Polynomial Optimization, 90C26, Combinatorics, Matrix (mathematics), ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Mathematics - Optimization and Control, Global optimization, Mathematics, LP-hierarchies, Discrete mathematics, T57-57.97, Applied mathematics. Quantitative methods, Hierarchy (mathematics), Degree (graph theory), Zero (complex analysis), QA75.5-76.95, Computational Mathematics, Semidefinite hierarchies, Optimization and Control (math.OC), Electronic computers. Computer science, Modeling and Simulation, Bounded function, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: International audience; We consider a new hierarchy of semidefinite relaxations for the general polynomial optimization problem $(P):\:f^{\ast}=\min \{\,f(x):x\in K\,\}$ on a compact basic semi-algebraic set $K\subset\R^n$. This hierarchy combines some advantages of the standard LP-relaxations associated with Krivine's positivity certificate and some advantages of the standard SOS-hierarchy. In particular it has the following attractive features: (a) In contrast to the standard SOS-hierarchy, for each relaxation in the hierarchy, the size of the matrix associated with the semidefinite constraint is the same and fixed in advance by the user. (b) In contrast to the LP-hierarchy, finite convergence occurs at the first step of the hierarchy for an important class of convex problems. Finally (c) some important techniques related to the use of point evaluations for declaring a polynomial to be zero and to the use of rank-one matrices make an efficient implementation possible. Preliminary results on a sample of non convex problems are encouraging.
Published: 2017

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

49. Positivity certificates in optimal control

Author: Pauwels, Edouard, Henrion, Didier, Lasserre, Jean-Bernard, Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-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)-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é de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), 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), Czech Technical University in Prague (CTU), Springer, European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), 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), 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é 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), and Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1)
Subjects: [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: Chapter of the book ``Geometric and Numerical Foundations of Movements", J.-P. Laumond, N. Mansard et J.B. Lasserre Eds., Springer Tracts in Advanced Robotics, New York, 2017 ISBN-10: 1461407680; ISBN-13: 978-1461407683; International audience; We propose a tutorial on relaxations and weak formulations of optimal control with their semidefinite approximations. We present this approach solely through the prism of positivity certificates which we consider to be the most accessible for a broad audience, in particular in the engineering and robotics communities. This simple concept allows to express very concisely powerful approximation certificates in control. The relevance of this technique is illustrated on three applications: region of attraction approximation, direct optimal control and inverse optimal control, for which it constitutes a common denominator. In a first step, we highlight the core mechanisms underpinning the application of positivity in control and how they appear in the different control applications. This relies on simple mathematical concepts and gives a unified treatment of the applications considered. This presentation is based on the combination and simplification of published materials. In a second step, we describe briefly relations with broader literature, in particular, occupation measures and Hamilton-Jacobi-Bellman equation which are important elements of the global picture. We describe the Sum-Of-Squares (SOS) semidefinite hierarchy in the semialgebraic case and briefly mention its convergence properties. Numerical experiments on a classical example in robotics, namely the nonholonomic vehicle, illustrate the concepts presented in the text for the three applications considered.
Published: 2017

50. Sorting out typicality with the inverse moment matrix SOS polynomial

Author: Lasserre, Jean-Bernard, Pauwels, Edouard, É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), 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), D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, R. Garnett, ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), 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, 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), and Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1)
Subjects: FOS: Computer and information sciences, Computer Science - Learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Machine Learning (cs.LG)
Abstract: International audience; We study a surprising phenomenon related to the representation of a cloud of data points using polynomials. We start with the previously unnoticed empirical observation that, given a collection (a cloud) of data points, the sublevel sets of a certain distinguished polynomial capture the shape of the cloud very accurately. This distinguished polynomial is a sum-of-squares (SOS) derived in a simple manner from the inverse of the empirical moment matrix. In fact, this SOS polynomial is directly related to orthogonal polynomials and the Christoffel function. This allows to generalize and interpret extremality properties of orthogonal polynomials and to provide a mathematical rationale for the observed phenomenon. Among diverse potential applications, we illustrate the relevance of our results on a network intrusion detection task for which we obtain performances similar to existing dedicated methods reported in the literature.
Published: 2016
Full Text: View/download PDF

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

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

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

59 results on '"European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources