In 2001, Lasserre introduced a nowadays famous hierarchy of relaxations, called the moment-sums of squares hierarchy, allowing one to obtain a converging sequence of lower bounds for the minimum of a polynomial over a compact semialgebraic set. Each lower bound is computed by solving a semidefinite program (SDP).

There are two common drawbacks related to this hierarchy. First, the size of the SDP problems arising from the hierarchy grows rapidly. Second, one relies on numerical SDP solvers, implemented in finite-precision, thus providing only approximate certificates.

In this talk, we explain how to address these two efficiency and certification issues.

In the first part, we recall how to exploit the sparsity pattern arising in polynomial optimization problems.  We present one application for an optimization problem in commuting variables, which is a framework to provide upper bounds on absolute roundoff errors of floating-point nonlinear programs. Then we present one application for optimization problems in non-commuting variables, which is a converging hierarchy of SDP relaxations for eigenvalue and trace optimization.

In the second part, we provide a hybrid symbolic-numeric algorithm computing exact rational sums of squares (SOS) decompositions for polynomials lying in the interior of the SOS cone. This algorithm computes an approximate decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. An exact decomposition is obtained thanks to the perturbation terms.  Then, we apply this algorithm to compute exact Reznick and Putinar’s representations respectively for positive definite forms and polynomials positive over basic compact semialgebraic sets.

Zoom Link: https://ncsu.zoom.us/j/96727369756?pwd=Nkc2c0g1aHRqcVM4Qzl3dktURjR3QT09