English
Exploiting sparsity in polynomial optimization - lecture 2
Multi angle
Auteurs : Magron, Victor (Auteur de la conférence)
CIRM (Editeur )
65F50 - Sparse matrices
90C22 - Semidefinite programming
90C23 - Polynomial optimization
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/2888/Slides/SparsePOPJNCF23.pdf
CIRM (Editeur )
Loading the player...
|
Résumé :
Polynomial optimization methods often encompass many major scalability issues on the practical side. Fortunately, for many real-world problems, we can look at them in the eyes and exploit the inherent data structure arising from the input cost and constraints. The first part of my lecture will focus on the notion of 'correlative sparsity', occurring when there are few correlations between the variables of the input problem. The second part will present a complementary framework, where we show how to exploit a distinct notion of sparsity, called 'term sparsity', occurring when there are a small number of terms involved in the input problem by comparison with the fully dense case. At last but not least, I will present a very recently developed type of sparsity that we call 'ideal-sparsity', which exploits the presence of equality constraints. Several illustrations will be provided on important applications arising from various fields, including computer arithmetic, robustness of deep networks, quantum entanglement, optimal power-flow, and matrix factorization ranks.
Mots-Clés : optimisation polynomiale; exploitation de la parcimonie; programmation semi-définie
Codes MSC : Mots-Clés : optimisation polynomiale; exploitation de la parcimonie; programmation semi-définie
65F50 - Sparse matrices
90C22 - Semidefinite programming
90C23 - Polynomial optimization
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/2888/Slides/SparsePOPJNCF23.pdf
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de Publication : 20/03/2023 Date de Captation : 06/03/2023 Sous Collection : Research School Catégorie arXiv : Optimization and Control Domaine(s) : Théorie du Contrôle & Optimisation Format : MP4 (.mp4) - HD Durée : 01:29:20 Audience : Chercheurs ; Etudiants Science Cycle 2 ; Doctoral Students, Post-Doctoral Students Download : https://videos.cirm-math.fr/2023-03-07_Magron.mp4 
|
Informations sur la Rencontre
Nom de la Rencontre : Francophone Computer Algebra Days / JNCF - Journées nationales de calcul formelOrganisateurs de la Rencontre : Berthomieu, Jérémy ; Boito, Paola ; Guerrini, Eleonora ; Ollivier, François ; Spaenlehauer, Pierre-Jean Dates : 06/03/2023 - 10/03/2023 Année de la rencontre : 2023 URL de la Rencontre : https://conferences.cirm-math.fr/2888.html
Données de citation
DOI : 10.24350/CIRM.V.20013803Citer cette vidéo: Magron, Victor (2023). Exploiting sparsity in polynomial optimization - lecture 2. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.20013803 URI : http://dx.doi.org/10.24350/CIRM.V.20013803 |
Voir Aussi
- [Multi angle] Using structured variants in lattice-based cryptography - lecture 2 / Auteur de la conférence Roux-Langlois, Adeline.
- [Multi angle] Using structured variants in lattice-based cryptography - lecture 1 / Auteur de la conférence Roux-Langlois, Adeline.
- [Multi angle] Exploiting sparsity in polynomial optimization - lecture 1 / Auteur de la conférence Magron, Victor.
Bibliographie
- MAGRON, Victor et WANG, Jie. Sparse Polynomial Optimization: Theory and Practice. arXiv preprint arXiv:2208.11158, 2022. - https://doi.org/10.48550/arXiv.2208.11158
- ANDERSEN, Erling D., ROOS, Cornelis, et TERLAKY, Tamas. On implementing a primal-dual interior-point method for conic quadratic optimization. Mathematical Programming, 2003, vol. 95, p. 249-277. - http://dx.doi.org/10.1007/s10107-002-0349-3
- BUGARIN, Florian, HENRION, Didier, et LASSERRE, Jean Bernard. Minimizing the sum of many rational functions. Mathematical Programming Computation, 2016, vol. 8, no 1, p. 83-111. - http://dx.doi.org/10.1007/s12532-015-0089-z
- BODLAENDER, Hans L. et KOSTER, Arie MCA. Treewidth computations I. Upper bounds. Information and Computation, 2010, vol. 208, no 3, p. 259-275. - https://doi.org/10.1016/j.ic.2009.03.008
- DUNNING, Iain, HUCHETTE, Joey, et LUBIN, Miles. JuMP: A modeling language for mathematical optimization. SIAM review, 2017, vol. 59, no 2, p. 295-320. - https://doi.org/10.1137/15M1020575
- FAIRBANKS, James, BESANĘON, M., SIMON, S., et al. Juliagraphs/graphs. jl: an optimized graphs package for the julia programming language, 2021 - https://github. com/JuliaGraphs/Graphs. jl
- GARSTKA, Michael, CANNON, Mark, et GOULART, Paul. COSMO: A conic operator splitting method for large convex problems. In : 2019 18th European Control Conference (ECC). IEEE, 2019. p. 1951-1956. - https://doi.org/10.23919/ECC.2019.8796161
- HENRION, Didier, LASSERRE, Jean-Bernard, et LÖFBERG, Johan. GloptiPoly 3: moments, optimization and semidefinite programming. Optimization Methods & Software, 2009, vol. 24, no 4-5, p. 761-779. - https://doi.org/10.1080/10556780802699201
- LOFBERG, Johan. YALMIP: A toolbox for modeling and optimization in MATLAB. In : 2004 IEEE international conference on robotics and automation (IEEE Cat. No. 04CH37508). IEEE, 2004. p. 284-289. - https://doi.org/10.1109/CACSD.2004.1393890
- STURM, Jos F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization methods and software, 1999, vol. 11, no 1-4, p. 625-653. - https://doi.org/10.1080/10556789908805766
- WANG, Jie. ChordalGraph: A Julia Package to Handle Chordal Graphs. 2020. -
Imagette Video
