Solving for Fundamental Matrix based on Rank Constrained Fundamental Matrix Estimation by Polynomial Global Optimization

[RoyiAvital]

In the paper Rank Constrained Fundamental Matrix Estimation by Polynomial Global Optimization they use a nice trick to force the rank constraint using the determinant and some polynomial tricks.

They utilize GloptiPoly 3 to do the transformations which later, using YALMIP solve the SDP problem using SDPT.

Yet in YALMIP, for the det() operator, there is an option for polynomial modelling.

I was wondering, is that the same model?
Can I use YALMIP directly to solve this model (Without GloptiPoly 3)?

[johanlofberg]

I don't know what you mean with same. det(X,'polynomial') == 0 adds the nonconvex nonlinear polynomial constraint to the model.

If you want to use a semidefinite relaxation (as you talk about gloptipoly) to attack the problem, you use the moment relaxation framework as that is the same strategy https://yalmip.github.io/tutorial/momentrelaxations/, or you attack the problem using any nonlinear local nonlinear solver, or a global nonlinear solver

[RoyiAvital]

I think the whole concept of the paper is to convert the det() constraint into a polynomial form.
Then they say this kind of polynomial optimization problem, though being non convex, can be converted into a convex problem by a set of LMI's.

Then the solution of the convex problem is the global solution of the polynomial problem (For the specific case of the Fundamental Matrix).

My question was about such transformation. Is it the same transformation as done by GloptiPoly 3?
Namely will YALMIP generate the optimal solution as well?

[johanlofberg]

A problem is not necessarily solved by a semidefinite relaxation. The linear convex semidefinite relaxation computes a lower bound on the achievable objective, and in some cases you are lucky and that lower bound is tight, and when even more lucky you are able to extract a solution to the original problem.

The moment framework derives the semidefinite relaxation, i.e. the same thing as gloptipoly

[RoyiAvital]

This is the algorithm in the paper using :

They claim the solution is always the optimal solution of the original problem (Again, this case specifically, not all polynomial problems).
So basically it can be solved directly by YALMIP without GloptiPoly.

[johanlofberg]

Yes, they solve the semidefinite relaxation, and have experimentally observed that the second-order relaxation yields a tight bound, from which they typically can extract a solution.

[RoyiAvital]

OK, I got it.
I will try to implement this in YALMIP.

Appreciate the pointers.