quadratic polynomials relaxation to SDP?

[Bartel]

Dear,

I'd like to solve the following set of quadratic polynomials
(see Hongdong Li, "Multi-View Structure Computation without Explicitly
Estimating Motion", if you want to know where they come from):

Find x, y
s.t. [x(i), x(j)] * Ai * [x(i); x(j)] = y(k) for different i, j,
k
y > 0, x > 0 (element wise inequalities)

where all Ai are 2x2 positive semi-definite matrices of the form:
[ [1, -cos a], [-cos a, 1] ]

This is rewritten in the (non-convex) form:

Find x, y
s.t. trace(Ai * Y) = y(k) for different i, k
Y = x * xT
y > 0, x > 0 (element wise inequalities)

where Ai is expendent with appropriate zero elements to symmetric nxn
matrices

the constraint Y = x * xT can be relaxed to a convex constraint Y >= x
* xT,
and to garantuee that rank(Y) = 1, Hongdong proposes to min trace(Y)

so that the relaxed problem becomes:

min trace(Y) over x, y
s.t. trace(Ai * Y) = y(k)
Y >= x * xT
y > 0, x > 0

In my specific case, some y(k) are known a-priori, so that the full
problem looks like:

min trace(Y) over x, y
s.t. trace(Ai * Y) = y(k)
trace(Aj * Y) = c
Y >= x * xT
y > 0, x > 0

Can someone tell me how to solve this? How would the command in cvxopt
look like?

[Bartel]

Small update, in trying to implement Li's Structure from Motion and
solving the above polynomial set:

I've been able to solve a very small problem (2 view 5 point, "2v5p")
using sparsePOP (Matlab version though there is also a free C++
distribution working with SDPA, but I haven't succeeded in compiling
it, some problem with not finding "mumps-for-sdpa"):

min f0 = sum ( [x(i), x(j)] * Ai * [x(i); x(j)] - y(k) )² over i,j,k
-> f0 is a polynomial of degree 4 with for the 2v5p 20 unknowns (2
times 5 "legs" x and binomial(5, 2) = 10 interpoint distances y)
sparsePOP was able to solve a (noise-free, random) example if at least
3 y(k)'s where known before hand (i.e. 17 dof remaining), which is
kind of OK (theoretically, I think fixing 1 y(k), to set the scene's
scale, should be enough)
However, when I tried to solve a slightly larger problem (2v8p),
SeDuMi, upon which sparsePOP relies for solving the relaxed sdp, ran
"out of memory". But 2v8p is still very small in structure from motion
problems.
I also tried a 3v4p setting, which also worked if setting 3 y(k)'s to
known (and correct) values.

I then tried the above relaxation in CVX, Matlab version, for 2v5p:

n = 2 * binomial(5, 2) -> number of polynomial equations (i,j,k)
var = 2 * 5 -> number of legs
m -> number of unkown inter-point distances y(k)
cvx_begin
variables Y(var, var) y(m);
minimize (trace(Y));
subject to
k = 1;
for i=1:n
if (known(i))
trace(A{i} * Y) == c(i)^2;
else
trace(A{i} * Y) == y(k);
k = k + 1;
end
end
Y == semidefinite(var);
y > 0;
cvx_end

where Y is supposed Y = x * xT and should have rank 1, i.e. x =
sqrt(diag(Y))
and c known interpoint distances
it worked only for m >= 9 (out of 10!), which is quiet bad.

Question:
would anyone know if using sdpa instead of sedumi in sparsePOP would
not "run out of memory"?
Or how to define the polynomial f0 such that the problem's size is
kept small? Because having to wait hours, even if there would be
sufficient memory, is not amusing.
Does f0 maybe happen to be a SOS (sum of square) polynomial? I think
not because [Ai, 0; 0, -1] is not sdp, though Ai is?

Any idea why sparsePOP is more robust in getting a good solution than
the manual relaxation in CVX?

I guess this has become the wrong media for the above problems, but I
thought to supply my progress, in case anyone happens to stumble upon
it.
Thank you!

[Joachim Dahl]

SDPA handles large sparse Schur complement matrices quite well, which 

supposedly occur frequently in SDP relaxations for polynomial optimization.

I think Sedumi handles such systems fairly well also, but it uses a sparse 

Cholesky factorization code that is quite old and less effective than MUMPS.

SDPT3 stores the Schur complement matrix as dense, so you cannot solve

large polynomial relaxations using it.

--
You received this message because you are subscribed to the Google Groups "CVXOPT" group.
To post to this group, send email to cvx...@googlegroups.com.
To unsubscribe from this group, send email to cvxopt+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/cvxopt?hl=en.