1. Sparse Polynomial Optimization: Theory and Practice
- Author
-
Magron, Victor, Wang, Jie, Equipe Polynomial OPtimization (LAAS-POP), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Academy of Mathematics and Systems Science [Beijing], This work was supported by the FMJH Program PGMO (EPICS project), as well as the PEPS2 Program (FastOPF project) funded by AMIES and RTE.This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme., World Scientific Press, ANR-18-ERC2-0004,COPS,Optimisation garantie pour la vérification des systèmes cyber-physiques(2018), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), Magron, Victor, TREMPLIN-ERC - Optimisation garantie pour la vérification des systèmes cyber-physiques - - COPS2018 - ANR-18-ERC2-0004 - TERC - VALID, Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID, and Polynomial Optimization, Efficiency through Moments and Algebra - POEMA - - H20202019-01-01 - 2022-12-31 - 813211 - VALID
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Mathematics - Algebraic Geometry ,Optimization and Control (math.OC) ,Mathematics - Operator Algebras ,FOS: Mathematics ,[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC] ,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] ,Operator Algebras (math.OA) ,Mathematics - Optimization and Control ,Algebraic Geometry (math.AG) ,Machine Learning (cs.LG) - Abstract
The problem of minimizing a polynomial over a set of polynomial inequalities is an NP-hard non-convex problem. Thanks to powerful results from real algebraic geometry, one can convert this problem into a nested sequence of finite-dimensional convex problems. At each step of the associated hierarchy, one needs to solve a fixed size semidefinite program, which can be in turn solved with efficient numerical tools. On the practical side however, there is no-free lunch and such optimization methods usually encompass severe scalability issues. Fortunately, for many applications, we can look at the problem in the eyes and exploit the inherent data structure arising from the cost and constraints describing the problem, for instance sparsity or symmetries. This book presents several research efforts to tackle this scientific challenge with important computational implications, and provides the development of alternative optimization schemes that scale well in terms of computational complexity, at least in some identified class of problems. The presented algorithmic framework in this book mainly exploits the sparsity structure of the input data to solve large-scale polynomial optimization problems. We present sparsity-exploiting hierarchies of relaxations, for either unconstrained or constrained problems. By contrast with the dense hierarchies, they provide faster approximation of the solution in practice but also come with the same theoretical convergence guarantees. Our framework is not restricted to static polynomial optimization, and we expose hierarchies of approximations for values of interest arising from the analysis of dynamical systems. We also present various extensions to problems involving noncommuting variables, e.g., matrices of arbitrary size or quantum physic operators., Comment: 220 pages, to appear in Series on Optimization and Its Applications, World Scientific Press
- Published
- 2023