Calamitas
5/14/2008 9:52:00 AM
On Wed, May 14, 2008 at 9:40 AM, Axel Etzold <AEtzold@gmx.de> 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