Subject: CGAL users discussion list
List archive
- From: Bernd Gaertner <>
- To: <>, Bernd Gaertner <>
- Subject: Re: [cgal-discuss] problem with the quadratic optimizer
- Date: Thu, 3 Jun 2010 12:13:58 +0200
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.
- [cgal-discuss] problem with the quadratic optimizer, vbarzov, 06/03/2010
- Re: [cgal-discuss] problem with the quadratic optimizer, Bernd Gaertner, 06/03/2010
Archive powered by MHonArc 2.6.16.