Sparse convex relaxations in polynomial optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913256229044224 |
|---|---|
| author | Averkov, Gennadiy Peters, Benjamin Sager, Sebastian |
| author_facet | Averkov, Gennadiy Peters, Benjamin Sager, Sebastian |
| contents | We present a novel, general, and unifying point of view on sparse approaches to polynomial optimization. Solving polynomial optimization problems to global optimality is a ubiquitous challenge in many areas of science and engineering. Historically, different approaches on how to solve nonconvex polynomial optimization problems based on convex relaxations have been developed in different scientific communities. Here, we introduce the concept of monomial patterns. A pattern determines what monomials are to be linked by convex constraints in a convex relaxation of a polynomial optimization problem. This concept helps to understand existing approaches from different schools of thought, to develop novel relaxation schemes, and to derive a flexible duality theory, which can be specialized to many concrete situations that have been considered in the literature. We unify different approaches to polynomial optimization including polyhedral approximations, dense semidefinite relaxations, SONC, SAGE, and TSSOS in a self-contained exposition. We also carry out computational experiments to demonstrate the practical advantages of a flexible usage of pattern-based sparse relaxations of polynomial optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03560 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sparse convex relaxations in polynomial optimization Averkov, Gennadiy Peters, Benjamin Sager, Sebastian Optimization and Control 90C23, 90C22, 90C26, 13J30 We present a novel, general, and unifying point of view on sparse approaches to polynomial optimization. Solving polynomial optimization problems to global optimality is a ubiquitous challenge in many areas of science and engineering. Historically, different approaches on how to solve nonconvex polynomial optimization problems based on convex relaxations have been developed in different scientific communities. Here, we introduce the concept of monomial patterns. A pattern determines what monomials are to be linked by convex constraints in a convex relaxation of a polynomial optimization problem. This concept helps to understand existing approaches from different schools of thought, to develop novel relaxation schemes, and to derive a flexible duality theory, which can be specialized to many concrete situations that have been considered in the literature. We unify different approaches to polynomial optimization including polyhedral approximations, dense semidefinite relaxations, SONC, SAGE, and TSSOS in a self-contained exposition. We also carry out computational experiments to demonstrate the practical advantages of a flexible usage of pattern-based sparse relaxations of polynomial optimization problems. |
| title | Sparse convex relaxations in polynomial optimization |
| topic | Optimization and Control 90C23, 90C22, 90C26, 13J30 |
| url | https://arxiv.org/abs/2403.03560 |