Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant

Polynomial optimization is concerned with computing the minimum value of a polynomial on a basic semialgebraic set. A well-known methodology is to apply positivity certificates (representations of polynomials positive on basic semialgebraic sets) to design a hierarchy of convex relaxations to solve polynomial optimization problems (POPs). Developed originally by Lasserre in [25], the hierarchy of semidefinite relaxations based on Putinar's Positivstellensatz is called the Moment-SOS hierarchy. We utilize this approach in many applications arising from optimization, operations research, signal processing, computational geometry, probability, statistics, control, PDEs, quantum information, and computer vision. For more details, the interested reader is referred to, e.g., [56, 53, 60, 48, 47, 9, 7, 51, 36, 50] and references therein. However, despite its theoretical efficiency (also observed in practice), the Moment-SOS hierarchy is facing a scalability issue mainly due to the increasing size of the resulting relaxations. Overcoming the scalability and efficiency issues has become a major scientific challenge in polynomial optimization. Many recent efforts in this direction are mainly developed around the following ideas: 1. SDP-relaxations variants with small maximal matrix size solved efficiently by interior point methods. This includes correlative sparsity [54, 26], term sparsity [58, 57, 59], symmetry exploitation [17, 43], Jordan symmetry reduction [6], sublevel relaxations [8]. 2. Exploit low-rank structures of SDP-relaxations; see, e.g., [61, 62]. 3. First-order methods to solve SDP-relaxations involving matrix variables of potentially large size with constant trace [33, 30].