Research on the tightness and applications of sparse Moment-SOS hierarchy of semidefinite relaxations

Sparse polynomial optimization problems (POPs) are optimization problems given by
polynomials with a small number of variables. By exploiting the sparsity, one gets a
semidefinite relaxation method for globally solving large-scale sparse POPs, which is
called the sparse Moment-Sum-of-Squares (Moment-SOS) hierarchy of semidefinite
relaxations. POPs with application backgrounds are usually equipped with sparsity, and
the sparse Moment-SOS hierarchy has been applied to solve many sparse POPs from
various fields, such as electric power systems, computer vision, and deep learning.
In this project, the PI will study the sparse Moment-SOS hierarchy for solving sparse
POPs. More specifically, we will investigate the tightness of the sparse Moment-SOS
hierarchy for solving the reformulation of sparse POPs obtained by the correlatively
sparse Lagrange multiplier expressions (CS-LMEs), which is called the CS-LME-type
relaxations and proposed in the recent collaborative work by the PI. In computational
practice, one can usually observe that the approximation for the global optimal value of
sparse POPs provided by the CS-LME-type relaxation is exact, for which cases we say
the relaxation is tight. We plan to investigate the theoretical property for the tightnessof CS-LME-type relaxations, based on the results of the PI's recent collaborative work
on characterizing the tightness of the sparse Moment-SOS hierarchy. Moreover, for CSLME-type relaxations, we also plan to investigate how to detect the tightness for a
computed optimal solution and get global optimizers for sparse POPs by studying the flat
truncation condition. Besides that, we plan to investigate a novel approach that uses the
sparse Moment-SOS hierarchy to solve low rank tensor completion problems, which has
broad applications in image science, recommendation systems, signal processing, etc. In
general, this research will broaden our ability to solve difficult problems given by sparse
polynomials, such as sparse generalized Nash equilibrium problems of polynomials,
which cannot be solved by existing approaches, and may lead to more globally solvable
models from the application.