Hi everyone, I’m experiencing some numerical problems
when using the SDPT3 solver for a (apparently) fairly simple SDP problem.
The problem under consideration is
$$ \min_X tr(MX), ; s.t. X\succcurlyeq0, X(end,end) = 1 $$
This problem is just the lifted relaxation of
$$ \min_\tilde{x} \tilde{x}^\top M \hat{x}, ; s.t. \tilde{x}(end)^2=1 $$
which in turn corresponds to a simple Least Squares (linear) problem:
$$ min_x ||A x - b|| $$
Obviously, this is just a testing problem before proceeding to the relaxation
of a more complex one which is not a Least Squares problem.
The curious fact is that Sedumi is working well, but SDPT3 fails to converge.
I know I should just stick with the solver working (it’s what I usually do)
but since this seems (to me) like a very simple problem
I was a little surprised that the usual SDP solvers could have any difficulty with it.
Furthermore, I’m concerned that I might be missing part of the complexity of the problem
since this could become the source of many headaches when things don’t work
in the more complex problem extending this one.
I’ve tried looking for some theoretical background that may
explain in which situations a SDP problem could get ill-conditioned
or something related, but couldn’t find anything straightforward
in the context of this specific model.
I would appreciate if any of the experts here
could share their impressions about this
Just to do some simple tests, I’m providing a simple test code:
% generate positive semidefinite matrix
m = 10;
n = 3;
A = randn(m,n);
b = randn(m,1);
M = [A,-b]'*[A,-b];
cvx_solver SDPT3
% cvx_solver sedumi
% cvx_precision low
cvx_begin SDP
variable X(n+1,n+1) semidefinite
X(end,end) == 1
minimize(trace(M*X))
cvx_end
It seems sometimes (rarely) the SDPT3 solver worked,
but in general any random problem will fail.
You can easily check that apparently there are no conditioning
issues with the data matrix M.
I tried different precisions, by the way.