From: Calamitas Date: 2008-05-14T18:52:08+09:00 Subject: Re: Gecoder syntax question On Wed, May 14, 2008 at 9:40 AM, Axel Etzold wrote: > Dear all, > > I have an optimization problem. I need to > minimize || A(x-y) || while maximizing ||x-y||, where > ||.|| is a norm, x,y are vectors with integer non-negative entries > and A is a (at that point fixed) matrix with float/double entries . > x is also fixed, so I am looking for vectors y "far from x" that are mapped > closely to where x is mapped under the linear mapping induced by the > matrix A. > > How can I declare a matrix with float or double precision entries in Gecoder to formulate the problem ? First off, your optimization problem seems to make little sense to me the way you specified it. For y = x, the first norm is 0 and thus minimal. If A is non-singular, that is the only value for y for which that norm is minimal. If A is singular, the optimization problem is unbound and thus there is no maximum for ||x-y|| for a fixed value of ||A(x-y)||. Maybe you should quantify what 'mapped closely' means, like ||A(x-y)|| <= 1. But I don't think Gecode/R can handle floats, or at least not for the unknowns. It seems to be a finite domain solver. If you only care about say 3 digits after the comma, you could scale all values up by 1000 and round to integers. My gut feeling is that this can easily give results that are way off, and not only for ill-conditioned problems. I'm no expert on Gecode/R, though, so could be that it does support floats. But your problem seems numerical in nature. I'm inclined to solve it by using the singular value decomposition to find the (or a) direction in which A scales the least. Using vector d to denote this direction, you can pick y = x + a * d, and that should give you the largest value for ||x-y|| for the specific value of ||A(x-y)||. Both norms above can be expressed as linear functions of a which is the only variable left, and you can easily pick the a you want. If A is singular, the smallest singular value will be 0 and you can pick a as large as you want and || A(x-y) || will still be 0. Of course, I'm assuming here that "a norm" means Euclidian norm. Peter