feasible or infeasible

[Yan Wang]

Hi Lofberg,

Today, I use the command "solvemoment" to solve a quadratic matrix inequality problem. All the constraints are expected to be positive. The "diagnostic" shows that this problem is feasible. However, I use the command "checkset" to check the residual of the each inequality. It shows that the two QMIs are negative. Could you please tell me whether this problem is feasible or not? Thanks a lot!!!

diagnostics = 

    yalmiptime: 0.2130

    solvertime: 1.7190

          info: 'Successfully solved (SeDuMi-1.3)'

       problem: 0

        dimacs: [NaN NaN NaN NaN NaN NaN]

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

|   ID|      Constraint|                             Type|   Primal residual|

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

|   #1|   Numeric value|                Matrix inequality|        6.3908e-10|

|   #2|   Numeric value|           Elementwise inequality|         0.0010646|

|   #3|   Numeric value|   Matrix inequality (polynomial)|            -3.208|

|   #4|   Numeric value|   Matrix inequality (polynomial)|           -3.2079|

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

 

[Johan Löfberg]

The semidefinite relaxation problem was feasible. However, the relaxation is not tight, hence the solution is not feasible for the underlying nonconvex problem.

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.MomentRelaxations

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.Relaxdouble

[Yan Wang]

hi Lofberg,

Thanks for your quick response! Then, I increase the order of the moment relaxation up to 3 with tolerable computational speed. The primal residual can be seen below. The 4th matrix inequality is still negative and the others are marginal. Can I regard that the returned value from the solver is a feasible solution? In my experience, the Sedumi solver always returns a marginal solution for feasibility problems. For example, the Lyapunov matrix always has an eigenvalue very close to 0. Is that true?

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

|   ID|      Constraint|                             Type|   Primal residual|

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

|   #1|   Numeric value|                Matrix inequality|        1.1621e-13|

|   #2|   Numeric value|           Elementwise inequality|        1.9833e-07|

|   #3|   Numeric value|           Elementwise inequality|        2.4772e-14|

|   #4|   Numeric value|   Matrix inequality (polynomial)|        -9.335e-15|

|   #5|   Numeric value|   Matrix inequality (polynomial)|        4.2156e-12|

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

[Johan Löfberg]

Numerical tolerances and feasiblities must always be judged based on the application in which the numbers are used. Is it good enough for you?...

If the optimal solution is on the border of feasibility of the LMI, you can often expect some small violations of feasibility, due to the way SDP solvers work

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Main.FrequentlyAskedQuestions#QQuestions36

If this is unacceptable in your application, you have to explicitly add non-zero lower bounds to your constraints. This leads to new complications, in the choice of a suitably small margin which doesn't affect optimality too much, while being large enough to push the solution into the interior.

However, in the case of moment relaxations, this is not possible, since by design you typically search for rank-1 solutions, i.e., you want the solution to be singular. Hence, it would not make sense to add a margin.

Here, 10^-15 is well within what you ever could expect as it basically is at machine precision. Simply consider the following matrix which by design is psd, but still MATLAB returns an eigenvalue which claims the matrix is indefinite

x = ones(10,1);min(eig(x*x'))

ans =

  -2.6274e-16