Super fast SDP solver for a problem with 6 variables only

[ofir....@gmail.com]

I am looking for a way to solve millions of small SDP problems in an extremely fast manner.
Each SDP problem is independent of the others and all problems are identical (except the data it self of course).
These SDP problems are quite simple and here is there formulation:

M is a symmetric 3x3 matrix, hence has 6 independent degrees of freedom.

These 6 numbers are the only variables in the optimization.

M0 is the data. It is another symmetric matrix (its elements are constants).

minimize |M-M0|^2    (quadratic convex energy)

such that: M>0  (i.e. M is positive semi-definite).

I can obviously use MOSEK to solve such a problem.

However, I need to solve tens of Millions of these (independent) problems in very short time.

My question is whether MOSEK is the right tool for this?

Is there an overhead in setting a problem with MOSEK? If so, can I "pay" it only once since all these problems have exactly the same structure?

Can I exploit some sort of parallelism here? In *theory*, of course.

But in practice, if I'll issue many threads or try to use OPEN MP, the overhead of managing these threads might be too much.

I'm ok with an approximate solution if that makes the answer easier.

It also perfectly fits a GPU implementation due to regularity and coherent memory access patterns. But I am not aware of batch GPU SDP solvers.

Does Mosek has special representation for 3x3 matrices that I can utilize here?

[Erling D. Andersen]

* I am not aware of a better tool than Mosek for your purpose. Writing one yourself is most likely your only alternative option.

* We cannot help you with GPUs. 

* Mosek internally is tuned for 3 by 3 matrices.

I  would to use a cilk_for loop i.e.

cilk_for(i=0; i<n; ++i)

{

   build task i

   solve problem i

   store solution i

}

 

See

   https://www.cilkplus.org/tutorial-cilk-plus-keywords

for more info about Cilk.

Cilk is deprecated in Intel C but is available in other compilers but I think you can do something similar with OpenMP using tasks.

Also it is most likely a good to a non parallel version first to see if this a viable approach. You can always assume linear speedup to get an idea of the solution time.