wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        general >> wanted >> Find optimal function
        
(Message started by: BNC on May 23^rd, 2003, 1:41am)

Title: Find optimal function
Post by BNC on May 23^rd, 2003, 1:41am

HI gang,

I have a nasty optimization problem on my hands. I need to find a function a(x) that solves this:
Int(-inf, inf, a(x)b(x,y))dx = f(y)
where b and f are known.

My first solution was to use numeric calculation, using a and f as 1D vectors and B as a matrix:
B*a=f
and then
a=B^-1f

Problem is... B is not invertable.

This is probably a common case, but it's my 1st encounter with it.

Any suggestions?

Title: Re: Find optimal function
Post by towr on May 23^rd, 2003, 1:39pm

doing it numerically B doesn't have to be invertable..

I'll look it up tomorrow if noone else gives the answer first.. (It's late and I have a programming contest tomorrow, so must sleep..)

Title: Re: Find optimal function
Post by BNC on May 25^th, 2003, 12:25am

Hi towr,

I hope your contest went well... :)

10x for looking into it. The only thing I came up with so far is the use of simulated anealing, but as my vectors are very long, I'm not happy about it.

Title: Re: Find optimal function
Post by towr on May 25^th, 2003, 2:56am

mew, it didn't go too bad, but not too good either.. we were 6 or 7 out of 12.. With 3 out of 9 assignments completed (vs 8/9 from the winners)
On the other hand we had little to no preperation, and the question were somewhat ill-phrased imo.. (They make a story around them, obscuring mathematical problems with realworld complications.)

Anyway, about the problem at hand..

There are ways to solve A*b = 0 given A
and to make B*a=f into A*b=0 can be done like this
http://www.ai.rug.nl/~towr/PHP/FORMULA/formula.php?md5=6d3ec087c3f308e3c9c54d7d33399a87
so you have
http://www.ai.rug.nl/~towr/PHP/FORMULA/formula.php?md5=d2ecd3fc270c4b1e2c77b828865f2946

this can be solved iteratively with 'newtons method for nonlinear systems'
G(x) = x - J(x)^-1F(x)
where J(x) is the Jacobian matrix (http://mathworld.wolfram.com/Jacobian.html) of F(x) (the second image)

here's matlab code for it (some dutch)

f is the function F(x)
jacf is the jacobian of F(x)
x0 is the vector you take as first approximation (it usually needs to be somewhere in the vicinity of where you need to be (just try it several times)
tol is the tolerance, how big of an error can be made
'afdruk' = 'print', 1 will print intermediate results
varargin, can be extra arguments for f

function nulpunt=vnewton(f,jacf,x0,tol,afdruk,varargin)

fx = feval(f, x0, varargin{:});
jx = feval(jacf, x0, varargin{:});

y = jx^-1*-fx;
i =0;
while norm(y,inf) > tol

if afdruk ~=0
fprintf('it:%i nulpunt:[ ', i);
fprintf('%3.3e ', x0);
fprintf('] fout: %3.3e\n', norm(y,inf));
end

x0 = x0 + y;

fx = feval(f, x0, varargin{:});
jx = feval(jacf, x0, varargin{:});

y = jx^-1*-fx;

i = i+1;
end

if afdruk ~=0
fprintf('it:%i nulpunt:[ ', i);
fprintf('%3.3e ', x0);
fprintf('] fout: %3.3e\n', norm(y));
end

nulpunt = x0;

%------------------------------------

I think this should solve the matrix problem.. I'm not sure how well it'll solve the original problem though.. (you may need a very, very large vector to get enough accuracy)

(basicly it's sort of gradiant decent instead of simulated annealing)

Title: Re: Find optimal function
Post by BNC on May 25^th, 2003, 6:25am

Thanks towr,

I'll give it a go, and let you know how it went.

Title: Re: Find optimal function
Post by towr on May 25^th, 2003, 7:00am

If it doesn't work I may have something else somewhere..
Though I can't say I fully understand that code and would have to rework it a little..

Title: Re: Find optimal function
Post by towr on May 26^th, 2003, 3:16am

on 05/23/03 at 01:41:24, BNC wrote:

I need to find a function a(x) that solves this:
Int(-inf, inf, a(x)b(x,y))dx = f(y)
where b and f are known.

I keep wondering if it may be solved with convolutions..
cause I suppose you could choose a c(t-x) = a(x)
and then
Int(-inf, inf, a(x)b(x,y))dx = f(y)
would become

Int(-inf, inf, c(t-x)b(x,y))dx = f(y)
using foruier transform you can then get
C(t) . B(t,y) = f(y)
and thus
C(t) = f(y)/B(t,y)
take the inverse fourier and you get c(t-x), and form that you can get a(x).. hopefully..

(I'm not really sure how to do it properly.. or if it's even allowed)

Title: Re: Find optimal function
Post by BNC on May 27^th, 2003, 2:16am

Hi towr,

As for the convolution, I don't see how it an be done. If b(x,y) was womewhat linear, it was possible to write b(x,y) ~ B0 + g(y-x), and then the inegral woud be come the conolution integral. But that's not the case here.

i got stuck in the Newton method with the Jacobian. My functions are quite complicated, and calculating the Jacobian analitically is not easy. On the other hand, I couldn't figure out a way to find it numerically.

On the happy side, I calculated my A matrix again, after adding a few more terms of the Tailor series from which it originated, and the "new" (more accurate, more complex) function yielded an invertable matrix... ;D

I'd like to thank you again for taking the time to think about my problem :) :) Hope I can return the favor sometime.