CGAL users discussion list

[Bernd Gaertner <>]

 wrote:
> Hi, I have been using CGAl for quadratic optimization with good success, yet I
> encounter a problem that often causes CGAl to crash.
>
> In the quadratic optimizer, I specify a matrix Q = transpose( V ) * V, where V
> is rather long than tall, hence Q has a low rank. In theory, Q is positive
> semi-definite, but in practice small rounding errors cause it to have barely
> negative eigenvalues and CGAL understandably complains on assertion that the
> matrix is not a proper semi-definite.

There are two simple solutions that I see, a clean (but possibly slow) 
one, and a quick hack. There is also a more complicated solution based 
on using the iterator-based interface, I could tell you more if the two 
simple ones don't do it for you.

The clean solution would be not to use double as input type but an exact 
floating-point type such as Gmpzf or MP_Float. Then you compute 
transpose( V ) * V over this exact type, and things will be ok.

The quick hack is to slightly increase the diagonal entries of the 
matrix (you need to experiment with by how much) to make it proper 
positive definite But then you are solving a slightly different problem, 
of course. It depends on your application whether you can afford it.

Best,
Bernd.