Dualization and Constraint Processing fails in SDP with interacting semiknown_vars and known_vars

[eliewolfe]

Consider the problem

problem = {
    "objective":  {'x': -1, 'y': -2, 'z': -1},
    "known_vars": {'1': 1, 'x': 3},
    "inequalities":  [{'x': 1, 'y': 1, 'z': 1, '1': -26},
                      {'x': 1, '1': -3},
                      {'y': 1, '1': -4},
                      {'z': 1, '1': -1}],
    "equalities": [{'x': -5, 'y': 1, 'z': -2, '1': -7}],
    "semiknown_vars": {'z': (0.5, 'x')}
}

the true objective value is -109/2 = -54.5 Indeed, this objective is correctly recovered when applying solveSDP_MosekFUSION(**problem, solve_dual=False, process_constraints=False). However, if we switch to process_constraints=True suddenly the returned objective wrongly evaluate to -53! Worst of all, if we switch to solve_dual=True the objective is now returned as None!

Note that this error is unlikely to show up in real problems, as in this artificial example z is effectively a fixed-valued term as well, and hence should not be listed among the semiknown_vars at all. Still, worth resolving.

[apozas]

I am getting into this problem, since this is a very deep thing that should be resolved. You found it in an artificial example, but we must make sure that the software is working properly.

The discrepancy between process_constraints=True and process_constraints=False is that the constant in the objective function is computed before processing, and it is not updated if the processing finds that the constraints lead to more constants. This is solved in 10a17b6 just by computing the constant after the (potential) processing. I am now working on the dualization problem.

[apozas]

I think I found a small bug that I have fixed in 9d52914. To my surprise, this is not solving the dualization problems. I would find very helpful to know where the expression that we compute for the dual, i.e. why

\begin{matrix}
\text{min} & c_0 + \text{Tr}( Z \cdot F_0) + I\cdot b + E\cdot d \\
\text{s.t.} & c_k + \text{Tr}(Z \cdot F_k) + \sum_j I_j A_{jk} + \sum_j E_j C_{jk} = 0\,\,\forall k>0,\\
 & Z \succeq 0
\end{matrix}

is the dual for the primal problem

\begin{matrix}
\text{max} & c_0 + \sum_k c_k x_k \\
\text{s.t.} & A\cdot x + b \geq 0, \\
& C \cdot x + d = 0, \\
 & G_{ij} - (F_0)_{ij} - \sum_k x_k (F_k)_{ij} = 0\,\,\forall i,j, \\
& G\succeq 0
\end{matrix}

Where are these formulas coming from? They are quite different from the ones in the MOSEK cookbook. @ecboghiu, do you have a reference for the derivation of this dual given the primal?

EDIT: I managed to get the expression.

[apozas]

Alright, I got it. The problem was not quite with z, but with x. Because it was fixed by known_values and we were counting this in the c0 term, its coefficient does not enter into the corresponding constraint in the dual. de605d7 corrects this by adding ck to the constraint only if the corresponding variable is not known.