SOS Problem: Primal residuals are positive but constraint is violated

[Mahathi Anand]

Hello,

I'm solving an SOS optimization problem with an objective function and several SOS constraints with SeDuMi solver. Essentially, I'm trying to construct a polynomial function that minimizes the objective function while satisfying the SOS constraints.
The problem is successfully solved and I get the following primal residual errors:

 

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

|   ID|                    Constraint|   Primal residual|   Dual residual|

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

|   #1|   SOS constraint (polynomial)|        6.2535e-07|             NaN|

|   #2|   SOS constraint (polynomial)|        2.1316e-14|             NaN|

|   #3|   SOS constraint (polynomial)|        1.2143e-16|             NaN|

|   #4|   SOS constraint (polynomial)|        1.3878e-16|             NaN|

|   #5|   SOS constraint (polynomial)|        8.6262e-07|             NaN|

|   #6|   SOS constraint (polynomial)|        5.3776e-16|             NaN|

|   #7|   SOS constraint (polynomial)|        2.2204e-16|             NaN|

|   #8|   SOS constraint (polynomial)|        6.9389e-17|             NaN|

|   #9|   SOS constraint (polynomial)|        3.9968e-15|             NaN|

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

| A primal-dual optimal solution would show non-negative residuals.      |

| In practice, many solvers converge to slightly infeasible              |

| solutions, which may cause some residuals to be negative.              |

| It is up to the user to judge the importance and impact of             |

| slightly negative residuals (i.e. infeasibilities)                     |

| https://yalmip.github.io/command/check/                                |

| https://yalmip.github.io/faq/solutionviolated/                         |

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

However, when I check for the minimum of Constraint #4 manually, I get negative values, indicating that it is not necessarily SOS. I'm trying to understand why this is the case,  and if I can indeed trust the results obtained. 
Any advice would be appreciated.

Thanks in advance. 

[Johan Löfberg]

You would have to describe more precisely what you mean when you say you check it. 10^-16 is basically machine epsilon so it can just as well be negative or zero by the flip of a bit

[Johan Löfberg]

and note that check simply reports the smallest eigenvalue of the Gramian in a primal kernel representation, when the SDP is the problem p(x) == x'*X*x, X>=0 where feasibility of X>=0 is guaranteed by primal-dual solvers but equality p==x'*X*x is not https://yalmip.github.io/reference/lofberg2009/

måndag 15 februari 2021 kl. 14:57:12 UTC+1 skrev mahath...@gmail.com:

[Mahathi Anand]

Well, first I substitute the obtained values of the parameters (polynomial coefficients) from the SOS solution onto the constraint and then I plot the constraint over variables. It should be positive throughout, but it is not the case. 
However, I must also add that I'm still able to extract an SOS decomposition for the constraint using sosd() command. So I'm not able to understand what to make of the obtained solution.  

[Johan Löfberg]

as indicated in the referenced paper, you will almost never be able to compute perfect sos-decompositions when the polynomial isn't strictly positive (which I guess it isn't here as the solver has bound gramians which numerically are singular). You will always have an error (unless the polynomial has very simply structure, or is positive)

also, if you in any sense touch a numerical object (any arithmetic operation) you can kill any kind of almost-zero numerics as you have. The following is a trivial example, this matrix is positive-semidefinite, but despite this it cannot be shown to be so

>> min(eig(ones(10)))

ans =

  -2.3078e-16

[Mahathi Anand]

Thank you so much for your response. The reference was quite helpful indeed. But I do have a little confusion I would like to clarify. In the paper, it says that "The polynomial constructed in the sum-of-squares decomposition indeed is non-negative, but it is not identical to the analyzed polynomial". Would this mean that the certificate provided by the SDP solver is 'wrong' due to the fact that it terminates earlier but the exact certificate does exist in the limit? In other words, the constraint would indeed be satisfied by a  polynomial that is slightly different from the one provided by the solver?

[Johan Löfberg]

SDP solvers are numerical tools, and thus SOS-decompositions can essentially never be anything but numerical approximations, and thus if your life relies on the correctness you're in deep troubles

If you setup a sos to prove that f(x) = -1e-15*x^2 is SOS, the sos problem deirved is the search of a polynomial p(x) = a*x^2 such that a>=0 and f(x) == p(x), i.e. the SDP problem [a>=0,  a == -1e-15]. When interpreted as the primal cone representation of a primal-dual SDP, this will in most solvers lead to a solution which works in the interior of the SDP cone (meaning any solution a will be a>=0) and assumptotically reaches feasibility of the equality. With tolerances, a silly solver could find a = 0 being a certificate, as that is feasible enough numerically. Obviously, the analyzed polynomial is not SOS, but numerically it is close to SOS thus leading to a wrong conclusion.

[Mahathi Anand]

Okay, thank you so much for taking your time and explaining.