Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension
| Autor: | Jie Wang, Victor Magron, Jean B. Lasserre |
|---|---|
| Přispěvatelé: | É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, European Project: 813211,H2020,POEMA(2019) |
| Rok vydání: | 2021 |
| Předmět: |
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 |
| Zdroj: | SIAM Journal on Optimization SIAM Journal on Optimization, 2021, ⟨10.1137/20M1323564⟩ SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2021, ⟨10.1137/20M1323564⟩ |
| ISSN: | 1095-7189 1052-6234 |
| DOI: | 10.1137/20m1323564 |
| Popis: | 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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|