Large negative dual residual for equality constraint

[Travis Arnold]

I am solving a simple least-squares problem with a semidefinite constraint and an equality constraint:

A = magic(4);

A = A(:, 1:3);

b = (1:4)';

X = sdpvar(2, 2);

constraints = [X >=0, X(1) == 1];

Z = A*[X(1); X(2); X(4)] - b;

objective = Z'*Z;

options = sdpsettings('solver', 'sedumi');

sol = optimize(constraints, objective, options);

disp(['value(X)', char(10)])

disp(value(X))

%eig(value(X))

disp([char(10), 'check(constraints)'])

check(constraints)

sol

The above script produces the following (omitting the output from the solver):

value(X)

   1.00000  -0.36515

  -0.36515   0.13333

check(constraints)

 

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

|   ID|            Constraint|   Primal residual|   Dual residual|

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

|   #1|     Matrix inequality|        3.0366e-09|      2.5016e-08|

|   #2|   Equality constraint|       -1.6716e-10|       -517.1615|

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

| 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/                 |

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

 

sol =

  scalar structure containing the fields:

    yalmipversion = 20190425

    yalmiptime =  0.18730

    solvertime =  0.24087

    info = Successfully solved (SeDuMi-1.3)

    problem = 0

sol.info says that the problem is successfully solved, but check(constraints) shows a large negative dual residual for the equality constraint, and it also says that the optimal solution should show only non-negative residuals. So, is the solution to the problem is optimal or not?

This question certainly hints at my lack of familiarity with optimization theory. Sorry in advance if the answer to my question is obvious!

[Johan Löfberg]

dual residual for equality (i.e. the dual) can have arbitrary sign.

Hence, this problem has been solved within normal precision

[Travis Arnold]

Gotcha, that is good to know. I am still confused about what the numbers in the "dual residual" column represent, can you help clarify that for me? It seems like they represent the constraints for the dual problem, but (and I may be mistaken here) the primal and dual problems do not necessarily have the same number of constraints. So it is confusing to me that check(constraints) will always have the same number of entries in both the "primal residual" and "dual residual" columns.

[Johan Löfberg]

From check

% Primal constraint residuals are calculated as:

%

%  Semidefinite constraint F(x)>=0 : min(eig(F))

%  Element-wise constraint F(x)>=0 : min(min(F))

%  Equality constraint F==0        : -max(max(abs(F)))

%  Second order cone t>=||x||      : t-||x||

%  Exponential cone constraint     : x(3) - exp(x(1)/x(2))*x(2)

%  Integrality constraint on x     : max(abs(x-round(x)))

%  Sum-of-square constraint        : Minus value of largest (absolute value) coefficient 

%                                   in the polynomial p-v'*v

%

% Dual constraints are evaluated similarily.

%

This effectively means that the dual residual for equality doesn't make much sense. All duals for equality are feasible, and displaying negated largest absolute value doesn't say much. For consistency, it should really always be displayed as 0, since by definition it doesn't violate anything